Tomasulo's Algorithm and Register Renaming

In 1967, an IBM engineer named Robert Tomasulo designed the floating-point unit of the IBM System/360 Model 91 and, almost as a side effect, invented the algorithm that every high-performance processor on Earth still uses today. It takes scoreboarding and fixes its two great weaknesses: it forwards results directly to whoever is waiting for them (no detour through the register file), and it makes the false WAR and WAW hazards disappear entirely through a trick called register renaming.

The magic is that Tomasulo stopped thinking about instructions as waiting on registers, and made them wait on values-in-transit instead. Each pending result gets a unique tag; an instruction that needs it simply parks with that tag and springs to life the moment a value carrying that tag appears on a shared broadcast wire. Registers, it turns out, were never the real dependency — they were just names.

The two false dependences, and why names cause them

A machine has only a handful of architectural register names — F0, F2, F4, \dots The compiler reuses them constantly. Watch what reuse does:

DIV.D F0, F2, F4 ; (i) writes F0 -- slow ADD.D F6, F0, F8 ; (j) reads F0 -- RAW on F0 (a TRUE dependence) S.D F6, 0(R1) ; (k) reads F6 SUB.D F8, F10, F12 ; (l) writes F8 -- but (j) still needs the OLD F8! => WAR MUL.D F6, F13, F14 ; (m) writes F6 -- but (j) also writes F6 => WAW

Instruction (l) wants to overwrite F8 before (j) has read it — a WAR hazard. Instruction (m) writes F6, which (j) also writes — a WAW hazard. Neither is a real flow of data. They exist only because the compiler ran out of register names and recycled F6 and F8. If every write got a fresh name, both hazards would evaporate.

Register renaming: give every result a fresh home

Register renaming separates the architectural register a program names from the physical storage that actually holds the value. Every time an instruction writes a register, the hardware allocates it a brand-new physical location (in Tomasulo's design, the tag of a reservation station; in modern chips, a physical register from a large pool). Subsequent readers are pointed at the specific physical location that holds the value they want.

maps each architectural-register write to a fresh physical location, so no two live values ever share a name;
with unique names, WAR and WAW hazards cannot occur — they were only ever conflicts over reused names;
RAW (true) dependences remain and are honoured: a reader waits for the exact physical value it needs;
it exposes far more instruction-level parallelism than the compiler's limited register names allowed.

Below, a tiny renamer maps architectural names to a growing pool of physical names. Watch a reused name like F6 get two different physical homes — that is the WAW hazard being dissolved, not stalled.

// Minimal register renamer: architectural regs -> physical regs via a map table. // Every WRITE allocates a fresh physical register; reads look up the current mapping. type Prog = { op: string; dst: string; src: string[] }[]; const prog: Prog = [ { op: "DIV.D", dst: "F0", src: ["F2", "F4"] }, { op: "ADD.D", dst: "F6", src: ["F0", "F8"] }, { op: "SUB.D", dst: "F8", src: ["F10", "F12"] }, // was a WAR on F8 { op: "MUL.D", dst: "F6", src: ["F13", "F14"] }, // was a WAW on F6 ]; const map: Record<string, string> = {}; // arch -> current physical name let next = 0; const phys = (arch: string) => map[arch] ?? arch; // unmapped = its initial value for (const ins of prog) { const srcs = ins.src.map(phys); // read: resolve to physical names const p = `p${next++}`; // write: allocate a FRESH physical reg map[ins.dst] = p; console.log(`${ins.op} ${ins.dst}->${p} = f(${srcs.join(", ")})`); } console.log("Note: F6 got two different physical homes -> the WAW dependence is GONE.");

Reservation stations and the common data bus

Tomasulo's hardware has two new pieces. In front of each functional unit sit several reservation stations — little buffers that hold an instruction plus its operands (or, if an operand isn't ready, the tag it is waiting for). Threading through the whole machine is the common data bus (CDB): when any unit finishes, it broadcasts (tag, value) on the CDB, and every reservation station and register listening for that tag grabs the value in the same cycle. This is tag-based wakeup, and it is why results forward instantly.

The life of an instruction, Tomasulo-style

Each instruction moves through three steps:

Step	What happens
1. Issue	Take the next instruction (in order). If a reservation station is free, allocate it. For each source operand: if its value is ready, copy it in; otherwise record the tag of the station that will produce it. Rename the destination by making the register point at this station's tag. (No free station ⇒ stall — a structural hazard.)
2. Execute	When both operands have arrived (all tags resolved), and the functional unit is free, compute. Waiting on a tag is the RAW dependence — enforced naturally, with no separate hazard check.
3. Write result	Broadcast (tag, value) on the CDB. Every waiting station and every register whose tag matches captures it simultaneously, and the station frees up.

There is no separate "read operands" stall and no WAR/WAW checking anywhere — renaming has made those hazards impossible, so the hardware never has to look for them. The only stalls left are the honest ones: a true RAW dependence (wait for the tag) or a structural one (no free station or unit).

They fight — and the CDB is a genuine bottleneck. In Tomasulo's original design there is a single common data bus, so if two functional units complete simultaneously, only one may broadcast; the other waits a cycle. This is why modern superscalar processors have multiple result buses (and multiple CDBs), and why the tag-match logic — every station comparing its stored tag against the broadcast tag every cycle — is one of the most timing-critical, power-hungry circuits on the chip. The elegant idea of "broadcast to everyone" gets expensive fast as you widen the machine, a theme that returns when we count the quadratic cost of wide superscalar issue.

A tempting overstatement: "renaming makes all dependences go away, so everything runs in parallel." No. Renaming abolishes WAR and WAW, which were never real — they were name collisions. A RAW dependence is a genuine flow of a value from producer to consumer, and no amount of renaming can let the consumer run before the value exists. In Tomasulo the RAW dependence is simply re-expressed as "wait for this tag on the CDB." If a chain of instructions each depends on the last (a \to b \to c \to d), renaming buys you nothing — the chain is inherently serial. That hard floor is the subject of the final lesson, the limits of ILP.

Why it still matters

Tomasulo's 1967 design is the direct ancestor of the out-of-order engine in your phone and laptop. Modern chips rename onto a pool of a few hundred physical registers (an Apple or AMD core has far more physical than architectural registers precisely to expose more parallelism), forward results over several buses, and add a reorder buffer to keep exceptions precise. But the two core ideas — rename to kill false dependences, and broadcast results by tag — are pure Tomasulo. It is one of the most durable ideas in all of computer engineering.