El algoritmo de Tomasulo es un algoritmo de hardware de arquitectura informática para la programación dinámica de instrucciones que permite la ejecución fuera de orden y permite un uso más eficiente de múltiples unidades de ejecución. Fue desarrollado por Robert Tomasulo en IBM en 1967 y se implementó por primera vez en la unidad de punto flotante del IBM System/360 Model 91. [ 1]
Las principales innovaciones del algoritmo de Tomasulo incluyen el cambio de nombre de los registros en el hardware, estaciones de reserva para todas las unidades de ejecución y un bus de datos común (CDB) en el que los valores calculados se transmiten a todas las estaciones de reserva que puedan necesitarlos. Estos avances permiten una mejor ejecución paralela de instrucciones que, de otro modo, se estancarían con el uso de marcadores u otros algoritmos anteriores.
Robert Tomasulo recibió el premio Eckert-Mauchly en 1997 por su trabajo en el algoritmo. [2]
Los siguientes son los conceptos necesarios para la implementación del algoritmo de Tomasulo:
El Bus de Datos Común (CDB) conecta las estaciones de reserva directamente con las unidades funcionales. Según Tomasulo, "preserva la precedencia al tiempo que fomenta la concurrencia". [1] : 33 Esto tiene dos efectos importantes:
Las instrucciones se emiten secuencialmente de modo que los efectos de una secuencia de instrucciones, como las excepciones generadas por estas instrucciones, se produzcan en el mismo orden en que se producirían en un procesador en orden, independientemente del hecho de que se estén ejecutando fuera de orden (es decir, no secuencialmente).
El algoritmo de Tomasulo utiliza el cambio de nombre de registros para realizar correctamente la ejecución fuera de orden. Todos los registros de estación de reserva y de propósito general contienen un valor real o un valor de reserva. Si un valor real no está disponible para un registro de destino durante la etapa de emisión, inicialmente se utiliza un valor de reserva. El valor de reserva es una etiqueta que indica qué estación de reserva producirá el valor real. Cuando la unidad finaliza y transmite el resultado en la CDB, el valor de reserva se reemplaza con el valor real.
Cada unidad funcional tiene una única estación de reserva. Las estaciones de reserva contienen la información necesaria para ejecutar una única instrucción, incluida la operación y los operandos. La unidad funcional comienza a procesar cuando está libre y cuando todos los operandos de origen necesarios para una instrucción son reales.
En términos prácticos, puede haber excepciones para las cuales no se dispone de suficiente información de estado sobre una excepción, en cuyo caso el procesador puede generar una excepción especial, denominada excepción imprecisa . Las excepciones imprecisas no pueden ocurrir en implementaciones en orden , ya que el estado del procesador solo se modifica en el orden del programa (consulte la sección Excepciones de la sección de pipeline RISC clásica ).
Los programas que experimentan excepciones precisas , en las que se puede determinar la instrucción específica que generó la excepción, pueden reiniciarse o volver a ejecutarse en el punto de la excepción. Sin embargo, aquellos que experimentan excepciones imprecisas generalmente no pueden reiniciarse ni volver a ejecutarse, ya que el sistema no puede determinar la instrucción específica que generó la excepción.
Las tres etapas que se enumeran a continuación son las etapas por las que pasa cada instrucción desde el momento en que se emite hasta el momento en que se completa su ejecución.
En la etapa de emisión, se emiten instrucciones para su ejecución si todos los operandos y estaciones de reserva están listos o si, de lo contrario, se bloquean. En este paso, se renombran los registros, lo que elimina los riesgos de WAR y WAW.
En la etapa de ejecución se llevan a cabo las operaciones de instrucción. En este paso, las instrucciones se retrasan hasta que todos sus operandos estén disponibles, lo que elimina los riesgos de RAW. La exactitud del programa se mantiene mediante un cálculo de dirección eficaz para evitar riesgos a través de la memoria.
En la etapa de escritura de resultados, los resultados de las operaciones de ALU se vuelven a escribir en los registros y las operaciones de almacenamiento se vuelven a escribir en la memoria.
Los conceptos de estaciones de reserva, cambio de nombre de registros y bus de datos común en el algoritmo de Tomasulo presentan avances significativos en el diseño de computadoras de alto rendimiento.
Las estaciones de reserva asumen la responsabilidad de esperar operandos en presencia de dependencias de datos y otras inconsistencias como tiempos de acceso de almacenamiento variables y velocidades de circuito, liberando así las unidades funcionales. Esta mejora supera los largos retrasos de punto flotante y los accesos a memoria. En particular, el algoritmo es más tolerante a los errores de caché. Además, los programadores se liberan de la necesidad de implementar código optimizado. Esto es el resultado de que el bus de datos común y la estación de reserva trabajen juntos para preservar las dependencias y fomentar la concurrencia. [1] : 33
Al rastrear los operandos de las instrucciones en las estaciones de reserva y el cambio de nombre de los registros en el hardware, el algoritmo minimiza la lectura después de la escritura (RAW) y elimina los riesgos de la arquitectura informática de escritura después de escritura (WAW) y escritura después de lectura (WAR) . Esto mejora el rendimiento al reducir el tiempo perdido que, de otro modo, se requeriría para los bloqueos. [1] : 33
Una mejora igualmente importante en el algoritmo es que el diseño no está limitado a una estructura de canalización específica. Esta mejora permite que el algoritmo sea adoptado más ampliamente por procesadores de múltiples problemas . Además, el algoritmo se extiende fácilmente para permitir la especulación de ramificaciones. [3] : 182
El algoritmo de Tomasulo se implementó en la arquitectura System/360 Model 91. Fuera de IBM, no se utilizó durante varios años. Sin embargo, su uso aumentó enormemente durante la década de 1990 por tres motivos:
Muchos procesadores modernos implementan esquemas de programación dinámica que son variantes del algoritmo original de Tomasulo, incluidos los populares chips Intel x86-64 . [5] [ verificación fallida ] [6]