Reorder buffer (ROB): Exercises — Hinglish deep dive

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

Yeh page ek self-test ladder hai. Har rung pichle se thoda zyada maangti hai. Solution cover karo, problem try karo, phir reveal karo. Yahan use kiya gaya har symbol parent ROB note mein build kiya gaya tha — agar koi term unfamiliar lage, toh pehle wapas jaake padho.

Quick vocabulary refresher (sab parent note se), taaki pehli line samajh aaye:

Definition Woh words jo tumhare paas loaded hone chahiye

Head pointer — sabse purani instruction ki taraf point karta hai, jo retire hone ki next turn mein hai.
Tail pointer — next free slot ki taraf point karta hai, jahan naya issued instruction likha jaata hai.
Retire / commit — woh moment jab ek instruction ka result ROB se permanent (architectural) register file mein copy hota hai, program order mein.
Issue — ek instruction ko ROB entry mili, program order mein (yeh execute hone se pehle hota hai).
Flush — ROB entries ko throw away karna jo kisi point se younger hain, kyunki woh galat nikle (mispredicted branch) ya kabhi hone hi nahi chahiye the (exception).
==Status = Pending== — entry issue ho chuki hai lekin uska result abhi compute nahi hua (execution finish nahi hui). Uski value field abhi bhi empty hai (?).
==Status = Completed== — execution finish ho gayi aur result value ROB mein likh di gayi, lekin architectural register file mein copy nahi hui abhi. Completed entry retire hone ke eligible hai, lekin sirf tab jab woh program order mein head pe pahunche.
==Status = Exception== — instruction fault kar gayi (jaise divide-by-zero); uske paas koi valid result nahi hai aur jab woh head pe pahunchi, toh commit karne ki jagah exception trigger hoga.

Neeche sab kuch ek circular buffer of $N$ entries use karta hai jiske indices $0, 1, \dots, N - 1$ hain jo $mod N$ use karke wrap around karte hain ( $N$ se divide karne ke baad remainder). Agar "mod" fuzzy hai: $7 mod 4 = 3$ kyunki $7 = 1 \times 4 + 3$ , aur bacha hua $3$ hai.

Neeche ki picture poori page ke liye mental model hai. Exercise 1.1 se pehle ise study karo: chheh numbered circles fixed physical slots hain; pale-yellow HEAD arrow sabse purani live instruction ko mark karta hai (yahan se retire karo), pink TAIL arrow next free slot ko mark karta hai (issue yahan likhta hai). Blue circles Completed entries hain, pink circle Pending entry hai, aur empty (board-coloured) circles free hain. Notice karo ki HEAD aur TAIL bas indices hain jo ring ke around chalte hain, $mod N$ se $5 \to 0$ wrap karte hue — yahi wrap ki wajah se buffer ko line ki jagah circle ki tarah draw kiya jaata hai.

Level 1 — Recognition

Goal: kya tum ek ROB snapshot padh ke uske baare mein facts bata sakte ho?

Exercise 1.1

Ek 8-entry ROB mein currently $head = 3$ aur $tail = 3$ hai. ROB kis state mein hai — empty ya full? Explain karo ki kaunsa rule batata hai.

Recall Solution 1.1

Parent note ne do rules diye:

Empty condition: $head = tail$
Full condition: $(tail + 1) mod N = head$

Yahan $head = tail = 3$ hai, toh empty rule fire hota hai. ROB empty hai.

Do rules alag kyun hone chahiye: agar hum ek completely full buffer ko bhi $head = tail$ satisfy karne dete, toh hum "full" aur "empty" mein farq nahi kar paate — dono ek jaisi dikhte. Isliye deliberately ek slot sacrifice kiya jaata hai: full ek step pehle declare hota hai pointers ke collision se. Isliye full rule $(tail + 1) mod N = head$ hai, $tail = head$ nahi.

Exercise 1.2

Ek 4-entry ROB ka yeh snapshot hai. Is cycle kaunsi single instruction retire hone ke eligible hai?

Entry	Inst	Status
0	I1	Completed
1 (H)	I2	Pending
2	I3	Completed
3	I4	Completed

Recall Solution 1.2

