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 desordenada 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 Modelo 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 desarrollos permiten una ejecución paralela mejorada 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 Common Data Bus (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, ocurran en el mismo orden que lo harían en un procesador en orden, independientemente del hecho de que se estén ejecutando fuera de orden. orden (es decir, no secuencialmente).
El algoritmo de Tomasulo utiliza el cambio de nombre de registros para realizar correctamente la ejecución desordenada. Todos los registros de estaciones de reserva y de uso general tienen un valor real o un valor de marcador de posición. Si un valor real no está disponible para un registro de destino durante la etapa de emisión, inicialmente se utiliza un valor de marcador de posición. El valor del marcador de posición es una etiqueta que indica qué estación de reserva producirá el valor real. Cuando la unidad finalice y transmita el resultado en el CDB, el marcador de posición será reemplazado por el valor real.
Cada unidad funcional dispone de una única estación de reserva. Las estaciones de reserva contienen la información necesaria para ejecutar una sola instrucción, incluida la operación y los operandos. La unidad funcional comienza a procesar cuando está libre y cuando todos los operandos fuente necesarios para una instrucción son reales.
En términos prácticos, puede haber excepciones para las cuales no hay suficiente información de estado disponible sobre una excepción, en cuyo caso el procesador puede generar una excepción especial, llamada excepción imprecisa . No pueden ocurrir excepciones imprecisas en implementaciones en orden , ya que el estado del procesador cambia solo en el orden del programa (consulte Canalización RISC clásica § Excepciones ).
Los programas que experimentan excepciones precisas , donde se puede determinar la instrucción específica que tomó 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 reiniciar ni volver a ejecutar, 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 están estancados. En este paso se cambia el nombre de los registros, eliminando los peligros de WAR y WAW.
En la etapa de ejecución, se llevan a cabo las operaciones de instrucción. Las instrucciones se retrasan en este paso hasta que todos sus operandos estén disponibles, eliminando los peligros de RAW. La corrección del programa se mantiene mediante un cálculo de dirección efectivo para evitar peligros 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 variaciones en el tiempo de acceso al almacenamiento y velocidades de circuito, liberando así las unidades funcionales. Esta mejora supera los largos retrasos en coma flotante y los accesos a la memoria. En particular, el algoritmo es más tolerante con los errores de caché. Además, los programadores no tienen que implementar código optimizado. Esto es el resultado del trabajo conjunto del bus de datos común y la estación de reserva para preservar las dependencias y fomentar la simultaneidad. [1] : 33
Al rastrear operandos para instrucciones en las estaciones de reserva y cambiar el nombre de los registros en el hardware, el algoritmo minimiza la lectura tras escritura (RAW) y elimina los peligros de la arquitectura informática de escritura tras escritura (WAW) y escritura tras lectura (WAR) . Esto mejora el rendimiento al reducir el tiempo perdido que de otro modo se necesitaría para las paradas. [1] : 33
Una mejora igualmente importante en el algoritmo es que el diseño no se limita a una estructura de tubería específica. Esta mejora permite que el algoritmo sea adoptado más ampliamente por procesadores de múltiples problemas. Además, el algoritmo se puede ampliar fácilmente para permitir la especulación en ramas. [3] : 182
El algoritmo de Tomasulo, fuera de IBM, no se utilizó durante varios años después de su implementación en la arquitectura System/360 Modelo 91. Sin embargo, su uso experimentó un gran aumento durante la década de 1990 por tres razones:
Muchos procesadores modernos implementan esquemas de programación dinámica que se derivan del algoritmo original de Tomasulo, incluidos los populares chips Intel x86-64 . [5] [ verificación fallida ] [6]