Reorder buffer (ROB): Question bank — Hardware deep dive

This is a rapid-fire misconception hunt for the Reorder buffer (ROB). Each line is a single reveal: read the prompt, answer out loud, then check. The answers give reasoning, not a bare "yes/no" — that reasoning is the point.

Prerequisite ideas you should already picture: Out-of-order execution feeding into an in-order retirement stage, tags flowing from Reservation-stations, and the whole thing serving Precise-exceptions.

Picture the ROB first

Before the traps, anchor the mental image. The ROB is a ring of slots. New instructions enter at the tail, walk their way around, and leave (retire) at the head. Between issue and retire, every slot carries a small status.

What limits how fast the ROB retires? (the IPC bound)

The performance formula uses three symbols. Let's earn each one before combining them.

Now the bound:

$IPC \leq min (ILP_{available}, \frac{N}{L})$

True or false — justify

The ROB retires instructions in the order they finished executing.

False. It retires strictly in program order from the head; finishing early only lets an entry sit in the Completed state and wait — it never lets a younger instruction commit before an older one.

An instruction leaves its reservation station and its ROB entry at the same moment.

False. It frees the reservation station the cycle it starts executing (scheduling is done), but keeps the ROB entry until it becomes the head and retires — often many cycles later.

A completed instruction has already written its result to the architectural register file.

False. Completed means the value sits in its ROB entry. The write to the architectural register file happens only at retire, when it reaches the head.

If head == tail, the ROB is full.

False. head == tail is the empty condition. Fullness is (tail + 1) mod N == head, which deliberately wastes one slot so the two states are distinguishable.

The ROB alone can enforce that two loads and a store to the same address stay ordered.

False. The ROB orders retirement of the store's architectural effect, but load/store value dependencies need a separate load-store queue; see Memory-ordering.

False. In a ROB-based scheme the ROB entry number is the tag — the newest matching ROB entry renames a register, which is exactly Register-renaming done inside the buffer.

Flushing on a branch misprediction throws away instructions older than the branch.

False. Only entries after the branch (the wrong-path speculative instructions) are flushed; everything at or before the branch is real and stays. See Branch-prediction.

A precise exception means the faulting instruction's result is discarded but the ones after it commit normally.

False. Precise means all instructions before the fault are committed and the faulting one and everything after are discarded — the machine looks like it stopped exactly at the fault.

Doubling the ROB size always doubles IPC.

False. IPC is capped by

min (ILP_{available}, N / L)

. Once ROB size is no longer the bottleneck (limited by the program's parallelism or by dependency-chain latency

L

), a bigger

N

does nothing.

An instruction with no destination register (like a store or a branch) still needs a ROB entry.

True. It needs an entry to preserve program order for retirement, exception status, and PC — even though it writes no register value.

Spot the error

"When I3 completes before I1, we immediately write I3's result to the register file to save time."

Wrong: that breaks in-order state. If an older instruction (I1) later faults, the file would already hold I3's value — an instruction that "should never have happened." Results wait in the ROB until retire.

"To find the source operand, scan the ROB from head to tail and take the first match."

Wrong direction. You want the newest writer of that register, so scan from the tail backward — the most recent matching entry is the correct producer.

"On a mispredicted branch we flush the whole ROB and restart fetch."

Wrong: you'd kill valid older work. Flush only the entries younger than the branch; the branch and everything before it are correct-path instructions.

"Since the ROB is a FIFO, we can allocate a new entry anywhere there's a free slot."

Wrong: allocation must be at the tail in program order. Arbitrary allocation destroys the ordering that makes in-order retirement (and precise exceptions) possible.

"The empty and full conditions are both head == tail, so we're stuck — the design is broken."

Wrong: there are two working designs, pick one. Design A (sacrificial slot): keep

N - 1

usable entries so full becomes (tail+1) mod N == head — simple comparison, but wastes one slot. Design B (occupancy counter): keep a count of valid entries; full is count == N, empty is count == 0 — uses all

N

slots but needs an extra increment/decrement each cycle. Both are standard; the trade-off is one wasted slot versus one extra counter.

"An instruction that raised an exception is flushed the instant it's detected during execution."

Wrong: the entry enters the Exception state and the fault is only acted upon when that entry reaches the head. Acting early could flush on a wrong-path instruction that never should retire.

"The ROB stores the actual operand values an instruction needs to execute."

Wrong: operand waiting is the reservation station's job. The ROB stores each instruction's produced result (once Completed) plus bookkeeping, not the inputs it's waiting on.

Why questions

Why must retirement be in-order even though execution is out-of-order?

Because the architectural state (registers, memory) must match a sequential program run so exceptions and interrupts are precise; only in-order commit guarantees older effects land before younger ones.

Why is the ROB entry number used as the operand tag instead of the register name?

Multiple in-flight instructions may target the same register name, so the name is ambiguous. The ROB index is unique per in-flight instruction, letting a consumer wait for exactly one producer — this is what makes Tomasulo-style renaming work.

Why does a store often occupy its ROB entry far longer than its execution latency?

Because it must wait to become the head before its memory write becomes architecturally visible; execution (address/data ready) can finish quickly, but commit is gated by program order.

Why does Speculative-execution need the ROB to be safe?

Speculative results live only in ROB staging entries, never in architectural state. If the speculation was wrong, flushing those entries erases the work with zero visible side effects.

Why does a longer dependency-chain latency

L

reduce achievable IPC for a fixed ROB size

N

Instructions in a long chain occupy their ROB entries longer waiting for producers, so fewer distinct instructions can be in flight per cycle; the throughput ceiling

N / L

drops as

L

grows.

Why can a superscalar machine retire several instructions in one cycle?

Because if the head and the next few entries are all Completed and in order, there's no ordering violation in committing them together — retirement width is a hardware choice, not a correctness limit.

Edge cases

What happens if the instruction at the head is still Issued (Pending) while every younger entry is Completed?

Nothing retires. Retirement is head-gated, so the whole ROB stalls on that one entry — this is exactly the case where a slow load can block commit of many finished instructions.

What if an exception-marked entry is not at the head yet?

It waits in the Exception state. The fault only triggers flush + handler when it becomes the head — younger instructions ahead of it in age but past it in program order have already retired correctly.

What if a branch is mispredicted but the branch entry itself hasn't reached the head?

Recovery (flush of younger entries + fetch redirect) can happen as soon as the branch resolves, without waiting for retirement, because only wrong-path entries are removed and the branch stays; its own architectural effect still commits at the head.

What does the ROB look like at the exact instant it becomes empty?

head == tail and every entry is Invalid — the wrap-around pointers coincide. The next issued instruction goes at the tail and both pointers begin diverging again.

Can two instructions writing the same architectural register both live in the ROB at once?

Yes — that's the whole point of renaming. Both coexist as distinct entries; a consumer reads the newest one, and at retirement the older one's write is simply overwritten (or its file write is harmless) preserving program-order semantics.

What happens on retirement if the destination register value equals the value already in the file?

The write still occurs (or is a harmless no-op); correctness doesn't depend on the value differing — it depends on the write happening in program order at the head.

Recall One-line self-test

Cover everything and answer: what three things does the head pointer gate? Answer ::: (1) in-order write to the architectural register file, (2) triggering of a precise exception, and (3) freeing of the entry so the tail can wrap into it.