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.
Conceptos para la implementación
Los siguientes son los conceptos necesarios para la implementación del algoritmo de Tomasulo:
Bus común de datos (CDB, del inglés "Common data bus")
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"[1]:33 Esto tiene dos consecuencias importantes:
- Las unidades funcionales (UF) pueden acceder al resultado de cualquier operación que tenga relación con el "registro de punto flotante", permitiendo que múltiples unidades esperen el resultado.
- La unidad de Detección de errores (Hazard Detection) y la unidad de Control de ejecución (Control Execution) se encuentran distribuidas. Las estaciones de reserva controlan cuando una instrucción puede ser ejecutada, en lugar de haber una única unidad de Detección de errores dedicada.
Orden de instrucciones
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)
Renombrado de registros
El algoritmo de Tomasulo utiliza el renombrado de registros para ejecutar de forma correcta las instrucciones que no tienen orden. Todos los registros, los de uso general y los de la estación de reserva, guardan o un valor real o una etiqueta (placeholder). Si durante la etapa de Emisión, no se encuentra disponible un valor real para ser enviado a otro registro, se utiliza como valor una etiqueta (placeholder) indicando la estación de reserva que producirá el valor real. Cuando la unidad termina de transmitir el resultado en el Bus Común de Datos, la etiqueta es reemplaza con el valor real.
Cada Unidad Funcional (UF) tiene una única Estación de Reserva, estas guardan la información necesaria para ejecutar una única instrucción, incluyendo la operación y los operandos. Las UF comienzan a procesar cuando están libres y todos los operandos necesarios para ejecutar la instrucción contienen un valor real.
Excepciones
Podrían ocurrir excepciones para las que no existe suficiente información del estado, en cuyo caso el procesador puede lanzar una excepción "imprecisa". Este tipo de excepciones no pueden ocurrir en implementaciones que no sean OoOE, ya que el estado del procesador sólo varía en el orden del programa.
Los programas que experimentan excepciones precisas, en las que la instrucción que provocó la excepción puede ser determinada pueden reiniciar o reejecutar en el momento de la excepción. Sin embargo si se experimenta una excepción imprecisa no se puede en general reiniciar o rejecutar, ya que el sistema no puede determinar la instrucción que provocó la excepción.
Referencias
- Tomasulo, Robert M. (Jan 1967). «An Efficient Algorithm for Exploiting Multiple Arithmetic Units». IBM Journal of Research and Development (IBM) 11 (1): 25-33. ISSN 0018-8646. doi:10.1147/rd.111.0025.