Why a superscalar core still stalls
In the previous guide we gave the core more lanes: a superscalar machine can fetch, decode, and start several instructions in the very same clock cycle, chasing more instruction-level parallelism from one stream. But widening the road does nothing if the cars must still depart in strict program order. The moment the next instruction in line is waiting on a result that is not ready — a slow cache miss, say, or a multiply still grinding away — every instruction behind it is stuck too, even the ones that could have run immediately. An in-order machine is a single-file queue: one slow customer at the front freezes everyone.
Picture a kitchen taking tickets in order. Ticket 1 needs an ingredient still on the delivery truck; tickets 2 and 3 have everything on the counter already. An in-order cook stands frozen at ticket 1, hands idle, while two easy dishes wait. The fix is obvious to any real cook: start whichever order is ready, and keep the finished plates aside until it is each one's turn to go out. That single idea — run early, plate in order — is out-of-order execution, and it is what every high-performance CPU has done since the 1990s.
True dependences you must obey, false ones you can dodge
You cannot simply run instructions in any order you like — some genuinely depend on others. The honest one is the read-after-write dependence (RAW), the same data hazard you met in the pipeline rung: if instruction A computes a value into a register and instruction B reads that register, then B truly must wait for A. The value does not exist until A produces it. This is a real arrow in the data flow, and no clever hardware may break it — doing so would change the program's answer.
But there is a second, sneakier kind that only looks like a dependence — a false dependence. Suppose two unrelated computations both happen to use register x5 as scratch space. They share no data; the compiler just ran out of register names and reused one. Yet a naive machine sees both touching x5 and refuses to reorder them, as if there were a real arrow. This is a write-after-write or write-after-read conflict: a naming collision, not a data flow. It is the cook insisting two different dishes cannot be plated at once merely because both were written on the same scrap of paper.
true (RAW) dependence -- you MUST wait:
i1: add x1, x2, x3 ; x1 <- x2 + x3
i2: sub x4, x1, x5 ; reads x1 -> needs i1's result
false dependence (WAW / name reuse) -- only an illusion:
i3: mul x6, x7, x8 ; uses x6 as scratch
i4: add x6, x9, x10 ; reuses the NAME x6, no shared data
rename i4's x6 to a fresh slot -> the false arrow vanishes,
i3 and i4 may now run in parallel.Here is the lovely trick: false dependences can be dissolved. Because they come from a shortage of register names, not a shortage of values, the hardware can quietly hand the second user a different physical storage slot. That is register renaming, the subject of the very next guide — it is the single mechanism that frees out-of-order machines from the program's accidental name clashes. For now, just hold the distinction: obey true dependences, erase false ones.
The window, the reservation stations, and wakeup
How does the core actually find the ready instructions? It keeps a pool of decoded instructions in flight — call it the instruction window — and lets any of them fire the moment its operands arrive. The classic structure that holds a waiting instruction is a reservation station: a little holding bay that remembers the operation, latches whichever operands are already available, and waits, watching, for the rest. When a result is finally produced on the broadcast lines, every station waiting on that value wakes up, grabs it, and becomes ready to execute.
This whole dance — rename, sit in a reservation station, wake on a broadcast, then execute — is the heart of Tomasulo's algorithm, designed at IBM in 1967 and still the skeleton of every out-of-order core today. We unpack its full mechanics in guide 3; here the picture to carry away is simply a crowd of instructions all sitting in their bays, each one firing independently the instant its last operand lands, in whatever order that happens to be. The kitchen has many cooks, and each starts the moment their ingredients are on the counter.
The size of the instruction window sets how far ahead the core can look for ready work. A bigger window can leap over a long cache miss, finding independent instructions deep in the stream to keep the execution units busy. But the window is expensive: every cycle it must compare every waiting station against every result. That quadratic-ish cost is one of the walls we hit in guide 5, when we ask why ILP stopped growing and multicore took over.
Plating in order: the reorder buffer and in-order commit
Now the crucial promise. If instructions finish out of order, why does the program still behave exactly as written? Because finishing is not the same as becoming permanent. Each instruction, when it executes, writes its result into a private staging area, not yet into the official program-visible state. A structure called the reorder buffer holds these finished-but-not-yet-official results in the original program order — a row of trays, one per in-flight instruction, lined up in the sequence the orders were taken.
Results leave the reorder buffer and become real strictly from the front, oldest first — this is in-order commit (also called retirement). An instruction may have finished computing many cycles ago, but it only commits — only updates the architectural registers and memory the rest of the world can see — when it reaches the head of the buffer and every instruction before it has already committed. The kitchen plates each finished dish onto the pass, but the waiter carries them out strictly in ticket order. Diners never see the scramble in the back.
- Issue (in order): decode each instruction, rename its registers to erase false dependences, and slot it into a reservation station and a reorder-buffer entry — all in strict program order.
- Execute (out of order): an instruction fires the moment its operands are ready, regardless of its program position; the broadcast of its result wakes whoever was waiting on it.
- Write result: the finished value is parked in the reorder-buffer entry and forwarded to waiting stations, but it is still invisible to the architectural state.
- Commit (in order): when an instruction reaches the head of the reorder buffer, its result is written into the real registers/memory and it retires; the world sees results purely in original order.
Why in-order commit is worth the trouble
Committing in order is not just for tidiness — it buys two priceless guarantees. The first is precise exceptions. If instruction 5 divides by zero, the machine must report the fault as if execution had stopped cleanly at 5, with instructions 1 through 4 done and 6 onward untouched. Because nothing past the reorder-buffer head has committed, the hardware just throws away every uncommitted entry behind the faulting one and the architectural state looks exactly as if it had run one at a time. Out-of-order execution stays completely invisible to the programmer.
The second is what makes the next two guides possible: speculation. Because results sit in the reorder buffer until commit, the core can run far ahead past a branch it has only guessed the outcome of — speculative execution — and if the guess was wrong, simply discard those uncommitted results and pretend they never ran. In-order commit is the eraser that makes guessing safe. The deep machinery of branch prediction — two-bit, correlating, and tournament predictors, the branch target buffer — is guide 4's whole story.