Reorder buffer (ROB): Visual walkthrough — Hinglish deep dive

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

Yeh page reorder buffer ko pictures ke saath rebuild karta hai. Hum shuru karte hain kuch nahi se — bas ek row of boxes — aur dheere dheere har cheez add karte hain: do pointers, wrap-around, out-of-order fill, in-order drain, aur flush. Har symbol pehle draw kiya jata hai, phir use hota hai.

Agar tumne abhi vocabulary nahi dekhi, toh pehle parent topic skim kar lo — lekin zaruri nahi hai. Hum yahan zero se build karte hain.

Step 1 — Aakhir hum draw kya kar rahe hain?

KYA: Do orderings ek saath exist karti hain — finish order (chaotic) aur commit order (jo original program order hona chahiye).

KYU: Hume ek aisi structure chahiye jo execution ko chaotic rehne de jabki commitment ko tidy banaye. Woh structure hai reorder buffer.

PICTURE: Figure dekho. Top track woh order hai jisme instructions finish hoti hain (jumbled arrows). Bottom track woh order hai jisme unhe commit karna hai (ek neat left-to-right line). ROB un dono ke beech ka funnel hai.

Step 2 — Buffer draw karo: boxes ki ek row aur do fingers

KYA: ROB kuch nahi balki $N$ identical slots ki ek row hai. Hum sab pictures mein $N = 8$ use karenge. Har slot mein ek in-flight instruction aa sakti hai.

KYU ek fixed size row? Hardware finite hai — koi "infinite list" nahi hoti. Ek fixed count $N$ maximum number of in-flight instructions hai, jise execution window kehte hain.

Hum row par do "fingers" (pointers) rakhte hain:

$head$ — woh finger jo drain karta hai. Iske "past" mein sab kuch ja chuka hai.
$tail$ — woh finger jo fill karta hai. Iske "future" mein sab kuch abhi bhi empty hai.

PICTURE: Aath boxes $0..7$ label kiye gaye hain. Green finger = head, orange finger = tail. Empty ROB ka matlab dono fingers ek hi box par baithe hain.

Recall

Tail pointer kisi cheez par point karta hai? ::: Next free slot par — jahan next issued instruction likhi jayegi.

Step 3 — Issue: boxes ko program order mein bharo (tail moves)

KYA: Jaise hi har instruction issue hoti hai (decode aur admit hoti hai), woh tail wale slot mein likhi jaati hai, phir tail ek aage badhta hai.

KYU program order mein? Kyunki saari trick positions par depend karti hai — buffer mein position yeh batati hai "kaun pehle aaya". Agar hum boxes out of order bharte, toh head ka matlab "oldest" nahi reh sakta. Order in = order of slots.

Program order mein chaar instructions lo:

I1: ADD R1, R2, R3
I2: SUB R4, R1, R5   (needs R1 from I1)
I3: MUL R6, R7, R8
I4: DIV R9, R4, R6   (needs R4 from I2 and R6 from I3)

Har ek next slot leta hai. Charon issue karne ke baad: head=0 (abhi bhi I1 par point kar raha hai), tail=4.

PICTURE: Slots $0, 1, 2, 3$ ab I1..I4 hold kar rahe hain, sab pending mark kiye gaye hain (result abhi compute nahi hua). head abhi $0$ par hai, tail $4$ par aa gaya hai.

Step 4 — Execute: results out of order aate hain (values bharo, drain mat karo)

KYA: Instructions functional units par run hoti hain aur alag alag times par finish hoti hain. Ek fast MUL ek slow ADD se pehle finish ho sakta hai jo pehle aayi thi. Jab koi finish hoti hai, hum uska value uske apne slot mein likhte hain aur us slot ko completed kar dete hain — lekin hum head nahi hilate.

KYU immediately commit nahi karte? Kyunki slot head ke baad ho sakta hai. Abhi commit karne se ek younger instruction ka result ek older se pehle visible ho jayega — program order toot jayega, aur ho sakta hai aise instruction ka kaam dikhne lage jo future exception ko erase kar dena chahiye.

