Tomasulo's algorithm: Difference between revisions

Revision as of 07:07, 27 February 2013

Revision as of 21:33, 14 May 2013

Line 1:

The '''Tomasulo algorithm''' is a hardware [[algorithm]] developed in 1967 by [[Robert Tomasulo]] from [[IBM]]. It allows sequential instructions that would normally be stalled due to certain dependencies to execute non-sequentially ([[out-of-order execution]]). It was first implemented for the [[IBM System/360]] [[Model 91’s91]]’s [[floating point unit]].

This algorithm differs from [[scoreboarding]] in that it utilizes [[register renaming]]. Where scoreboarding resolves [[Write-after-Write]] (WAW), [[Read-after-Write]] (RAW) and [[Write -after -Read]] (WAR) [[Hazardcomputer architecture]] [[hazard (computer architecture)|hazardshazard]]s by [[stalling (computer architecture)|stalling]], register renaming allows the continual issuing of instructions. The Tomasulo algorithm also uses a [[common data bus]] (CDB) on which computed values are broadcast to all the [[reservation stations]] that may need it. This allows for improved [[parallel execution]] of instructions which may otherwise stall under the use of scoreboarding.

Robert Tomasulo received the [[Eckert-Mauchly Award]] in 1997 for this algorithm.

Line 8:

The following are the concepts necessary to the implementation of Tomasulo's Algorithm.

*Instructions are issued sequentially so that the effects of a sequence of instructions such as exceptions[[exception (computing)|exception]]s raised by these instructions occur in the same order as they would on an in-order processor, regardless of the fact that they are being executed out-of-order (i.e. non-sequentially).

*All general-purpose and [[Reservation_stations|reservation station]] registers hold either real or virtual values. If a real value is unavailable to a destination register during the issue stage, a virtual value is initially used. The functional unit that is computing the real value is assigned as the virtual value. The [[virtual register]] values are converted to real values as soon as the designated [[functional unit]] completes its computation.

*Functional units use [[reservation stations]] with multiple slots. Each slot holds information needed to execute a single instruction, including the operation and the operands. The functional unit begins processing when it is free and when all source operands needed for an instruction are real.

Line 34:

***If the instruction is a load then: execute as soon as the memory unit is available

***Else, if the instruction is a store then: wait for the value to be stored before sending it to the memory unit

*Else, the instruction is an [[arithmetic logic unit]] (ALU) operation then: execute the instruction at the corresponding functional unit

===Stage 3: write result===