Ejecución fuera de orden

En ingeniería informática , la ejecución fuera de orden (o, más formalmente, ejecución dinámica ) es un paradigma utilizado en unidades centrales de procesamiento de alto rendimiento para hacer uso de ciclos de instrucciones que de otro modo se desperdiciarían. En este paradigma, un procesador ejecuta instrucciones en un orden regido por la disponibilidad de datos de entrada y unidades de ejecución, ^[1] en lugar de por su orden original en un programa. ^{[2] [3]} De este modo, el procesador puede evitar estar inactivo mientras espera a que se complete la instrucción anterior y puede, mientras tanto, procesar las siguientes instrucciones que pueden ejecutarse de forma inmediata e independiente. ^[4]

La ejecución fuera de orden es una forma restringida de arquitectura de flujo de datos , que fue un área de investigación importante en la arquitectura informática en la década de 1970 y principios de 1980.

La primera máquina en utilizar la ejecución fuera de orden fue la CDC 6600 (1964), diseñada por James E. Thornton , que utiliza un marcador para evitar conflictos. Permite que una instrucción se ejecute si sus registros de operando de origen (lectura) no deben ser escritos por ninguna instrucción anterior no ejecutada (dependencia verdadera) y el registro de destino (escritura) no debe ser un registro utilizado por ninguna instrucción anterior no ejecutada (dependencia falsa). La 6600 carece de los medios para evitar el bloqueo de una unidad de ejecución en falsas dependencias ( conflictos de escritura tras escritura (WAW) y escritura tras lectura (WAR), denominados respectivamente conflicto de primer orden y conflicto de tercer orden por Thornton, quien denominó a las dependencias verdaderas ( lectura tras escritura (RAW)) como conflicto de segundo orden) porque cada dirección tiene solo una única ubicación a la que puede hacer referencia. El WAW es peor que el WAR para el 6600, porque cuando una unidad de ejecución encuentra un WAR, las otras unidades de ejecución aún reciben y ejecutan instrucciones, pero tras un WAW la asignación de instrucciones a las unidades de ejecución se detiene, y no pueden recibir más instrucciones hasta que el registro de destino de la instrucción que causa el WAW haya sido escrito por una instrucción anterior. ^[5]

Aproximadamente dos años después, el IBM System/360 Model 91 (1966) introdujo el cambio de nombre de registros con el algoritmo de Tomasulo ^[6] , que disuelve las falsas dependencias (WAW y WAR), haciendo posible la ejecución totalmente fuera de orden. Una instrucción que direcciona una escritura en un registro r _n se puede ejecutar antes de que se ejecute una instrucción anterior que utiliza el registro r _n , escribiendo en realidad 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 abordan r _n , pero hasta entonces se da r _n para las instrucciones anteriores y alt-r _n para las posteriores que abordan r _n .

En el Modelo 91, el cambio de nombre de los registros se implementa mediante un bypass denominado Bus de datos común (CDB) y búferes de operandos de origen 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 direccionados por cualquier instrucción no ejecutada se encuentra en el CDB. Otra ventaja que tiene el 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 cargas y almacenamientos para que se ejecuten antes de las cargas y almacenamientos anteriores, ^[7] 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. ^[8] Solo se renombran los registros de punto flotante del Modelo 91, lo que lo hace sujeto 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 manera general y hacerse práctica fuera de las supercomputadoras.

