Tomasulo's algorithm

Tomasulo's algorithm allows execution of instructions in data-flow order, rather than sequential order. This can increase the throughput of the unit, by avoiding pipeline stalls. Each pending instruction is held in a ``reservation station'' until the values of its operands become available, then issued ``out-of-order''.

The flow of instructions is pictured in figure 2. Each instruction, as it arrives,

Figure 2: Flow of instructions in Tomasulo's algorithm

fetches its operands from a special register file. Each register in this file holds either an actual value, or a ``tag'' indicating the reservation station that will produce the register value when it completes. The instruction and its operands (either values or tags) are stored in a reservation station (RS). The RS watches the results returning from the execution pipelines, and when a result's tag matches one of its operands, it records the value in place of the tag. When the station has the values of both of its operands, it may issue its instruction to an execution pipeline. When the tagged result returns from the pipeline, the RS is cleared, and the result value, if needed, is stored in the destination register. However, if a subsequent instruction has modified the register tag, the result is discarded. This is because its value in a sequential execution would be overwritten.

In addition to an ALU instruction, we include instructions that read register values to an external output and write values from an external input. There is also a ``stall'' output, indicating that an instruction cannot be received either because there is no available RS to store it, or because the value of the register to be read to an output is not yet available.