Out-of-order execution: Visual walkthrough — Hardware deep dive

Everything below starts from one honest question: why does a computer ever sit idle?

Step 1 — What "in program order" even means

WHAT. A program is a list of tiny commands. Each command reads some boxes, computes, and writes a box. We call each box a register — think of it as a labelled cubby-hole that holds one number. R1, R2, ... are register names.

We write one command like this:

$destination cubby R 1 = first input R 2 + second input R 3$

Read left to right: "take the number in cubby R2, add the number in cubby R3, put the answer in cubby R1."

WHY start here. Every later idea — dependencies, renaming, reordering — is just a statement about which command needs which cubby. If we don't pin down cubbies first, nothing else is meaningful.

PICTURE. The figure shows four cubbies and one instruction reaching into two of them (red = the destination being written).

Step 2 — The stall: why a naive CPU wastes time

WHAT. Different instructions take different amounts of time. A register add finishes in 1 cycle (one tick of the clock). A LOAD — fetching a number from far-away memory — can take 3 or more cycles. A cycle is just one heartbeat of the processor.

A CPU that runs instructions strictly in the written order must finish instruction $k$ before it starts instruction $k + 1$ . So a slow LOAD freezes everyone behind it — even people who don't need its result. That freeze is a stall.

WHY this matters. The whole point of out-of-order execution is to delete these unnecessary stalls. We must see the enemy before we fight it.

PICTURE. A timeline (cycles left→right). The red block is a 3-cycle LOAD; the black adds behind it sit idle even though they could run.

Step 3 — The dependency graph: what may actually be reordered

WHAT. We are only allowed to run instructions early if doing so cannot change the answer. The rule that forbids reordering is the true dependency:

Take the parent's four instructions and draw an arrow $A \to B$ whenever $B$ reads what $A$ wrote:

I1: R1 = LOAD [addr1]
I2: R2 = R3 + R4
I3: R5 = R1 + R2      (reads R1 from I1, R2 from I2)
I4: R6 = R7 * R8

$I 3$ reads R1 (written by I1) and R2 (written by I2), so $I 1 \to I 3$ and $I 2 \to I 3$ . Nothing points to I2 or I4 — they are free.

WHY. This graph, not the written order, is the real law. Anything not connected by an arrow may run in any order. In-order execution ignores the graph and obeys the list; that is its only crime.

PICTURE. The four instructions as nodes; red arrows are the two true dependencies. Notice I4 floats alone.

This is instruction-level parallelism: independent nodes can execute at the same time.

Step 4 — False dependencies (WAW and WAR), and how renaming erases them

WHAT. Sometimes two instructions clash only because they reuse the same cubby name, not because they exchange a value. There are two flavours of this false clash.

Flavour 1 — Write-After-Write (WAW). Two instructions write the same name:

A1: R1 = R2 + R3
A2: R1 = R6 - R7     (writes R1 again — but a NEW value)

Both write R1. If they finished out of order, the wrong one might be left in R1. Yet the second R1 is a totally different number from the first — the clash exists only because we ran out of names.

Flavour 2 — Write-After-Read (WAR). A later instruction writes a name that an earlier instruction still needs to read:

B1: R4 = R1 + R5     (reads R1 — the OLD value)
B2: R1 = R6 - R7     (overwrites R1)

B2 must not clobber R1 before B1 has read it. Again, no value flows from B1 to B2; the arrow exists only because both touch the name R1.

Both WAW and WAR are false dependencies: pure name-reuse, no real data flowing.

FIX. Give the CPU a big secret pool of extra cubbies (physical registers, ~168 of them) far more numerous than the names the programmer sees (architectural registers, ~16–32). A lookup table — the Register Alias Table — remaps each write to a fresh physical cubby. To avoid confusing these cubbies with instruction tags later, we name physical registers $ϕ_{47}$ (Greek "phi", "physical"):

$name programmer wrote R 1 ⟼ fresh physical cubby, chosen now ϕ_{47}$

$physical registers ≫ architectural registers$

Term-by-term: the left symbol is the name the code uses; $⟼$ is "is currently mapped to"; $ϕ_{47}$ is a private cubby the programmer never names. In WAW, the two writes now land in different physical cubbies. In WAR, B2's write lands in a fresh cubby, so B1 still reads the old one untouched. Both false arrows vanish.

WHY. Deleting false dependencies leaves only true arrows — the pure data-flow graph of Step 3. Now the CPU may schedule maximally.