Para tener excepciones precisas , el estado correcto en orden de la ejecución del programa debe estar disponible en caso de una excepción. En 1985 se desarrollaron varios enfoques según lo descrito por James E. Smith y Andrew R. Pleszkun. ^[9] El CDC Cyber ​​205 fue un precursor, ya que en caso de 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. ^[10] Sin embargo, para que todas las excepciones sean precisas, tiene que 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 contiene los valores antiguos (sobrescritos) de los registros que se restauran cuando una excepción requiere la reversión de las instrucciones. ^[9] Mediante simulación, Smith determinó que agregar un buffer de reordenamiento (o buffer 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%. ^[9] Una importante investigación académica en este tema fue liderada por Yale Patt con su simulador HPSm. ^[11]

En la década de 1980, muchos de los primeros microprocesadores RISC , como el Motorola 88100 , presentaban errores de escritura en los registros, lo que generaba excepciones imprecisas. Las instrucciones comenzaban a ejecutarse en orden, pero algunas (por ejemplo, las de punto flotante) necesitaban más ciclos para completar la ejecución. Sin embargo, la ejecución en un solo ciclo de las instrucciones más básicas reducía en gran medida 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 la ramificación. ^[12] 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 de los almacenamientos anteriores. 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 desacoplarlo del decodificador de instrucciones, para evitar el estancamiento 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 realizaban efectivamente un cambio de nombre de registro limitado. ^[7] Una arquitectura desacoplada similar se había utilizado un poco antes en Culler 7. ^[13] La ISA del ZS-1, al igual que el posterior POWER de IBM, ayudó a la ejecución temprana de las ramas.

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 sólo registros de punto flotante) con excepciones precisas. Utiliza un archivo de registro físico (es decir, un archivo reasignado dinámicamente con valores no confirmados y confirmados) en lugar de un búfer de reordenación, pero la capacidad de cancelar instrucciones sólo se necesita en la unidad de ramificación, que implementa un búfer de historial (llamado pila de contador de programa por IBM) para deshacer los cambios en los registros de conteo, enlace y condición. La capacidad de reordenación incluso de las instrucciones de punto flotante sigue siendo muy limitada; debido a la incapacidad del POWER1 de reordenar las instrucciones aritméticas de punto flotante (los resultados se hicieron disponibles en orden), sus registros de destino no se renombran. POWER1 tampoco tiene estaciones de reserva necesarias para el uso fuera de orden de la misma unidad de ejecución. ^{[14] [15] El año siguiente, el modelo 900 del} ES/9000 de IBM tenía el cambio de nombre de registros añadido para los registros de propósito general. También tiene estaciones de reserva con seis entradas para la unidad de enteros duales (en cada ciclo, se pueden seleccionar de seis a dos instrucciones y luego ejecutarlas) y seis entradas para la FPU. Otras unidades tienen colas FIFO simples. La distancia de reordenación es de hasta 32 instrucciones. ^[16] 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 entre tres y cinco años por delante de la competencia. ^{[17] [18]}

Los primeros procesadores superescalares de un solo chip ( Intel i960CA en 1989) usaban una programación de puntuación 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 la proliferación hasta las computadoras personales . El Motorola 88110 (1992) usó un búfer de historial para revertir instrucciones. ^[19] Las cargas se podían ejecutar antes de los almacenamientos anteriores. Mientras los almacenamientos y las ramas esperaban para comenzar la ejecución, las instrucciones posteriores de otros tipos podían seguir fluyendo a través de todas las etapas de la tubería, incluida la reescritura. La capacidad de 12 entradas del búfer de historial puso un límite a la distancia de reordenamiento. ^{[20] [21] [22]} El PowerPC 601 (1993) fue una evolución del RISC Single Chip , en sí mismo una simplificación de POWER1. El 601 permitía que las instrucciones de punto flotante y de ramificación superaran a las instrucciones enteras que ya se encontraban en la cola de instrucciones obtenidas, de las cuales las cuatro entradas más bajas se escaneaban para comprobar su capacidad de procesamiento. En caso de un error de caché, se podían reordenar las cargas y los almacenamientos. Solo se podían renombrar los registros de enlace y de conteo. ^[28] En el otoño de 1994, NexGen e IBM con Motorola llevaron el cambio de nombre de los 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 . ^[29] 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 ramificación puede tener una instrucción esperando frente a ella sin bloquear el flujo de instrucciones a las otras unidades. Un búfer de reordenamiento de cinco entradas no permite que 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 memoria caché antes que un almacenamiento anterior. ^{[30] [31]}

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 anterior. 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é. ^[32] HAL SPARC64 (1995) superó la capacidad de reordenamiento del modelo 900 ES/9000 al tener tres estaciones de reserva de 8 entradas para unidad de generación de direcciones , enteros y de punto flotante , y una estación de reserva de 12 entradas para carga/almacenamiento, lo que permite un mayor reordenamiento del acceso a la memoria caché/memoria que los procesadores anteriores. Hasta 64 instrucciones pueden estar en un estado reordenado a la vez. ^{[33] [34]} Pentium Pro (1995) introdujo una estación de reserva unificada , que con una capacidad de 20 micro-OP permitió una reordenación muy flexible, respaldada por un buffer de reordenación de 40 entradas. Las cargas se pueden reordenar antes que las cargas y los almacenamientos. ^[35]

La tasa de ejecución por ciclo prácticamente alcanzable aumentó aún más a medida que la ejecución fuera de orden completa fue adoptada por SGI / MIPS ( R10000 ) y HP PA-RISC ( PA-8000 ) en 1996. El 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 núcleos en orden distintos de HP / Intel Itanium 2 e IBM POWER6 , aunque este último tenía una unidad de punto flotante fuera de orden . ^[36] Los otros procesadores en orden de alta gama se quedaron muy atrás, a saber, UltraSPARC III / IV de Sun y los mainframes de IBM que habían perdido la capacidad de ejecución fuera de orden por segunda vez, permaneciendo en orden en la generación z10 . Los procesadores posteriores de gran tamaño en orden se centraron en el rendimiento multiproceso, pero finalmente la serie SPARC T y Xeon Phi cambiaron a la ejecución fuera de orden en 2011 y 2016 respectivamente. ^{[ cita requerida ]}

