Ejecución fuera de orden

Podría decirse que la primera máquina en utilizar la ejecución fuera de orden fue la CDC 6600 (1964), que utilizaba un marcador para resolver conflictos. Sin embargo, la 6600 carecía de manejo de conflictos WAW , optando en su lugar por detenerse. Esta situación fue denominada "Conflicto de Primer Orden" por Thornton. ^{[ 5 ]} Si bien contaba con resolución de conflictos RAW (denominada "Conflicto de Segundo Orden" ^{[ 6 ]} ) y resolución de conflictos WAR (denominada "Conflicto de Tercer Orden" ^{[ 7 ]} ), lo cual es suficiente para declararla capaz de una ejecución fuera de orden completa, la 6600 no tenía un manejo preciso de excepciones. Era posible una forma temprana y limitada de predicción de bifurcaciones siempre que la bifurcación fuera a ubicaciones en lo que se denominó la "Pila de Instrucciones", que estaba limitada a una profundidad de siete palabras desde el Contador de Programa. ^{[ 8 ]}

Aproximadamente dos años después, el IBM System/360 Modelo 91 (1966) introdujo el cambio de nombre de registros con el algoritmo de Tomasulo , ^{[ 9 ]} que disuelve las dependencias falsas (WAW y WAR), haciendo posible la ejecución fuera de orden completa. Una instrucción que apunta a una escritura en un registro r _n puede ejecutarse antes de que se ejecute una instrucción anterior que usa el registro r _n , escribiendo realmente en un registro alternativo (renombrado) alt-r _n , que se convierte en un registro normal r _n solo cuando se han ejecutado todas las instrucciones anteriores que apuntan a r _n , pero hasta entonces se da r _n para las instrucciones anteriores y alt-r _n para las posteriores que apuntan a r _n .

En el Modelo 91, el cambio de nombre de los registros se implementa mediante un bypass denominado Common Data Bus (CDB) y búferes de operandos de la fuente de memoria, lo que deja los registros arquitectónicos físicos sin usar durante muchos ciclos, ya que el estado más antiguo de los registros a los que apunta cualquier instrucción no ejecutada se encuentra en el CDB. Otra ventaja del Modelo 91 sobre el 6600 es la capacidad de ejecutar instrucciones fuera de orden en la misma unidad de ejecución , no solo entre las unidades como el 6600. Esto se logra mediante estaciones de reserva , desde las cuales las instrucciones van a la unidad de ejecución cuando están listas, a diferencia de la cola FIFO de cada unidad de ejecución del 6600. El Modelo 91 también es capaz de reordenar las cargas y los almacenamientos para que se ejecuten antes que las cargas y los almacenamientos precedentes, ^{[ 10 ]} a diferencia del 6600, que solo tiene una capacidad limitada para mover cargas más allá de cargas, y almacenamientos más allá de almacenamientos, pero no cargas más allá de almacenamientos y almacenamientos más allá de cargas. ^{[ 11 ]} Solo se renombran los registros de punto flotante del Modelo 91, lo que lo sujeta a las mismas limitaciones WAW y WAR que el CDC 6600 al ejecutar cálculos de punto fijo. Tanto el 91 como el 6600 también sufren excepciones imprecisas , que debían resolverse antes de que la ejecución fuera de orden pudiera aplicarse de forma general y hacerse práctica fuera de las supercomputadoras.

Para tener excepciones precisas , el estado correcto de ejecución del programa debe estar disponible cuando se produzca una excepción. En 1985 se desarrollaron varios enfoques, como los descritos por James E. Smith y Andrew R. Pleszkun. ^{[ 12 ]} El CDC Cyber ​​205 fue un precursor, ya que ante una interrupción de memoria virtual, todo el estado del procesador (incluida la información sobre las instrucciones parcialmente ejecutadas) se guarda en un paquete de intercambio invisible , de modo que pueda reanudarse en el mismo estado de ejecución. ^{[ 13 ]} Sin embargo, para que todas las excepciones sean precisas, debe haber una forma de cancelar los efectos de las instrucciones. El CDC Cyber ​​990 (1984) implementa interrupciones precisas mediante el uso de un búfer de historial, que almacena los valores antiguos (sobrescritos) de los registros que se restauran cuando una excepción requiere la reversión de las instrucciones. ^{[ 12 ]} Mediante simulación, Smith determinó que añadir un búfer de reordenamiento (o búfer de historial o equivalente) al Cray-1S reduciría el rendimiento de la ejecución de los primeros 14 bucles de Livermore (no vectorizados) en solo un 3 %. ^{[ 12 ]} Yale Patt lideró una importante investigación académica sobre este tema con su simulador HPSm . ^{[ 14 ]}