Maan lo I3 (MUL) pehle finish hoti hai $R 6 = 120$ ke saath, phir I1 (ADD) $R 1 = 25$ ke saath:

PICTURE: I1 aur I3 ke slots violet (completed) ho jaate hain apni values ke saath; I2 aur I4 pending rehti hain. Sabse important baat: green head finger nahi hili — woh abhi bhi slot $0$ (I1) par point kar rahi hai. Notice karo I3 completed hai lekin stuck hai, kyunki uske aage I2 nahi hui.

Step 5 — Retire: head se drain karo, in order (head moves)

KYA: Har cycle mein hum sirf head ke neeche wale slot ko dekhte hain. Agar woh completed hai, toh uska value architectural register file mein copy karte hain, slot free karte hain, aur head ko aage badhate hain. Agar woh pending hai, toh stall karte hain — iske peeche koi nahi nikal sakta.

Trace karo:

Head I1 par (completed) → $R 1 = 25$ register file mein likho, head→1.
Head I2 par (pending) → stall, chahe uske peeche I3 finish ho chuki ho.
Baad mein I2 $R 4 = 15$ ke saath complete hoti hai → I2 retire karo, head→2. Phir I3 already completed hai → I3 retire karo ( $R 6 = 120$ ), head→3.

KYU wrap matter karta hai ab: enough retirements ke baad head right end se nikal jaata hai. mod N use wapas slot $0$ par bhejta hai, jo ab free ho chuka hai. Row ring ki tarah behave karti hai — isliye ROB ek circular FIFO hai.

PICTURE: Aath slots ek circle mein mod gaye hain. Green head arrow clockwise rotate ho raha hai drain karte waqt; orange tail arrow usse aage fill kar raha hai. Dono ke beech ka gap in-flight window hai.

Recall

ROB ko circle kyun draw karte hain, line nahi? ::: Kyunki head aur tail mod N ke saath advance karte hain; slot $N - 1$ ke baad woh slot $0$ par wrap ho jaate hain, freed slots ko hamesha reuse karte hain — yeh ek circle hai, koi dead-ending line nahi.

Step 6 — Edge cases: full, empty, aur unke beech ki fence

KYA: Do dangerous corners: buffer empty (retire karne ke liye kuch nahi) aur buffer full (issue karne ke liye koi slot nahi). Hume inhe alag bata sakna chahiye, kyunki ek pure circle mein head == tail dono ka matlab ho sakta hai.

KYU ek slot sacrifice karo? Kyunki $N$ slots aur dono conditions pointer equality use karti hain, toh meanings alag rakhne ke liye "gap of one" chahiye. Cost: ek slot; benefit: unambiguous state. (Alternatives exist — ek alag count register — lekin fence classic textbook picture hai.)

Degenerate case — full ROB stalls issue: agar buffer full hai, toh front end issuing band kar deta hai jab tak head kuch retire nahi kar leta. Execution ki chaos $N$ se bounded hai.

PICTURE: Do mini-rings side by side. Left ring: head aur tail ek hi slot par → EMPTY label. Right ring: tail head se ek slot peeche, ek grey "fence" slot → FULL label.

Step 7 — Flush: future ko ek hi jhatkay mein mitana

KYA: Maan lo head instruction ek exception raise kare (jaise divide-by-zero), ya kisi slot $k$ par ek branch mispredicted nikle isliye uske baad har slot wrong-path kaam hai. Hum flush karte hain: offending slot ke theek baad se leke tail tak har slot ko throw away karte hain, aur tail ko wapas set karte hain.

KYU yeh safe hai — aur kyun ROB apna naam kamaata hai: discard ki gayi instructions ne kabhi register file touch nahi kiya; unke results kabhi sirf ROB slots mein the (Step 4). Ek slot delete karo, result delete ho gaya. Architectural state abhi bhi slot $k$ ke predecessors tak ki har cheez reflect karta hai, aur uske baad kuch nahi — jo precisely ek precise state ki definition hai.

