Tema 2. Funcionamiento de los algoritmos de Pizarra y Tomasulo, con códigos ejemplo

Algoritmo de Tomasulo

                 Para reducir al máximo el número de paradas por riesgos estructurales y de datos, la planificación dinámica reordena las instrucciones en tiempo de ejecución. La emisión de instrucciones sigue en orden, pero permite la lectura de operandos y la ejecución fuera de orden. Existen para ello diferentes algoritmos de planificación, aunque casi todos derivan de los dos más conocidos:

- Algoritmo de la Pizarra

- Algoritmo de Tomasulo

Algoritmo de Pizarra

                El algoritmo de Pizarra es un método centralizado para programar dinámicamente un pipeline, de modo que las instrucciones se puedan ejecutar fuera de orden cuando no hay conflictos y el hardware está disponible. En una pizarra, las dependencias de datos de todas las instrucciones se registran. Las instrucciones se ponen en marcha sólo cuando la pizarra determina que no hay conflictos con instrucciones previamente manejadas o incompletas. Si una instrucción se detiene porque es inseguro continuar, la tabla monitorea el flow de las instrucciones ejecutándose hasta que todas las dependencias se hayan resuelto antes de que se maneje la instrucción parada.

Tiene 4 etapas:

- Emisión: comprobación de riesgos estructurales por la unidad funcional, WAW

- Lectura de operandos: comprobación de riesgos estructurales por los registros, RAW

- Ejecución: cada unidad funcional con su latencia

- Escritura de resultados: comprobación de riesgos estructurales por los registros WAR

Ejemplo:

Partiendo de este código,

Loop: LD F2,0(R1)
      ADDD F6,F2,F4
      MULTD F8,F6,F0
SUBI R1,R1,#8

BNEZ R1,Loop

Esto sería lo que tendríamos, tras aplicar el algoritmo de Pizarra:

Loop: LD F2,0(R1)

ADDD F6,F2,F4
      MULTD F8,F6,F0
LD F10,-8(R1)
4
      MULTD F14,F12
ADDD F12,F10,
F,F0
      SUBI R1,R1,#16

BNEZ R1,Loop

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 la pizarra ("Scoreboard algorithm") 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 necesite. Esto permite mejorar la ejecución paralela de instrucciones en situaciones en las que el scoreboarding fallaría y provocaría la parada.

             El algoritmo de Tomasulo está distribuido, y dividido en tres etapas:

- Emisión: comporbación de riesgos estructurales por la estación de reserva

- Ejecución: RAW, comprobación de riesgos estructurales por la UF

- Escritura de resultados en el CDB: comprobación de riesgos estructurales por el CDB

En la actualidad, gran parte de los procesadores hacen uso de variaciones de este algoritmo para la planificación dinámica de instrucciones.

Ejemplo:

Tenemos este código original:

DIVD F0, F2, F4

ADDD F6, F0, F8

SD F6, 0(R1)

SUBD F8, F10, F14

MULD F6, F10, F8

Existe una dependencia externa, WAR (Write after Write), entre ADDD y SUBD, y vemos que hay una dependendica de datos, WAW (Write After Read) entre ADDD y MULD (debido a que DIVD necesita tomar ciclos mucho más largos para obtener F0)

•

Renombrando registros:

DIVD F0, F2, F4

ADDD S, F0, F8

SD S, 0(R1)

SUBD T, F10, F14

MULD F6, F10, T

Referencias:

• Encliclopedia Wikipedia: http://www.wikipedia.org

• Planificación dinámica: 

http://www.cs.umd.edu/class/fall2001/cmsc411/projects/dynamic/intro.html

• Algoritmo de Tomasulo:

http://www.ecs.umass.edu/ece/koren/architecture/Tomasulo1/tomasulo_files/tomasulo.htm

• Apuntes de clase de "Arquitectura para Gráficos y Multimedia", de la Universidad Rey Juan Carlos, Madrid

• Varios documentos y apuntes diversos, encontrados por www.google.es