Reorder buffer (ROB): Exercises — Hardware deep dive

This page is a self-test ladder. Each rung asks a little more of you than the last. Cover the solution, try the problem, then reveal. Every symbol used here was built in the parent ROB note — if a term feels unfamiliar, jump back and re-read before continuing.

Quick vocabulary refresher (all from the parent note), so line one makes sense:

Definition The words you must have loaded

Head pointer — points at the oldest instruction, the next one allowed to retire.
Tail pointer — points at the next free slot, where a newly issued instruction is written.
Retire / commit — the moment an instruction's result is copied from the ROB into the permanent (architectural) register file, in program order.
Issue — an instruction is given a ROB entry, in program order (this happens before it executes).
Flush — throwing away ROB entries younger than some point, because they turned out to be wrong (mispredicted branch) or must never have happened (exception).
==Status = Pending== — the entry has been issued but its result has not yet been computed (execution not finished). Its value field is still empty (?).
==Status = Completed== — execution finished and the result value is written into the ROB, but not yet copied to the architectural register file. A Completed entry is eligible to retire, but only when it reaches the head in program order.
==Status = Exception== — the instruction faulted (e.g. divide-by-zero); it carries no valid result and, when it reaches the head, triggers the exception instead of committing.

Everything below uses a circular buffer of $N$ entries with indices $0, 1, \dots, N - 1$ that wrap around using $mod N$ (remainder after dividing by $N$ ). If "mod" is fuzzy: $7 mod 4 = 3$ because $7 = 1 \times 4 + 3$ , and the leftover is $3$ .

The picture below is the mental model to hold for the whole page. Study it before Exercise 1.1: the six numbered circles are the fixed physical slots; the pale-yellow HEAD arrow marks the oldest live instruction (retire from here), the pink TAIL arrow marks the next free slot (issue writes here). Blue circles are Completed entries, the pink circle is a Pending entry, and empty (board-coloured) circles are free. Notice that HEAD and TAIL are just indices that walk around the ring, wrapping $5 \to 0$ via $mod N$ — that wrap is the whole reason the buffer is drawn as a circle, not a line.

Level 1 — Recognition

Goal: can you read a ROB snapshot and state facts about it?

Exercise 1.1

An 8-entry ROB currently has $head = 3$ and $tail = 3$ . What state is the ROB in — empty or full? Explain which rule tells you.

Recall Solution 1.1

The parent note gave two rules:

Empty condition: $head = tail$
Full condition: $(tail + 1) mod N = head$

Here $head = tail = 3$ , so the empty rule fires. The ROB is empty.

Why the two rules must differ: if we let a completely full buffer also satisfy $head = tail$ , we could not tell "full" and "empty" apart — they'd look identical. So we deliberately keep one slot sacrificed: full is declared one step before the pointers collide. That is why the full rule is $(tail + 1) mod N = head$ , not $tail = head$ .

Exercise 1.2

A 4-entry ROB has this snapshot. Which single instruction is eligible to retire this cycle?

Entry	Inst	Status
0	I1	Completed
1 (H)	I2	Pending
2	I3	Completed
3	I4	Completed

Recall Solution 1.2

Retirement is in program order from the head. The head is at entry 1 (I2). To retire, the head instruction must be Completed.

I2 is Pending, so retirement stalls — even though I3 and I4 are done. No instruction retires this cycle.

Note: I1 in entry 0 is older by index but it is behind the head — it has already retired in a previous cycle (that is why the head moved past it). It is not a candidate.

Level 2 — Application

Goal: run the pointer machinery yourself.

Exercise 2.1

An $N = 6$ ROB starts at $head = 4$ , $tail = 4$ (empty). You issue 5 instructions, then retire 3. Give the final $head$ and $tail$ .

Recall Solution 2.1

Issuing advances the tail (one slot per issue); retiring advances the head.

Issue 5 times from $tail = 4$ : $tail = (4 + 5) mod 6 = 9 mod 6 = 3.$ Retire 3 times from $head = 4$ : $head = (4 + 3) mod 6 = 7 mod 6 = 1.$

Final: $head = 1$ , $tail = 3$ .

Sanity check — occupancy = number issued minus number retired = $5 - 3 = 2$ live instructions. Occupancy from pointers is $(tail - head) mod N = (3 - 1) mod 6 = 2$ . ✓ Matches.

Exercise 2.2

Same 6-entry ROB. It is currently full. How many valid (occupied) entries does it hold — is it $6$ or $5$ ?

