Reorder buffer (ROB): Worked examples — Hardware deep dive

This page drills the Reorder buffer (ROB) until no situation can surprise you. We do not add new theory; we take the head/tail pointers, the retire-in-order rule, and the flush-on-exception rule from the parent note and push them through every case a ROB can face.

Before anything, three plain-word reminders (so no symbol appears un-earned):

Recall What are Head and Tail again?

Head ::: the pointer to the oldest instruction still in the buffer — the only one allowed to retire next. Tail ::: the pointer to the next free slot — where the next issued instruction is written. Retire ::: copy a completed result out to the real (architectural) register file and free its slot.

Recall The one golden rule

Instructions may execute in any order, but they may only retire in program order — strictly Head-first.

The scenario matrix

Every ROB situation is one of these cells. The examples below each carry a tag like [Cell C] so you can see the whole space is covered.

Cell	Case class	What makes it tricky
A	Empty buffer (Head = Tail, nothing in flight)	degenerate: is it empty or full?
B	Full buffer (Tail+1 wraps onto Head)	issue must stall
C	Wrap-around indexing crosses the array end	modulo arithmetic
D	Out-of-order completion, in-order retire	youngest finishes first — must wait
E	Operand forwarding from a pending ROB entry	tag-and-wait, newest match
F	Precise exception at the head vs. a younger faulting inst	flush everything younger
G	Branch misprediction flush	discard speculative tail
H	Limiting / performance (ROB size vs IPC)	formula $IPC = min (ILP, N / L)$
I	Word problem (real pipeline sizing)	translate English → formula
J	Exam twist (store that must not commit early)	memory ordering subtlety

The cells map onto Instruction-retirement, Register-renaming, Precise-exceptions, Branch-prediction, and Superscalar-processors respectively.

Example 1 — Empty vs Full, the degenerate confusion `[Cell A + B]`

Forecast: guess now — can one equation ( $Head = Tail$ ) mean two opposite things?

Write the two candidate conditions. From the parent note: $empty ⟺ Head = Tail, full ⟺ (Tail + 1) mod N = Head .$ Why this step? We need to test the reading against both rules, not one.
Plug in $N = 8$ , Head=Tail=3 for the empty moment. Empty rule: $3 = 3$ ✓. Full rule: $(3 + 1) mod 8 = 4 \neq = 3$ . So this is empty. Why? No instruction was ever written, so Tail never moved past Head.
The full moment. If we insist on using only "Head=Tail" we'd wrongly call a full buffer empty. That is exactly why real hardware never lets Tail equal Head by filling: the full rule stops issue one slot early. Why? With 8 slots, we treat the buffer as full when 7 are occupied and $(Tail + 1) mod 8 = Head$ , so Head=Tail can only mean empty.

Verify: Empty rule true, full rule false → unambiguously empty. If we had allowed all 8 slots to fill, Head=Tail would be ambiguous; sacrificing one slot removes the ambiguity. Usable capacity $= N - 1 = 7$ .

Example 2 — Wrap-around indexing `[Cell C]`

Forecast: the array only has indices 0,1,2,3 — what happens after index 3?

First retirement: $Head = (2 + 1) mod 4 = 3$ . Why the mod? $mod N$ wraps the number line into a circle so index 4 becomes 0. Look at the ring in the figure — retiring is one clockwise step.
Second retirement: $Head = (3 + 1) mod 4 = 0$ . Why? $4 mod 4 = 0$ — the pointer falls off the end and reappears at the start. This is the whole reason we chose a circular FIFO.
Third retirement: $Head = (0 + 1) mod 4 = 1$ .

Verify: Sequence $2 \to 3 \to 0 \to 1$ . Net advance = 3 steps on a ring of 4, and indeed $(2 + 3) mod 4 = 1$ ✓.

Example 3 — Out-of-order completion, in-order retire `[Cell D]`

Forecast: I4 finished first. Is its result in the register file at cycle 8?

List completion status at cycle 8. Done by cycle 8: I4(c5), I1(c6), I2(c7). Not done: I3(c12). Why? Retirement can only consider completed instructions.
Apply Head-first rule. Head = I1.
- Cycle 6: I1 completes → retire I1. Head → I2.
- Cycle 7: I2 completes and is now Head → retire I2. Head → I3. Why this step? Each retire is only legal because the Head slot is complete.
Can I4 retire at cycle 8? Head is now I3, which is still pending until cycle 12. So retirement stalls on I3. I4 stays parked in its ROB slot even though it finished at cycle 5. Why? Program order forbids I4 committing before I3.

Verify: At cycle 8, register file holds I1 and I2 results only. I3, I4 remain in the ROB. I4 waited $8 - 5 = 3$ extra cycles — a concrete instance of the parent's "executed in 1 cycle, sits in ROB for many."

Example 4 — Operand forwarding, newest match wins `[Cell E]`

Forecast: three writers to R1 — which one is "the" R1 the new instruction should see?

Find the newest writer of R1. Scanning tail→head, the closest-to-tail entry writing R1 is slot9. Why newest? The reader must see the most recent definition in program order, i.e. the last write before it — that's slot9, per the parent's piecewise rule ( $i$ = newest matching entry).
Check slot9's status. It is pending. So the reader cannot grab a value; instead it tags slot9 and waits for the broadcast. Why not read slot7's value 9? Because slot7 is older; slot9 overwrites R1 later. Reading 9 would be a stale value — a Register-renaming bug.
What does the reader wait on? Not "R1" but "ROB slot 9". This is the renaming trick: the ROB slot number is the physical tag. Why? Multiple R1's coexist; the slot number disambiguates them.

Verify: Correct source = slot9 (pending) → tag-and-wait. Had slot9 not existed, the newest would be slot7 (completed) → forward value 9 directly. Had no slot written R1, read architectural RF[R1]. All three branches of the parent's piecewise function are exercised.