PICTURE: Ring jisme branch slot $k$ par hai (magenta). Slots $k + 1, k + 2$ wrong-path hain (crossed out); ek bada sweep arrow tail ko $k + 1$ par snap karta hai. Head side untouched hai — committed kaam survive karta hai.

Recall

Ek mispredicted branch zero damage ke saath recover kyun ho sakta hai? ::: Kyunki speculative results sirf ROB slots mein the, kabhi architectural registers mein nahi; tail ko branch ke past reset karna unhe commit hone se pehle hi discard kar deta hai.

Step 8 — Window aur IPC: bada ROB kyun help karta hai (ek point tak)

KYA: Slots ki sankhya $N$ woh width of the window hai jitna hum independent kaam ke liye aage dekh sakte hain. Zyada slots → zyada instructions in flight → overlap ke zyada chances.

KYU min? Do ceilings hain, aur tum lower ek ko hit karte ho:

Agar program mein parallelism kam hai, $N$ badhane se kuch nahi hoga — $ILP_{available}$ cap kar deta hai.
Agar buffer bahut chhota hai, toh woh bhar jaata hai aur issue stall ho jaata hai (Step 6) — $N / L$ cap kar deta hai.

Degenerate readings: $N = 1$ ke saath ROB ek plain in-order pipeline hai (window of one). Jaise $N \to \infty$ , IPC $ILP_{available}$ par saturate hota hai — extra slots useless ho jaate hain jab program ki parallelism exhaust ho jaati hai.

PICTURE: Vertical axis par IPC, horizontal par ROB size $N$ . Ek rising line $N / L$ jo bend ho jaati hai flat jab horizontal ceiling $ILP_{available}$ se milti hai — "knee" sabse chhota worthwhile ROB hai.

Ek picture mein summary

Sab kuch ek frame mein: slots ki ring, head jo committed values register file mein drain kar raha hai (in order), tail jo naye issues fill kar raha hai (in order), ring ke andar out-of-order completed values glow kar rahi hain, aur ek flush arrow ready hai tail ko mispredict par snap karne ke liye.

Recall Feynman Retelling — ek story ki tarah bolo

Socho ek ticket queue jo aath chairs ki ring ki tarah draw ki gayi hai. Do ushers us par chalte hain: tail usher new arrivals ko ek ek chair par bithata hai, hamesha us order mein jisme woh bahar se aate hain — yeh hai issue, aur yeh program ka order seating mein bake kar deta hai. Log phir apna khana (execute) wildly alag speeds par lete hain; ek fast eater teen chairs peeche jaldi finish kar sakta hai, lekin woh jaane nahi diya jaata — uski tray bas "done" mark ho jaati hai. Sirf head usher logon ko bahar jane deta hai, aur sirf sab se aage wali chair waale ko, aur tabhi jab unki tray done ho — yeh hai retire in program order, woh akela moment jab kuch real hota hai (registers mein likha jaata hai). Jab ushers ki chairs milti hain, hum gap padhte hain: same chair matlab room empty hai; ek chair apart (ek kept-empty fence chair ke saath) matlab full hai, toh hum seating band karte hain. Aur agar front person ke paas bura ticket nikle (ek exception ya wrong-guess branch), toh hum kisi ko chase nahi karte — hum tail usher ko bas kehte hain "us chair ke baad baith gaye sab log kabhi yahan the hi nahi", uski position wapas snap karte hain. Kyunki un mein se koi room se gaya nahi tha (kuch registers hit nahi hua), unhe mitana kuch nahi lagta aur bahar ki duniya ek perfectly clean, in-order story dekhti hai — reorder buffer ka poora point. Bada room ( $N$ ) matlab zyada overlap, lekin tabhi tak jab tak program ke paas seat karne ke liye independent diners hain.

Related builds: Register-renaming, Reservation-stations, Instruction-retirement, Memory-ordering, Superscalar-processors.