True dependences you must respect, false ones you can dissolve
From the previous guide you know the goal of out-of-order execution is to run whichever instruction has its data ready, while still producing results in program order. The thing standing in the way is dependences — but not all dependences are equal. A true dependence is a real flow of data: one instruction writes a value that a later instruction reads. That is a read-after-write dependence, and no amount of cleverness lets you read a value before it has been produced. True dependences are sacred; you must wait.
But look at this little RISC-V-ish sequence. The two halves have nothing to do with each other — yet they fight over the name x1. Instruction 2 reads x1 (true dependence on 1, fine), but instruction 3 wants to write x1 again, and it cannot do so until instruction 2 has finished reading the old x1. That stall has nothing to do with data flowing; it is purely a clash over a register name. This is a false dependence — the compiler simply ran out of architectural register names and reused one.
1: add x1, x2, x3 ; x1 = x2 + x3 (writes x1) 2: mul x4, x1, x5 ; x4 = x1 * x5 (TRUE dep on 1 via x1) 3: add x1, x6, x7 ; x1 = x6 + x7 (wants to reuse the NAME x1) 4: sub x8, x1, x9 ; x8 = x1 - x9 (true dep on 3, not on 1) Instr 3 & 4 are an independent computation -- only the recycled name 'x1' chains them artificially behind 1 & 2.
Here is the key insight that unlocks everything: false dependences are an accident of naming, not of computation. If instructions 3 and 4 used a different register for their x1, the two computations could run in parallel. We cannot change the program — the architectural register x1 is fixed by the ISA contract. But the hardware has far more physical registers hiding inside than the ISA exposes. So let it quietly hand out fresh physical names. That trick is register renaming.
Register renaming: give every writer its own fresh name
Register renaming keeps a private pool of physical registers — say 128 of them — far larger than the 32 architectural names the programmer sees. The hardware also keeps a small map table: 'right now, architectural x1 lives in physical register p37'. Every time an instruction writes a register, renaming allocates a brand-new physical register and updates the map. Every time an instruction reads a register, it looks up the map to find which physical register currently holds that value.
Watch what happens to our example. Instruction 1 writes x1, so it gets p37; the map now says x1 = p37. Instruction 2 reads x1, looks it up, and depends on p37 — true dependence preserved, exactly as it should be. Then instruction 3 writes x1 again, but renaming gives it a fresh register p52 and updates the map to x1 = p52. Instruction 4 reads x1, finds p52, and depends only on instruction 3. The false chain between the two computations has vanished: instructions 1-2 work on p37 while 3-4 work on p52, completely in parallel. We did not delete a single instruction — we just stopped letting them collide over a name.
Reservation stations: a waiting room where data, not order, decides
Renaming removes false dependences, but instructions still must wait for their true inputs. Where do they wait? Not in a strict queue — that would force order back on us. Instead each functional unit (the ALU, the FPU, the load/store unit) is fronted by a few reservation stations: small slots that hold a waiting instruction along with its operands. Recall the kitchen analogy from the previous guide — a reservation station is a prep counter holding one order's ticket, slowly filling its bowls as ingredients arrive, ready to cook the instant the last one lands.
Each slot in a reservation station holds, for each operand, either the value itself (if it is already known) or the name of the physical register that will eventually produce it (a 'tag'). An instruction sits in its station until both operands have real values, then it 'fires' — it is sent to the functional unit to execute. Because firing is triggered by data readiness, not by program position, an instruction deep in the program can leap ahead of an earlier one that is still stalled waiting on a slow memory load. This data-driven firing is the heart of dynamic scheduling.
Tomasulo's algorithm: tags, a common data bus, and a quiet broadcast
Tie renaming and reservation stations together and you get Tomasulo's algorithm, designed by Robert Tomasulo for the IBM 360/91 in 1967 and still the conceptual core of out-of-order cores today. Its genius is how a finished result reaches everyone who is waiting for it. When a functional unit produces a value, it does not write it to one place and let stalled instructions poll for it. Instead it broadcasts the value and its tag on a shared wire called the common data bus. Every reservation station listens at once; any slot waiting on that tag grabs the value in the same cycle.
- Issue (in order): take the next instruction, rename its destination to a fresh physical register, and place it in a free reservation station — copying in any operands already available, or recording the tag of the producer for those not yet ready.
- Wait and snoop: the instruction sits in its station, watching the common data bus. Each cycle, if a broadcast tag matches a tag it is waiting on, it captures that value into its slot.
- Execute (out of order): once both operands hold real values and the functional unit is free, the instruction fires and computes — regardless of where it sat in the program.
- Write result: broadcast the value plus its tag on the common data bus, so every waiting reservation station — and the register file — can pick it up in one shot.
What this buys you, and what it honestly does not
Put it all together and a stalled load no longer freezes the whole machine. While one instruction waits on memory, renaming and reservation stations let independent work behind it stream through the functional units, raising the superscalar core's real instruction-level parallelism well above what a simple in-order pipeline with forwarding alone could reach. The hardware is, in effect, re-scheduling your program on the fly, every cycle, using information the compiler never had — the actual run-time latencies of each operation.
Be honest about the price, though. All this machinery — the rename map, the wide common data bus that every station must snoop, the associative comparisons, the reorder buffer — costs transistors, area, and a lot of power, and it grows worse than linearly as you widen the window. It also does nothing for a long true dependence chain: if every instruction needs the previous one's result, there is simply no parallelism to find, and the cleverest out-of-order engine runs no faster than an in-order one. As the final guide explains, these diminishing returns and rising power are exactly the limits of ILP that pushed the industry toward multicore.