Reorder buffer (ROB)

5.3.5 · Hardware › Advanced Microarchitecture

Overview

Reorder buffer ek out-of-order processor ka central bookkeeping structure hai jo in-order retirement of instructions ko enable karta hai, jabki out-of-order execution bhi allow karta hai. Yeh ek fundamental problem solve karta hai: "Hum instructions ko tab execute kaise karein jab unke operands ready hon, lekin program sequentially execute hone ka illusion bhi maintain karein?"

---

Core Problem & Solution

Teen-Phase Model

1. Issue → Instruction ko ROB entry milti hai (program order mein) 2. Execute → Instruction out-of-order run karti hai jab ready ho 3. Retire/Commit → Sabse puraani completed instruction architectural state mein likhti hai (program order mein)

---

ROB Structure & Operation

ROB ke do pointers hote hain:

• Head pointer → sabse puraani instruction (retire hone wali)
• Tail pointer → agla free entry (jahaan nayi instruction jaayegi)

---

Derivation: Circular FIFO Kyun?

Chaliye first principles se derive karein ki ROB circular queue kyun honi chahiye.

Requirement 1: Instructions ko program order mein retire karna hoga → FIFO (first-in-first-out) discipline chahiye

Requirement 2: Finite hardware resources → Unbounded queue nahi ho sakti; fixed-size buffer with $N$ entries chahiye

Requirement 3: Continuous operation → Jaise instructions retire hoti hain (head free karta hai), nayi instructions issue hoti hain (tail fill karta hai)

Problem: Linear array indices $0$ se $N-1$ ke saath:

• Head aage badhta hai: $\text{head}=\text{head}+1$
• Tail aage badhta hai: $\text{tail}=\text{tail}+1$
• $N$ retirements ke baad, head array ke end tak pahunch jaata hai
• Freed entries reuse karne ke liye wrap around karna padega

Solution: Circular indexing ke liye modulo arithmetic use karein:

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

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

Full condition (tail, head ko pakad leta hai): $(\text{tail}+1)\mathrm{mod}N=\text{head}$

Empty condition (head, tail ko pakad leta hai): $\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 (agle cycle mein 0 pe wrap hoga)

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

Maano I3 (MUL) pehle complete hoti hai (fastest operation), phir 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 |

R6=120 ko abhi register file mein kyun nahi likhte? Kyunki I1 retire nahi hui hai—hum architectural state ke liye program order maintain karte hain.

Cycle 8: Retirement

I1 sabse puraani hai AUR completed hai → Retire I1

• R1=25 ko architectural register file mein likho
• ROB entry 0 free karo
• Head, 1 pe advance karo

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

Cycle 10: I2 complete hoti hai

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

Cycle 11: I2 retire karo, phir I3

I2 aur I3 dono completed hain aur order mein hain:

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

Sirf I4 pending rehti hai.

---

Detailed Mechanics: Operand Forwarding

1. ROB check karo (tail se head ki taraf backwards) sabse nayi instruction ke liye jo $R_k$ mein likh rahi hai
2. Agar status=completed ke saath mila: Value directly forward karo
3. Agar status=pending ke saath mila: ROB entry ko tag karo, broadcast ka wait karo
4. Agar nahi mila: Architectural register file se padho

Yeh kyun kaam karta hai: ROB entry number ek physical register tag ban jaata hai. "R1 ka wait karo" ke bajaye, instruction "ROB entry 7 ka wait karo" ke liye wait karti hai.

Operand lookup ki example derivation:

Source register $R_k$ ki zaroorat wali instruction ke liye:

\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}$$ Jahaan $i$ **sabse naya** (tail ke sabse kareeb) matching entry hai. --- ## Precise Exceptions with ROB > [!intuition] ROB Precise Exceptions Ko Kaise Enable Karta Hai > Ek exception **precise** hota hai agar processor state faulting instruction se pehle ki saari instructions reflect kare aur baad ki koi bhi nahi. ROB ise trivial banata hai: **Jab ROB head par instruction exception cause kare**: 1. Saari younger instructions flush karo (head ke baad ki saari entries) 2. Architectural state pehle se hi saari puraani instructions reflect karti hai (already retired) 3. Correct PC ke saath exception handler par jump karo **Example**: I3 par division by zero | ROB Entry | Inst | Status | Exception | |-----------|------|--------| | 0 | I1 | Completed | - | | 1 (H) | I2 | Completed | - | | 2 | I3 | Exception | DIV/0 | | 3 | I4 | Completed | - | **Retirement process**: - I1 retire karo ✓ - I2 retire karo ✓ - I3 retire karne ki koshish karo → **Exception detect hua** - ROB entries 3,4,... **Flush** karo - Precise state: I1, I2 committed; I3, I4 kabhi huye hi nahi --- ## ROB vs. Reservation Stations > [!definition] Complementary Structures > - ==Reservation stations== un instructions ko hold karte hain jo **operands ka wait kar rahi hain** (execution scheduling) > - ==ROB== un instructions ko hold karta hai jo **retire hone ka wait kar rahi hain** (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**: Ek instruction apna reservation station 1 cycle baad chod sakti hai (execute ho ke) lekin ROB mein 50 cycles tak reh sakti hai (puraani instructions ke pehle retire hone ka wait karti hui). --- > [!example] Branch Misprediction Recovery **Scenario**: I2 par branch predicted taken, lekin 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) ``` **Jab branch resolve hota hai (misprediction detect hoti hai)**: 1. ROB entry $k$ par branch instruction ko mispredicted mark kiya jaata hai 2. $k$ ke baad ki saari ROB entries **Flush** karo (I3, I4) 3. Fetch ko correct target par redirect karo (I5 ka PC) 4. Saara speculative kaam discard ho jaata hai **commit se pehle** **ROB ise safe kyun banata hai**: I3, I4 ke results kabhi architectural state tak nahi pahunche (abhi bhi ROB staging area mein hain). --- ## Performance Analysis > [!formula] ROB Size Ka IPC Par Impact **Execution window**: Maximum in-flight instructions ki number = ROB size $N$ Instruction-level parallelism (ILP) utilization: $$\text{IPC} = \min\left(\text{ILP}_{\text{available}}, \frac{N}{L}\right)$$ Jahaan: - $N$ = ROB size - $L$ = Longest dependency chain ki average latency - $\text{ILP}_{\text{available}}$ = Program mein per cycle independent instructions **Yeh formula kyun?** - **Numerator** $N$: Total in-flight instruction capacity - **Denominator** $L$: Instructions average kitni der ROB mein rehti hain - Result: Effective instruction retirement rate **Optimal ROB size ki derivation**: Ek processor ke liye: - $W$ issue width (instructions/cycle) - $D$ average instruction dependency distance Full issue bandwidth ke liye expected in-flight instructions: $$N_{\text{optimal}} = W \times D$$ **Example**: 4-wide issue, 10-cycle average dependency chain → Full bandwidth ke liye ROB size ≥ 40 entries chahiye --- ## Common Mistakes & Misconceptions > [!mistake] "ROB execution fast karta hai" **Yeh sahi kyun lagta hai**: ROB critical path mein hai, toh iska performance improve karna toh banta hai. **Reality**: ROB khud execution fast nahi karta—functional units karte hain. ROB speedup ke liye **opportunity** enable karta hai: 1. Out-of-order execution allow karke (performance) 2. Precise state maintain karke (correctness) **Fix**: ROB ko ==permission machinery== samjho. Yeh processor ko aggressive hone ki permission deta hai (speculate karo, out-of-order execute karo) jabki ek safety net bhi maintain karta hai. --- > [!mistake] "ROB entries tab free hoti hain jab instruction complete ho jaati hai" **Yeh sahi kyun lagta hai**: Instruction done hai, phir use rokke kyun rakhein? **Reality**: ROB entry result tab tak hold karti hai jab tak instruction **retire** (commit) nahi ho jaati. Completion ≠ retirement. **Example timeline**: - Cycle 5: Instruction complete hoti hai (ROB entry mein likhti hai) - Cycle 5-20: ROB mein puraani instructions ka wait karti hai - Cycle 20: Retire hoti hai (register file mein likhti hai, ROB free karta hai) **Kyun**: Precise exceptions aur correct program semantics ke liye in-order commit maintain karna zaroori hai. --- > [!mistake] "Bada ROB hamesha better performance deta hai" **Yeh sahi kyun lagta hai**: Zyada in-flight instructions = zyada parallelism. **Reality**: Diminishing returns + complexity cost. **Bottleneck analysis**: $$\text{IPC} = \min(\text{IPC}_{\text{ROB}}, \text{IPC}_{\text{functional\_units}}, \text{IPC}_{\text{memory}})$$ Agar functional units bottleneck hain (execution ports saturated hain), toh ROB enlarge karne se koi fayda nahi. **Optimal sizing**: ROB itna bada hona chahiye ki sabse lambi latency event (typically cache miss ~200 cycles) hide ho sake. Usse zyada, cost/benefit kam hoti jaati hai. Typical sizes: - Mobile: 40-60 entries - Desktop: 100-150 entries - Server: 200-300 entries --- ## Hardware Implementation Details > [!formula] Operand Matching ke liye CAM (Content-Addressable Memory) Jab ek result common data bus par broadcast hota hai: **Problem**: Kaunsi instructions ko yeh result chahiye? **Solution**: ROB entries source tags store karti hain, CAM saari entries parallel mein search karta hai: $$\text{Match}_i = (\text{SourceTag}_i == \text{BroadcastTag}) \land \text{Valid}_i$$ **Energy cost**: Har broadcast par CAM search = high power **Optimization**: ==Wakeup-select== two-stage scheduling 1. Wakeup: CAM ready instructions identify karta hai 2. Select: Issue karne ke liye subset choose karo (priority logic) --- > [!example] Superscalar ROB: Multi-Instruction Retirement 4-wide superscalar processor per cycle mein 4 instructions tak retire kar sakta hai. **Requirements**: 1. Saari 4 completed honi chahiyein 2. Saari 4 head se consecutive honi chahiyein 3. Kisi bhi 4 mein koi exception na ho **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 entry 10 par point kar raha hai | Entry | Complete | Exception |-------|----------|-----------| | 10 | Yes | No | | 11 | Yes | No | | 12 | No | No | | 13 | Yes | No | Sirf 2 instructions (10, 11) retire ho sakti hain kyunki 12, 13 ko block kar rahi hai. --- ## ROB in Modern Processors **Intel Skylake** (2015): - 224-entry ROB - Unified reservation station (97 entries) - Mispredicted branch flush ke liye ~4-5 cycle penalty **Apple M1** (2020): - ~630-entry ROB (estimated, officially published nahi) - Memory latency hide karne ke liye massive window - Aggressive prefetching + out-of-order enable karta hai **AMD Zen 3** (2020): - 256-entry ROB - Separate integer/FP schedulers - Fast retirement: 8 ops/cycle bandwidth --- > [!recall]- Ek 12-saal ke bachche ko samjhao > Socho tum ek teacher ho aur classroom mein students exam de rahe hain. Tum chahte ho ki students problems jitni jaldi ho sake finish karein (out-of-order), lekin tumhein papers ko us order mein grade karna hai jisme students baithe hain (in-order) taaki fair ho. ROB ek **staging shelf** ki tarah hai tumhari desk ke peeche: 1. Jaise students finish karte hain (execute), woh papers shelf par rakhte hain 2. Papers kisi bhi order mein pile hote hain (fast students pehle finish karte hain) 3. Tum shelf se left-to-right grade karte ho (program order), papers ko "permanent grade book" (register file) mein daalte ho Agar kisi student ne mistake ki aur use retake karna pada (exception), tum daayein wale saare papers phenk dete ho (younger instructions) kyunki unhein aage kaam nahi karna chahiye tha jab is student ko problem thi. Shelf (ROB) students ko apni pace se kaam karne deta hai (performance) jabki tum order maintain karte ho (correctness). Shelf ke bina, ya toh tum ek-ek karke har student ka wait karte (slow!) ya out-of-order grade karne ka risk lete (unfair!). --- > [!mnemonic] ROB Ka Role Yaad Rakho > **R-O-B = Result Ordering Buffer** Teen phases, teen words: - **Issue** → Reservation (ROB ticket lo) - **Execute** → Out-of-order (chaos theek hai) - **Retire** → Bookkeeping (order restore karo) Physical mnemonic: ROB executed instructions ke liye ek **waiting room** hai. Jo bhi finish ho gaye hain woh apna number call hone ka wait karte hain (order mein). --- ## Connections - [[Register-renaming]] - ROB entries physical register tags ki tarah kaam karti hain - [[Tomasulo-algorithm]] - Original out-of-order scheme; ROB ise in-order commit ke saath extend karta hai - [[Reservation-stations]] - Execution se pehle instructions hold karte hain; ROB baad mein hold karta hai - [[Precise-exceptions]] - ROB enabling mechanism hai - [[Branch-prediction]] - ROB mispredictions se recovery enable karta hai - [[Speculative-execution]] - ROB commit delay karke safe speculation allow karta hai - [[Instruction-retirement]] - Pipeline ka commit/retire phase - [[Memory-ordering]] - Store buffer, correct memory semantics ke liye ROB ke saath interact karta hai - [[Superscalar-processors]] - Multiple in-flight instructions manage karne ke liye ROB chahiye - [[Register-file-management]] - ROB architectural aur physical registers ko decouple karta hai --- #flashcards/hardware Reorder buffer ka primary purpose kya hai? :: Out-of-order execution enable karna jabki precise exceptions aur correct program semantics ke liye in-order retirement maintain karna. ROB ke through instruction flow ke teen phases kya hain? ::: Issue (ROB entry allocate karo), Execute (out-of-order completion), Retire/Commit (architectural state mein in-order write karo). ROB circular FIFO structure kyun honi chahiye? ::: Tail par program order mein entries allocate karne ke liye, head par program order mein deallocate karne ke liye, aur fixed-size buffer mein freed entries continuously reuse karne ke liye. Har ROB entry mein kya information hoti hai? ::: Instruction type, destination register, result value, completion status, exception, aur PC. ROB precise exceptions kaise enable karta hai? ::: Jab head instruction fault kare, ROB mein saari younger instructions flush ho jaati hain; architectural state sirf retired instructions reflect karti hai. Instruction completion aur retirement mein kya fark hai? ::: Completion = execution finish, result ROB mein likha; Retirement = instruction sabse puraani completed hai, result architectural registers mein likha. ROB register renaming kaise implement karta hai? ::: ROB entry numbers physical register tags ki tarah kaam karte hain; operands architectural registers ke bajaye ROB entries reference karte hain. ROB full hone ki condition kya hai? ::: `(tail + 1) mod N == head` jahaan N ROB size hai. ROB branch mispredictions kaise handle karta hai? ::: Branch ke baad ki saari ROB entries (younger instructions) flush karta hai, phir fetch ko correct path par redirect karta hai—speculative results architectural state tak nahi pahunchte. ROB entries execution complete hone ke baad immediately free kyun nahi ho sakti? ::: Precise state maintain karne ke liye in-order retirement ka wait karna padta hai; younger instructions execute ho chuki hain lekin tab tak commit nahi kar sakti jab tak saari puraani instructions retire nahi ho jaatein. Ek 4-wide superscalar processor per cycle mein kitni instructions retire kar sakta hai? :: 4 tak, lekin sirf tab jab woh head se consecutive hों, saari completed hों, aur kisi mein bhi exception na ho. ROB size aur IPC ka kya relationship hai? ::: IPC, ROB size ke saath tab tak scale karta hai jab tak ROB sabse lambi latency operations hide kar sake; uske baad diminishing returns aa jaati hain. ## 🖼️ 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 ```