Retirement head se program order mein hoti hai. Head entry 1 (I2) pe hai. Retire karne ke liye, head instruction Completed honi chahiye.

I2 Pending hai, toh retirement stall ho jaati hai — chahe I3 aur I4 done ho. Is cycle koi instruction retire nahi hoti.

Note: Entry 0 mein I1 index se older hai lekin woh head ke peeche hai — woh pehle hi ek previous cycle mein retire ho chuki hai (isliye head usse aage nikal gayi). Yeh candidate nahi hai.

Level 2 — Application

Goal: pointer machinery khud chalao.

Exercise 2.1

Ek $N = 6$ ROB $head = 4$ , $tail = 4$ (empty) se start hota hai. Tum 5 instructions issue karte ho, phir 3 retire karte ho. Final $head$ aur $tail$ batao.

Recall Solution 2.1

Issue karne se tail advance hota hai (har issue pe ek slot); retire karne se head advance hota hai.

$tail = 4$ se 5 baar issue karo: $tail = (4 + 5) mod 6 = 9 mod 6 = 3.$ $head = 4$ se 3 baar retire karo: $head = (4 + 3) mod 6 = 7 mod 6 = 1.$

Final: $head = 1$ , $tail = 3$ .

Sanity check — occupancy = issued minus retired = $5 - 3 = 2$ live instructions. Pointers se occupancy $(tail - head) mod N = (3 - 1) mod 6 = 2$ hai. ✓ Match karta hai.

Exercise 2.2

Wohi 6-entry ROB. Abhi woh full hai. Kitni valid (occupied) entries hold karta hai — $6$ ya $5$ ?

Recall Solution 2.2

Kyunki "full" tab declare hota hai jab $(tail + 1) mod N = head$ , ek slot hamesha empty rakha jaata hai full aur empty mein tie-breaker ke liye. Toh ek "full" 6-entry ROB ==5 valid instructions== hold karta hai, 6 nahi.

(Real designs aksar ek alag 1-bit "full" flag add karte hain taaki woh saare $N$ slots use kar sakein aur sacrificed slot drop kar sakein. Lekin pointers-only scheme mein jaise parent ne describe kiya, usable depth $N - 1$ hai.)

Level 3 — Analysis

Goal: correctness ke baare mein reason karo, sirf mechanics nahi.

Exercise 3.1 — Newest-writer operand lookup (with wrap-around)

Ek 6-entry ROB jiska live region ring ke top se past wrap ho gaya hai: tail index head index se neeche baith gaya hai. Live entries, program order mein (oldest first), slots $4, 5, 0, 1$ occupy karti hain. Head slot 4 pe hai; tail (next free) slot 2 pe hai:

Entry	Dest	Status	Value	Program order
4 (H)	R1	Completed	25	oldest
5	R4	Completed	15	2nd
0	R1	Pending	?	3rd
1	R7	Completed	40	newest
2 (T)	—	free	—	—
3	—	free	—	—

Ek nayi instruction (tail region mein issued) source register R1 chahti hai. Woh kaunsi entry padhti/wait karti hai, aur tum ring ko $5 \to 0$ boundary ke across backwards scan kaise karte ho?

Recall Solution 3.1

Lookup tail se backwards head ki taraf scan karta hai newest entry ke liye jiska dest = R1 ho. Kyunki region wrap ho gayi, "tail se backwards" ka matlab hai: tail se thoda pehle shuru karo aur $mod N$ se decrement karo, toh live slots ka scan order hai $1 \to 0 \to 5 \to 4 (har step hai (idx - 1) mod 6) .$ Notice karo step $0 \to 5$ : yahi wrap hai — index $0$ ko decrement karna $(0 - 1) mod 6 = 5$ deta hai, exactly top-of-ring boundary cross karta hai. Yahi subtlety hai; baaki logic non-wrapped case jaisa hai.

$1, 0, 5, 4$ scan karte hue: R1 ke liye pehla (newest) match slot 0 hai (entry 1 R7 likhti hai, R1 nahi). Slot 0 Pending hai, toh nayi instruction slot 4 se older R1=25 nahi uthati. Woh ROB slot 0 se tag karti hai khud ko aur wait karti hai us broadcast ke liye.