PICTURE. Top row: a false WAW arrow (two writes to R1). Bottom row: a false WAR arrow (read of R1, then a write to R1). Right side: after renaming, each write gets its own red physical cubby $ϕ$ — both arrows gone.

See Register renaming for the full machinery.

Step 5 — The ready condition: when may an instruction fire?

WHAT. Each waiting instruction sits in a small holding pen called a reservation station. It holds the instruction and slots for its two inputs, $src_{1}$ and $src_{2}$ . Each slot is in one of two states:

Ready — the actual number is sitting in the slot.
Waiting — the slot instead holds a tag: the name of the producer instruction (we write producer tags as $P_{j}$ , a Producer instruction, distinct from the physical cubbies $ϕ$ of Step 4) that will supply the value.

The instruction may execute only when both inputs are ready:

$Ready (I) = Ready (src_{1}) \land Ready (src_{2})$

Term-by-term: $Ready (I)$ is a yes/no for the whole instruction; $\land$ is logical AND (true only if both sides are true); each $Ready (src_{i})$ is the yes/no for one input slot. One waiting slot means the whole thing waits.

WHY AND, not OR? An add needs both numbers to add. Missing either makes the result garbage. So the gate is the strictest one: AND.

PICTURE. A reservation station box: src1 filled (black number, ready), src2 still holding a red producer tag $P_{j}$ (waiting). The instruction can't fire yet.

Step 6 — Wakeup: the Common Data Bus broadcasts

WHAT. When a producer $P_{j}$ finishes, it shouts its result to everyone at once over a shared wire, the Common Data Bus (CDB). The shout is a pair:

$(who I am tag : P_{j}, the number I made value : V)$

Every reservation station snoops (listens to) the CDB. First we need two tiny pieces of logic notation, each earned before use:

With those two words in hand, the wakeup rule reads:

$\forall I : trigger: this slot waits on P_{j} (src_{i} = P_{j}) \Rightarrow consequence: swallow the value, flip to Ready (src_{i} \leftarrow V, Ready (src_{i}) \leftarrow true)$

Term-by-term, left to right: $\forall I$ = "for every instruction in every station, check this"; the trigger $src_{i} = P_{j}$ asks "is this slot waiting on producer $P_{j}$ ?"; $\Rightarrow$ says "if yes, then do the following"; the arrow $\leftarrow$ means "gets assigned"; so the slot swallows the value $V$ and flips itself to Ready.

WHY broadcast to all, not one at a time? Many instructions may wait on the same result. A single parallel shout wakes them all in one cycle; walking a list would cost cycles per waiter — that is exactly why the rule begins with $\forall$ (every waiter at once), not "the next waiter."

PICTURE. One producer drives the red CDB wire; three stations snoop; two matching tags light up and fill.

Step 7 — Structural limits: only so many buses and ports

WHAT. Steps 5–6 assumed any ready instruction can fire and any finished one can broadcast. Real hardware is finite. Two structural hazards appear:

Execution ports. A CPU has a fixed number of execution units (ports). If more instructions are ready than there are ports, only that many fire this cycle; the rest wait one more cycle. The scheduler picks by age/priority.
CDB bandwidth. The Common Data Bus can carry only a fixed number of results per cycle (often one or two). If two instructions finish in the same cycle but only one bus slot exists, one broadcast is delayed a cycle — and its waiters wake a cycle later.

A structural hazard is a stall caused by not enough machine, not by a data arrow.

WHY this matters. It changes our earlier bound. Even with zero dependencies, throughput is capped by execution width (how many ports) and result-bus width. This is exactly the "Execution width" term in the parent's IPC bound.

PICTURE. Four ready instructions, only two ports: two fire now (red), two are held to the next cycle. A second panel shows two finishers contending for a single CDB slot.

Step 8 — Putting it together: the out-of-order timeline

WHAT. Now watch the four instructions of Step 3 run. Latencies: LOAD = 3 cycles, everything else = 1 cycle. An instruction fires the cycle after its last input becomes ready. Assumption stated explicitly: this machine has two execution ports and a CDB wide enough that no two results collide here — so no structural hazard bites in this small example.

Trace each instruction's start cycle:

I1 (LOAD) has no dependency → fires cycle 1, busy cycles 1–3, result ready end of cycle 3.
I2 (add) is free → fires cycle 1 on the second port, result ready end of cycle 1.
I4 (multiply) is free but both ports are busy in cycle 1 (I1, I2), so it fires cycle 2, ready end of cycle 2.
I3 needs R1 (ready end of 3) and R2 (ready end of 1). Its last input arrives end of cycle 3, so I3 fires cycle 4, ready end of cycle 4.

