Segmentación de instrucciones
Ciclo reloj Instr. | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | LI | DI | EJ | MEM | ES | ||
| 2 | LI | DI | EJ | MEM | ES | ||
| 3 | LI | DI | EJ | MEM | ES | ||
| 4 | LI | DI | EJ | MEM | |||
| 5 | LI | DI | EJ | ||||
| (LI = Lectura de Instrucción, DI = Decodificación de Instrucción, EJ = Ejecución, MEM = Acceso a Memoria, ES = Escritura de vuelta al registro). En el cuarto ciclo de reloj (la columna verde), la primera instrucción está en la etapa MEM, mientras que la última (y más reciente) no ha sido segmentada todavía. | |||||||
La segmentación de instrucciones es una técnica que permite implementar el paralelismo a nivel de instrucción en un único procesador. La segmentación intenta tener ocupadas con instrucciones todas las partes del procesador dividiendo las instrucciones en una serie de pasos secuenciales que efectuarán distintas unidades de la CPU, tratando en paralelo diferentes partes de las instrucciones. Permite una mayor tasa de transferencia efectiva por parte de la CPU que la que sería posible a una determinada frecuencia de reloj, pero puede aumentar la latencia debido al trabajo adicional que supone el propio proceso de la segmentación.
Introducción
Las Unidades Centrales de Procesamiento (CPU) están gobernadas por un reloj. Cada pulso enviado por el reloj no tiene por qué hacer lo mismo; de hecho, la lógica de la CPU dirige sucesivos pulsos a distintos lugares para así llevar a cabo una secuencia que resulte útil. Hay muchos motivos por los que no puede llevarse a cabo la ejecución de una instrucción al completo en un único paso; cuando se habla de segmentación, los efectos que no pueden producirse al mismo tiempo se dividen en pasos separados de la instrucción, pero dependientes entre sí.
Por ejemplo, si un pulso de reloj introduce un valor en un registro o comienza un cálculo, hará falta cierto tiempo para que el valor sea estable en las salidas del registro o para que el cálculo se complete. Otro ejemplo: leer una instrucción de una unidad de memoria no es una operación que pueda hacerse al mismo tiempo que una instrucción escribe un resultado en la misma unidad de memoria.
Número de pasos
El número de pasos dependientes varían según la arquitectura de la máquina. Algunos ejemplos:
- Entre 1956 y 1961, el proyecto IBM Stretch proponía los términos Fetch (Lectura), Decode (Decodificación) y Execute (Ejecución) que se convirtieron en habituales.
- La segmentación RISC clásica comprende:
- Lectura de instrucción
- Decodificación de instrucción y lectura de registro
- Ejecución
- Acceso a memoria
- Escritura de vuelta en el registro
- Muchos diseños incluyen segmentación de 7, 10 e incluso 20 etapas (como es el caso del Pentium 4 de Intel).
- Los núcleos "Prescott" y "Cedar Mill" de la microarquitectura NetBurst de Intel, utilizados en las versiones más recientes del Pentium 4 y sus derivados Pentium D y Xeon, tienen una segmentación de 31 etapas.
- El "Xelerated X10q Network Processor" cuenta con una segmentación de más de 1000 etapas, si bien en este caso 200 de estas etapas representan CPU independientes con instrucciones programadas de forma individual. Las etapas restantes se usan para coordinar los accesos a la memoria y las unidades funcionales presentes en el chip.[1]
Conforme la segmentación se hace más "profunda" (aumentando el número de pasos dependientes), un paso determinado puede implementarse con circuitería más simple, lo cual puede permitir que el reloj del procesador vaya más rápido.[2] En inglés, las segmentaciones de este tipo pueden llamarse superpipelines.[3]
Se dice que un procesador está totalmente segmentado si puede leer una instrucción en cada ciclo. Por tanto, si ciertas instrucciones o condiciones requieren un retardo que impide la lectura de nuevas instrucciones, el procesador no está totalmente segmentado.
Peligros
El modelo de la ejecución secuencial asume que cada instrucción se completa antes de que comience la siguiente; esta suposición no es cierta en el caso de un procesador segmentado. Una situación donde el resultado esperado es problemático se denomina peligro. Imaginemos las siguientes dos instrucciones actuando sobre los registros de un procesador hipotético:
1: añadir 1 a R5 2: copiar R5 a R6
Si el procesador dispone de las 5 etapas mostradas en la ilustración inicial de este artículo, la instrucción 1 se leería en el momento t1 y su ejecución se completaría en t5, mientras que la instrucción 2 se leería en t2 y se completaría en t6. La primera instrucción podría depositar el número incrementado en R5 como su quinto paso (escritura de vuelta al registro) en t5. Pero la segunda instrucción podría obtener el número de R5 (que se dispone a copiar a R6) en su segundo paso (decodificación de instrucción y lectura de registro) en el momento t3. Parece que la primera instrucción no habrá todavía incrementado para entonces su valor; tenemos, por lo tanto, un peligro.
Escribir programas informáticos en un lenguaje compilado podría no dar pie a este tipo de preocupaciones, ya que el compilador podría estar diseñado para generar código máquina que evita los peligros.
Medidas cautelares
En algunos de los primeros DSP y procesadores RISC, la documentación aconsejaba a los programadores evitar este tipo de dependencias en instrucciones adyacentes o cuasi-adyacentes (llamadas huecos de retardo), o declaraba que la segunda instrucción usaba un valor antiguo en lugar del valor deseado (en el ejemplo de arriba, el procesador podría limitarse a copiar el valor todavía sin incrementar), o declaraba que el valor usado no está definido. El programador podría tener otras cosas que ordenarle hacer al procesador mientras tanto; o bien, para asegurar los resultados correctos, el programador podía insertar NOPs en el código, lo cual por otro lado iba en contra de las ventajas que aporta la segmentación.
Soluciones
Los procesadores segmentados suelen utilizar tres técnicas para funcionar como se espera de ellos cuando el programador da por sentado que cada instrucción se completa antes de que comience la siguiente:
- Los procesadores que pueden computar la presencia de un peligro pueden frenarse, retardando el procesamiento de la segunda instrucción (y posteriores) hasta que los valores que necesita como entrada están listos para usarse. Esto crea una burbuja en la segmentación, y también va a la contra de las ventajas que aporta la segmentación.
- Algunos procesadores pueden no solo computar la presencia de un peligro sino también compensar ese factor contando con rutas de datos adicionales que proporcionan las entradas necesarias para un paso de la computación antes de que una instrucción posterior ejecute esos pasos; es un atributo denominado reenvío de operandos.[4][5]
- Algunos procesadores pueden determinar que las instrucciones aparte de la siguiente de la secuencia no dependen de las instrucciones actuales, y que pueden ejecutarse sin que surja ningún peligro. Tales procesadores pueden realizar ejecución fuera de orden.
Ramas
A menudo, una ramificación saliente de la secuencia normal de instrucciones está relacionada con un peligro. A menos que el procesador pueda llevar a afecto la rama en un único ciclo de reloj, la segmentación continuará leyendo instrucciones de forma secuencial. No puede permitirse que tales instrucciones se lleven a afecto porque el programador ha pasado el control a otra parte del programa.
Una rama condicional es si cabe todavía más problemática. El procesador puede o no ramificar, dependiendo de un cálculo que todavía no ha tenido lugar. Puede darse el caso de que varios procesadores se frenen, intenten hacer una predicción de salto, o puedan empezar a ejecutar dos secuencias distintas del programa (ejecución ansiosa), en ambos casos asumiendo que la rama se ha tomado y no se ha tomado, descartando todo el trabajo que corresponde a la suposición incorrecta.[6]
Un procesador con una implementación de un predictor de saltos que normalmente realiza predicciones acertadas puede minimizar la penalización en el rendimiento que supone la ramificación. Sin embargo, si la predicción de los saltos se equivoca con excesiva frecuencia, esto puede crear más trabajo para el procesador, que tiene que quitar de la segmentación la ruta incorrecta de código que ha comenzado a ejecutarse, antes de poder continuar la ejecución en la posición correcta.
Los programas escritos para un procesador segmentado evitan de forma deliberada las ramificaciones para minimizar las posibles pérdidas de velocidad. Por ejemplo, el programador puede encargarse de los casos habituales con ejecución secuencial, y usar ramificaciones solo al detectar casos poco frecuentes. El uso de programas como gcov para analizar la cobertura de código permite al programador medir la frecuencia con la que se ejecutan determinadas ramas, y obtener así información añadida que le permita optimizar el código.
Situaciones especiales
Programas auto-modificables
La técnica del código automodificable puede resultar problemática en un procesador segmentado. Al emplear esta técnica, uno de los efectos de un programa es la modificación de sus propias instrucciones subsiguientes. Si el procesador cuenta con un caché de instrucciones, la instrucción original puede haber sido ya copiada a una cola de entrada de prelectura, y la modificación no tendrá efecto.
Instrucciones no interrumpibles
Una instrucción puede ser no interrumpible para asegurar su atomicidad, por ejemplo cuando intercambia dos elementos. Un procesador secuencial permite interrupciones entre las instrucciones, pero un procesador segmentado yuxtapone las instrucciones, con lo cual ejecutar una instrucción no interrumpible hace que partes de las instrucciones ordinarias sean no interrumpibles también. El fallo de coma de Cyrix hacía que un sistema de un único núcleo se colgase empleando un bucle infinito en el que siempre se estaba segmentando una instrucción no interrumpible.
Consideraciones de diseño
Velocidad
La segmentación tiene ocupadas todas las partes que conforman el procesador e incrementa la cantidad de trabajo útil que éste puede realizar en un determinado espacio de tiempo. Lo habitual es que la segmentación reduzca el tiempo de los ciclos del procesador e incremente la tasa de transferencia efectiva de instrucciones. Las ventajas en cuanto a velocidad disminuyen cuando la ejecución se encuentra con peligros que requieren que esta reduzca su velocidad por debajo de la tasa ideal. Un procesador no segmentado solo ejecuta una instrucción cada vez. El comienzo de la siguiente instrucción no se retrasa por la aparición de peligros, sino incondicionalmente.
La necesidad de un procesador segmentado de organizar todo su trabajo en pasos modulares puede requerir la duplicación de registros, lo cual incrementa la latencia de algunas instrucciones.
Economía
Al simplificar cada uno de los pasos, la segmentación puede hacer posibles las operaciones complejas de forma más económica que añadiendo circuitería compleja, por ejemplo para los cálculos numéricos. Por otra parte, un procesador que rehúsa perseguir un aumento en la velocidad recurriendo a la segmentación puede ser más sencillo y barato de fabricar.
Predecibilidad
En comparación con entornos donde el programador tiene que evitar los peligros o buscar la forma de soslayarlos, el uso de un procesador no segmentado puede hacer más fácil la programación y la propia tarea de formar a los programadores. El procesador no segmentado también hace más fácil predecir la sincronización exacta de una secuencia determinada de instrucciones.
Ejemplo ilustrado
A la derecha tenemos una segmentación genérica con cuatro etapas: lectura, decodificación, ejecución y escritura. La caja gris de la parte de arriba es la lista de instrucciones que esperan a ser ejecutadas, la caja gris de abajo es la lista de instrucciones que han completado su ejecución, y finalmente la caja blanca central es la segmentación en sí.
La ejecución procede del modo siguiente:
| Reloj | Ejecución |
|---|---|
| 0 |
|
| 1 |
|
| 2 |
|
| 3 |
|
| 4 |
|
| 5 |
|
| 6 |
|
| 7 |
|
| 8 |
|
| 9 |
|
Burbuja en la segmentación
Un procesador segmentado puede enfrentarse a los peligros frenando y creando una burbuja en la segmentación, lo cual se traduce en uno o más ciclos en los que no ocurre nada útil.
En la ilustración de la derecha, en el ciclo 3, el procesador no puede decodificar la instrucción lila, quizá porque el procesador ha determinado que la decodificación depende de los resultados producidos por la ejecución de la instrucción verde. La instrucción verde puede proceder a su fase de ejecución y luego a la de escritura tal como estaba previsto, pero la instrucción lila se ve retrasada un ciclo entero en la fase de lectura. La instrucción azul, que iba a ser leída durante el ciclo 3, también se ve retrasada un ciclo, y lo mismo le ocurre a la instrucción roja que la sigue.
Por culpa de la burbuja (los círculos azules de la ilustración), la circuitería de decodificación del procesador no hace nada durante el ciclo 3, lo mismo que le ocurre a la circuitería de ejecución durante el ciclo 4 y a la de escritura durante el ciclo 5.
Cuando la burbuja finalmente sale de la segmentación (en el ciclo 6), la ejecución normal continúa, pero ahora todo ocurre con un ciclo de retraso. Se tardará 8 ciclos (del 1 al 8) en lugar de 7 en ejecutar completamente las cuatro instrucciones mostradas en colores.
Historia
Los usos históricamente más significativos de la segmentación fueron con el proyecto ILLIAC II y con el proyecto IBM Stretch, aunque ya se usó antes una versión más sencilla en el Z1 en 1939 y en el Z3 en 1941.[7]
La segmentación empezó a popularizarse a finales de los 70 en las supercomputadoras en forma de procesadores vectoriales y de matrices. Una de las primeras supercomputadoras fue la serie Cyber construida por Control Data Corporation. Su principal arquitecto, Seymour Cray, dirigió posteriormente Cray Research. Cray desarrolló la línea XMP de supercomputadoras, usando segmentación para las funciones tanto de multiplicación como de suma y sustracción. Posteriormente, Star Technologies añadió el paralelismo (varias funciones segmentadas trabajando en paralelo), desarrollado por Roger Chen. En 1984, Star Technologies añadió el circuito de división segmentado desarrollado por James Bradley. A mediados de los 80, la supercomputación estaba al alcance de muchas empresas de todo el mundo.
La segmentación no estaba limitada a supercomputadoras. En 1976, la serie 470 del mainframe de propósito general de la Corporación Amdahl tenía una segmentación de 7 etapas, y un circuito de predicción de saltos patentado.
En la actualidad, la segmentación y la mayoría de innovaciones aquí descritas forman parte de la unidad de instrucciones de la mayoría de los microprocesadores.
Véase también
- Estado de espera
- Segmentación RISC clásica
Referencias
- Glaskowsky, Peter (18 de agosto de 2003). «Xelerated's Xtraordinary NPU — World’s First 40Gb/s Packet Processor Has 200 CPUs». Microprocessor Report (en inglés) 18 (8): 12-14. Consultado el 20 de marzo de 2017.
- John Paul Shen, Mikko H. Lipasti (2004). Modern Processor Design. McGraw-Hill Professional.
- Sunggu Lee (2000). Design of Computers and Other Complex Digital Devices. Prentice Hall.
- «CMSC 411 Lecture 19, Pipelining Data Forwarding». Csee.umbc.edu. Consultado el 8 de febrero de 2014.
- (en inglés). hpc.serc.iisc.ernet.in. Septiembre de 2000. Archivado desde el original el 27 de diciembre de 2013. Consultado el 8 de febrero de 2014.
- Los primeros procesadores segmentados que carecían de toda esta heurística, como es el caso del procesador PA-RISC de Hewlett-Packard, se enfrentaban a los peligros simplemente avisando al programador; en este caso, le comunicaban que una o más instrucciones siguiendo a la rama se ejecutarían tanto si se seguía la rama como si no. Esto podía ser útil; por ejemplo, tras calcular un número en un registro, una rama condicional podía ir seguida de la carga en un registro de un valor que resultase más útil en las computaciones subsiguientes tanto en el caso de haberse seguido la rama como en el caso contrario.
- Raul Rojas (1997). «Konrad Zuse's Legacy: The Architecture of the Z1 and Z3». IEEE Annals of the History of Computing (en inglés) 19 (2).
Enlaces externos
- Predicción de saltos en la familia Pentium () (en inglés)
- Artículo de ArsTechnica acerca de la segmentación (en inglés)
- (en inglés)
- Esta obra contiene una traducción derivada de «Instruction pipelining» de la Wikipedia en inglés, concretamente de esta versión, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.