Wrap ke across bhi newest kyun jeetता hai: R1 slot 4 pe define kiya gaya tha, phir slot 0 pe redefine kiya gaya; slot 0 program order mein baad mein hai (3rd vs oldest), toh baad ki read ko slot 0 ki (future) value dekhni chahiye, stale 25 nahi. Physical index ka numerically smaller hona irrelevant hai — program order, jo pointer walk se track hota hai, wahi matter karta hai. Yeh "newest matching writer" search exactly register renaming hai action mein.

Neeche ki figure exactly yahi wrapped snapshot draw karti hai taaki tum backward scan ko boundary cross karte hue dekh sako.

Exercise 3.2 — Precise exception boundary

Ek 4-entry ROB, head entry 1 pe:

Entry	Inst	Status
1 (H)	I2	Completed
2	I3	Exception (DIV/0)
3	I4	Completed
0	I5	Completed

I4 aur I5 already computed hain. Kaunse results architectural register file tak pahunchte hain, aur kaunse discard hote hain?

Recall Solution 3.2

Head se in order retire karo:

I2 (Completed) retire karo → commit. ✓
Head I3 tak pahunchti hai → yeh Exception carry karta hai. Retirement yahan rokti hai. Hum I3 ka (garbage) result commit nahi karte; instead exception lete hain.
I3 se younger sab kuch flush karo: entries 3 (I4) aur 0 (I5) throw away — chahe woh execute ho chuke hों.

Committed: sirf I2 (plus kuch bhi older jo pehle retire ho chuka). Discarded: I3, I4, I5.

Yahi precise exception ki definition hai: state un saari instructions reflect karti hai fault se pehle aur koi nahi at-or-after. In-order retirement discipline yeh free mein deta hai — fault tab hi effect le sakta hai jab woh sabse purani instruction ban jaaye.

Level 4 — Synthesis

Goal: pointer math, timing, aur performance reasoning ko combine karo.

Exercise 4.1 — Branch misprediction flush count (no wrap aur wrap cases)

Ek 16-entry ROB. Ek mispredicted branch entry $k = 5$ pe hai, aur tail (next free) entry $12$ pe hai.

(a) Kitni entries flush hoti hain? (b) Ab maan lo branch $k = 14$ pe hai aur tail entry $3$ pe hai — toh younger, speculative entries $15 \to 0$ boundary ke across wrap karti hain. Kitni entries flush hoti hain, aur kya wahi formula kaam karta hai?

Recall Solution 4.1

Flush count hamesha "live entries ki count jo branch se strictly younger hain," jo ring-distance hai branch ke baad wale slot se tail tak (lekin tail include nahi): $flush = (tail - (k + 1)) mod N .$

(a) No wrap. Younger entries hain $6, 7, 8, 9, 10, 11$ (entry 12 free tail hai). $flush = (12 - 6) mod 16 = 6.$ 6 entries flush huin. Slot 5 pe branch rakha jaata hai — yeh ek real, correct instruction hai; sirf uski prediction galat thi.

(b) Wrap. Younger entries hain $15, 0, 1, 2$ — range top-of-ring boundary $15 \to 0$ cross karti hai. $k = 14$ , $tail = 3$ plug karo: $flush = (3 - (14 + 1)) mod 16 = (3 - 15) mod 16 = (- 12) mod 16 = 4.$ 4 entries flush huin — aur actually inhe list karo ( $15, 0, 1, 2$ ) toh 4 milti hain. Wohi $mod N$ formula wrap ko automatically handle karta hai: negative intermediate $- 12$ ko $mod$ se range mein fold kiya jaata hai, aur isliye circular-buffer arithmetic mein har jagah $mod$ likha jaata hai. Hardware mein koi alag "kya wrap hua?" branch ki zaroorat nahi.

Exercise 4.2 — ROB-limited IPC

Parent ne performance model diya: $IPC = min (ILP_{available}, \frac{N}{L}) .$ Ek program mein $ILP_{available} = 4$ independent instructions per cycle hain. Sabse lambi dependency chain ki average latency $L = 5$ cycles hai. (a) $N = 16$ aur (b) $N = 32$ ke liye sustained IPC compute karo. Kaunsa resource har case mein limit karta hai?

Recall Solution 4.2