The last work finishes at the end of cycle 4, so the out-of-order span is 4 cycles.

For the in-order machine, instructions must run in written order on the same two ports, and each waits for the previous to make room in program order: I1 cycles 1–3, I2 cycle 4, I3 cycle 5, I4 cycle 6 → span 6 cycles.

$speedup = \frac{in-order span}{out-of-order span} = \frac{6}{4} = 1.5 \times$

Term-by-term: numerator 6 = in-order cycles; denominator 4 = out-of-order cycles; the ratio is how many times faster the reordered machine finishes.

WHY only 1.5× and not more? Because the true chain $I 1 \to I 3$ is genuine and cannot be shortened — that is the critical path, the longest arrow-path in the graph. I3 can never start before end of cycle 3 no matter how clever the machine is, so at least 4 cycles are unavoidable here. OoOE deletes wasted stalls (I2, I4 no longer queue behind the load), but never real dependencies. Bigger programs with more free instructions and longer chains see 2–3×.

PICTURE. Two stacked timelines, in-order (top, 6 cycles) vs out-of-order (bottom, 4 cycles). The red bars highlight the two cycles OoOE saves.

Step 9 — Memory operations: the trickiest out-of-order case

WHAT. Registers are easy — their names are visible in the instruction, so the CPU knows every register dependency the moment it decodes. Memory is different. A STORE [addr] writes a memory location and a LOAD [addr2] reads one, but the machine often does not know the actual addresses until after those instructions compute them. So it cannot tell in advance whether a load and an earlier store touch the same location. This unknown is the memory disambiguation problem.

To manage pending memory operations we introduce one new structure, defined before use:

Three ordering rules the machine must never break:

Memory RAW (true): a LOAD must return the value of the most recent earlier STORE to the same address. This is a genuine value flow through memory — unbreakable, exactly like a register RAW.
Memory WAW (false): two STOREs to the same address must leave memory holding the later one's value. Order of the writes matters, but no value flows between them.
Memory WAR (false): a STORE must not overwrite a location that an earlier LOAD still needs to read.

Before a load takes a value, the LSQ scans every earlier store's address:

$load may bypass earlier stores ⟺ every earlier store S has addr (S) \neq = addr(load)$

Term-by-term: $⟺$ = "exactly when / if and only if"; the right side says each earlier store's address differs from the load's address. If they all differ, the load may skip ahead and read memory. If one matches, the load must instead take that store's value directly — this is store-to-load forwarding (hand the value straight from the store buffer, skipping memory) — or wait if that store's value is not ready yet.

Handling the false memory hazards (WAW / WAR). Unlike register WAW/WAR, memory locations are not renamed into a huge pool — the address space is the address space. Instead the CPU keeps stores in the LSQ in program order and only lets a store write real memory when it commits (retires). Loads read from the LSQ (via forwarding) rather than racing a not-yet-committed store. So memory WAW is resolved by committing stores in order, and memory WAR is resolved because a younger store's value stays bottled in the LSQ until every older load has already read the old value. False memory arrows are thus neutralised by ordered commit, not by renaming.

Degenerate case — a wrong guess (memory speculation). Aggressive CPUs let a load go early, guessing no earlier store aliases it, before all earlier store addresses are even known. If a later-computed store address turns out to match, that was a memory-ordering violation: the speculatively-executed load — and everything that consumed its value — is squashed and re-executed with the correct forwarded value. This is the same flush-and-restart machinery used for exceptions and mispredicted branches.

WHY all this care? Without ordered memory, out-of-order execution would silently corrupt data: a load could read stale bytes, or a store could clobber a value still owed to an earlier read. The LSQ makes memory obey the same true/false dependency logic we built for registers — true RAW respected, false WAW/WAR neutralised by in-order store commit. This same ordering discipline underpins cache coherence and memory consistency models once several cores share memory.

PICTURE. An LSQ column in program order; a young load reaching back past two stores; the red store shares its address, forcing store-to-load forwarding instead of a plain memory read.

Step 10 — The degenerate case: making it look in-order again (the ROB)

WHAT. Executing early creates a danger: results finish in a scrambled order. But if an instruction faults (e.g. divide-by-zero, bad memory), the world must look exactly as if the program stopped cleanly at that instruction — everything before it committed, everything after it erased. This clean picture is a precise exception.

