Tomasulo's Algorithm: Dynamic Scheduling with Reservation Stations

The problem: false dependencies stall real parallelism

A pipelined machine wants to keep many instructions in flight, but hazards get in the way. There are three kinds of data hazard:

• RAW (read-after-write) — a true dependence: an instruction needs a value another must produce first. This is fundamental and cannot be removed.
• WAR (write-after-read) — a false/name dependence: a later write to a register must wait only because an earlier instruction still needs the old value.
• WAW (write-after-write) — another name dependence: two writes to the same register must retire in order so the final value is correct.

WAR and WAW arise purely from reusing register names, not from actual data flow. With only a handful of architectural registers (the 360 had 4 floating-point registers), compilers reuse names constantly, so these false hazards are everywhere. An in-order machine or a scoreboard stalls on them. Tomasulo's key realization: if the hardware gives each in-flight result a fresh tag and tracks operands by tag, the register name stops mattering — the false dependencies simply vanish, exposing far more instruction-level parallelism from the same binary.

How it works: reservation stations, tags, and the CDB

Each functional unit (adders, multipliers, load/store) has a small set of reservation stations (RS). Each RS entry holds: Op (operation), Vj, Vk (operand values once known), Qj, Qk (the tag of the RS that will produce each not-yet-ready operand), A (address for loads/stores), and Busy. A Register Status table maps each architectural register to the tag of the RS that will write it (the renaming step). Instructions flow through three stages:

1. Issue / Dispatch (in program order): grab a free RS on the right unit; for each operand, copy its value if available, else record the producing tag in Q. Set the destination register's status to this RS's tag — this renames the register. If no RS is free, stall (structural hazard).
2. Execute: when both operands are ready (Qj=Qk=0), the unit runs. Waiting stations monitor the CDB. Loads/stores compute an address and respect memory ordering.
3. Write Result: broadcast {tag, value} on the Common Data Bus. Every RS with a matching Qj or Qk captures the value and clears the tag; the register file updates if its status still names this tag; the RS frees.

The CDB broadcast is the renaming resolution: a result reaches all consumers by tag, never touching an intermediate register name.

Complexity and a worked step trace

Per cycle the machine issues O(1) instructions (one, or a few in superscalar variants). The dominant cost is the CDB match: each broadcast must compare its tag against the Q fields of every RS. With R reservation stations and B CDB result buses, that is O(R x B) tag comparators — the wakeup/select logic that limits how wide and fast real designs can go. Storage is O(R) RS entries plus O(number of registers) status bits.

Trace this sequence (assume MUL = 4 cycles, ADD/SUB = 2), showing how renaming lets the SUB run early:

I1: MUL  F0 = F2 * F4     ; slow producer\nI2: ADD  F6 = F0 + F8     ; RAW on F0 -> must wait for I1\nI3: SUB  F8 = F10 - F12   ; WAR on F8 with I2\n\nIssue I1 -> RS Mult1; Status[F0]=Mult1\nIssue I2 -> RS Add1; Qj=Mult1 (F0 pending), Vk=F8; Status[F6]=Add1\nIssue I3 -> RS Add2; Vj=F10, Vk=F12; Status[F8]=Add2\n   (I2 already captured F8's VALUE at issue, so I3 rewriting F8\n    creates NO stall -> WAR hazard eliminated by renaming)\nI3 executes immediately (operands ready) -> CDB {Add2, val}\nI1 finishes -> CDB {Mult1, prod}; Add1 grabs it, Qj=0\nI2 now executes -> CDB {Add1, sum}

I3 completed before I2 despite the F8 name clash — exactly the parallelism a stall-based machine would forfeit.

Where it lives in real systems

Tomasulo's ideas are not a historical curiosity — they are the backbone of virtually every high-performance CPU shipped today:

• x86 out-of-order cores — from the Intel P6 (Pentium Pro, 1995) through modern Core, and AMD's K-series through Zen 5, all use reservation-station-style schedulers (unified or per-port) plus register renaming into a large physical register file.
• Arm / Apple silicon — Apple's M-series and high-end Arm Cortex-X cores implement very wide (8+ decode) out-of-order engines built on the same dynamic-scheduling foundation.
• Reorder Buffer (ROB) extension — real machines pair Tomasulo scheduling with a ROB so instructions commit in program order, giving precise exceptions and enabling speculative execution past branches (the original 360/91 lacked precise interrupts).

The vocabulary you meet in modern microarchitecture — the scheduler, wakeup/select, the physical register file, in-order retirement — descends directly from reservation stations, the CDB, and the register-status renaming table Tomasulo defined in 1967.

Comparison to scoreboarding and the tradeoff

The natural rival is the CDC 6600 scoreboard (Thornton, 1964). Both allow out-of-order execution, but they handle name dependencies differently:

• Scoreboard: no renaming. A centralized scoreboard tracks which units are busy and which registers are pending, and it stalls instructions to avoid WAR (delay write-back) and WAW (delay issue). It cannot forward results directly between units — values round-trip through the register file.
• Tomasulo: renaming + broadcast. Reservation stations buffer operands and tags, so WAR/WAW disappear rather than being avoided by stalling, and results forward straight to consumers over the CDB, cutting a register-file latency out of the critical path.

The tradeoff is complexity and scalability. Tomasulo needs associative tag matching across every RS on each broadcast — the O(R x B) comparator array is power-hungry and clock-limiting, which is why designs cap the number of reservation stations, split the CDB, or move to physical-register-file renaming. A scoreboard is cheaper and simpler but leaves parallelism on the table. Modern CPUs choose Tomasulo's richer scheme and pay the hardware bill.

Pitfalls, failure modes, and significance

Pitfalls and limits:

• No precise exceptions in the pure form. Because instructions complete out of order, an exception or misprediction can't cleanly roll back to a well-defined state. This is the reason real machines bolt on a reorder buffer for in-order commit.
• Single CDB is a bottleneck. Only one result can broadcast per bus per cycle; if many units finish together they contend. Wide superscalars need multiple result buses, multiplying the comparator cost.
• Memory disambiguation. Loads and stores can't freely reorder — the hardware must respect RAW/WAR/WAW through memory via load/store queues and address comparison, a subtlety beyond the register logic.
• Structural stalls. Run out of free reservation stations and issue halts, so RS depth must match the parallelism you hope to exploit.

Significance: Tomasulo showed that hardware can extract parallelism from unmodified, register-poor binaries at run time, adapting to actual latencies rather than compile-time guesses. Dormant while machines stayed simple, the idea roared back with 1990s superscalars and now underpins essentially all mainstream performance CPUs — one of the most influential ideas in computer architecture.

Tomasulo vs. related instruction-scheduling schemes

Scheme	Renaming	Removes WAR/WAW?	Distributed hazard tracking?	Notes
In-order pipeline (stall)	None	No	N/A	Simple; stalls whole pipeline on any dependence
CDC 6600 Scoreboard (1964)	No	No (stalls to avoid them)	Centralized scoreboard	Allows OoO but stalls on WAR/WAW; no renaming
Tomasulo (1967)	Yes (RS tags)	Yes	Distributed (reservation stations + CDB)	OoO issue; results broadcast; original had no precise exceptions
Tomasulo + Reorder Buffer	Yes (ROB entries)	Yes	Distributed + in-order commit	Adds precise exceptions & speculation; modern standard