Algoritmo de Tomasulo

Algoritmo de Tomasulo

El algoritmo de Tomasulo es un algoritmo de planificación dinámica desarrollado en 1967 por Robert Tomasulo de IBM.

Se inventó para la IBM 360/91 cuando no existían las caches 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: comprobació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.

Etapas del Algoritmo Tomasulo

Tomasulo solo tiene que hacer frente a riesgos RAW porque evita los riesgos de nombre mediante el nombramiento de registro.

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

Características:

• Técnica de planificación dinámica de instrucciones con gestión distribuida. Inicialmente, en el IBM/360 (1967, Robert Tomasulo) era sólo para operaciones de FP. Hoy se aplica a todas las instrucciones, y la mayoría de procesadores avanzados llevan un algoritmo similar al clásico (estudiaremos el clásico pero para todo tipo de instrucciones, porque es el explicado en los libros generalmente).

• 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. Evidentemente la implementación que veremos aquí es hardware.

• 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)

Definiciones

En este algoritmo se ponen una serie de entradas en cada UF, 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). La R.S. tendrá una serie de campos para anotar el valor de los operandos fuente (y si es necesario el valor del resultado de la operación y la etiqueta asociada al registro destino).

• Buffers de Memoria: Son las R.S. para instrucciones de 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. En el alg. clásico y en general, hay buffers separados para instrucciones de carga y para los de almacenamiento.

• 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 (es decir, se usa en la fase WB, produciéndose un bypass). Se trata de un recurso común por el que hay que competir. En general, las máquinas suelen tener más de un CDB (p.ej. uno para enteros y otro para FP) puesto que el número de WB por cada ciclo puede ser mayor que 1. 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 log2 del número de etiquetas).

• Etiqueta (tag): Son identificadores que se asocian a los registros destino cada vez que se emite una instrucción.

Especificación de Arquitectura de Tomasulo

• Campos de cada Estación de Reserva (según versión, algunos son prescindibles):

ü  Op: operación

ü  Qj, Qk: Etiqueta de los operandos j y k. Si está vacío, el operando está disponible.

ü  Vj, Vk: Valores de los operandos.

ü  Ocupado: Indica que la RS está en uso.

• Buffer de LD:

ü  Dirección: para el acceso a memoria (etiqueta si oper. no disponible o valor oper.)

ü  Ocupado: Indica que el buffer está en uso.

• Buffer de ST:

ü  Qi: Etiqueta de la RS que producirá el valor a almacenar en memoria.

ü  Dirección: para el acceso a memoria (etiqueta si oper. no disponible o valor oper.)

ü  Vi: valor a almacenar. Estará vacío cuando Qi esté lleno.

ü  Ocupado: Indica que el buffer está en uso.

• Fichero de Registros FP. Cada registro tendrá la estructura:

ü  Qi: Etiqueta de la RS que producirá el valor a almacenar en el registro.

ü  Vi: valor del registro.

ü  Ocupado: Indica que el valor actual del registro no es válido (espera por el nuevo).

Tomasulo en procesadores actuales

En general los micros con planificación dinámica son capaces de emitir y ejecutar varias Instrucciones a la vez, y su arquitectura es muy potente.

• Uno de los primeros microprocesadores con planificación dinámica fue Motorola PowerPC 620 (1995). Es un ejemplo muy bueno: su cadena (4 fases: IF ID IS EX) y arquitectura es muy similar al algoritmo clásico Tomasulo. Poseía unas pocas R.S. por cada UF.

Ø Dos unidades enteras simples (1 ciclo).

Ø Una unidad entera compleja (3 a 20 ciclos) para MULT y DIV enteras.

Ø Una unidad de carga-almacenamiento (1 ciclo si acierta en caché).

Ø Una unidad de punto flotante (31 ciclos DIVFP, 2 ciclos ADDFP y MULTFP).

Ø Y una unidad de saltos, que actualice BTB en caso de fallo de predicción.

• Pentium Pro (su parte INT es idem que P.II, P.III y similar al P4). Su cadena es de 11 fases. Posee 40 R.S. comunes a todas las UF:

Ø  Dos unidades enteras (1 ciclo). Una de ellas se usan para saltos (actualiza BTB en caso de fallo de predicción). La otra se usa también para multiplicaciones y divisiones enteras.

Ø  Dos unidades FP para multiplicaciones y divisiones de punto flotante. Realmente solo puede empezar en el mismo ciclo una de ellas.

Ø  Una unidad de carga (1 ciclo).

Ø  Una unidad de almacenamiento más compleja (lleva un buffer MOB especial).

• MIPS R10000 (similar a los actuales). Posee 16 R.S. para INT, 16 para FP y 16 para Ld-St:

Ø  Dos unidades enteras (una también sirve para saltos, y la otra para MULT INT).

Ø  Una unidad para cálculo de direcciones de acceso a memoria (para carga-almacenamiento).

Ø  Una unidad de punto flotante simple (sólo para ADDFP).

Ø  Una unidad de punto flotante compleja (DIV, MULT, SQRT-FP).

Ventajas Algoritmo Tomasulo

• Disminución costes debido a dependencias de datos
• Simplificación del compilador
• Mismo código funciona bien en diferentes segmentaciones

Desventajas Algoritmo Tomasulo

• Mayor complejidad hardware
• Terminación fuera de orden à aparecen riegos WAR y WAW
• Complica el tratamiento de las interrupciones 

Planificación Dinámica vs Estática

PLANIFICACION DINAMICA	PLANIFICACION ESTATICA
Complicación hardware	Menos hardware
Compilador no tiene que optimizar	Compilador más difícil
Trasparente al usuario	Posible problema de herencia (compilador debe conocer endoarquitectura)
El hardware extrae el rendimiento que puede en cada versión	Inconveniente: dependencia compilación – rendimiento
Tamaño de código estático no se toca	Tamaño de código estático puede crecer (mas fallos de cache)
Defecto: ventana de instrucciones limitada (Fase IF) (análisis local)	Ventaja: ventana de instrucciones infinita (análisis global )
En tiempo de ejecución se conoce más: Valores de registro (dir: acceso) Predicción dinámica, etc.	El compilador no puede conocer: Valores de registros (dir acceso) Predicción dinámica, etc.
No puede eliminar instrucciones	Puede eliminar instrucciones (de overhead u otras)
No necesita muchos registros de usuario	Puede necesitar muchos registros de usuario

Representantes comerciales de la arquitectura Superescalar

• Nvidia (serie GeForce 6, )
• Sun SPARC
• AMD (AMD -K5-PR100)
• INTEL (INTEL PENTIUM)

Bibliografía:

• http://rvmaster-agm.blogspot.com/2010/11/tema-2-como-funcionan-el-algoritmos-de.html
• http://www.uhu.es/josem.bravo/AeIC/Tema3%28PrimeraParte%29.pdf
• http://www.dia.eui.upm.es/asignatu/Arq_com/AC%20Grado/Paco%20Aylagas/4-Planificacion%20Dinamica.pdf