Out-of-order execution: Worked examples — Hardware deep dive

This page is the drill floor for Out-of-order execution. The parent note built the ideas: renaming, reservation stations, the reorder buffer (ROB), the ready condition. Here we throw every kind of situation at those ideas and grind through each one by hand.

Before we start, one promise: every symbol you see here was earned in the parent note, and I re-anchor it the first time it appears. If a term feels new, that is a bug — tell me.

Definition Fast vocabulary refresh (read once, then drill)

In-flight instruction :: one that has been fetched but has not yet committed. It lives somewhere between the front of the pipe and the ROB head.
Latency :: how many cycles an instruction spends executing before its result exists. A register add = 1 cycle; a memory LOAD here = 3 cycles.
Result-ready cycle :: the cycle at the end of which the value exists on the Common Data Bus (CDB) — the shared wire every reservation station listens ("snoops") on.
IPC (Instructions Per Cycle) :: our headline score for speed — the average number of instructions the CPU finishes per clock cycle. If $N$ instructions take $C$ cycles, then $IPC = N / C$ . Higher is faster. Everything on this page is ultimately a fight to raise IPC, and the "ceilings" below are the things that cap it.
RAW / WAR / WAW :: three ways two instructions can touch the same register. Read-After-Write is a true dependency (real data flow). Write-After-Read and Write-After-Write are false — they exist only because we reused a register name, and register renaming deletes them.
Commit / retire :: the in-order moment a result becomes officially real (architectural state).
ILP (Instruction-Level Parallelism) :: how many independent instructions could run at the same time in a piece of code. "Window-limited ILP" = the parallelism you can actually see inside the current window; "critical-path-limited ILP" = the parallelism left after the longest dependency chain forces some ordering. See instruction-level parallelism.
Physical register (written P1, P2, …) :: a real storage slot inside the CPU, of which there are ~168. Renaming maps the named registers you wrote (R1, R2, …, only 16–32 of them) onto these many physical slots. The P-prefix on this page always means "a physical register the renamer handed out"; R-prefix means "an architectural register the programmer wrote."
The symbol $\infty$ :: read it as "unlimited / as many as you could ever want." When an example says " $\infty$ ports," it means: pretend the CPU can start any number of instructions in the same cycle, so ports never run out. We use it to isolate one ceiling at a time.

We follow two timing rules on this whole page so every answer is reproducible. Read them once carefully — they resolve every "is it 3 or 4 cycles?" question later.

Formula The ONE rule for "total cycles" (removes all inconsistency)

Total cycles = the cycle in which the last instruction commits. We compute this in two independent steps and take the larger: $Total = max (execution-bound last-result-ready cycle + 1, retire-bound ⌈ N / R ⌉ measured from first commit)$

The +1 on the execution term is the single write-back-to-architectural-state cycle for that last result.
The retire term matters only when many results pile up faster than $R$ /cycle can drain them. When does commit "hide"? When results trickle out no faster than $R$ /cycle (e.g. a dependency chain), retire keeps pace and the retire term is not larger — so it adds nothing. When does commit bind? When results finish in a burst wider than $R$ (e.g. many independent ops on wide ports), the retire term wins. Examples 4, 5 and 8 show each case explicitly. From here on we always apply this $max$ , so there is never ambiguity about whether to add commit cycles.

The scenario matrix

Everything OoOE can throw at you falls into one of these cells. The examples below are labelled with the cell(s) they cover, and together they hit every row.

#	Case class	What makes it tricky	Covered by
A	No dependencies (fully parallel)	limited only by execution width	Ex 1
B	RAW chain (true dependency)	critical path — cannot be beaten	Ex 2
C	WAW / WAR false dependency	must rename to unlock parallelism	Ex 3
D	Mixed: slow LOAD + independents + dependent	reorder around latency	Ex 4
E	Not enough ports (execution-width limit)	ready ≠ can-fire	Ex 5
F	Exception / speculative squash	precise state via ROB	Ex 6
G	Degenerate: window too small	can't see the independent work	Ex 7
H	Limiting case: zero dependencies, infinite width	IPC → execution/retire width	Ex 8
I	Real-world word problem (cache miss)	memory-level parallelism	Ex 9
J	Exam twist: is a reorder legal?	spot the true vs false hazard	Ex 10