Example 5 — Precise exception at a younger instruction `[Cell F]`

Forecast: I4 already completed. Does its result survive?

Retire from Head while no fault at Head. Retire I1 ✓, retire I2 ✓. Head → I3. Why? I1, I2 are older than the fault and completed → they are legitimately part of the program's committed state.
Head reaches I3, which carries an exception flag. At retirement we detect the DIV/0. We do not write I3's (garbage) result. Why here and not at execution? Exceptions are recognized only at retirement so they are taken in program order — this is what makes them precise. See Precise-exceptions.
Flush everything from I3 onward. I3 and I4 are squashed; I4's completed result is discarded even though it finished. Why discard a completed I4? I4 is younger than the faulting I3 — a precise exception means "none after the fault takes effect."

Verify: Committed = {I1, I2}. Discarded = {I3, I4}. Architectural state = exactly all instructions before the fault, none after. Handler entered with I3's saved PC. This is the picture:

Example 6 — Branch misprediction flush `[Cell G]`

Forecast: I3, I4 already ran speculatively. Are their register writes visible?

Locate the branch entry. BEQ is at ROB slot $k$ (= I2's slot). On resolution it's flagged mispredicted. Why the ROB and not the execution unit decides recovery? Because only the in-order ROB knows which instructions are younger than the branch.
Flush all entries after $k$ . I3 and I4 are squashed. Their results sat only in the ROB staging area — never in the register file — so nothing architectural is corrupted. Why safe? Speculative-execution results are quarantined in the ROB until retirement; discarding them costs nothing but time.
Redirect fetch to the correct target (I5). Head keeps advancing on I1, I2 (both correct-path) as they complete. Why keep I2? The branch instruction itself is a real, in-order instruction — only its speculative successors were wrong.

Verify: Survivors = {I1, I2}. Squashed = {I3, I4}. Fetch redirected to I5. No wrong-path result ever touched the register file (see Branch-prediction).

Example 7 — ROB size limits IPC, small window `[Cell H]`

Forecast: with tons of ILP available, does IPC just equal 6?

Apply the parent's formula. $IPC = min (ILP_{available}, \frac{N}{L})$ . Why a min? You are capped by either how much parallel work exists or how many instructions you can keep in flight — whichever is smaller.
Compute the window bound. $N / L = 32/8 = 4$ . So $IPC = min (6, 4) = 4$ . Why is 4 < 6? The ROB can hold 32 in-flight, each occupying its slot for ~8 cycles, so it drains only $32/8 = 4$ per cycle — the window, not the ILP, is the bottleneck.
Shrink ROB to 16. $N / L = 16/8 = 2$ , so $IPC = min (6, 2) = 2$ . Halving the ROB halves throughput here. Why? We are firmly in the window-limited regime, where IPC is linear in $N$ .

Verify: $N = 32 \Rightarrow 4$ ; $N = 16 \Rightarrow 2$ . Both below the ILP ceiling of 6 → both window-limited, consistent with the down-sloping line in the figure.

Example 8 — Word problem: sizing a ROB `[Cell I]`

Forecast: guess whether $N = 32$ is enough for IPC 6.

Set the window bound at least equal to the ILP. We need $N / L \geq ILP$ , i.e. $N \geq ILP \times L$ . Why $\geq$ and not $=$ ? Once $N / L$ reaches the ILP ceiling, the min switches to the ILP term; extra slots don't hurt but aren't required.
Plug in $ILP = 6, L = 8$ . $N \geq 6 \times 8 = 48$ . Smallest is $N = 48$ . Why did 32 fail? $32/8 = 4 < 6$ — too small a window, exactly Example 7.
Now $L = 12$ . $N \geq 6 \times 12 = 72$ . Why bigger? Longer latency means each instruction occupies its slot longer, so you need more slots to keep 6 retiring per cycle. A cache miss deepens $L$ and demands a larger ROB — the real reason server CPUs grow ROBs.

Verify: $N = 48$ : $48/8 = 6 = ILP$ → IPC $= min (6, 6) = 6$ ✓. $N = 72$ : $72/12 = 6$ → IPC $= 6$ ✓. Both hit target exactly.

Example 9 — Exam twist: the store that must not commit early `[Cell J]`

Forecast: the store is "done" at cycle 3 — is memory safe to update?

Recall stores retire at the ROB head like everything else. A store's write to memory is an architectural side effect, so it happens only at retirement, in order. Why? If the older LOAD I1 faults (page fault at [A]), a precise exception requires the store to never have happened. See Memory-ordering.
I1 blocks the head until cycle 40. So I2's memory write is held in a store buffer / ROB until I1 retires. At cycle 3 memory is not updated. Why the wait? Committing I2 early would be visible to I3's LOAD and to other cores, breaking program-order memory semantics.
After I1 retires (cycle 40), I2 retires and writes [B]; then I3's LOAD of [B] sees the new value (via forwarding while speculative, but only architecturally correct once I2 commits). Why forward to I3 meanwhile? Store-to-load forwarding lets I3 execute early with I2's data, but I3 also cannot retire before I2 — order preserved.

Verify: Memory write of [B] occurs at cycle 40 (I1 → I2 retire), not cycle 3. I3 reads the correct post-store value. No early architectural side effect — the ROB's in-order commit protected memory ordering.

Recall Quick self-test

With $N = 4$ , is Head=Tail=1 empty or full? ::: Empty (full needs $(Tail + 1) mod N = Head$ ). ILP=6, N=24, L=8 → IPC? ::: $min (6, 24/8) = min (6, 3) = 3$ . Older instruction faults — does a younger completed instruction commit? ::: No, it is flushed.