Reorder buffer (ROB): Visual walkthrough — Hardware deep dive

This page rebuilds the reorder buffer as pictures. We start with nothing — just a row of boxes — and slowly grow every piece: the two pointers, the wrap-around, the out-of-order fill, the in-order drain, and the flush. Every symbol is drawn before it is used.

If you have not met the vocabulary yet, skim the parent topic first — but you do not need it. We build from zero here.

Step 1 — What problem are we even drawing?

WHAT: Two orderings live at once — the finish order (chaotic) and the commit order (must be the original program order).

WHY: We need one structure that lets execution be chaotic while making commitment tidy. That structure is the reorder buffer.

PICTURE: Look at the figure. The top track is the order instructions finish (jumbled arrows). The bottom track is the order they must commit (a neat left-to-right line). The ROB is the funnel between them.

Step 2 — Draw the buffer: a row of boxes and two fingers

WHAT: The ROB is nothing more than $N$ identical slots in a row. We will use $N = 8$ in all pictures. Each slot can hold one in-flight instruction.

WHY a row of fixed size? Hardware is finite — there is no "infinite list". A fixed count $N$ is the maximum number of in-flight instructions, called the execution window.

We place two "fingers" (pointers) on the row:

$head$ — the finger that drains. Everything to its "past" is already gone.
$tail$ — the finger that fills. Everything to its "future" is still empty.

PICTURE: Eight boxes labelled $0..7$ . Green finger = head, orange finger = tail. Empty ROB means both fingers sit on the same box.

Recall

What does the tail pointer point at? ::: The next free slot — where the next issued instruction will be written.

Step 3 — Issue: fill boxes in program order (tail moves)

WHAT: As each instruction is issued (decoded and admitted), it is written into the slot at tail, then tail steps forward by one.

WHY in program order? Because the whole trick relies on the positions in the buffer encoding "who came first". If we filled boxes out of order, head could no longer mean "oldest". Order in = order of slots.

Take four instructions in program order:

I1: ADD R1, R2, R3
I2: SUB R4, R1, R5   (needs R1 from I1)
I3: MUL R6, R7, R8
I4: DIV R9, R4, R6   (needs R4 from I2 and R6 from I3)

Each grabs the next slot. After issuing all four: head=0 (still pointing at I1), tail=4.

PICTURE: Slots $0, 1, 2, 3$ now hold I1..I4, all marked pending (result not computed yet). head still at $0$ , tail moved to $4$ .