The three ceilings from the parent note govern every cell (IPC = Instructions Per Cycle, just defined above): $IPC \leq min (Window-limited ILP, Execution width, Critical-path-limited ILP)$ Each example below is really asking: which of these three ceilings is binding here? (Example 8 will unmask a hidden fourth ceiling: retire bandwidth.)

The figure below draws those three ceilings as three bars of illustrative heights. The green dashed line sits at the shortest bar — that is the one that actually limits IPC. Every example is a hunt for which bar is shortest: the blue "window" bar (can you see the work?), the yellow "execution width" bar (is there space to run it?), or the red "critical path" bar (are you forced to sequence?).

Example 1 — Cell A: fully independent instructions

Worked example Four adds, nothing shared

I1: R1 = R2 + R3
I2: R4 = R5 + R6
I3: R7 = R8 + R9
I4: R10 = R11 + R12

All 1-cycle. The machine has 2 add ports (can start 2 adds per cycle) and retire bandwidth $R = 2$ per cycle. How many cycles to finish (commit) all four?

Forecast: guess before reading — is it 1, 2, or 4 cycles?

Check dependencies. No instruction reads a register another writes. So no RAW, no WAR, no WAW. Why this step? Dependencies are the only reason OoOE is forced to serialize. Zero dependencies means the critical-path ceiling = 1 (any single instruction is the whole chain).
Check resources. 4 ready instructions, but only 2 add ports. So cycle 1 fires I1, I2 (ready end cyc 1); cycle 2 fires I3, I4 (ready end cyc 2). Why this step? Being ready is necessary but not sufficient — you also need a free port. Here the execution-width ceiling = 2/cycle is the binding one.
Apply the total-cycles rule. Execution-bound = last-ready (cyc 2) + 1 = 3. Retire-bound = $⌈ 4/ R ⌉ = ⌈ 4/2 ⌉ = 2$ cycles of committing. With $R = 2$ matched to the port width, commit keeps pace and does not dominate; total commit of the last pair lands in cycle 3. Why this step? We deliberately set $R = 2$ so retire matches issue — this is the "commit hides" case.
Total = 3 cycles (2 to compute, +1 to commit the final pair).

Verify: last result ready cyc 2, +1 commit ⇒ 3. Sustained IPC $= 4/3 \approx 1.33$ ; the steady-state throughput while ports are saturated is 2/cycle = execution width, the binding ceiling. ✓

Example 2 — Cell B: a pure RAW chain

Worked example Each depends on the one before

I1: R1 = R2 + R3    ; 1 cycle
I2: R4 = R1 + R5    ; needs R1
I3: R6 = R4 + R7    ; needs R4
I4: R8 = R6 + R9    ; needs R6

$\infty$ ports (unlimited — see the vocab note), retire $R = 1$ /cycle. Cycles to finish?

Forecast: with unlimited execution units, does this run in 1 cycle?

Draw the data-flow graph: I1 → I2 → I3 → I4, a single strand. Why this step? A RAW edge is a true dependency — I2 literally needs the number I1 produces. No renaming, no extra port removes it.
Time each fire. I1 fires cyc 1, ready end of cyc 1. I2 fires cyc 2 (after its operand). I3 cyc 3. I4 cyc 4. Why this step? This is the critical-path ceiling at work. It is the one limit no hardware can beat — even Apple's 600-entry window cannot make I4 run before I3 finishes.
Apply the total-cycles rule. Results trickle out one per cycle (I1 ready cyc1, …, I4 ready cyc4). Execution-bound = last-ready (cyc 4) + 1 = 5. Retire-bound = $⌈ 4/1 ⌉ = 4$ commits, but they start as I1 finishes and keep pace at 1/cycle — never larger than the execution term. So the $max$ picks the execution term. Why this step? Chains are the case where commit hides: one result per cycle exactly matches $R = 1$ .
Total = 5 cycles (chain of 4 + one final commit). IPC $= 4/5 = 0.8$ ; steady-state throughput along the chain is 1/cycle, matching critical-path-limited ILP.

