Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 67 ยท CPU Design

Dynamic Scheduling: Scoreboarding and Tomasulo's Algorithm

Learn how hardware reorders instructions at run time: scoreboarding, Tomasulo's reservation stations, register renaming and the common data bus, with a Python simulator.

A pipeline that issues instructions strictly in order stalls whenever one instruction waits for a slow result, even if the next instruction has nothing to do with it. Dynamic scheduling lets the hardware run instructions in whatever order their data becomes ready, while keeping the program's meaning. Two classic designs introduced the idea: the scoreboard (CDC 6600, 1964) and Tomasulo's algorithm (IBM 360/91, 1967).

This lesson explains the three kinds of data hazard those designs must respect, how a scoreboard and Tomasulo's reservation stations handle them, and then runs a cycle-by-cycle simulation. It deepens the overview in advanced CPU techniques and builds on pipeline hazards.

Three kinds of data dependence

Two instructions that touch the same register can interfere:

Name Pattern Meaning
RAW (read after write) I1 writes R, I2 reads R True dependence: I2 needs the value, so it must wait
WAR (write after read) I1 reads R, I2 writes R Anti-dependence: only a name clash, I2 must not overwrite R too early
WAW (write after write) I1 writes R, I2 writes R Output dependence: only a name clash, the later write must win

Only RAW is a real flow of data. WAR and WAW arise because a small number of register names are reused. If the hardware gave each result a fresh name, only the true dependences would remain.

Scoreboarding

A scoreboard is a table that tracks, for every instruction, which stage it is in, and for every functional unit and register, who uses it. An instruction is issued in order, but then waits in its unit until:

  • its source operands are ready (RAW), and
  • it is safe to write its destination: no earlier instruction still has to read the old value (WAR).

It also refuses to issue if the destination register is already pending in another unit (WAW), or if no functional unit is free (structural hazard). Instructions can execute and finish out of order, but the scoreboard stalls on WAR and WAW. It has no renaming, so it can never hide those name clashes.

Tomasulo's algorithm

Tomasulo added three ideas that remove the name clashes:

  1. Reservation stations. Each functional unit has a few buffers in front of it. An issued instruction goes to a free station and copies the operand values it already has (instead of pointing at registers).
  2. Register renaming through tags. If an operand is not ready, the station stores a tag: the name of the station that will produce it. The register status table records, for each register, the tag of the latest instruction that will write it.
  3. The common data bus (CDB). When a result is ready, it is broadcast with its tag. Every station waiting for that tag grabs the value at the same moment, and the register file writes it if the tag is still the latest.
flowchart LR
  IQ["Instruction queue<br/>in order"] --> RS1["Reservation stations<br/>adders"]
  IQ --> RS2["Reservation stations<br/>multipliers"]
  RS1 --> FU1["Adder units"]
  RS2 --> FU2["Multiplier units"]
  FU1 -->|"result + tag"| CDB(("Common data bus"))
  FU2 -->|"result + tag"| CDB
  CDB --> RS1
  CDB --> RS2
  CDB --> REG["Register file<br/>+ status table"]

Results travel on the CDB with a tag; waiting stations and the register file snoop it.

Renaming happens at issue time: because the operand value or tag is copied into the station, a later instruction that writes the same register cannot disturb it (WAR gone), and the register status table points to the newest writer so the older result is not written back over it (WAW gone). Only true RAW dependences make an instruction wait.

For each instruction the algorithm has three steps:

  1. Issue (in order): take a free station, capture ready operands or tags, set the destination's tag in the status table. Stall if no station is free.
  2. Execute: when all operands are present, the unit starts. Different units run in parallel.
  3. Write result: broadcast on the CDB (one per cycle), free the station.

Tomasulo's original design completes instructions out of order, so exceptions are imprecise. Modern processors add a reorder buffer so that results commit in program order, as described in advanced CPU techniques.

A simulator you can run

The simulator below models Tomasulo's algorithm with these assumptions: one instruction is issued per cycle, three reservation stations per unit type, one CDB write per cycle (oldest first), latencies ADD/SUB = 2 and MUL = 4 cycles, and a consumer may start the cycle after its operand is broadcast.

Python Tomasulo's algorithm, cycle by cycle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Study the table. Instruction 2 must wait for instruction 1's multiply (a true RAW), but instructions 3 and 4 do not wait for anything: instruction 3 reads and writes F8 and instruction 4 writes F0, even though instruction 1 also writes F0. Renaming means the WAW and WAR clashes cost nothing. Instruction 5 finally waits for both producers.

When instruction 1 broadcasts its result (cycle 6), the status table says that instruction 4 is now the latest writer of F0, so instruction 1 does not update the register file. Instruction 4 writes F0 in cycle 8, and its value is the one that stays. Instruction 1 result would still reach any station that was waiting for its tag.

Scoreboard versus Tomasulo

Feature Scoreboard Tomasulo
Renaming none tags and reservation stations
WAR/WAW stall eliminated
Operand routing through registers CDB broadcast to stations and registers
Control central table distributed in each station
Bottleneck few registers, stalls one CDB

Modern out-of-order cores keep Tomasulo's spirit (renaming, wakeup by broadcast, issue queues) but use a physical register file and a reorder buffer for in-order commit.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which data hazard is a true dependence that no renaming can remove?

    In RAW the second instruction really needs the value the first produces; WAR and WAW are only name clashes.
  2. 2. What does a scoreboard do when a later instruction writes a register that an earlier, still-waiting instruction has yet to read?

    A scoreboard has no renaming, so it must delay the write to avoid a WAR hazard.
  3. 3. What does a reservation station copy when an instruction is issued?

    Capturing values or tags is what renames the operands.
  4. 4. What is the role of the common data bus (CDB)?

    All waiting stations compare the tag and grab the value at the same time.
  5. 5. Why do modern processors add a reorder buffer to Tomasulo's scheme?

    Out-of-order completion makes exceptions imprecise; in-order commit through a reorder buffer restores precise state.

Summary

  • RAW is a true dependence; WAR and WAW are name dependences caused by reusing register names.
  • A scoreboard allows out-of-order execution but stalls on WAR and WAW hazards.
  • Tomasulo's algorithm uses reservation stations, tags and a common data bus to rename operands, so only RAW dependences cause waiting.
  • Issue is in order; execution and result broadcast follow data readiness.
  • Modern out-of-order CPUs add a reorder buffer for precise exceptions and in-order commit.

Continue with the next chapter, The Memory Hierarchy.