(a) $N = 16$ : $\frac{N}{L} = \frac{16}{5} = 3.2$ . Toh $IPC = min (4, 3.2) = 3.2$ . ROB bottleneck hai — window itni chhoti hai ki 5-cycle occupancy ke saath 4-wide parallelism expose nahi ho paati.

(b) $N = 32$ : $\frac{N}{L} = \frac{32}{5} = 6.4$ . Toh $IPC = min (4, 6.4) = 4$ . Ab program ka ILP (4) bottleneck hai — ROB aur bada karna kuch nahi khareedta.

Interpretation: $N / L$ hai "kitni instructions hum in-flight rakh sakte hain given ki har ek $L$ cycles tak rehti hai." $N$ badhana tab hi help karta hai jab tak woh $ILP_{available} \times L = 4 \times 5 = 20$ se zyada na ho jaaye. $N = 20$ se aage min ILP se pin ho jaata hai. Toh yahan full IPC reach karne wala sabse chhota ROB $N = ⌈ ILP \cdot L ⌉ = 20$ hai.

Neeche ka plot dono terms aur unke beech $min$ draw karta hai, taaki tum "knee" dekh sako jahan limit ROB se ILP shift hoti hai. Yellow curve dekho: woh $N / L$ dashed line ke saath blue tak rise karti hai jab tak knee $N = 20$ tak, phir pink ILP ceiling pe flatten hoti hai; do marked dots exactly $N = 16$ aur $N = 32$ ke upar ke answers hain.

Level 5 — Mastery

Goal: design-level reasoning jahan kai structures interact karte hain.

Exercise 5.1 — Sizing a balanced machine

Tum ek superscalar core (dekho Superscalar-processors) design kar rahe ho jo 4 instructions per cycle tak issue aur retire karta hai. Loads ki latency $L = 5$ cycles hai aur dependency chains dominate karti hain. Tum chahte ho ROB itna bada ho ki woh kabhi is workload ke liye retirement bottleneck na bane.

(a) Minimum ROB size $N$ kya hai? (b) Tumhare paas alag Reservation-stations bhi hain. Agar ek instruction reservation station mein sirf 1 cycle rehti hai operands aane ke baad lekin ROB mein $L = 5$ cycles tak, toh roughly kitna ratio of ROB entries to reservation stations inhe balanced rakhta hai?

Recall Solution 5.1

(a) Machine sustained $IPC = 4$ chahta hai. $IPC = min (ILP, N / L)$ se, humein chahiye $\frac{N}{L} \geq ILP \Rightarrow N \geq ILP \times L = 4 \times 5 = 20.$ Minimum $N = 20$ entries. (Real cores generously round up karte hain — jaise 32, 64, 224 — cache misses tolerate karne ke liye jo $L$ ko 5 se kahin aage kheeench dete hain.)

(b) Little's-law intuition: occupancy $=$ arrival-rate $\times$ residence-time. Dono structures same arrival rate dekhte hain (4/cycle). Ek reservation station ~1 cycle hold hota hai; ek ROB entry ~ $L = 5$ cycles. Toh $\frac{ROB entries}{reservation stations} \approx \frac{L}{1} = \frac{5}{1} .$ Roughly 5× zyada ROB entries reservation stations se. Yeh parent ke remark se match karta hai ki ek instruction ~1 cycle mein reservation station chhod sakti hai lekin ROB mein kaafi cycles tak lingering karti hai — toh commit-side buffer deeper hona chahiye.

Recall One-line self-checks (cloze)

Ek completed instruction tab tak retire nahi ho sakti jab tak ek older instruction abhi bhi ::: pending hai (in-order retirement). Ek $N$ -entry ROB ke liye full condition hai ::: $(tail + 1) mod N = head$ . Operand lookup mein hum ::: newest (closest-to-tail) matching writer search karte hain. Ek mispredicted branch saari entries ::: branch se younger flush karta hai, branch khud rakhta hai. ROB-limited IPC cap hoti hai ::: $min (ILP_{available}, N / L)$ pe.

Related deep-dive threads: Register-renaming, Tomasulo-algorithm, Precise-exceptions, Speculative-execution, Branch-prediction, Instruction-retirement, Memory-ordering, Register-file-management.