Reorder buffer (ROB)

Overview

The reorder buffer is the central bookeeping structure in out-of-order processors that enables in-order retirement of instructions while allowing out-of-order execution. It solves the fundamental problem: "How do we execute instructions whenever their operands are ready, yet maintain the illusion that the program executed sequentially?"

---

Core Problem & Solution

The Three-Phase Model

1. Issue → Instruction gets a ROB entry (in program order) 2. Execute → Instruction runs out-of-order when ready 3. Retire/Commit → Oldest completed instruction writes to architectural state (in program order)

---

ROB Structure & Operation

The ROB has two pointers:

• Head pointer → oldest instruction (next to retire)
• Tail pointer → next free entry (where new instruction goes)

---

Derivation: Why Circular FIFO?

Let's derive why the ROB must be a circular queue from first principles.

Requirement 1: Instructions must retire in program order → Need FIFO (first-in-first-out) discipline

Requirement 2: Finite hardware resources → Can't have unbounded queue; need fixed-size buffer with $N$ entries

Requirement 3: Continuous operation → As instructions retire (freing head), new instructions issue (filling tail)

Problem: With linear array indices $0$ to $N-1$:

• Head advances: $\text{head} = \text{head} + 1$
• Tail advances: $\text{tail} = \text{tail} + 1$
• After $N$ retirements, head reaches end of array
• Need to wrap around to reuse freed entries

Solution: Use modulo arithmetic for circular indexing:

$\text{next\_head} = (\text{head} + 1) \mod N$

$\text{next\_tail} = (\text{tail} + 1) \mod N$

Full condition (tail catches head): $(\text{tail} + 1) \mod N = \text{head}$

Empty condition (head catches tail): $\text{head} = \text{tail}$

---

Step-by-Step ROB Operation

Initial state: Empty ROB (Head=0, Tail=0)

Instructions in program order:
I1: ADD R1, R2, R3
I2: SUB R4, R1, R5  (depends on I1)
I3: MUL R6, R7, R8
I4: DIV R9, R4, R6  (depends on I2 and I3)

Cycle 1-4: Issue Phase

ROB Entry	Inst Dest	Value	Status
0 (H)	I1	R1	?
1	I2	R4	?
2	I3	R6	?
3 (T)	I4	R9	?

Head=0, Tail=4 (wraps to 0 in next cycle)

Cycle 7: Execution (out-of-order completion)

Suppose I3 (MUL) completes first (fastest operation), then I1 (ADD):

| ROB Entry | Inst | Dest | Value | Status | |-----------|------|-------|-----------| | 0 (H) | I1 | R1 | 25 | Completed | | 1 | I2 | R4 | ? | Pending | | 2 | I3 | R6 | 120 | Completed | | 3 | I4 | R9 | ? | Pending |

Why don't we write R6=120 to register file yet? Because I1 hasn't retired—we maintain program order for architectural state.

Cycle 8: Retirement

I1 is oldest AND completed → Retire I1

• Write R1=25 to architectural register file
• Free ROB entry 0
• Head advances to 1

| ROB Entry | Inst | Dest | Value | Status | |-----------|------|------|-----------| | 1 (H) | I2 | R4 | ? | Pending | | 2 | I3 | R6 | 120 | Completed | | 3 | I4 | R9 | ? | Pending |

Cycle 10: I2 completes

ROB Entry	Inst	Dest	Value	Status
1 (H)	I2	R4	15	Completed
2	I3	R6	120	Completed
3	I4	R9	?	Pending

Cycle 11: Retire I2, then I3

Both I2 and I3 are completed and in order:

• Retire I2: Write R4=15, Head→2
• Retire I3: Write R6=120, Head→3

Only I4 remains pending.

---

Detailed Mechanics: Operand Forwarding

1. Check ROB (from tail backwards to head) for newest instruction writing $R_k$
2. If found with status=completed: Forward value directly
3. If found with status=pending: Tag the ROB entry, wait for broadcast
4. If not found: Read from architectural register file

Why this works: The ROB entry number becomes a physical register tag. Instead of "wait for R1", the instruction waits for "wait for ROB entry 7".

Example derivation of operand lookup:

For instruction neding source register $R_k$:

