Algoritmo de Tomasulo

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

Los siguientes son los conceptos necesarios para la implementación del algoritmo de Tomasulo:

Bus comun de datos (CDB, del inglés "Common data bus")[editar]

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:

  1. 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.
  2. 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[editar]

Las instrucciones son emitidas de forma secuencial, por tanto las excepciones disparadas por éstas ocurren en el mismo orden en que ingresan al procesador, sin importar que estén siendo ejecutadas en otro orden (no secuencial)

Unidad de Punto flotante de Tomasulo

Renombrado de registros[editar]

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, éstas guardan la información necesaria para ejecutar una única instrucción, incluyendo la operación y los operandos. Las UF comienzan a procesar cuando estan libres y todos los operandos necesarios para ejecutar la instrucción contienen un valor real.

Exceptions[editar]

Practically speaking, there may be exceptions for which not enough status information about an exception is available, in which case the processor may raise a special exception, called an "imprecise" exception. Imprecise exceptions cannot occur in non-OoOE implementations, as processor state is changed only in program order (see RISC Pipeline Exceptions).

Programs that experience "precise" exceptions, where the specific instruction that took the exception can be determined, can restart or re-execute at the point of the exception. However, those that experience "imprecise" exceptions generally cannot restart or re-execute, as the system cannot determine the specific instruction that took the exception.

  1. Tomasulo, Robert M. (Jan 1967). «An Efficient Algorithm for Exploiting Multiple Arithmetic Units». IBM Journal of Research and Development (IBM) 11 (1): 25-33. doi:10.1147/rd.111.0025. ISSN 0018-8646.