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 su orden original en un programa. [2] [3] Al hacerlo, el procesador puede evitar estar inactivo mientras espera 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 de computadoras en los años 1970 y principios de los 1980.
La primera máquina que utilizó 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 se ejecute una instrucción 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). ). El 6600 carece de los medios para evitar detener una unidad de ejecución en dependencias falsas ( conflictos de escritura tras escritura (WAW) y escritura después de lectura (WAR), denominados respectivamente conflicto de primer orden y conflicto de tercer orden por Thornton, quien denominó dependencias verdaderas ( lectura). después de escribir (RAW)) como conflicto de segundo orden) porque cada dirección tiene una sola 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 ante un WAW la asignación de instrucciones a las unidades de ejecución se detiene y no pueden recibir más instrucciones. hasta que una instrucción anterior haya escrito en el registro de destino de la instrucción que causa WAW. [5]
Aproximadamente dos años después, IBM System/360 Modelo 91 (1966) introdujo el cambio de nombre de registros con el algoritmo de Tomasulo , [6] que disuelve las dependencias falsas (WAW y WAR), haciendo posible la ejecución completa fuera de orden. Una instrucción que dirige una escritura en un registro r n se puede ejecutar antes de que se ejecute una instrucción anterior que usa el registro r n , escribiendo en un registro alternativo (renombrado) alt-r n , que se convierte en un registro normal r n únicamente. cuando se hayan ejecutado todas las instrucciones anteriores que se dirigen a r n , pero hasta entonces se da r n para las instrucciones anteriores y alt-r n para las posteriores que se dirigen a r n .
En el Modelo 91, el cambio de nombre de los registros se implementa mediante una derivación denominada Common Data Bus (CDB) y buffers 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 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á listo, 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 almacenes para ejecutar antes de las cargas y almacenes anteriores, [7] a diferencia del 6600, que solo tiene un capacidad limitada para mover cargas más allá de las cargas y tiendas más allá de las tiendas, pero no cargas más allá de las tiendas y tiendas más allá de las cargas. [8] Solo se cambia el nombre de los registros de punto flotante del Modelo 91, lo que lo hace sujeto a las mismas limitaciones WAW y WAR que el CDC 6600 cuando ejecuta cálculos de punto fijo. Tanto el 91 como el 6600 también sufren de 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 de ejecución del programa debe estar disponible ante una excepción. En 1985 se desarrollaron varios enfoques descritos por James E. Smith y Andrew R. Pleszkun. [9] El CDC Cyber 205 fue un precursor, ya que tras una interrupción de la memoria virtual, todo el estado del procesador (incluida la información sobre las instrucciones ejecutadas parcialmente) se guarda en un paquete de intercambio invisible , para que pueda reanudarse en el mismo estado. de ejecución. [10] Sin embargo, para que todas las excepciones sean precisas, tiene que haber una manera 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 instrucciones. [9] Smith simuló que agregar un búfer de reordenamiento (o búfer de historial o equivalente) a Cray-1S reduciría el rendimiento de la ejecución de los primeros 14 bucles de Livermore (no vectorizados) en solo un 3%. [9] Yale Patt dirigió una importante investigación académica en este tema con su simulador HPSm. [11]
En la década de 1980, muchos de los primeros microprocesadores RISC , como el Motorola 88100 , tenían reescritura desordenada en los registros, lo que generaba excepciones imprecisas. Las instrucciones comenzaron a ejecutarse en orden, pero algunas (por ejemplo, las de punto flotante) necesitaron más ciclos para completar la ejecución. Sin embargo, la ejecución en un solo ciclo de las instrucciones más básicas redujo en gran medida el alcance del problema en comparación con el CDC 6600.
Smith también investigó cómo hacer que diferentes unidades de ejecución funcionen de manera más independiente entre sí y de la memoria, el front-end y la bifurcación. [12] Implementó esas ideas en el Astronautics ZS-1 (1988), que presenta un desacoplamiento de la tubería de entero/carga/almacenamiento de la tubería de punto flotante, lo que permite el reordenamiento entre tuberías. El ZS-1 también era capaz de ejecutar cargas por delante de las tiendas anteriores. En su artículo de 1984, opinó que aplicar las excepciones precisas sólo en el canal de entero/memoria debería ser suficiente para muchos casos de uso, ya que incluso permite la memoria virtual . Cada canal tenía un búfer de instrucciones para desacoplarlo 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 canalizaciones se asoció con dos colas direccionables que efectivamente realizaban un cambio de nombre de registro limitado. [7] Una arquitectura desacoplada similar se había utilizado un poco antes en Culler 7. [13] El ISA del ZS-1, al igual que el posterior POWER de IBM, ayudó a la ejecución temprana de ramas.
Con el POWER1 (1990), IBM volvió a la ejecución desordenada. Fue el primer procesador en combinar el cambio de nombre de registros (aunque nuevamente solo registros de punto flotante) con excepciones precisas. Utiliza un archivo de registro físico (es decir, un archivo reasignado dinámicamente con valores confirmados y no confirmados) en lugar de un búfer de reorden completo de datos, pero la capacidad de cancelar instrucciones solo es necesaria en la unidad de sucursal, que implementa un búfer de historial (llamado pila de contadores de programas). por IBM) para deshacer cambios en los registros de recuento, vinculación y condición. La capacidad de reordenamiento incluso de las instrucciones de punto flotante es todavía muy limitada; debido a la incapacidad de POWER1 para reordenar instrucciones aritméticas de punto flotante (los resultados estuvieron disponibles en orden), sus registros de destino no cambian de nombre. POWER1 tampoco tiene estaciones de reserva necesarias para el uso fuera de servicio de una misma unidad de ejecución. [14] [15] Al año siguiente, el ES/9000 modelo 900 de IBM cambió el nombre de los registros también para los registros de propósito general. También cuenta con estaciones de reserva con seis entradas para la unidad de entero dual (cada ciclo, desde las seis instrucciones hasta dos se pueden seleccionar y luego ejecutar) y seis entradas para la FPU. Otras unidades tienen colas FIFO simples. La distancia de reordenamiento 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 una ejecución fuera de orden, y un analista calificó la tecnología del A19 de tres a cinco años por delante de la competencia. [17] [18]
Los primeros procesadores superescalares de un solo chip ( Intel i960 CA en 1989) utilizaron una programación de puntuación simple como la que tenía el CDC 6600 un cuarto de siglo antes, pero en 1992-1996 un rápido avance de las técnicas, permitido por el aumento del número de transistores , redujo la proliferación. a computadoras personales. Motorola 88110 (1992) utilizó un búfer de historial para revertir instrucciones. [19] Las cargas podrían ejecutarse por delante de las tiendas anteriores. Mientras las tiendas y sucursales esperaban para comenzar la ejecución, las instrucciones posteriores de otros tipos podían seguir fluyendo a través de todas las etapas del proceso, incluida la reescritura. La capacidad de 12 entradas del buffer histórico puso un límite a la distancia de reorden. [20] [21] [22] 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 rama y de punto flotante superaran a las instrucciones de números enteros que ya estaban en la cola de instrucciones recuperadas, de las cuales las cuatro entradas más bajas fueron escaneadas para determinar su capacidad de envío. En caso de que se pierda el caché, se podrían reordenar las cargas y los almacenes. Sólo se puede cambiar el nombre del enlace y del registro de recuento. [28] En el otoño de 1994, NexGen e IBM con Motorola cambiaron el nombre de los registros de propósito general a CPU de un solo chip. El Nx586 de NexGen fue el primer procesador x86 capaz de ejecutarse fuera de orden, logrado con micro-OP . La distancia de reordenamiento es de hasta 14 micro-OP. [29] PowerPC 603 cambió el nombre de los registros de propósito general y FP. Cada una de las cuatro unidades de ejecución no ramificadas puede tener una instrucción en espera frente a ella sin bloquear el flujo de instrucciones hacia las otras unidades. Un buffer de reordenamiento de cinco entradas no permite que más de cuatro instrucciones superen a una instrucción no ejecutada. Debido a un búfer de almacenamiento, una carga puede acceder al caché antes que un almacén 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 buffer 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 almacenes en caso de errores de caché. [32] HAL SPARC64 (1995) superó la capacidad de reordenamiento del modelo ES/9000 900 al tener tres estaciones de reserva de 8 entradas para unidades de generación de números enteros, coma flotante y direcciones , y una estación de reserva de 12 entradas para carga. /store, que permite una mayor reordenación del acceso a la memoria caché/memoria que los procesadores anteriores. Se pueden reordenar hasta 64 instrucciones a la vez [33] [34] Pentium Pro (1995) introdujo una estación de reserva unificada , que con una capacidad de 20 micro-OP permitía un reordenamiento muy flexible, respaldado por un Búfer de reorden de 40 entradas. Las cargas se pueden reordenar antes que las cargas y los almacenes. [35]
La tasa de ejecución por ciclo prácticamente alcanzable aumentó aún más a medida que SGI / MIPS ( R10000 ) y HP PA-RISC ( PA-8000 ) adoptaron la ejecución fuera de orden completa en 1996. El mismo año Cyrix 6x86 y AMD K5 incorporó técnicas avanzadas de reordenamiento a 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 distintos de HP / Intel Itanium 2 e IBM POWER6 , aunque este último Tenía una unidad de punto flotante fuera de servicio . [36] Los otros procesadores ordenados de gama alta 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 hasta el final. generación z10 . Posteriormente, los grandes procesadores en orden se centraron en el rendimiento multiproceso, pero finalmente la serie SPARC T y Xeon Phi cambiaron a ejecución fuera de orden en 2011 y 2016 respectivamente.
Casi todos los procesadores para teléfonos y otras aplicaciones de gama baja permanecieron en orden hasta c. 2010. Primero, el Scorpion de Qualcomm (distancia de reordenamiento de 32) se envió con Snapdragon , [37] y un poco más tarde, el A9 de Arm sucedió al A8 . Para las computadoras personales x86 de gama baja en orden, los primeros Intel Atom fueron desafiados por primera vez por Bobcat de AMD , y en 2013 fueron reemplazados por un Silvermont fuera de servicio . [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 todavía prevalece en microcontroladores y sistemas integrados , así como en núcleos de clase telefónica como el Arm's A55. y A510 en configuraciones big.LITTLE .
Para apreciar la ejecución fuera de orden, es útil describir primero en orden, para poder hacer una comparación de las dos. Las instrucciones no se pueden completar instantáneamente: toman tiempo (múltiples ciclos). Por lo tanto, los resultados se quedarán atrás cuando se necesitan. In-order todavía tiene que realizar un seguimiento de las dependencias. Sin embargo, su enfoque es bastante sencillo: detenerse siempre. out-of-order utiliza técnicas de seguimiento de datos mucho más sofisticadas, como se ve a continuación.
En procesadores anteriores, el procesamiento de instrucciones se realizaba en un ciclo de instrucciones que normalmente constaba de los siguientes pasos:
A menudo, un procesador en orden tiene una grabación de vector de bits en la que una canalización escribirá los registros. [39] Si algún operando de entrada tiene el bit correspondiente establecido en este vector, la instrucción se detiene. Básicamente, el vector desempeña una función muy simplificada de protección contra riesgos de registro. 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 peligros.
Este nuevo paradigma divide el procesamiento de instrucciones en estos pasos:
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 la parada que ocurre en el paso (2) del procesador en orden cuando la instrucción no está completamente lista para ser procesada debido a datos faltantes.
Los procesadores OoOE llenan estos espacios a tiempo con otras instrucciones que están listas y luego reordenan los resultados al final para que parezca que las instrucciones se procesaron normalmente. 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 que los datos, operandos, quedan 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 propio procesador ejecuta las instrucciones en un orden aparentemente aleatorio.
El beneficio del procesamiento OoOE crece a medida que el proceso 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 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 desacoplar la etapa de graduación de la etapa de ejecución. Uno de los primeros nombres del paradigma fue arquitectura desacoplada . En los procesadores en orden anteriores , estas etapas operaban de manera bastante sincronizada y canalizada.
Es posible que las instrucciones del programa no se ejecuten 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 canalizado mediante el uso de 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 fino entre los dos. [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 rama , es posible que sea necesario vaciar todo el búfer, lo que desperdicia muchos ciclos de reloj y reduce la efectividad. Además, los buffers más grandes generan más calor y utilizan más espacio en el troquel . Por esta razón, los diseñadores de procesadores hoy en día prefieren un enfoque de diseño de subprocesos múltiples .
Generalmente se considera que las arquitecturas desacopladas no son útiles para la informática de propósito general, ya que no manejan bien el código de control intensivo. [41] El código intensivo de control incluye cosas como 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 cuando las instrucciones podrían emitirse 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 para 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 sucursales 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 que se descarten resultados debido a predicciones erróneas en instrucciones de rama más antiguas y excepciones tomadas en instrucciones más antiguas.
La capacidad de emitir instrucciones más allá de ramas que aún están por resolver se conoce como ejecución especulativa .
No espere a que se ejecuten las instrucciones anteriores si esta instrucción no depende de ellas.
El algoritmo "permite que instrucciones secuenciales que normalmente se detendrían debido a ciertas dependencias se ejecuten de forma no secuencial" (también conocida como ejecución fuera de orden).
Esta flexibilidad mejora el rendimiento ya que permite la ejecución con menos tiempo de "espera".
{{cite book}}: |work=ignorado ( ayuda )El nuevo A19 se basa en técnicas "superescalares" de computadoras científicas para ejecutar muchas instrucciones al mismo tiempo. El A19 puede superponer hasta 140 operaciones, más de 10 veces más que los mainframes convencionales.