Reorder buffer (ROB): Worked examples — Hinglish deep dive

5.3.5 · D3 · Hardware › Advanced Microarchitecture › Reorder buffer (ROB)

Yeh page Reorder buffer (ROB) ko tab tak drill karti hai jab tak koi bhi situation tumhe surprise na kar sake. Hum koi nayi theory add nahi kar rahe; hum head/tail pointers, retire-in-order rule, aur flush-on-exception rule ko parent note se lete hain aur unhe har us case mein push karte hain jo ek ROB face kar sakta hai.

Kuch bhi shuru karne se pehle, teen plain-word reminders (taaki koi bhi symbol bina samjhe na aaye):

Recall Head aur Tail kya hain phir se?

Head ::: pointer jo buffer mein sabse purani instruction ko point karta hai — sirf yahi agle retire hone ki permission rakhta hai. Tail ::: pointer jo next free slot ko point karta hai — jahan next issued instruction likhi jaati hai. Retire ::: ek completed result ko real (architectural) register file mein copy karna aur uska slot free karna.

Recall Ek golden rule

Instructions kisi bhi order mein execute ho sakti hain, lekin woh sirf program order mein retire ho sakti hain — strictly Head-first.

Scenario matrix

Har ROB situation in cells mein se ek hoti hai. Neeche ke examples mein har ek ke saath [Cell C] jaisa tag hoga taaki tum dekh sako ki poora space covered hai.

Cell	Case class	Kya cheez tricky banati hai
A	Empty buffer (Head = Tail, kuch bhi in flight nahi)	degenerate: kya yeh empty hai ya full?
B	Full buffer (Tail+1 Head par wrap karta hai)	issue ko stall karna padega
C	Wrap-around indexing array end cross karti hai	modulo arithmetic
D	Out-of-order completion, in-order retire	sabse young pehle finish hoti hai — wait karna padega
E	Operand forwarding ek pending ROB entry se	tag-and-wait, newest match
F	Precise exception head par vs. ek younger faulting instruction	sab younger flush kar do
G	Branch misprediction flush	speculative tail discard karo
H	Limiting / performance (ROB size vs IPC)	formula $IPC = min (ILP, N / L)$
I	Word problem (real pipeline sizing)	English → formula mein translate karo
J	Exam twist (store jo early commit nahi honi chahiye)	memory ordering subtlety

Yeh cells Instruction-retirement, Register-renaming, Precise-exceptions, Branch-prediction, aur Superscalar-processors par respectively map hoti hain.

Example 1 — Empty vs Full, degenerate confusion `[Cell A + B]`

Forecast: abhi guess karo — kya ek equation ( $Head = Tail$ ) ke do opposite meanings ho sakte hain?

Do candidate conditions likho. Parent note se: $empty ⟺ Head = Tail, full ⟺ (Tail + 1) mod N = Head .$ Yeh step kyun? Hume reading ko dono rules ke against test karna hai, sirf ek ke nahi.
$N = 8$ , Head=Tail=3 empty moment ke liye plug karo. Empty rule: $3 = 3$ ✓. Full rule: $(3 + 1) mod 8 = 4 \neq = 3$ . Toh yeh empty hai. Kyun? Koi bhi instruction kabhi write nahi hui, isliye Tail kabhi Head se aage nahi gayi.
Full moment. Agar hum sirf "Head=Tail" use karte hain toh hum ek full buffer ko galti se empty bolenge. Isliye real hardware Tail ko Head ke equal fill karke kabhi nahi hone deta: full rule issue ko ek slot pehle rok deta hai. Kyun? 8 slots ke saath, hum buffer ko full maante hain jab 7 occupied hain aur $(Tail + 1) mod 8 = Head$ ho, toh Head=Tail ka matlab sirf empty ho sakta hai.

Verify: Empty rule true, full rule false → unambiguously empty. Agar hum saare 8 slots fill hone dete, toh Head=Tail ambiguous hota; ek slot sacrifice karna ambiguity hata deta hai. Usable capacity $= N - 1 = 7$ .

Example 2 — Wrap-around indexing `[Cell C]`

Forecast: array mein sirf indices 0,1,2,3 hain — index 3 ke baad kya hoga?

Pehla retirement: $Head = (2 + 1) mod 4 = 3$ . Mod kyun? $mod N$ number line ko ek circle mein wrap karta hai taaki index 4 ban jaaye 0. Ring mein dekho — retire karna ek clockwise step hai.
Doosra retirement: $Head = (3 + 1) mod 4 = 0$ . Kyun? $4 mod 4 = 0$ — pointer end se gir ke wapas start par aa jaata hai. Yahi reason hai hum ne ek circular FIFO choose kiya.
Teesra retirement: $Head = (0 + 1) mod 4 = 1$ .

Verify: Sequence $2 \to 3 \to 0 \to 1$ . Net advance = 4 ki ring par 3 steps, aur wakai $(2 + 3) mod 4 = 1$ ✓.

Example 3 — Out-of-order completion, in-order retire `[Cell D]`

Forecast: I4 pehle finish hua. Kya uska result cycle 8 par register file mein hai?