En la década de 1980, muchos microprocesadores RISC de la época presentaban escrituras fuera de orden en los registros, lo que invariablemente generaba excepciones imprecisas. El Motorola 88100 fue uno de los pocos microprocesadores de la época que no sufrió excepciones imprecisas a pesar de las escrituras fuera de orden, aunque sí permitía excepciones de punto flotante tanto precisas como imprecisas. ^{[ 15 ]} Las instrucciones comenzaban su ejecución en orden, pero algunas (por ejemplo, las de punto flotante) requerían más ciclos para completarse. Sin embargo, la ejecución en un solo ciclo de las instrucciones más básicas redujo considerablemente el alcance del problema en comparación con el CDC 6600.

Smith también investigó cómo hacer que las diferentes unidades de ejecución operaran de manera más independiente entre sí y de la memoria, el front-end y las bifurcaciones. ^{[ 16 ]} Implementó esas ideas en el Astronautics ZS-1 (1988), que presentaba un desacoplamiento de la tubería de enteros/carga/almacenamiento de la tubería de punto flotante, lo que permitía la reordenación entre tuberías. El ZS-1 también era capaz de ejecutar cargas antes que almacenamientos precedentes. En su artículo de 1984, opinó que aplicar las excepciones precisas solo en la tubería de enteros/memoria debería ser suficiente para muchos casos de uso, ya que incluso permite la memoria virtual . Cada tubería tenía un búfer de instrucciones para desacoplarla del decodificador de instrucciones, para evitar el bloqueo del front-end. Para desacoplar aún más el acceso a la memoria de la ejecución, cada una de las dos tuberías estaba asociada con dos colas direccionables que efectivamente realizaban un renombrado limitado de registros. ^{[ 10 ]} Una arquitectura desacoplada similar se había utilizado un poco antes en el Culler 7. ^{[ 17 ]} El ISA del ZS-1, al igual que el POWER posterior de IBM, ayudó a la ejecución temprana de bifurcaciones.

Con el POWER1 (1990), IBM volvió a la ejecución fuera de orden. Fue el primer procesador en combinar el cambio de nombre de registros (aunque de nuevo solo registros de punto flotante) con excepciones precisas. Utiliza un archivo de registros físico (es decir, un archivo reasignado dinámicamente con valores tanto confirmados como no confirmados) en lugar de un búfer de reordenamiento, pero la capacidad de cancelar instrucciones solo es necesaria en la unidad de bifurcación, que implementa un búfer de historial (llamado pila de contador de programa por IBM) para deshacer cambios en los registros de conteo, enlace y condición. La capacidad de reordenamiento incluso de las instrucciones de punto flotante sigue siendo muy limitada; debido a la incapacidad del POWER1 para reordenar las instrucciones aritméticas de punto flotante (los resultados estaban disponibles en orden), sus registros de destino no se renombran. El POWER1 tampoco tiene estaciones de reserva necesarias para el uso fuera de orden de la misma unidad de ejecución. ^{[ 18 ] [ 19 ]} Al año siguiente, el modelo 900 ES/9000 de IBM incorporó el cambio de nombre de registros para los registros de propósito general. También cuenta con estaciones de reserva con seis entradas para la unidad de enteros duales (en cada ciclo, se pueden seleccionar y ejecutar hasta dos instrucciones de entre seis) y seis entradas para la FPU. Otras unidades tienen colas FIFO simples. La distancia de reordenamiento es de hasta 32 instrucciones. ^{[ 20 ]} El A19 de la serie A de mainframes de Unisys también se lanzó en 1991 y se afirmó que tenía ejecución fuera de orden, y un analista dijo que la tecnología del A19 estaba de tres a cinco años por delante de la competencia. ^{[ 21 ] [ 22 ]}