Verify: chain length 4 ⇒ last ready cyc 4, +1 commit ⇒ 5. Adding ports does nothing: $min (\infty width, \infty window, critical path)$ still forces the chain. ✓

Example 3 — Cell C: false dependency killed by renaming

Worked example The R1 that lies (WAW + WAR)

I1: R1 = R2 + R3
I2: R4 = R1 + R5    ; RAW on R1 (true)
I3: R1 = R6 + R7    ; WAW with I1, WAR with I2 (both false)
I4: R8 = R1 + R9    ; RAW on I3's R1 (true)

2 add ports, retire $R = 2$ /cycle. Cycles with renaming vs without?

Forecast: does I3 have to wait for I1 to finish?

Classify each shared use of R1. I2 reads I1's R1 (true RAW). I3 writes R1 again — the name collides with I1's write (WAW) and with I2's read (WAR). Those two are false: they exist only because the assembler reused the name R1. Why this step? False dependencies are artifacts of naming, not data. The parent note's insight: rename them away.
Rename onto physical registers. Recall P-prefixed names are the CPU's many real storage slots. Give I1's result physical slot P1 and I3's result a different slot P2. Now:
- I2 reads P1, I4 reads P2. The two chains {I1→I2} and {I3→I4} touch different physical slots, so they are independent. Why this step? Using two distinct physical slots for the two R1 writes exposes the real data-flow graph — two separate 2-long strands instead of one tangle.
Schedule (2 ports). Cyc 1: fire I1 and I3 (both ready, independent), ready end cyc 1. Cyc 2: fire I2 and I4, ready end cyc 2. Execution-bound = 2 + 1 = 3; retire-bound with $R = 2$ keeps pace. Total = 3 cycles.
Without renaming: I3 stalls until I1's write retires and I2's read completes → serial-ish: cyc1 I1, cyc2 I2, cyc3 I3, cyc4 I4, last ready cyc 4, +1 commit ⇒ 5 cycles.

Verify: speedup $= 5/3 \approx 1.67 \times$ . With renaming, steady-state throughput = 2/cycle = execution width, the binding ceiling once false deps vanish. ✓

The figure shows this split visually: the top row is the tangled single strand forced by name reuse (blue → red edges), and the bottom row is the two clean, parallel strands after P1/P2 separate them.