Cycle 8 par completion status list karo. Cycle 8 tak done: I4(c5), I1(c6), I2(c7). Not done: I3(c12). Kyun? Retirement sirf completed instructions ko consider kar sakta hai.
Head-first rule apply karo. Head = I1.
- Cycle 6: I1 complete hota hai → I1 retire. Head → I2.
- Cycle 7: I2 complete hota hai aur ab Head hai → I2 retire. Head → I3. Yeh step kyun? Har retire tabhi legal hai jab Head slot complete ho.
Kya I4 cycle 8 par retire ho sakta hai? Head ab I3 hai, jo cycle 12 tak pending hai. Toh retirement I3 par stall ho jaata hai. I4 apne ROB slot mein parked rehta hai chahe woh cycle 5 par finish ho gaya tha. Kyun? Program order I4 ko I3 se pehle commit karne se mana karta hai.

Verify: Cycle 8 par, register file mein sirf I1 aur I2 ke results hain. I3, I4 ROB mein rehte hain. I4 ne $8 - 5 = 3$ extra cycles wait kiya — parent ke "1 cycle mein execute, ROB mein kai cycles baithta hai" ka ek concrete example.

Example 4 — Operand forwarding, newest match wins `[Cell E]`

Forecast: R1 ke teen writers hain — nayi instruction ko kaun sa "R1" dekhna chahiye?

R1 ka newest writer dhundo. Tail→head scan karte hue, R1 likhne wali closest-to-tail entry slot9 hai. Newest kyun? Reader ko program order mein sabse recent definition dekhni chahiye, yaani apne se pehle last write — woh slot9 hai, parent ke piecewise rule ke mutabiq ( $i$ = newest matching entry).
Slot9 ka status check karo. Woh pending hai. Toh reader koi value grab nahi kar sakta; bajaye iske woh slot9 ko tag karta hai aur broadcast ka wait karta hai. Slot7 ki value 9 kyun nahi read karte? Kyunki slot7 purana hai; slot9 baad mein R1 ko overwrite karta hai. 9 read karna stale value hogi — ek Register-renaming bug.
Reader kis cheez ka wait karta hai? "R1" ka nahi balki "ROB slot 9" ka. Yahi renaming trick hai: ROB slot number hi physical tag hai. Kyun? Multiple R1 ek saath exist karte hain; slot number unhe disambiguate karta hai.

Verify: Correct source = slot9 (pending) → tag-and-wait. Agar slot9 exist nahi karta, newest hota slot7 (completed) → value 9 directly forward karo. Agar koi bhi slot R1 nahi likhta, architectural RF[R1] read karo. Parent ke piecewise function ki teeno branches exercise ho gayi hain.

Example 5 — Precise exception ek younger instruction par `[Cell F]`

Forecast: I4 already complete ho gaya. Kya uska result survive karta hai?

Head se retire karo jab tak Head par koi fault na ho. I1 retire karo ✓, I2 retire karo ✓. Head → I3. Kyun? I1, I2 fault se purane hain aur complete ho gaye → woh legitimately program ki committed state ka hissa hain.
Head I3 tak pahunchta hai, jisme exception flag hai. Retirement par hum DIV/0 detect karte hain. Hum I3 ka (garbage) result nahi likhte. Execution par kyun nahi, yahan kyun? Exceptions sirf retirement par recognize ki jaati hain taaki woh program order mein li jaayein — yahi unhe precise banata hai. Dekho Precise-exceptions.
I3 se aage sab kuch flush karo. I3 aur I4 squash ho jaate hain; I4 ka completed result discard ho jaata hai chahe woh finish ho gaya tha. Ek completed I4 kyun discard karte hain? I4 faulting I3 se younger hai — precise exception ka matlab hai "fault ke baad kuch bhi effect mein nahi aata."

Verify: Committed = {I1, I2}. Discarded = {I3, I4}. Architectural state = exactly fault se pehle ki saari instructions, baad mein koi nahi. Handler I3 ke saved PC ke saath enter kiya. Yeh picture hai:

Example 6 — Branch misprediction flush `[Cell G]`

Forecast: I3, I4 already speculatively run ho gaye. Kya unke register writes visible hain?

Branch entry locate karo. BEQ ROB slot $k$ par hai (= I2 ka slot). Resolution par yeh mispredicted flag hota hai. ROB kyun decide karta hai recovery, execution unit kyun nahi? Kyunki sirf in-order ROB jaanta hai kaun si instructions branch se younger hain.
$k$ ke baad ki saari entries flush karo. I3 aur I4 squash ho jaate hain. Unke results sirf ROB staging area mein the — register file mein kabhi nahi — toh kuch bhi architectural corrupt nahi hota. Safe kyun? Speculative-execution results ROB mein quarantine hote hain retirement tak; unhe discard karna sirf time ka cost hai.
Fetch ko correct target (I5) par redirect karo. Head I1, I2 par advance karta rehta hai (dono correct-path) jaise woh complete hote hain. I2 kyun rakhte hain? Branch instruction khud ek real, in-order instruction hai — sirf uske speculative successors galat the.