Los primeros procesadores de un solo chip superescalares ( Intel i960CA en 1989) utilizaban una planificación de marcador simple como la que tenía el CDC 6600 un cuarto de siglo antes. En 1992-1996 un rápido avance de las técnicas, posibilitado por el aumento del número de transistores , vio su proliferación hasta las computadoras personales . El Motorola 88110 (1992) utilizaba un búfer de historial para revertir instrucciones. ^{[ 23 ]} Las cargas podían ejecutarse antes que los almacenamientos precedentes. Mientras los almacenamientos y las bifurcaciones esperaban para comenzar la ejecución, las instrucciones subsiguientes de otros tipos podían seguir fluyendo a través de todas las etapas de la tubería, incluida la escritura diferida. La capacidad de 12 entradas del búfer de historial imponía un límite a la distancia de reordenamiento. ^{[ 24 ] [ 25 ] [ 26 ]} El PowerPC 601 (1993) fue una evolución del RISC Single Chip , que a su vez era una simplificación del POWER1. El 601 permitía que las instrucciones de salto y de punto flotante superaran a las instrucciones enteras que ya estaban en la cola de instrucciones obtenidas, cuyas cuatro entradas más bajas se escaneaban para determinar su capacidad de despacho. En caso de un fallo de caché, las cargas y los almacenamientos podían reordenarse. Solo los registros de enlace y de conteo podían renombrarse. ^{[ 27 ] [ 28 ] [ 29 ] [ 30 ] [ 31 ]} En otoño de 1994, NexGen e IBM con Motorola llevaron el renombrado de registros de propósito general a las CPU de un solo chip. El Nx586 de NexGen fue el primer procesador x86 capaz de ejecución fuera de orden y presentaba una distancia de reordenamiento de hasta 14 microoperaciones . ^{[ 32 ]} El PowerPC 603 renombró tanto los registros de propósito general como los de punto flotante. Cada una de las cuatro unidades de ejecución sin salto puede tener una instrucción en espera delante de ella sin bloquear el flujo de instrucciones a las otras unidades. Un búfer de reordenamiento de cinco entradas permite que no más de cuatro instrucciones superen a una instrucción no ejecutada. Gracias a un búfer de almacenamiento, una carga puede acceder a la caché antes que un almacenamiento precedente. ^{[ 33 ] [ 34 ]}

PowerPC 604 (1995) fue el primer procesador de un solo chip con reordenamiento a nivel de unidad de ejecución , ya que tres de sus seis unidades tenían cada una una estación de reserva de dos entradas que permitía que la entrada más nueva se ejecutara antes que la más antigua. La capacidad del búfer de reordenamiento es de 16 instrucciones. Una cola de carga de cuatro entradas y una cola de almacenamiento de seis entradas rastrean el reordenamiento de cargas y almacenamientos en caso de fallos de caché. ^{[ 35 ]} HAL SPARC64 (1995) superó la capacidad de reordenamiento del modelo ES/9000 900 al tener tres estaciones de reserva de 8 entradas para enteros, punto flotante y unidad de generación de direcciones , y una estación de reserva de 12 entradas para carga/almacenamiento, lo que permite un mayor reordenamiento del acceso a caché/memoria que los procesadores anteriores. Hasta 64 instrucciones pueden estar en un estado reordenado a la vez. ^{[ 36 ] [ 37 ]} Pentium Pro (1995) introdujo una estación de reserva unificada , que con una capacidad de 20 micro-OP permitía una reordenación muy flexible, respaldada por un búfer de reordenación de 40 entradas. Las cargas se pueden reordenar antes que las cargas y los almacenamientos. ^{[ 38 ]}

La tasa de ejecución por ciclo prácticamente alcanzable aumentó aún más cuando SGI / MIPS ( R10000 ) y HP PA-RISC ( PA-8000 ) adoptaron la ejecución fuera de orden completa en 1996. Ese mismo año, Cyrix 6x86 y AMD K5 introdujeron técnicas avanzadas de reordenamiento en las computadoras personales convencionales. Desde que DEC Alpha obtuvo la ejecución fuera de orden en 1998 ( Alpha 21264 ), los núcleos de procesador fuera de orden de mayor rendimiento no han sido igualados por los núcleos en orden, excepto HP / Intel Itanium 2 e IBM POWER6 , aunque este último tenía una unidad de punto flotante fuera de orden . ^{[ 39 ]} Los otros procesadores en orden de gama alta se quedaron muy atrás, a saber, Sun UltraSPARC III / IV y los mainframes de IBM que habían perdido la capacidad de ejecución fuera de orden por segunda vez, permaneciendo en orden hasta la generación z10 . Posteriormente, los grandes procesadores de ejecución secuencial se centraron en el rendimiento multihilo, pero finalmente las series SPARC T y Xeon Phi cambiaron a la ejecución fuera de orden en 2011 y 2016, respectivamente.