Casi todos los procesadores para teléfonos y otras aplicaciones de gama baja se mantuvieron en orden hasta c.  2010. Primero, el Scorpion de Qualcomm (distancia de reordenamiento de 32) enviado en Snapdragon , ^[37] y un poco más tarde el A9 de Arm sucedió al A8 . Para las computadoras personales x86 de gama baja, la microarquitectura Bonnell en orden en los primeros procesadores Intel Atom fue desafiada primero por la microarquitectura Bobcat de AMD , y en 2013 fue reemplazada por una microarquitectura Silvermont fuera de orden . ^[38] Debido a que la complejidad de la ejecución fuera de orden impide lograr el menor consumo de energía, costo y tamaño mínimos, la ejecución en orden aún prevalece en microcontroladores y sistemas integrados , así como en núcleos de clase telefónica como A55 y A510 de Arm en configuraciones big.LITTLE .

La ejecución fuera de orden es más sofisticada en relación con la línea base de ejecución en orden. En los procesadores de ejecución en orden segmentados, la ejecución de instrucciones se superpone de forma segmentada y cada una requiere varios ciclos de reloj para completarse. La consecuencia es que los resultados de una instrucción anterior se retrasarán con respecto a los que puedan necesitarse en la siguiente. La ejecución en orden todavía tiene que realizar un seguimiento de estas dependencias. Sin embargo, su enfoque es bastante poco sofisticado: se bloquea en todo momento. 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 anteriores, el procesamiento de instrucciones se realizaba en un ciclo de instrucción que normalmente constaba de los siguientes pasos:

1. Instrucción fetch .
2. Si hay operandos de entrada disponibles (en los registros del procesador, por ejemplo), 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 se están recuperando de la memoria ), el procesador se detiene hasta que estén disponibles.
3. La instrucción es ejecutada por la unidad funcional apropiada.
4. La unidad funcional escribe los resultados en el archivo de registro .

A menudo, un procesador en orden tiene un registro de vector de bits en el que se escribirán los registros mediante una secuencia de comandos. ^[39] Si algún operando de entrada tiene el bit correspondiente establecido en este vector, la instrucción se detiene. Básicamente, el vector cumple una función muy simplificada de protección contra los peligros de los registros. Por lo tanto, la ejecución fuera de orden utiliza matrices 2D, mientras que la ejecución en orden utiliza un vector 1D para evitar los peligros.

Este nuevo paradigma divide el procesamiento de instrucciones en estos pasos:

1. Búsqueda de instrucciones.
2. Decodificación de instrucciones.
3. Cambio de nombre de 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 espera en la cola hasta que sus operandos de entrada estén disponibles. La instrucción puede salir de la cola antes que las instrucciones anteriores.
6. La instrucción se emite a la unidad funcional apropiada y es ejecutada por esa unidad.
7. Los resultados se ponen en cola.
8. Solo después de que todas las instrucciones anteriores hayan escrito sus resultados nuevamente en el archivo de registro, entonces este resultado se vuelve a escribir en el archivo de registro. Esto se denomina etapa de graduación o retiro.

El concepto clave del procesamiento OoOE es permitir que el procesador evite una clase de bloqueos que ocurren cuando los datos necesarios para realizar una operación no están disponibles. En el esquema anterior, el procesador OoOE evita el bloqueo que ocurre en el paso (2) del procesador en orden cuando la instrucción no está completamente lista para ser procesada debido a la falta de datos.

Los procesadores OoOE llenan estos espacios a tiempo con otras instrucciones que están listas, luego reordenan los resultados al final para que parezca que las instrucciones se procesaron de manera normal. La forma en que se ordenan las instrucciones en el código de computadora original se conoce como orden de programa ; en el procesador, se manejan en orden de datos , el orden en el que los datos, los operandos, están disponibles en los registros del procesador. Se necesitan circuitos bastante complejos para convertir de un orden a otro y mantener un orden lógico de la salida; el procesador mismo ejecuta las instrucciones en un orden aparentemente aleatorio.

El beneficio del procesamiento OoOE crece a medida que se profundiza el flujo de instrucciones y se amplía la diferencia de velocidad entre la memoria principal (o memoria caché ) y el procesador. En las máquinas modernas, el procesador funciona muchas veces más rápido que la memoria, por lo que durante el tiempo que un procesador en orden pasa esperando que lleguen los datos, podría haber procesado una gran cantidad de instrucciones.

Una de las diferencias creadas por el nuevo paradigma es la creación de colas que permiten desacoplar el paso de envío del paso de emisión y la etapa de graduación de la etapa de ejecución. Un nombre temprano para el paradigma fue arquitectura desacoplada . En los primeros procesadores en orden , estas etapas operaban de manera bastante escalonada y en cadena.

