Tomasulo's algorithm

Tomasulo's algorithm is a computer architecture hardware algorithm for dynamic scheduling of instructions that allows out-of-order execution and enables more efficient use of multiple execution units. It was developed by Robert Tomasulo at IBM in 1967 and was first implemented in the IBM System/360 Model 91's floating-point unit.

The major innovations of Tomasulo's algorithm include register renaming in hardware, reservation stations for all execution units, and a common data bus (CDB) on which computed values broadcast to all reservation stations that may need them. These developments allow for improved parallel execution of instructions that would otherwise stall under the use of scoreboarding or other earlier algorithms.

Robert Tomasulo received the Eckert–Mauchly Award in 1997 for his work on the algorithm.

r empty Example of Tomasulo's algorithm

In the execute stage, the instruction operations are carried out. Instructions are delayed in this step until all of their operands are available, eliminating RAW hazards. Program correctness is maintained through effective address calculation to prevent hazards through memory.

• If one or more of the operands is not yet available then: wait for operand to become available on the CDB.
• When all operands are available, then: if the instruction is a load or store
  • Compute the effective address when the base register is available, and place it in the load/store buffer
    • 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

Pseudocode

Instruction state	Wait until	Action or bookkeeping
FP operation	r & CDB available	Mem[RS[r].A]←RS[r].Vk; RS[r].Busy←no;

The concepts of reservation stations, register renaming, and the common data bus in Tomasulo's algorithm presents significant advancements in the design of high-performance computers.

Reservation stations take on the responsibility of waiting for operands in the presence of data dependencies and other inconsistencies such as varying storage access time and circuit speeds, thus freeing up the functional units. This improvement overcomes long floating point delays and memory accesses. In particular the algorithm is more tolerant of cache misses. Additionally, programmers are freed from implementing optimized code. This is a result of the common data bus and reservation station working together to preserve dependencies as well as encouraging concurrency.

By tracking operands for instructions in the reservation stations and register renaming in hardware the algorithm minimizes read-after-write (RAW) and eliminates write-after-write (WAW) and Write-after-Read (WAR) computer architecture hazards. This improves performance by reducing wasted time that would otherwise be required for stalls.

An equally important improvement in the algorithm is the design is not limited to a specific pipeline structure. This improvement allows the algorithm to be more widely adopted by multiple-issue processors. Additionally, the algorithm is easily extended to enable branch speculation.

Tomasulo's algorithm was implemented in the System/360 Model 91 architecture. Outside of IBM, it went unused for several years. However, it saw a vast increase in usage during the 1990s for three reasons:

1. Once caches became commonplace, the algorithm's ability to maintain concurrency during unpredictable load times caused by cache misses became valuable in processors.
2. Dynamic scheduling and branch speculation from the algorithm enables improved performance as processors issued more and more instructions.
3. Proliferation of mass-market software meant that programmers would not want to compile for a specific pipeline structure. The algorithm can function with any pipeline architecture and thus software requires few architecture-specific modifications.

Many modern processors implement dynamic scheduling schemes that are variants of Tomasulo's original algorithm, including popular Intel x86-64 chips."Robert Tomasulo – Award Winner". ACM Awards. ACM. Retrieved 8 December 2014.

1 2 3 4 5 Intel 64 and IA-32 Architectures Software Developer's Manual (Report). Intel. September 2014. Retrieved 8 December 2014.

↑ Savard, John J. G. (2018) [2014]. "Pipelined and Out-of-Order Execution". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.

• Dynamic Scheduling - Tomasulo's Algorithm at the Wayback Machine(archived December 25, 2017)
• HASE Java applet simulation of the Tomasulo's algorithm