Algoritmo de Tomasulo

El algoritmo de Tomasulo es un algoritmo de planificación dinámica desarrollado por Robert Tomasulo, de IBM. Se diseñó para permitir a un procesador ejecutar instrucciones fuera de orden. Este algoritmo difiere del algoritmo de marcador (Scoreboard) en que este último no dispone de renombrado de registros. En su lugar, el algoritmo de Scoreboard (scoreboarding) resuelve los riesgos Escritura Después de Escritura (EDE o WAW) y Escritura Después de Lectura (EDL o WAR) deteniendo la ejecución, mientras que el algoritmo de Tomasulo permite el lanzamiento de dichas instrucciones. Además, el algoritmo de Tomasulo utiliza un bus de datos común en el que los valores calculados son enviados a todas las estaciones de reserva que los necesiten. Esto permite mejorar la ejecución paralela de instrucciones en situaciones en las que el scoreboarding fallaría y provocaría la parada. Se implementó por primera vez en la unidad de punto flotante del procesador IBM360/91. En la actualidad, gran parte de los procesadores hacen uso de variaciones de este algoritmo para la planificación dinámica de instrucciones. Los siguientes son los conceptos necesarios para la implementación del algoritmo de Tomasulo: El Bus Común de Datos, o CDB, conecta a las estaciones de reserva directamente con las unidades funcionales (UF). De acuerdo a la definición del Algoritmo de Tomasulo, el CDB "preserva la precedencia, mientras que garantiza el soporte para la concurrencia" Esto tiene dos consecuencias importantes: Las instrucciones son emitidas de forma secuencial, por tanto las excepciones disparadas por estas ocurren en el mismo orden en que ingresan al procesador, sin importar que estén siendo ejecutadas en otro orden (no secuencial) El algoritmo de Tomasulo utiliza el renombrado de registros para ejecutar de forma correcta las instrucciones que no tienen orden.