The fix is the reorder buffer (ROB): a queue holding every in-flight instruction in program order. Instructions execute out of order but retire (become permanent, i.e. write the architectural state the programmer sees) only from the head, strictly in program order. This ordered retirement is the mechanism that guarantees precise exceptions:

The head instruction $I_{h}$ may retire only when:

$Can_Commit (I_{h}) = Complete (I_{h}) \land \neg Exception (I_{h})$

Term-by-term: $I_{h}$ is the instruction at the head of the queue; $Complete$ = it finished executing; $\land$ = AND (from Step 5); $\neg$ = logical NOT (turns true into false); $Exception$ = it faulted. So it retires only if finished and fault-free.

To show the fault case we extend our running program with two more instructions, I5 and I6, fetched after I3 and executed speculatively (early, before we knew they were safe):

I5: R9  = R1 + 1     (fetched after I3, executed early)
I6: R10 = R9 * 2     (fetched after I5, executed early)

Suppose it is I3 that faults. Then: flush everything behind I3 (including I5, I6), throw away those speculatively-computed results, restore architectural state to just after I2, and hand control to the OS.

WHY. This is the degenerate boundary of the whole scheme: even when execution is maximally scrambled, in-order retirement guarantees the outside world (memory, interrupts, a debugger) sees a clean sequential story. Speed inside, order outside — and it is precisely because stores commit in program order (Step 9) and results retire in program order here that a mid-program fault can be made to look precise.

PICTURE. The ROB as a queue. I1,I2 retired (left, done); I3 at head faulted (red); I5,I6 finished but sit behind, about to be flushed.

This clean rollback is exactly what makes speculative execution and branch prediction safe — wrong guesses simply never retire.

The one-picture summary

WHAT. Every idea on this page compressed into a single flow: instructions enter in order, get renamed (false WAW/WAR arrows die), wait in reservation stations until the CDB wakes them, compete for finite ports, respect memory ordering via the LSQ, execute out of order, land in the ROB, and leave in order so exceptions stay precise.

Recall Feynman retelling — say it in plain words

Imagine a to-do list. A dumb worker does items strictly top to bottom, so a slow item (waiting for a delivery) freezes the whole list even though later items need nothing. A smart worker first draws arrows: "item C needs item A's result." Only those arrows are real rules. If two items clash just because they'd scribble on the same sticky-note — either both writing it, or one writing while another still needs to read it — the smart worker gives each its own fresh note (renaming), and both fake clashes vanish. Now every item sits in a waiting-tray with its inputs; the moment a finished item shouts its answer to the whole room (the bus), any tray missing that answer grabs it and becomes runnable. But there are only so many hands (ports) and one loudspeaker (the bus), so if too many items are ready at once, some wait a turn — that's a structural jam, not a real dependency. Memory items are extra sneaky: two might touch the same shelf without the worker knowing until late, so a special ledger (the LSQ) checks shelf numbers before letting a read skip ahead, and stores only actually write the shelf when they finally file. Finally, finished work is only filed from the top of an in-order stack (the reorder buffer); if one item turns out to be a disaster, everything filed after it is shredded and the desk looks like that item stopped everything cleanly. Fast inside, tidy outside.

Recall Quick self-test

Which dependency types are deleted by renaming? ::: The false ones — WAW and WAR (name-reuse), never true RAW. What is the difference between $ϕ_{47}$ and $P_{j}$ ? ::: $ϕ_{47}$ is a physical register (a storage cubby); $P_{j}$ is a producer tag (the name of the instruction that will make the value). What do $\forall$ and $\Rightarrow$ mean in the CDB wakeup rule? ::: $\forall$ = "for every" (check every waiting slot); $\Rightarrow$ = "leads to" (if the tag matches, then swallow the value and flip to Ready). Why must an instruction wait for BOTH operands (AND not OR)? ::: An operation needs every input to produce a correct result; a missing input means garbage. Why can't the CPU always reorder a LOAD ahead of a STORE? ::: Their addresses may alias (same location); the LSQ must confirm no earlier store hits that address, else it forwards the store's value or the load re-executes. How are false memory WAW/WAR hazards neutralised? ::: Not by renaming — stores commit to memory in program order and stay bottled in the LSQ until then, so writes never reorder past reads that still need the old value. Why does retirement happen in program order even though execution doesn't? ::: To give precise exceptions — the reorder buffer retires from its head in order, so the outside world always sees a clean "stopped exactly here" boundary. In Step 8's example, what is the out-of-order span and speedup? ::: 4 cycles out-of-order vs 6 in-order, a 6/4 = 1.5× speedup, limited by the true I1→I3 critical path.