Las instrucciones del programa no pueden ejecutarse en el orden especificado originalmente, siempre que el resultado final sea correcto. Separa las etapas de búsqueda y decodificación de la etapa de ejecución en un procesador segmentado mediante un búfer .

El propósito del buffer es particionar el acceso a la memoria y ejecutar funciones en un programa de computadora y lograr un alto rendimiento explotando el paralelismo de grano fino entre ambos. ^[40] Al hacerlo, oculta efectivamente toda la latencia de la memoria desde la perspectiva del procesador.

En teoría, un búfer más grande puede aumentar el rendimiento. Sin embargo, si el procesador tiene una predicción errónea de una rama , es posible que sea necesario vaciar todo el búfer, lo que desperdicia muchos ciclos de reloj y reduce la eficacia. Además, los búferes más grandes generan más calor y utilizan más espacio en la matriz . Por este motivo, los diseñadores de procesadores actuales prefieren un enfoque de diseño multiproceso .

En general, se piensa que las arquitecturas desacopladas no son útiles para la computación de propósito general, ya que no manejan bien el código de control intensivo. ^[41] El código de control intensivo incluye elementos como las ramas anidadas que ocurren con frecuencia en los núcleos del sistema operativo . Las arquitecturas desacopladas desempeñan un papel importante en la programación en arquitecturas de palabras de instrucción muy largas (VLIW). ^[42]

Para evitar falsas dependencias de operandos, que disminuirían la frecuencia con la que se podrían emitir instrucciones fuera de orden, se utiliza una técnica llamada cambio de nombre de registros . En este esquema, hay más registros físicos que los definidos por la arquitectura. Los registros físicos están etiquetados de modo que puedan existir múltiples versiones del mismo registro arquitectónico al mismo tiempo.

La cola de resultados es necesaria para resolver problemas como predicciones erróneas de bifurcaciones y excepciones/trampas. La cola de resultados permite reiniciar los programas después de una excepción, lo que requiere que las instrucciones se completen en el orden del programa. La cola permite descartar resultados debido a predicciones erróneas en instrucciones de bifurcaciones anteriores y excepciones tomadas en instrucciones anteriores.

La capacidad de emitir instrucciones más allá de ramas que aún no se han resuelto se conoce como ejecución especulativa .

• ¿Las instrucciones se envían a una cola centralizada o a múltiples colas distribuidas?

Los procesadores IBM PowerPC utilizan colas que se distribuyen entre las distintas unidades funcionales, mientras que otros procesadores fuera de servicio utilizan una cola centralizada. IBM utiliza el término estaciones de reserva para sus colas distribuidas.

• ¿Existe una cola de resultados real o los resultados se escriben directamente en un archivo de registro? En este último caso, la función de cola se gestiona mediante mapas de registros que contienen la información de cambio de nombre de los registros para cada instrucción en curso.

Los primeros procesadores fuera de orden de Intel utilizan una cola de resultados denominada búfer de reordenamiento , mientras que la mayoría de los procesadores fuera de orden posteriores utilizan mapas de registros.

Más precisamente: los microprocesadores de la familia Intel P6 tienen un búfer de reordenamiento (ROB) y una tabla de alias de registro (RAT). El ROB fue motivado principalmente por la recuperación de errores de predicción de bifurcaciones.

La familia Intel P6 se ​​encuentra entre los primeros microprocesadores OoOE, pero fue suplantada por la arquitectura NetBurst . Años más tarde, NetBurst resultó ser un callejón sin salida debido a su largo proceso de desarrollo que suponía la posibilidad de frecuencias de funcionamiento mucho más altas. Los materiales no pudieron igualar los ambiciosos objetivos de reloj del diseño debido a problemas térmicos y los diseños posteriores basados ​​en NetBurst, a saber, Tejas y Jayhawk, fueron cancelados. Intel volvió al diseño P6 como base de las microarquitecturas Core y Nehalem . Las microarquitecturas posteriores Sandy Bridge , Ivy Bridge y Haswell son un alejamiento de las técnicas de reordenamiento utilizadas en P6 y emplean técnicas de reordenamiento de EV6 y P4 , pero con un proceso de desarrollo algo más corto. ^{[43] [44]}

El Wikilibro Diseño de microprocesadores tiene una página sobre el tema: Ejecución fuera de orden

• Programación de instrucciones
• Valla de memoria
• Sistema de repetición
• Estantería de amortiguación

• Smith, James E. ; Pleszkun, AR (junio de 1985). "Implementación de interrupciones precisas en procesadores segmentados". ACM SIGARCH Computer Architecture News . 13 (3): 36–44. doi :10.1145/327070.327125.