Example 4 — Cell D: slow LOAD + independents + dependent (the parent's showcase, re-derived)

Worked example Reorder around a memory load

I1: R1 = LOAD [addr]   ; 3 cycles
I2: R2 = R3 + R4       ; 1 cycle, independent
I3: R5 = R1 + R2       ; needs I1 AND I2
I4: R6 = R7 * R8       ; 1 cycle, independent

One LOAD port, one ALU port, retire $R = 1$ /cycle in program order. Cycles in-order vs out-of-order?

Forecast: the LOAD takes 3 cycles — do I2 and I4 have to sit behind it?

In-order. I1 occupies cyc 1–3. I2 cannot start until I1 leaves → cyc 4. I3 → cyc 5. I4 → cyc 6. Total 6. Why this step? In-order issue means one stall poisons everyone behind it, even the innocent I2/I4.
Out-of-order — fire independents early. I2 has no operand waiting → fire cyc 1 on the ALU port (ready end cyc 1). I4 → fire cyc 2 on the ALU port (ready end cyc 2). The LOAD I1 runs cyc 1–3 on its own port. Why this step? Different ports = I2/I4 don't compete with the LOAD. This is the whole point of OoOE.
Fire the dependent I3. I3 needs I1 (ready end cyc 3) and I2 (ready end cyc 1). Last operand ready end of cyc 3 → I3 fires cyc 4, result ready end cyc 4. Why this step? I3 sits on the genuine dependency chain I1 → I3; that chain, not the ports, sets its earliest fire.
Apply the total-cycles rule. I3 is last in program order; its result is ready end cyc 4. Execution-bound = 4 + 1 = 5. Retire-bound: only 4 instructions, committed in order at $R = 1$ but no burst (I2 ready cyc1, I4 cyc2, I1 cyc3, I3 cyc4 — one per cycle) so retire keeps pace and does not dominate. The $max$ gives 5. Why this step? The parent note's "≈5 cycles including commit settling" is exactly this: the +1 is the in-order commit of the last result I3.

Verify: speedup $6/5 = 1.2 \times$ , matching the parent note. Residual latency = the genuine chain I1→I3 plus one in-order commit step. ✓

The timeline figure stacks both schedules: the top block is in-order (I2/I4 stranded behind the red LOAD, red dashed finish line at 6), the bottom block is out-of-order (I2/I4 pulled early, green dashed finish line at 5).

Example 5 — Cell E: ready ≠ can-fire, AND retire bandwidth bites

Worked example Six ready adds, two ports, one retire slot

I1..I6: six independent 1-cycle adds, all operands ready at cycle 0

Two add ports, retire $R = 1$ /cycle. How many cycles until all six are committed?

Forecast: all six are ready immediately — so 1 cycle? Or does something else cap it?

All ready at once. No dependency delays them. Critical-path ceiling = 1. Window is big enough (window ceiling ≥ 6). Why this step? Two ceilings say "go fast"; we must find the binding one.
Ports limit starting. 2 per cycle: cyc 1 fires I1,I2 (ready end 1); cyc 2 fires I3,I4 (ready end 2); cyc 3 fires I5,I6 (ready end 3). Why this step? Execution-width ceiling = 2/cycle. Execution alone would finish producing results by end of cyc 3.
Now apply the total-cycles rule honestly. Six results become ready in a burst (2 per cycle) but retire only drains $R = 1$ per cycle. Retire-bound = $⌈ 6/1 ⌉ = 6$ commit cycles. Committing starts in cyc 2 (one cycle after I1/I2 ready) and proceeds 1/cycle: I1 cyc2, I2 cyc3, I3 cyc4, I4 cyc5, I5 cyc6, I6 cyc7. Why this step? This is the reviewer's exact point: with only one retire slot, six results cannot all be committed by cycle 4. The retire term wins the $max$ . Execution-bound = 3+1 = 4, retire-bound reaches cyc 7 → Total = 7 cycles.
The binding ceiling here is retire bandwidth, not ports. Ports fill the ROB with finished results faster than commit can publish them.

Verify: results produced by end cyc 3, but $⌈ 6/1 ⌉ = 6$ in-order commits starting cyc 2 ⇒ last commit cyc $2 + 6 - 1 = 7$ . Sustained IPC $= 6/7 \approx 0.86 = R$ (retire bandwidth), the true bottleneck. ✓ Lesson: readiness lets you choose, ports decide how many start, retire decides how many become real.

Example 6 — Cell F: exception squashes speculative work

Worked example Fault at the ROB head

ROB (program order, head on left):
[ I3(fault) | I4 done | I5 done ]
   ^head

I1, I2 already committed. I3 divides by zero. I4, I5 already executed out-of-order. What is the architectural state after handling?

Forecast: do I4 and I5's results survive, since they finished?

I3 is at the head and faulted. Commit rule: Can_Commit(I_h) = Complete(I_h) ∧ ¬Exception(I_h). Here Exception is true → cannot commit. Why this step? Only the head can commit, and it must be exception-free. This enforces the illusion of sequential execution.
Flush everything after the head. I4, I5 are younger than the faulting I3. Their computed values live only in the ROB, never in architectural registers/memory → discard them. Why this step? Precise exceptions demand: "I3 faulted, nothing after it happened." Speculative results must be invisible.
Roll back. Architectural state = state right after I2 (I3's inputs). Signal the OS.

Verify: committed set = {I1, I2}; discarded = {I4, I5}; I3 pending. Count of visible results = 2, exactly the pre-fault instructions. ✓ (Same principle powers speculative execution and branch prediction recovery.)

Example 7 — Cell G: window too small to see the work

Worked example The independent instruction is out of reach

I1: R1 = LOAD [addr]   ; 100-cycle cache miss
I2..I5: four adds, each RAW-dependent on the previous (chain, needs I1)
I50: R99 = R98 + R97   ; totally independent of everything

Instruction window = 4 entries, retire 1/cycle. Can I50 execute during the 100-cycle miss?

Forecast: there's free independent work at I50 — will OoOE grab it?

Window holds only 4 in-flight instructions. While I1 stalls on the miss, the window fills with I1..I4 and cannot advance (I1 blocks the ROB head from committing). Why this step? The window ceiling caps how far ahead the CPU can see. I50 is 46 instructions past the window edge — invisible.
CPU stalls ~100 cycles doing nothing useful, even though I50 could run. Why this step? Independent work you cannot see is independent work you cannot use. This is exactly why modern chips grow windows to 200–600 entries.
Fix: a window ≥ 50 would pull I50 in and hide the miss latency behind it.

Verify: with window 4, reachable-independent-work = 0 during the miss → binding ceiling is window-limited ILP ≈ 0 useful IPC for those cycles. Enlarge window past 50 → I50 reachable. ✓

Example 8 — Cell H: the clean limit (infinite width) — unmasking retire bandwidth

Worked example Push execution width to infinity

N independent 1-cycle instructions, all operands ready at cycle 0.
Execution width = W ports. Window ≥ N. Retire bandwidth = R per cycle.

As $W \to \infty$ (width grows without bound — the $\infty$ from the vocab note), what is sustained IPC?

Forecast: does IPC grow forever, or hit a wall?

Execution finishes fast. With zero dependencies the critical-path ceiling = 1 (never binds) and window ≥ N (never binds), so execution needs only $⌈ N / W ⌉$ cycles. As $W \to \infty$ , that is 1 cycle: every result is ready at end of cycle 1. Why this step? We removed three ceilings on purpose to expose whatever is left.
But results must still be committed in order at $R$ /cycle. Publishing all $N$ results takes $⌈ N / R ⌉$ commit cycles. Apply the total-cycles rule: $Total = max (⌈ N / W ⌉ + 1, ⌈ N / R ⌉)$ . Why this step? Infinite ports are useless if you can only make results real at $R$ /cycle. This is the hidden fourth ceiling — retire bandwidth.
Take the limit. As $W \to \infty$ , sustained IPC $= N / max (1, ⌈ N / R ⌉) \to R$ (for $N \geq R$ ). So IPC saturates at the retire width $R$ , never at the infinite execution width. Why this step? It pins down which ceiling truly caps a burst of independent work: not ports, but commit.

Verify: $N = 8$ . With $R = 1$ : total $= max (1, 8) = 8$ , IPC $= 8/8 = 1 = R$ . With $R = 8$ : total $= max (1, 1) = 1$ , IPC $= 8/1 = 8 = R$ (and $= N$ , since $R \geq N$ ). With $R = 16 \geq N$ : IPC $= N = 8$ , capped by $N$ not $W$ . ✓ IPC $\to R$ , confirming retire bandwidth is the wall.

Example 9 — Cell I: real-world word problem (memory-level parallelism)

Worked example Two cache misses — serial or overlapped?

A loop issues two independent LOADs that both miss L1 and go to main memory (100 cycles each). The window is large enough to hold both.

I1: R1 = LOAD [addrA]   ; miss, 100 cycles
I2: R2 = LOAD [addrB]   ; miss, 100 cycles, independent of I1
I3: R3 = R1 + R2        ; needs both

How long, in-order (blocking) vs out-of-order (non-blocking loads), retire 1/cycle?

Forecast: two 100-cycle misses — is that 200 cycles or 100?

In-order (blocking). I1 stalls the pipe 100 cycles, then I2 stalls another 100 → ~200 cycles, then I3. Why this step? A blocking machine serializes the misses even though they are independent.
Out-of-order + non-blocking loads. I1 and I2 are independent → both miss requests launch in the same window. Memory serves them overlapped (memory-level parallelism). Both back at ~cycle 100. I3 fires cycle 101. Why this step? OoOE's window lets both miss addresses be outstanding at once — the misses share the ~100-cycle wait instead of stacking. Commit of just 3 instructions at 1/cycle is trivially not the bottleneck against a 100-cycle miss.

Verify: in-order ≈ 200 cyc; OoO ≈ 101 cyc; speedup $200/101 \approx 1.98 \times \approx 2 \times$ . ✓ (Interacts with cache coherence and memory consistency when other cores are involved.)

Example 10 — Cell J: exam twist — "is this reorder legal?"

Worked example Spot the hazard type

The compiler wants to swap I2 and I3. Is it legal for the OoOE engine to execute I3 before I2?

I1: R1 = R2 + R3
I2: R4 = R1 + R5     ; reads R1
I3: R1 = R6 + R7     ; writes R1

Forecast: I2 reads R1, I3 overwrites R1 — safe to run I3 first?

Identify the hazard between I2 and I3. I2 reads R1; I3 writes R1. Write-After-Read = WAR = a false dependency. Why this step? WAR is not real data flow — it only says "don't clobber R1 before I2 reads it."
Apply renaming. Give I3's write a fresh physical register P2 (distinct from I1's P1 that I2 reads). Now I3 writes P2, I2 reads P1 — no conflict. Why this step? Renaming converts the ordering constraint into a naming fact. With separate physical slots, execution order is free.
Conclusion: Yes, legal — after renaming, I3 may execute before I2. The engine must still commit them in program order (ROB, 1/cycle), so architectural R1 ends up holding I3's value regardless of execution order.

Verify: hazard = WAR (false) → removable by rename → reorder legal. Contrast: had I3 read R1 (RAW), reorder would be illegal. ✓

Recall Self-test (reveal after answering)

IPC in one sentence ::: instructions finished per clock cycle, $N / C$ — the headline speed score Cell A binding ceiling ::: execution width (with matched retire), commit adds one settling cycle Cell B binding ceiling ::: critical path (dependency chain length) Why can't a huge window beat a RAW chain? ::: the chain is a true data dependency — later instructions literally need earlier results WAR and WAW are removed by ::: register renaming (they are false / naming-only) What does a P-prefixed name mean on this page? ::: a physical register — a real CPU storage slot handed out by the renamer (vs R = architectural register the programmer wrote) What does $\infty$ mean in these examples? ::: unlimited — pretend that resource never runs out, so we can isolate one ceiling Why does Example 4 total 5 and not 4 cycles? ::: the in-order commit of the last instruction (I3) adds one settling cycle after its result is ready Why does Example 5 total 7 and not 3 cycles? ::: six results burst out but retire drains only 1/cycle — retire bandwidth binds What hidden fourth ceiling does Example 8 unmask? ::: retire / commit bandwidth — sustained IPC saturates at R, never at infinite execution width What makes I4/I5 discardable after an I3 fault? ::: they are younger than the faulting head; their results live only in the ROB, never committed During a cache miss, what lets OoOE keep working? ::: a large enough instruction window to reach independent work Two independent misses take ~100 not ~200 cycles because ::: memory-level parallelism — both requests are outstanding at once