Recall Solution 2.2

Because "full" is declared when $(tail + 1) mod N = head$ , one slot is always kept empty as the tie-breaker between full and empty. So a "full" 6-entry ROB holds ==5 valid instructions==, not 6.

(Real designs often add a separate 1-bit "full" flag so they can use all $N$ slots and drop the sacrificed slot. But with the pointers-only scheme the parent described, usable depth is $N - 1$ .)

Level 3 — Analysis

Goal: reason about correctness, not just mechanics.

Exercise 3.1 — Newest-writer operand lookup (with wrap-around)

A 6-entry ROB whose live region has wrapped past the top of the ring: the tail index sits below the head index. The live entries, in program order (oldest first), occupy slots $4, 5, 0, 1$ . The head is at slot 4; the tail (next free) is at slot 2:

Entry	Dest	Status	Value	Program order
4 (H)	R1	Completed	25	oldest
5	R4	Completed	15	2nd
0	R1	Pending	?	3rd
1	R7	Completed	40	newest
2 (T)	—	free	—	—
3	—	free	—	—

A new instruction (issued into the tail region) needs source register R1. Which entry does it read/wait for, and how do you scan the ring backwards across the $5 \to 0$ boundary?

Recall Solution 3.1

The lookup scans from the tail backwards toward the head for the newest entry whose dest = R1. Because the region wrapped, "backwards from the tail" means: start just before the tail and decrement with $mod N$ , so the scan order of live slots is $1 \to 0 \to 5 \to 4 (each step is (idx - 1) mod 6) .$ Notice the step $0 \to 5$ : that is the wrap — decrementing index $0$ gives $(0 - 1) mod 6 = 5$ , exactly crossing the top-of-ring boundary. This is the only subtle part; the logic is otherwise identical to the non-wrapped case.

Scanning $1, 0, 5, 4$ : the first (newest) match for R1 is slot 0 (entry 1 writes R7, not R1). Slot 0 is Pending, so the new instruction does not grab the older R1=25 from slot 4. It tags itself to ROB slot 0 and waits for that broadcast.

Why newest wins even across the wrap: R1 was defined at slot 4, then redefined at slot 0; slot 0 is later in program order (3rd vs oldest), so a subsequent read must see slot 0's (future) value, not the stale 25. The physical index being numerically smaller is irrelevant — program order, tracked by the pointer walk, is what counts. This "newest matching writer" search is exactly register renaming in action.

The figure below draws exactly this wrapped snapshot so you can watch the backward scan cross the boundary.

Exercise 3.2 — Precise exception boundary

A 4-entry ROB, head at entry 1:

Entry	Inst	Status
1 (H)	I2	Completed
2	I3	Exception (DIV/0)
3	I4	Completed
0	I5	Completed

I4 and I5 are already computed. Which results reach the architectural register file, and which are discarded?

Recall Solution 3.2

Retire from the head in order:

Retire I2 (Completed) → commits. ✓
Head reaches I3 → it carries an Exception. Retirement stops here. We do not commit I3's (garbage) result; instead we take the exception.
Flush everything younger than I3: entries 3 (I4) and 0 (I5) are thrown away — even though they finished executing.

Committed: only I2 (plus anything older that retired earlier). Discarded: I3, I4, I5.

This is the definition of a precise exception: state reflects all instructions before the fault and none at-or-after it. The in-order retirement discipline gives it for free — the fault can only take effect once it becomes the oldest instruction.

Level 4 — Synthesis

Goal: combine pointer math, timing, and performance reasoning.

Exercise 4.1 — Branch misprediction flush count (no wrap and wrap cases)

A 16-entry ROB. A mispredicted branch sits at entry $k = 5$ , and the tail (next free) is at entry $12$ .

(a) How many entries are flushed? (b) Now suppose instead the branch is at $k = 14$ and the tail is at entry $3$ — so the younger, speculative entries wrap across the $15 \to 0$ boundary. How many entries are flushed, and does the same formula still work?

Recall Solution 4.1

The flush count is always "number of live entries strictly younger than the branch," which is the ring-distance from the slot after the branch up to (but not including) the tail: $flush = (tail - (k + 1)) mod N .$

(a) No wrap. Younger entries are $6, 7, 8, 9, 10, 11$ (entry 12 is the free tail). $flush = (12 - 6) mod 16 = 6.$ 6 entries flushed. The branch at slot 5 is kept — it is a real, correct instruction; only its prediction was wrong.