Verify: Survivors = {I1, I2}. Squashed = {I3, I4}. Fetch I5 par redirect. Koi bhi wrong-path result register file ko kabhi nahi chua (dekho Branch-prediction).

Example 7 — ROB size IPC limit karta hai, small window `[Cell H]`

Forecast: bahut saari ILP available hai, toh kya IPC bas 6 ke barabar ho jaata hai?

Parent ka formula apply karo. $IPC = min (ILP_{available}, \frac{N}{L})$ . Min kyun? Tum ya toh itne parallel work se cap ho jaate ho ya phir kitni instructions in flight rakh sakte ho — jo bhi chhota ho.
Window bound compute karo. $N / L = 32/8 = 4$ . Toh $IPC = min (6, 4) = 4$ . 4 < 6 kyun hai? ROB 32 in-flight rakh sakta hai, har ek ~8 cycles ke liye apna slot occupy karta hai, toh woh sirf $32/8 = 4$ per cycle drain karta hai — window, ILP nahi, bottleneck hai.
ROB ko 16 tak shrink karo. $N / L = 16/8 = 2$ , toh $IPC = min (6, 2) = 2$ . ROB ko half karna yahan throughput ko bhi half kar deta hai. Kyun? Hum firmly window-limited regime mein hain, jahan IPC $N$ mein linear hai.

Verify: $N = 32 \Rightarrow 4$ ; $N = 16 \Rightarrow 2$ . Dono 6 ki ILP ceiling se neeche → dono window-limited, figure mein down-sloping line ke saath consistent.

Example 8 — Word problem: ek ROB size karna `[Cell I]`

Forecast: guess karo kya $N = 32$ IPC 6 ke liye enough hai.

Window bound ko ILP ke kam se kam barabar set karo. Hume chahiye $N / L \geq ILP$ , yaani $N \geq ILP \times L$ . $\geq$ kyun, $=$ kyun nahi? Jab $N / L$ ILP ceiling tak pahunch jaata hai, min ILP term par switch ho jaata hai; extra slots hurt nahi karte lekin required nahi hain.
$ILP = 6, L = 8$ plug karo. $N \geq 6 \times 8 = 48$ . Sabse chhota hai $N = 48$ . 32 kyun fail hua? $32/8 = 4 < 6$ — window bahut chhota, exactly Example 7.
Ab $L = 12$ . $N \geq 6 \times 12 = 72$ . Bigger kyun? Lambi latency ka matlab hai har instruction apna slot zyada der occupy karti hai, toh tumhe 6 per cycle retire karne ke liye zyada slots chahiye. Cache miss $L$ ko deep karta hai aur ek bada ROB demand karta hai — yahi real reason hai server CPUs ROBs grow karte hain.

Verify: $N = 48$ : $48/8 = 6 = ILP$ → IPC $= min (6, 6) = 6$ ✓. $N = 72$ : $72/12 = 6$ → IPC $= 6$ ✓. Dono exactly target hit karte hain.

Example 9 — Exam twist: woh store jo early commit nahi honi chahiye `[Cell J]`

Forecast: store cycle 3 par "done" hai — kya memory safely update ho sakti hai?

Yaad karo stores baki sab ki tarah ROB head par retire hote hain. Ek store ka memory mein likhna ek architectural side effect hai, isliye yeh sirf retirement par hota hai, order mein. Kyun? Agar purana LOAD I1 fault kare (page fault at [A]), toh ek precise exception require karta hai ki store kabhi hua hi na ho. Dekho Memory-ordering.
I1 head ko cycle 40 tak block karta hai. Toh I2 ka memory write ek store buffer / ROB mein hold hota hai jab tak I1 retire ho. Cycle 3 par memory update nahi hoti. Wait kyun? I2 ko early commit karna I3 ke LOAD aur dusre cores ko visible ho jaata, program-order memory semantics tod deta.
I1 retire hone ke baad (cycle 40), I2 retire hota hai aur [B] likhta hai; phir I3 ka LOAD of [B] nayi value dekhta hai (speculative hote hue forwarding ke zariye, lekin architecturally sirf I2 commit hone ke baad correct hota hai). Meanwhile I3 ko forward kyun karte hain? Store-to-load forwarding I3 ko I2 ke data ke saath execute karne deta hai, lekin I3 bhi I2 se pehle retire nahi ho sakta — order preserved.

Verify: [B] ka memory write cycle 40 par hota hai (I1 → I2 retire), cycle 3 par nahi. I3 correct post-store value read karta hai. Koi early architectural side effect nahi — ROB ke in-order commit ne memory ordering protect ki.

Recall Quick self-test

$N = 4$ ke saath, kya Head=Tail=1 empty hai ya full? ::: Empty (full ke liye chahiye $(Tail + 1) mod N = Head$ ). ILP=6, N=24, L=8 → IPC? ::: $min (6, 24/8) = min (6, 3) = 3$ . Purani instruction fault karti hai — kya ek younger completed instruction commit hoti hai? ::: Nahi, woh flush ho jaati hai.