How Does Tomasulo's Algorithm Enable Out-of-Order Execution?

Robert Tomasulo's algorithm is a hardware scheduling technique developed in 1967 for the IBM System/360 Model 91 floating-point unit. It enables dynamic out-of-order execution by decoupling instruction issue from execution, using reservation stations to buffer operands and eliminate false data dependencies. Instead of stalling the entire pipeline when an instruction waits for data, the processor dispatches independent instructions to available functional units as soon as their operands are ready.

The Challenge of Data Dependencies

In a traditional in-order pipeline, instructions must wait if they depend on the result of a previous instruction. These dependencies fall into two categories:

  • True Data Dependencies (RAW - Read After Write): An instruction needs a value that a preceding instruction has not yet computed.
  • False Data Dependencies (WAR - Write After Read, and WAW - Write After Write): Two instructions use the same architectural register name, creating an artificial bottleneck even though no actual data flows between them.

Tomasulo's algorithm resolves false dependencies dynamically in hardware through implicit register renaming, while managing true dependencies by tracking data readiness rather than register names.

Core Components of Tomasulo's Architecture

To achieve dynamic scheduling, the algorithm relies on three primary hardware structures:

  1. Reservation Stations (RS): Buffers placed in front of each functional unit (such as adders or multipliers). Each reservation station holds an issued instruction, its operation code, and either the actual operand values or tags pointing to the reservation stations that will produce them.
  2. Register Status Table (Register Result Status): A table that tracks which reservation station, if any, will write the next value to each architectural register.
  3. Common Data Bus (CDB): A broadcast bus that connects the outputs of all functional units back to the reservation stations and the register file.

The Three Stages of Execution

Instructions flow through three main stages in Tomasulo's algorithm:

1. Issue

The instruction is fetched from the instruction queue in program order. If a reservation station for the required functional unit is available, the instruction is issued to it. The hardware checks the Register Status Table for each source operand:

  • If the operand is already available in the register file, its value is copied directly into the reservation station.
  • If the operand is still being computed by another instruction, the reservation station stores a tag identifying the producer's reservation station instead of a value.

Finally, the Register Status Table is updated so that the destination register points to the newly allocated reservation station. This step performs register renaming, eliminating WAR and WAW hazards because subsequent instructions will reference the tag rather than the architectural register.

2. Execute

An instruction in a reservation station waits until all of its source operands are available. It monitors the Common Data Bus for matching tags. Once all operands are present and the functional unit is free, the instruction begins execution. Because multiple reservation stations can hold independent instructions, a later instruction whose operands are ready can execute before an earlier instruction that is still waiting, achieving out-of-order execution.

3. Write Result

When a functional unit finishes computing a result, it broadcasts the value along with its reservation station tag onto the Common Data Bus. All reservation stations waiting for that tag—as well as the corresponding architectural register if it still points to that tag—capture the value simultaneously. The reservation station is then marked free for future instructions.

Why It Matters

By combining reservation stations with the Common Data Bus, Tomasulo's algorithm transforms a static sequence of instructions into a dynamic dataflow graph at runtime. If an instruction has a latency of \(L\) cycles, independent instructions behind it do not have to wait \(L\) cycles to begin their work. This approach laid the foundation for modern superscalar processors, which still rely on reservation stations, register renaming, and out-of-order execution to maximize instruction-level parallelism.