(b) Wrap. Younger entries are $15, 0, 1, 2$ — the range crosses the top-of-ring boundary $15 \to 0$ . Plugging in $k = 14$ , $tail = 3$ : $flush = (3 - (14 + 1)) mod 16 = (3 - 15) mod 16 = (- 12) mod 16 = 4.$ 4 entries flushed — and indeed listing them ( $15, 0, 1, 2$ ) gives 4. The same $mod N$ formula handles the wrap automatically: the negative intermediate $- 12$ is folded back into range by $mod$ , which is precisely why the circular-buffer arithmetic is written with $mod$ everywhere. No special "did we wrap?" branch is needed in hardware.

Exercise 4.2 — ROB-limited IPC

The parent gave the performance model: $IPC = min (ILP_{available}, \frac{N}{L}) .$ A program has $ILP_{available} = 4$ independent instructions per cycle. The longest dependency chain has average latency $L = 5$ cycles. Compute the sustained IPC for (a) $N = 16$ and (b) $N = 32$ . Which resource limits each case?

Recall Solution 4.2

(a) $N = 16$ : $\frac{N}{L} = \frac{16}{5} = 3.2$ . Then $IPC = min (4, 3.2) = 3.2$ . The ROB is the bottleneck — the window is too small to expose all 4-wide parallelism given the 5-cycle occupancy.

(b) $N = 32$ : $\frac{N}{L} = \frac{32}{5} = 6.4$ . Then $IPC = min (4, 6.4) = 4$ . Now the program's ILP (4) is the bottleneck — enlarging the ROB further buys nothing.

Interpretation: $N / L$ is "how many instructions we can keep in flight given each stays $L$ cycles." Growing $N$ helps only until it exceeds $ILP_{available} \times L = 4 \times 5 = 20$ . Beyond $N = 20$ the min is pinned by ILP. So the smallest ROB that reaches full IPC here is $N = ⌈ ILP \cdot L ⌉ = 20$ .

The plot below draws both terms and the $min$ between them, so you can see the "knee" where the limit switches from ROB to ILP. Look at the yellow curve: it rises along the blue $N / L$ dashed line until the knee at $N = 20$ , then flattens onto the pink ILP ceiling; the two marked dots are exactly the $N = 16$ and $N = 32$ answers above.

Level 5 — Mastery

Goal: design-level reasoning where several structures interact.

Exercise 5.1 — Sizing a balanced machine

You are designing a superscalar core (see Superscalar-processors) that issues and retires up to 4 instructions per cycle. Loads have latency $L = 5$ cycles and dominate the dependency chains. You want the ROB large enough that it never becomes the retirement bottleneck for this workload.

(a) What is the minimum ROB size $N$ ? (b) You also have separate Reservation-stations. If an instruction occupies a reservation station for only 1 cycle after operands arrive but sits in the ROB for up to $L = 5$ cycles, roughly what ratio of ROB entries to reservation stations keeps them balanced?

Recall Solution 5.1

(a) The machine wants sustained $IPC = 4$ . From $IPC = min (ILP, N / L)$ , we need $\frac{N}{L} \geq ILP \Rightarrow N \geq ILP \times L = 4 \times 5 = 20.$ Minimum $N = 20$ entries. (Real cores round up generously — e.g. 32, 64, 224 — to tolerate cache misses that stretch $L$ far beyond 5.)

(b) Little's-law intuition: occupancy $=$ arrival-rate $\times$ residence-time. Both structures see the same arrival rate (4/cycle). A reservation station is held ~1 cycle; a ROB entry ~ $L = 5$ cycles. So $\frac{ROB entries}{reservation stations} \approx \frac{L}{1} = \frac{5}{1} .$ Roughly 5× as many ROB entries as reservation stations. This matches the parent's remark that an instruction can leave its reservation station after ~1 cycle yet linger in the ROB for many cycles — so the commit-side buffer must be the deeper one.

Recall One-line self-checks (cloze)

A completed instruction cannot retire while an older instruction is still ::: pending (in-order retirement). The full condition for an $N$ -entry ROB is ::: $(tail + 1) mod N = head$ . On operand lookup we search for the ::: newest (closest-to-tail) matching writer. A mispredicted branch flushes all entries ::: younger than the branch, keeping the branch itself. ROB-limited IPC caps at ::: $min (ILP_{available}, N / L)$ .

Related deep-dive threads: Register-renaming, Tomasulo-algorithm, Precise-exceptions, Speculative-execution, Branch-prediction, Instruction-retirement, Memory-ordering, Register-file-management.