Casi todos los procesadores para teléfonos y otras aplicaciones de gama baja siguieron siendo de ejecución en orden hasta aproximadamente 2010. Primero, el Scorpion de Qualcomm (distancia de reordenamiento de 32) se envió en Snapdragon , ^{[ 40 ]} y un poco más tarde el A9 de Arm sucedió al A8 . Para las computadoras personales x86 de gama baja, la microarquitectura Bonnell de ejecución en orden en los primeros procesadores Intel Atom fue desafiada primero por la microarquitectura Bobcat de AMD , y en 2013 fue sucedida por una microarquitectura Silvermont de ejecución fuera de orden . ^{[ 41 ]} Debido a que la complejidad de la ejecución fuera de orden impide lograr el consumo de energía, el costo y el tamaño mínimos, la ejecución en orden sigue siendo predominante en microcontroladores y sistemas embebidos , así como en núcleos de clase de teléfono como el A55 y el A510 de Arm en configuraciones big.LITTLE .

La ejecución fuera de orden es más sofisticada que la ejecución en orden. En los procesadores con ejecución en orden segmentada, la ejecución de instrucciones se superpone de forma secuencial, requiriendo cada una varios ciclos de reloj para completarse. Como consecuencia, los resultados de una instrucción anterior se retrasan cuando se necesitan en la siguiente. La ejecución en orden también debe gestionar estas dependencias. Sin embargo, su enfoque es bastante simple: se detiene en cada paso. La ejecución fuera de orden utiliza técnicas de seguimiento de datos mucho más sofisticadas, como se describe a continuación.

En los procesadores más antiguos, el procesamiento de instrucciones se realiza en un ciclo de instrucciones que normalmente consta de los siguientes pasos:

1. Obtención de instrucciones .
2. Si los operandos de entrada están disponibles (por ejemplo, en los registros del procesador), la instrucción se envía a la unidad funcional correspondiente . Si uno o más operandos no están disponibles durante el ciclo de reloj actual (generalmente porque deben obtenerse de la memoria ), el procesador se detiene hasta que estén disponibles.
3. La instrucción es ejecutada por la unidad funcional correspondiente.
4. La unidad funcional escribe los resultados de vuelta al archivo de registros .

A menudo, un procesador de ejecución en orden dispone de un vector de bits que registra en qué registros se escribirá mediante una tubería. ^{[ 42 ]} Si alguno de los operandos de entrada tiene activado el bit correspondiente en este vector, la instrucción se detiene. En esencia, el vector cumple una función muy simplificada de protección contra riesgos de registro. Por lo tanto, la ejecución fuera de orden utiliza matrices bidimensionales, mientras que la ejecución en orden utiliza un vector unidimensional para evitar riesgos.

Este nuevo paradigma divide el procesamiento de instrucciones en estos pasos: ^{[ 43 ]}

1. Obtención de instrucciones.
2. Decodificación de instrucciones.
3. Cambio de nombre de la instrucción.
4. Envío de instrucciones a una cola de instrucciones (también llamada búfer de instrucciones o estaciones de reserva ).
5. La instrucción permanece en la cola hasta que sus operandos de entrada estén disponibles. La instrucción puede salir de la cola antes que las instrucciones más antiguas.
6. La instrucción se emite a la unidad funcional correspondiente y es ejecutada por dicha unidad.
7. Los resultados están en cola.
8. Solo después de que todas las instrucciones anteriores hayan registrado sus resultados en el archivo de registro, este resultado se vuelve a registrar en dicho archivo. Esto se conoce como la etapa de graduación o de retiro.

El concepto clave del procesamiento fuera de orden consiste en permitir que el procesador evite una serie de bloqueos que se producen cuando no se dispone de los datos necesarios para realizar una operación. En el esquema anterior, el procesador evita el bloqueo que se produce en el paso 2 del procesamiento en orden cuando la instrucción no está completamente lista para ser procesada debido a la falta de datos.

Los procesadores de ejecución fuera de orden llenan estos espacios en el tiempo con otras instrucciones que están listas, luego reordenan los resultados al final para que parezca que las instrucciones se procesaron normalmente, registran y aplican el orden original del programa , o confirman en lotes ininterrumpibles donde el orden no causará corrupción de datos. La forma en que se ordenan las instrucciones en el código informático original se conoce como orden del programa ; en el procesador se manejan en orden de datos , el orden en que los datos están disponibles en los registros del procesador. Se necesita un circuito bastante complejo para convertir de un orden a otro y mantener un orden lógico de la salida.

La ventaja del procesamiento fuera de orden aumenta a medida que la tubería de instrucciones se profundiza y la diferencia de velocidad entre la memoria principal (o memoria caché ) y el procesador se amplía. En las máquinas modernas, el procesador funciona mucho más rápido que la memoria, por lo que, durante el tiempo que un procesador en orden pasa esperando la llegada de datos, teóricamente podría haber procesado una gran cantidad de instrucciones.