Step 4 — Execute: results arrive out of order (fill values, don't drain)

WHAT: Instructions run on the functional units and finish at different times. A fast MUL might finish before a slow ADD that came earlier. When one finishes, we write its value into its own slot and flip that slot to completed — but we do not move head.

WHY not commit immediately? Because the slot might be after the head. Committing it now would let a younger instruction's result become visible before an older one — breaking program order, and possibly exposing work from an instruction that a future exception should erase.

Say I3 (MUL) finishes first with $R 6 = 120$ , then I1 (ADD) with $R 1 = 25$ :

PICTURE: Slots for I1 and I3 turn violet (completed) with their values shown; I2 and I4 stay pending. Crucially the green head finger has not moved — it still points at slot $0$ (I1). Notice I3 is completed but stuck, because I2 in front of it is not.

Step 5 — Retire: drain from the head, in order (head moves)

WHAT: Each cycle we look only at the slot under head. If it is completed, we copy its value into the architectural register file, free the slot, and step head forward. If it is pending, we stall — nobody behind may pass.

Trace it:

Head at I1 (completed) → write $R 1 = 25$ to the register file, head→1.
Head at I2 (pending) → stall, even though I3 behind it is finished.
Later I2 completes with $R 4 = 15$ → retire I2, head→2. Then I3 already completed → retire I3 ( $R 6 = 120$ ), head→3.

WHY the wrap matters now: after enough retirements the head walks off the right end. mod N sends it back to slot $0$ , which by now is free again. The row behaves like a ring — this is why the ROB is a circular FIFO.

PICTURE: The eight slots bent into a circle. Green head arrow rotating clockwise as it drains; orange tail arrow ahead of it filling. The gap between them is the in-flight window.

Recall

Why is the ROB drawn as a circle, not a line? ::: Because head and tail advance with mod N; after slot $N - 1$ they wrap to slot $0$ , reusing freed slots forever — that is a circle, not a dead-ending line.

Step 6 — The edge cases: full, empty, and the fence between them

WHAT: Two dangerous corners: the buffer empty (nothing to retire) and the buffer full (no slot to issue into). We must be able to tell them apart, because in a pure circle head == tail could mean either.

WHY sacrifice a slot? Because with $N$ slots and both conditions using pointer equality, we need a "gap of one" to keep the meanings separate. Cost: one slot; benefit: unambiguous state. (Alternatives exist — a separate count register — but the fence is the classic textbook picture.)

Degenerate case — full ROB stalls issue: if the buffer is full, the front end simply stops issuing until the head retires something. The chaos of execution is bounded by $N$ .

PICTURE: Two mini-rings side by side. Left ring: head and tail on the same slot → labelled EMPTY. Right ring: tail one slot behind head, one grey "fence" slot → labelled FULL.

Step 7 — The flush: erasing the future in one stroke

WHAT: Suppose the head instruction raises an exception (e.g. divide-by-zero), or a branch at some slot $k$ turns out mispredicted so every slot after it is wrong-path work. We flush: throw away every slot from just after the offending one up to the tail, and set tail back.

WHY this is safe — and why the ROB earns its name: the discarded instructions never touched the register file; their results were only ever sitting in ROB slots (Step 4). Deleting a slot deletes the result. The architectural state still reflects exactly everything up to and including slot $k$ 's predecessors, and nothing after — which is precisely the definition of a precise state.

PICTURE: The ring with branch at slot $k$ (magenta). Slots $k + 1, k + 2$ are wrong-path (crossed out); a big sweep arrow snaps tail back to $k + 1$ . The head side is untouched — committed work survives.

Recall

Why can a mispredicted branch be recovered with zero damage? ::: Because speculative results lived only in ROB slots, never in architectural registers; resetting tail past the branch discards them before any of them could commit.

Step 8 — The window and IPC: why a bigger ROB helps (up to a point)

WHAT: The number of slots $N$ is the width of the window we can see forward for independent work. More slots → more instructions in flight → more chances to overlap.

WHY the min? Two ceilings, and you hit the lower one:

If the program has little parallelism, growing $N$ does nothing — $ILP_{available}$ caps you.
If the buffer is too small, it fills and stalls issue (Step 6) — $N / L$ caps you.

Degenerate readings: with $N = 1$ the ROB is a plain in-order pipeline (window of one). As $N \to \infty$ , IPC saturates at $ILP_{available}$ — extra slots become useless once the program's parallelism is exhausted.

PICTURE: IPC on the vertical axis versus ROB size $N$ on the horizontal. A rising line $N / L$ that bends flat when it hits the horizontal ceiling $ILP_{available}$ — the "knee" is the smallest worthwhile ROB.

The one-picture summary

Everything in one frame: the ring of slots, head draining committed values into the register file (in order), tail filling new issues (in order), out-of-order completed values glowing inside the ring, and a flush arrow ready to snap the tail back on a mispredict.

Recall Feynman retelling — say it like a story

Picture a ticket queue drawn as a ring of eight chairs. Two ushers walk it: the tail usher seats new arrivals one chair at a time, always in the order they arrive off the street — that is issue, and it keeps the program's order baked into the seating. The people then get their food (execute) at wildly different speeds; a fast eater three chairs back may finish first, but he is not allowed to leave — his tray just gets marked "done". Only the head usher lets people out, and only the person in the very front chair, and only if their tray is done — that is retire in program order, the only moment anything becomes real (written to registers). When the ushers' chairs meet, we read the gap: same chair means the room is empty; one chair apart (with a kept-empty fence chair) means full, so we stop seating. And if the front person turns out to hold a bad ticket (an exception or a wrong-guess branch), we don't chase anyone down — we just tell the tail usher "everyone seated after that chair was never here", snapping his position back. Because none of those people had left the room (nothing hit the registers), erasing them costs nothing and the outside world sees a perfectly clean, in-order story — the whole point of the reorder buffer. Wider room ( $N$ ) means more overlap, but only until the program runs out of independent diners to seat.

Related builds: Register-renaming, Reservation-stations, Instruction-retirement, Memory-ordering, Superscalar-processors.