Algoritmo de tomasulo

Este algoritmo es llamado así en honor al ingeniero Robert Tomasulo que trabajo en el proyecto. Junto a su equipo creo el IBM 360/91.

La organización interna del 360/91 comparte varias características con el PowerPC 604 y el Pentium Pro. Las principales diferencias son:

ü  No tiene predicción de saltos ni especulación

ü  No hay unidad de commit (Unidad de coma flotante)

Las instrucciones de Load/Store  a través de una unidad funcional  realizan un direccionamiento computacional efectivo, prediciendo independientemente instrucciones de Load/Store  en Buffer. Las instrucciones Load se ejecutan en un segundo lo suficiente para acceder a memoria y escribir los resultados para luego enviar el valor del resultado de la memoria al archivo de registro y/o cualquier otra estación que espera dicho resultado. Las instrucciones Store completan la ejecución en la etapa de resultado, el cual escribe el resultado en la memoria. Notese que todas las escrituras ocurren en la etapa de resultado ya sea en registro o memoria, esta restricción simplifica el algoritmo de tomasulo.

Al inicio era sólo para operaciones de FP (fichero de registros). Hoy se aplica a todas las instrucciones, y la mayoría de procesadores avanzados llevan un algoritmo similar. Este algoritmo se puede aplicar a otro tipo de sistemas donde hay ciertos recursos compartidos por diversos agentes, y se quieren gestionar los recursos de forma distribuida.

Durante su ejecución provoca un reordenamiento dinámico en la ejecución (fase EX) de las instrucciones, aunque la emisión sigue siendo en el orden del código original. Permite la ejecución de instrucciones no dependientes de otras anteriores (aunque estas últimas estén bloqueadas esperando por algún operando fuente).  Va a realizar un renombrado dinámico de registros para evitar riesgos por dependencias (WAR, WAW) entre instrucciones. Todos los registros de destino se renombran y el nuevo nombre que toman se llama etiqueta (tag).

En este algoritmo se ponen una serie de entradas en cada UF (unidad funcional), llamadas estaciones de reserva RS. A éstas llegan las emisiones (IS) de instrucciones con toda la información de la misma, también llegan los valores de los operandos fuente, si han podido leerse, o cierta información (etiqueta) que indica que operando falta (no se bloquea la cadena).

Estación de Reserva (Reservation Stations, R.S.): Lugar dónde esperan las instrucciones emitidas junto a las ALU’s (U.F.), hasta que pueden ejecutarse en la U.F. Esta espera se debe a la no disponibilidad de todos los operandos fuente (hay RAW: una instrucción anterior aún no ha generado algún operando).

En la implementación del algoritmo de Tomasulo, las estaciones de reserva (RS) son registros asociados a las unidades funcionales. De manera que forman una pequeña cola de instrucciones a la entrada de la unidad funcional (de unas pocas por UF si la operación no es muy común, como DIV, a muchas si es muy frecuente).

Buffers de Memoria: Son las estaciones de reserva para instrucciones de load/store (carga/almacenamiento). Es el lugar dónde esperan los acceso a memoria emitidos hasta que disponen de todos sus operandos y el bus de memoria (caché) está libre.

Bus Común de Datos (Common Data Bus, CDB): Une la salida de las unidades funcionales y la carga de memoria con el fichero de registros, las estaciones de reserva (y los buffers). Las UF mandan el dato de salida a través de él para que lo lean el resto de elementos de la CPU. En general, las máquinas suelen tener más de un CDB (ejemplo: uno para enteros y otro para FP). Cualquier CDB tiene dos buses: uno para el resultado de una operación (32 líneas para INT/float, 64 para double) y otro para la etiqueta asociada al mismo (tamaño log₂ del número de etiquetas).

Etiqueta (tag): Son identificadores que se asocian a los registros destino cada vez que se emite una instrucción. A partir de renombrar un registro destino con una etiqueta, es ésta la que circula por toda la CPU (estaciones de reserva, buffers, el fichero de registros, CDB, etc.). Una etiqueta estará en uso desde que la instrucción se emite hasta que su resultado es puesto en el CDB

Etapas de Ejecución

Fetch (IF): Acceso a caché de instrucciones para leer instrucción apuntada por PC (contador de programa)

Issue (IS): Emisión de la instrucción. Al inicio esta etapa se hacía en un solo ciclo (hoy en día esta etapa dura varios ciclos de reloj). En esta epata se realiza todo esto:

          - Decodificación

          - Lectura de operandos ya disponibles

          - Envío hacia la estación de reserva (esta sería la auténtica emisión).

Al final de IS, se intenta enviar una instrucción a una estación de reserva (o buffer de load/store), asignando una etiqueta (tag) al registro destino. Si hay una estación de reserva (o buffer) libre en la UF (unidad funcional) requerida por la operación: Se emite la instrucción mandando a la R.S. los operandos disponibles. Para los que no estén disponibles, se anota la etiqueta por la que esperan. Si no hay RS (o buffer) libre o no quedan etiquetas libres, la etapa IS se bloqueará hasta que una R.S. de la unidad funcional afectada se libere.

Execution (EX): Cuando una estación de reserva (buffer) obtuvo todos sus operandos, empieza a ejecutarse. La RS puede quedar libre:

  

      ü  Al comenzar a ejecutarse en la unidad funcional (primer EX1). Entonces, esta etapa     

                        conservará en algún otro sitio dos campos: uno para el resultado y otro para la etiqueta asociada            al valor de salida (se envía en WB junto al resultado de la operación).

      ü  final de WB. La R.S. tendrá todos los campos necesarios para operandos fuente, resultado y  etiqueta.

Write (WB): El resultado de una operación y su etiqueta se escriben en el bus común de datos, de manera que las estaciones de reserva o buffers que estén esperando por este valor (tienen la misma etiqueta en alguno de sus operandos) lo toman, es decir, se produce un desvío a través del bus común de datos. Igualmente el valor del bus común de datos se escribe en el fichero de registros, si su etiqueta coincide con alguno. Tras la escritura la etiqueta se libera. El fichero de registros deberá, por tanto, tener información sobre la última etiqueta que va asociada a cada registro.

Esquema del algoritmo de tomasulo

Fuente: http://icaro.eii.us.es/descargas/Transparencias_Planificacion_dinamica_2004.pdf, tema 3: Planificacion o reordenamiento (scheduling) de instrucciones, Arquitectura de Sistemas Paralelos 1, recuperado 14/4/2013

Simuladores.- El algoritmo de tomasulo puede entenderse de una mejor manera con dos simuladores que planteamos a continuación:

Simulador1 Tomasulo.- DinBucle es un simulador simplificado de procesadores RISC con algoritmo de planificación dinámica (estilo Tomasulo clásico), desarrollado en el departamento de Arquitectura y Tecnología de Computadores, Universidad de Sevilla.

Simulador2 Tomasulo (descarga): El enlace es de descarga directa Autor: Vicente Arnau Llombart, España

Bibliografía

http://icaro.eii.us.es/descargas/Transparencias_Planificacion_dinamica_2004.pdf, tema 3: Planificacion o reordenamiento (scheduling) de instrucciones, Arquitectura de Sistemas Paralelos 1, recuperado 14/4/2013

Patterson D. A. - Hennessy J. L. (2011), Computer Architecture 5th edition: A quantitative approach, Estados Unidos, Morgan Kaufmann 

Patterson D. A. - Hennessy J. L. (2000), Estructura y diseño de computadores: Interficie circuitería/Programación , Barcelona: España, Editorial Reverté