\text{ROB}[i].\text{value} & \text{if } \exists i: \text{ROB}[i].\text{dest} = R_k \text{ and } \text{ROB}[i].\text{complete} = \text{true} \\ \text{wait}(\text{ROB}[i]) & \text{if } \exists i: \text{ROB}[i].\text{dest} = R_k \text{ and } \text{ROB}[i].\text{complete} = \text{false} \\ \text{RF}[R_k] & \text{otherwise} \end{cases}$$ Where $i$ is the **newest** (closest to tail) matching entry. --- ## Precise Exceptions with ROB > [!intuition] How ROB Enables Precise Exceptions > An exception is **precise** if the processor state reflects all instructions before the faulting instruction and none after. The ROB makes this trivial: **When instruction at ROB head causes exception**: 1. Flush all younger instructions (all entries after head) 2. Architectural state already reflects all older instructions (already retired) 3. Jump to exception handler with correct PC **Example**: Division by zero at I3 | ROB Entry | Inst | Status | Exception | |-----------|------|--------| | 0 | I1 | Completed | - | | 1 (H) | I2 | Completed | - | | 2 | I3 | Exception | DIV/0 | | 3 | I4 | Completed | - | **Retirement process**: - Retire I1 ✓ - Retire I2 ✓ - Try retire I3 → **Exception detected** - **Flush** ROB entries 3,4,... - Precise state: I1, I2 committed; I3, I4 never happened --- ## ROB vs. Reservation Stations > [!definition] Complementary Structures > - ==Reservation stations== hold instructions **waiting for operands** (execution scheduling) > - ==ROB== holds instructions **waiting to retire** (commit scheduling) **Information flow**: ``` Issue → ROB entry allocated + Reservation station allocated Execute → Reservation station freed, result written to ROB Retire → ROB entry freed, result written to register file ``` **Key difference**: An instruction might leave its reservation station after1 cycle (executed) but stay in ROB for50 cycles (waiting for older instructions to retire first). --- > [!example] Branch Misprediction Recovery **Scenario**: Branch at I2 predicted taken, but actually not taken ``` I1: ADD R1, R2, R3 I2: BEQ R4, R5, target (predicted taken, actually not taken) I3: SUB R6, R7, R8 (wrong path, speculatively issued) I4: MUL R9, R10, R11 (wrong path) I5: (correct path) (not issued yet) ``` **When branch resolves (misprediction detected)**: 1. Branch instruction at ROB entry $k$ marked mispredicted 2. **Flush** all ROB entries after $k$ (I3, I4) 3. Redirect fetch to correct target (PC of I5) 4. All speculative work discarded **before** it commits **Why ROB makes this safe**: Results from I3, I4 never reached architectural state (still in ROB staging area). --- ## Performance Analysis > [!formula] ROB Size Impact on IPC **Execution window**: Maximum number of in-flight instructions = ROB size $N$ Instruction-level parallelism (ILP) utilization: $$\text{IPC} = \min\left(\text{ILP}_{\text{available}}, \frac{N}{L}\right)$$ Where: - $N$ = ROB size - $L$ = Average latency of longest dependency chain - $\text{ILP}_{\text{available}}$ = Independent instructions per cycle in program **Why this formula?** - **Numerator** $N$: Total in-flight instruction capacity - **Denominator** $L$: How long instructions occupy ROB on average - Result: Effective instruction retirement rate **Derivation of optimal ROB size**: Given a processor with: - $W$ issue width (instructions/cycle) - $D$ average instruction dependency distance Expected in-flight instructions for full issue bandwidth: $$N_{\text{optimal}} = W \times D$$ **Example**: 4-wide issue, 10-cycle average dependency chain → Need ROB size ≥ 40 entries for full bandwidth --- ## Common Mistakes & Misconceptions > [!mistake] "ROB speeds up execution" **Why this feels right**: ROB is in the critical path, so it must improve performance. **Reality**: ROB itself doesn't speed up execution—functional units do that. ROB enables the **opportunity** for speedup by: 1. Allowing out-of-order execution (performance) 2. Maintaining precise state (correctness) **The fix**: Think of ROB as ==permission machinery==. It permits the processor to be aggressive (speculate, execute out-of-order) while maintaining a safety net. --- > [!mistake] "ROB entries are freed when instruction completes" **Why this feels right**: Instruction is done, why keep it around? **Reality**: ROB entry holds result until instruction **retires** (commits). Completion≠ retirement. **Example timeline**: - Cycle 5: Instruction completes (writes ROB entry) - Cycle 5-20: Waits in ROB for older instructions - Cycle 20: Retires (writes register file, frees ROB) **Why**: Must maintain in-order commit for precise exceptions and correct program semantics. --- > [!mistake] "Larger ROB always means better performance" **Why this feels right**: More in-flight instructions = more parallelism. **Reality**: Diminishing returns + complexity cost. **Bottleneck analysis**: $$\text{IPC} = \min(\text{IPC}_{\text{ROB}}, \text{IPC}_{\text{functional\_units}}, \text{IPC}_{\text{memory}})$$ If functional units are the bottleneck (saturated execution ports), enlarging ROB doesn't help. **Optimal sizing**: ROB should be large enough to hide the longest latency event (typically cache miss ~200 cycles). Beyond that, cost/benefit decreases. Typical sizes: - Mobile: 40-60 entries - Desktop: 100-150 entries - Server: 200-300 entries --- ## Hardware Implementation Details > [!formula] CAM (Content-Addressable Memory) for Operand Matching When a result broadcasts on the common data bus: **Problem**: Which instructions need this result? **Solution**: ROB entries store source tags, CAM searches all entries in parallel: $$\text{Match}_i = (\text{SourceTag}_i == \text{BroadcastTag}) \land \text{Valid}_i$$ **Energy cost**: CAM search on every broadcast = high power **Optimization**: ==Wakeup-select== two-stage scheduling 1. Wakeup: CAM identifies ready instructions 2. Select: Pick subset to issue (priority logic) --- > [!example] Superscalar ROB: Multi-Instruction Retirement 4-wide superscalar processor can retire up to 4 instructions per cycle. **Requirements**: 1. All 4 are completed 2. All 4 are consecutive from head 3. No exceptions in any of the 4 **Retirement bandwidth**: $$\text{Retire\_BW} = \min\left(W_{\text{retire}}, \sum_{i=0}^{W_{\text{retire}}-1} \mathbb{1}[\text{ROB}[\text{head}+i].\text{complete}]\right)$$ **Example**: Head points to entry 10 | Entry | Complete | Exception |-------|----------|-----------| | 10 | Yes | No | | 11 | Yes | No | | 12 | No | No | | 13 | Yes | No | Can only retire 2 instructions (10, 11) because12 blocks 13. --- ## ROB in Modern Processors **Intel Skylake** (2015): - 224-entry ROB - Unified reservation station (97 entries) - ~4-5 cycle penalty for mispredicted branch flush **Apple M1** (2020): - ~630-entry ROB (estimated, not officially published) - Massive window for hiding memory latency - Enables aggressive prefetching + out-of-order **AMD Zen 3** (2020): - 256-entry ROB - Separate integer/FP schedulers - Fast retirement: 8ops/cycle bandwidth --- > [!recall]- Explain to a 12-year-old > Imagine you're a teacher with a classroom of students taking a test. You want students to finish problems as fast as they can (out-of-order), but you need to grade papers in the order students sit (in-order) to be fair. The ROB is like a **staging shelf** behind your desk: 1. As students finish (execute), they put papers on the shelf 2. Papers pile up in any order (fast students finish first) 3. You grade from the shelf left-to-right (program order), moving papers to the "permanent grade book" (register file) If a student made a mistake and needs to retake (exception), you throw away all papers to the right (younger instructions) because they shouldn't have been working ahead while this student had a problem. The shelf (ROB) lets students work at their own pace (performance) while you maintain order (correctness). Without the shelf, you'd either have to wait for each student one-by-one (slow!) or risk grading out-of-order (unfair!). --- > [!mnemonic] Remember ROB's Role > **R-O-B = Result Ordering Buffer** Three phases, three words: - **Issue** → Reservation (get ROB ticket) - **Execute** → Out-of-order (chaos is fine) - **Retire** → Bookeeping (restore order) Physical mnemonic: ROB is a **waiting room** for executed instructions. Everyone who finished waits for their number to be called (in order). --- ## Connections - [[Register-renaming]] - ROB entries serve as physical register tags - [[Tomasulo-algorithm]] - Original out-of-order scheme; ROB extends it with in-order commit - [[Reservation-stations]] - Hold instructions before execution; ROB holds after - [[Precise-exceptions]] - ROB is the enabling mechanism - [[Branch-prediction]] - ROB enables recovery from mispredictions - [[Speculative-execution]] - ROB allows safe speculation by delaying commit - [[Instruction-retirement]] - The commit/retire phase of the pipeline - [[Memory-ordering]] - Store buffer interacts with ROB for correct memory semantics - [[Superscalar-processors]] - Need ROB to manage multiple in-flight instructions - [[Register-file-management]] - ROB decouples architectural from physical registers --- #flashcards/hardware What is the primary purpose of the reorder buffer? :: To enable out-of-order execution while maintaining in-order retirement for precise exceptions and correct program semantics. What are the three phases of instruction flow through a ROB? ::: Issue (allocate ROB entry), Execute (out-of-order completion), Retire/Commit (in-order write to architectural state). Why must the ROB be a circular FIFO structure? ::: To allocate entries in program order at the tail, dealocate in program order at the head, and reuse freed entries continuously in a fixed-size buffer. What information does each ROB entry contain? ::: Instruction type, destination register, result value, completion status, exception, and PC. How does the ROB enable precise exceptions? ::: When the head instruction faults, all younger instructions in the ROB are flushed; architectural state reflects only retired instructions. What is the difference between instruction completion and retirement? ::: Completion = execution finished, result written to ROB; Retirement = instruction is oldest completed, result written to architectural registers. How does ROB implement register renaming? ::: ROB entry numbers serve as physical register tags; operands reference ROB entries instead of architectural registers. What condition indicates the ROB is full? ::: `(tail + 1) mod N == head` where N is ROB size. How does the ROB handle branch mispredictions? ::: Flushes all ROB entries after the branch (younger instructions), then redirects fetch to correct path—speculative results never reach architectural state. Why can't ROB entries be freed immediately after execution completes? ::: Must wait for in-order retirement to maintain precise state; younger instructions might have executed but can't commit until all older instructions retire. How many instructions can a4-wide superscalar processor retire per cycle? :: Up to 4, but only if they are consecutive from head, all completed, and none have exceptions. What is the relationship between ROB size and IPC? ::: IPC scales with ROB size up to the point where ROB can hide longest latency operations; beyond that, diminishing returns. ## 🖼️ Concept Map ```mermaid flowchart TD OOE[Out-of-order execution] -->|creates need for| ROB[Reorder buffer] ROB -->|enables| IOR[In-order retirement] ROB -->|implemented as| FIFO[Circular FIFO queue] FIFO -->|indexed via| MOD[Modulo arithmetic] ROB -->|tracks with| HEAD[Head pointer, oldest] ROB -->|tracks with| TAIL[Tail pointer, next free] HEAD -->|retires| COMMIT[Commit to architectural state] TAIL -->|allocates at| ISSUE[Issue in program order] ISSUE -->|then| EXEC[Execute out-of-order] EXEC -->|then| COMMIT ROB -->|stages results for| EXC[Precise exceptions] IOR -->|guarantees| EXC ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Reorder buffer (ROB) ek aisa hardware structure hai jo processor ko do contradictory chezein ek sath karne deta hai: instructions ko **out-of-order execute** karo (jab bhi operands ready ho jayein, turant chala do), lekin unhe **in-order retire** karo (program ke sequence mein hi commit karo). Yeh bilkul aise hai jaise ek restaurant mein different dishes alag-alag time pe ready hoti hain (kuch fast, kuch slow), lekin waiter table pe order ke hisaab se hi serve karta hai—varna confusion ho jayega! > > ROB ek **circular FIFO queue** hai with entries jaise train ke bogies. Har instruction ko issue time pe ek ROB entry milti hai (program order mein). Jab execution complete hota hai (chahe out-of-order), result ROB entry mein likha jaata hai, lekin architectural register file mein **nahi**. Yeh result ROB mein wait karta hai jab tak ki sabse purana instruction (head pointer pe) retire na ho jaye. Retirement ka matlab hai ki ab yeh result permanent register file mein likh sakte hain—ab yeh "committed" hai. > > Iska sabse bada fayda hai **precise exceptions**: agar koi instruction exception throw kare (division by zero, page fault), toh processor simply sabhi younger instructions (ROB mein uske bad wale) ko flush kar deta hai. Architectural state bilkul accurate rehta hai—sirf retired instructions ka effect hai, baki ka koi trace nahi.Iske bina speculative execution aur branch prediction implement karna almost impossible hota. Modern processors mein ROB size typically 100-300 entries hota hai, jo memory latency aur long dependency chains ko hide karne ke liye kafi hota hai. Yeh complexity thodi badha deta hai (CAM searches, pointers manage karna), lekin performance gain immense hai—IPC (instructions per cycle) 2x-4x improve ho jata hai compared to strict in-order execution. ![[audio/5.3.05-Reorder-buffer-(ROB).mp3]]