Ejecución fuera de orden para niños

En arquitectura de computadores, la ejecución fuera de orden u OoOE (Out-of-Order Execution), es un paradigma utilizado en la mayoría de los microprocesadores de alto rendimiento, como forma de aprovechar los ciclos de instrucción, que de otro modo serían desperdiciados, produciéndose en consecuencia cierta demora de trabajo. Gran parte de los diseños modernos de CPU, soportan la ejecución fuera de orden.

Historia

La ejecución fuera de orden es una forma restringida de computación de flujo de datos, siendo una importante área de investigación en arquitectura de computadores en los años 1970 y principios de los años 1980. Uno de los más importantes trabajos académicos en la materia fue llevado a cabo por Yale Patt con su simulador HPSm. Un artículo publicado por James E. Smith y A.R. Pleszkun, publicado en 1985, completó la idea al describir cómo se podía mantener el preciso comportamiento de las excepciones en las máquinas basadas en ejecución fuera de orden.

La primera máquina en utilizar esta idea probablemente fue el CDC 6600 (1964), el cual utilizaba marcadores para solucionar conflictos entre registros. Unos tres años más tarde fue presentado el IBM 360/91 (1966), que implementaba el novedoso Algoritmo de Tomasulo. IBM también presentó el primer microprocesador fuera de orden, el POWER1 (1990) para sus equipos RS/6000. Sin embargo fue la aparición del Intel Pentium Pro (1995) lo que terminó de lanzar esta tecnología. Muchos otros fabricantes comenzaron entonces a aplicar la idea en sus diseños: IBM/Motorola PowerPC 601 (1992/1993), Fujitsu/HAL Sparc64 I (1995), HP PA-8000 (1996), MIPS R-10000 (1996), AMD K5 (1996) y DEC Alpha 21264 (1998). Excepciones notables a esta tendencia fueron el UltraSparc de Sun, el HP/Intel IA-64, y el Transmeta Crusoe.

La complejidad lógica de los esquemas fuera de orden fue la razón de que esta técnica no alcanzara una posición importante hasta mediados de los años 1990. Incluso actualmente no se aplica en muchos procesadores de bajo coste destinados a mercados muy sensibles a los costes de fabricación ya que se necesita una "gran" superficie de silicio para construir este tipo de hardware.

Una vulnerabilidad en las implementaciones de algunos fabricantes de microprocesadores del mecanismo de ejecución fuera de orden se informó a los fabricantes el 1 de junio de 2017, pero no se publicó hasta enero de 2018, como una vulnerabilidad explotable que dejó a Millones de sistemas vulnerables. La vulnerabilidad fue nombrada Spectre. Una vulnerabilidad similar, Meltdown, que se reveló al mismo tiempo, aprovechó la suposición de que algunos fabricantes habían hecho al cargar datos en la caché de un procesador al permitir que los datos se almacenen en caché desde un límite de seguridad privilegiado. Esto dio lugar a una condición de carrera que podría cronometrarse para filtrar información privilegiada.

Ideas básicas

Procesadores en orden

En los primeros procesadores, las instrucciones eran procesadas según estos pasos:

1. Captura de la instrucción.
2. Si los operandos de entrada están disponibles (en los registros por ejemplo), la instrucción es enviada a la correspondiente unidad funcional. Si alguno de ellos no lo está durante el ciclo de reloj actual (generalmente porque está siendo capturado desde memoria), el procesador inserta burbuja hasta poder utilizar el dato.
3. La instrucción es ejecutada por la unidad funcional adecuada.
4. La unidad funcional escribe los resultados en el archivo de registros.

Procesadores fuera de orden

Este nuevo paradigma rompe con lo anterior basándose en el siguiente orden:

1. Captura de la instrucción.
2. Envío de la instrucción a una cola (también llamada buffer o estación de reserva).
3. La instrucción espera en cola hasta que los operandos de entrada estén disponibles, de manera que una instrucción más reciente puede abandonar el buffer antes que otra anterior si ya tiene los datos disponibles.
4. La instrucción es enviada a la correspondiente unidad funcional, que la ejecuta.
5. Se envía el resultado a cola.
6. La instrucción en curso solamente puede escribir en el archivo de registros una vez que todas las anteriores a ella hayan escrito sus correspondientes resultados.

La idea clave del procesamiento OoO consiste en permitir al procesador evitar ciertos tipos de burbuja que suceden cuando la información necesaria para realizar una operación no está disponible. Siguiendo los pasos antes explicados, el procesador OoO evita las burbujas comentadas en el paso 2 de la ejecución en orden cuando la instrucción no se puede completar a causa de la falta de datos.

Los procesadores OoO rellenan esos "huecos" de tiempo con instrucciones que sí están listas para ejecutarse para después reordenar los resultados y aparentar que fueron procesadas de manera normal. La forma en que las instrucciones son ordenadas en el código original a ejecutar se conoce como orden de programa, mientras que el orden en que el procesador las maneja es el orden de datos, siendo aquel en que los datos van quedando disponibles para su captura desde los registros del procesador. Se necesita una circuitería bastante compleja para convertir un orden en otro y poder además mantener el orden lógico de la salida; el propio procesador ejecuta las instrucciones de forma aperentemente aleatoria.

Los beneficios del procesamiento OoO crecen a medida que se profundiza en la segmentación, así como con el crecimiento de la diferencia de velocidades entre la memoria principal (o memoria cache) y el procesador. En las máquinas modernas, el procesador funciona a velocidades mucho mayores que la memoria, de modo que mientras un procesador en orden pierde tiempo esperando por los datos, uno OoO ya habría procesado un gran número de instrucciones.

Emisión fuera de orden

Para evitar falsas dependencias de operandos, algo que reduciría la frecuencia de reloj si las instrucciones son emitidas fuera de orden, se utiliza la técnica conocida como renombre de registros. Para ello, el procesador físicamente cuenta con más registros que los que vienen definidos por la arquitectura. Los registros físicos son etiquetados de forma que pueden convivir múltiples versiones del mismo registro de arquitectura.

Reinicio de programas

La cola de resultados es necesaria para resolver problemas tales como predicciones erróneas de salto o el lanzamiento de excepciones. La cola de resultados permite a los programas reiniciarse tras una excepción, lo que requiere que las instrucciones sean completadas en el orden del código del programa. La cola permite también que los resultados puedan ser descartados si proceden de predicciones erróneas de saltos o excepciones resultado de la ejecución de instrucciones antiguas.

La capacidad de emitir instrucciones antes de que se resuelvan los saltos se conoce como ejecución especulativa.

Aplicación en algunas arquitecturas

• Los procesadores PowerPC de IBM usan colas distribuidas entre las diferentes unidades funcionales, mientras que otros procesadores fuera de orden utilizan una cola centralizada. IBM denomina estaciones de reserva a dichas colas.

• Los primeros procesadores fuera de orden de Intel utilizan una cola de resultados llamada buffer de reordenación, mientras que la mayoría de los últimos procesadores fuera de orden utilizan mapas de registros.

Véase también

En inglés: Out-of-order execution Facts for Kids

• Algoritmo de marcador
• Algoritmo de Tomasulo