Algoritmo de Tomasulo

Se invento para la IBM 360/91 cuando aun no existian los caches. El principio en el que se basa es “register renaming”. En el algoritmo de Tomasulo el renombrado de registros es provisto por las “estaciones de reserva” que guardan los operandos de las instrucciones que esperan a ser lanzadas. La idea basica es que las estaciones de reserva busca y buferea un operando tan pronto como esta disponible, eliminando la necesidad de obtener ese operando de un registro. Ademas las instrucciones pendientes indican que numero de estacion de reserva va a proveer la entrada necesaria. Finalmente cuando se produce overlap de escrituras sucesivas a un registro, solo la ultima es la que realmente se usa para actualizar el registro. Cuando se leen las instrucciones, los especificadotes de los registros de operandos pendientes son renombrados a nombres de estaciones de reserva. Como hay mas estaciones de reserva que registros esta tecnica elimina muchos hazards provenientes de las dependencias de nombres (elimina WAR y WAW)

El uso de estaciones de reserva lleva a dos propiedades importantes: primero el control para detectar hazards y el control de ejecución estan distribuidos (la info en las estaciones de reserva de cada unidad funcional determina cuando una instrucción puede empezar a ejecutarse en esa unidad funcional), segundo los resultados son pasados directamente a las unidades funcionales desde las RE donde estan bufereados, en vez de pasar a los registros. Este bypassing se hace a traves del common data bus CDB (va a todas las unidades funcionales que estan esperando el dato).

Como van pasando las instrucciones en el pipeline agregando Tomasulo:1. Issue: se toma la instrucción de la cola FIFO. Si hay una estacion de reserva

vacia se guarda alli junto con los valores de los operandos si estos estan en los registros. Si no hay ER vacia entonces se hace stall hasta que alguna se libere. Si los opernado no estan en los registros se colocan los numeros de las unidades funcionales que los van a producir en los campos Qi y Qj. Este paso renombra los registros.

2. Ejecución: Si uno o mas de los operandos no esta disponibles se monitorea el CDB esperando a que se lo calcule. Cuando todos los operandos estan disponibles, se puede ejecutar la operación en la unidad funcional correspondiente. Es posible que varias instrucciones esten listas para ejecutar en ese ciclo de clock en la misma unidad funcional. En ese caso se elige una de ellas. Los loads y stores requieren un proceso de ejecución de 2 pasos. El primer paso computa la direccion efectiva y la pone en el load o store buffer. Los loads en el load buffer se ejecutan tan pronto como la unidad de memoria esta disponible. Los stores en el store buffer esperan por el valor a ser guardado antes de enviarlo a la unidad de memoria.Para preservar el comportamiento de excepciones no se permite que se ejecute ninguna instrucción antes que todos los saltos que preceden dicha instrucción en el programa se hayan completado. Esto garantiza que las excepciones que se produzcan realmente se habrían producido durante la ejecución.

3. Write Result: cuando el resultado esta disponible, se lo escribe en el CDB y desde ahí a los registros y a las estaciones de reserva (incluyendo los store buffers) que esperan por ese resultado. Los stores también escriben datos a la memoria durante este paso, cuando ambos la dirección y los valores están disponibles son enviados a la unidad de memoria y se completa el store.

Se usan estructuras de datos atacadas a las ER, Load Buffer, Store Buffer para detectar y eliminar hazards. Estos tags son esencialmente nombres para un set extendido de registros virtuales usados en el renombrado. El tag field es de 4 bits que denota una de las cinco estaciones de reserva y uno de los seis load buffers. Esto es equivalente a tener 11 registros (la 360 tenia 4 por arquitectura). En un procesador con mas registros el renombrado provee un set de registros virtuales mas grande. El tag describe que estaciones de reserva contienen la instrucción que va a producir el resultado necesitado como operando.

Each reservation station has six fields:Op—The operation to perform on source operands S1 and S2.Qj, Qk—The reservation stations that will produce the corresponding sourceoperand; a value of zero indicates that the source operand is already availablein Vj or Vk, or is unnecessary. (The IBM 360/91 calls these SINKunit andSOURCEunit.)Vj, Vk—The value of the source operands. Note that only one of the V field orthe Q field is valid for each operand. For loads, the Vk field is used to the offsetfrom the instruction.A–used to hold information for the memory address calculation for a load orstore. Initially, the immediate field of the instruction is stored here; after the addresscalculation, the effective address is stored here.Busy—Indicates that this reservation station and its accompanying functionalunit are occupied.

The register file has a field, Qi:Qi—The number of the reservation station that contains the operation whoseresult should be stored into this register. If the value of Qi is blank (or 0), nocurrently active instruction is computing a result destined for this register,meaning that the value is simply the register contents.The load and store buffers each have a field, A, which holds the result of the effectiveaddress once the first step of execution has been completed.In the next section, we will first consider some examples that show how thesemechanisms work and then examine the detailed algorithm.