Reservation stations: Visual walkthrough — Hinglish deep dive

5.3.6 · D2 · Hardware › Advanced Microarchitecture › Reservation stations

Shuru karne se pehle, teen plain-English words jo hum aage earn karenge:

Step 1 — Problem Draw Karo: Names Jo Jhooth Bolte Hain

KYA. Yeh chaar instructions dekho. R1 likha jaata hai, phir padha jaata hai, phir dobara likha jaata hai, phir dobara padha jaata hai.

1. MUL R1, R2, R3   ; R1 = R2 * R3   (writes R1)
2. ADD R4, R1, R5   ; R4 = R1 + R5   (reads R1)
3. SUB R1, R6, R7   ; R1 = R6 - R7   (writes R1 AGAIN)
4. ADD R8, R1, R9   ; R8 = R1 + R9   (reads the NEW R1)

KYUN. Poori pareshani sirf naam R1 mein hai. Line 2 ko pehla R1 chahiye (line 1 se). Line 4 ko doosra R1 chahiye (line 3 se). Agar hum out of order chalayein, toh kiska R1 "the" R1 hai? Yahi ambiguity exactly pipeline hazards ki family hai jise hum khatam karna chahte hain.

PICTURE. Figure mein cup R1 ko overwrite hote dikhaaya gaya hai. Neela arrow woh read hai jo purani juice chahta hai; laal arrow woh read hai jo nayi juice chahta hai. Ek cup dono nahi rakh sakta — yahi bug hai.

Step 2 — Har Desk Ko Ek Nickname Do (Tag)

KYA. Hum desks banate hain aur har ek ko nickname dete hain: Mult1, Add1, Add2, Add3. Hum ek chota lookup table bhi banate hain, register status table, jismein har register name ke liye ek row hai.

KYUN. Hum chahte hain ek sawaal ka jawab: "agar main abhi R1 padhun, toh uski newest value kahan se aa rahi hai?" Status table exactly yehi batata hai. Iska rule:

PICTURE. Khaali rows green draw ki gayi hain (cup padhna safe hai). Tag hold karne wali row orange draw ki gayi hai (us desk ka wait karo). Abhi tak kuch issue nahi hua, toh har row green hai.

Har desk khud yeh slots carry karta hai (yeh desk ki poori memory hai):

Step 3 — MUL Issue Karo: Pehla Tag Mint Karo

KYA. Line 1 (MUL R1, R2, R3) free desk Mult1 le leta hai. Dono inputs R2, R3 apne cups mein ready hain, toh numbers seedha copy kar lete hain.

$Mult1 : {O p = MUL, V_{j} = [R 2], V_{k} = [R 3], Q_{j} = 0, Q_{k} = 0}$

$V_{j} = [R 2]$ — abhi cup R2 se actual number copy kar liya.
$Q_{j} = 0, Q_{k} = 0$ — koi promise pending nahi; dono inputs ready hain ⇒ yeh desk turant compute kar sakta hai.

Phir yeh crucial line:

$Status [R 1] \leftarrow Mult1$

KYUN. Yeh ek tag ka janam hai. Hum announce kar rahe hain: "ab se, jo bhi R1 padhega woh asal mein desk Mult1 ka eventual output padh raha hai." Naam R1 ko quietly Mult1 mein rename kar diya gaya hai.

PICTURE. Row R1 green se orange ho jaati hai aur ab nickname Mult1 store karta hai. R1 row se Mult1 desk tak ek arrow jaata hai — "teri value abhi yahan rehti hai."

Step 4 — ADD Issue Karo (Line 2): Ek Number Nahi, Promise Capture Karo

KYA. Line 2 (ADD R4, R1, R5) desk Add1 le leta hai. Input R5 ready hai (value copy karo). Lekin input R1? Hum $Status [R 1]$ lookup karte hain aur woh kehta hai Mult1 — promise hai, number nahi.

$Add1 : {O p = ADD, V_{j} = ?, V_{k} = [R 5], Q_{j} = Mult1, Q_{k} = 0}$

$Q_{j} = Mult1$ — "mera pehla input abhi yahan nahi hai; woh desk Mult1 se aayega." Yeh woh promise hai jo likha ja raha hai.
$V_{j} = ?$ — jaanboojh kar khaali; abhi uske liye koi number nahi hai.

Aur is instruction ke apne output register ke liye:

$Status [R 4] \leftarrow Add1$

KYUN. Yeh woh moment hai jab R1 par RAW ("read-after-write") dependency encode hoti hai — stall ke roop mein nahi, balki ek subscription ke roop mein. Add1 ab Mult1 jo bhi shout karega uske liye subscribed hai. Isse compare karo scoreboarding se, jahaan ek central board sabhi dependencies ki policing karta hai; yahan har desk sirf apne khud ke promises ki parwaah karta hai.

PICTURE. Add1 ke $Q_{j}$ slot se Mult1 desk tak ek dashed orange wire draw ki gayi hai. Woh dashed wire promise hai. Jab yeh solid ho jaaye, value aa chuki hai.

Step 5 — SUB Issue Karo (Line 3): Tag Overwrite Ho Jaata Hai

KYA. Line 3 (SUB R1, R6, R7) R1 ko dobara likhta hai. Yeh desk Add2 le leta hai; dono inputs ready hain. Decisive move:

$Status [R 1] \leftarrow Add2 (pehle Mult1 tha, ab Add2 hai)$

KYUN. Yeh poore algorithm ka dil hai. R1 ka ab ek naya latest owner hai. Purana Mult1 se binding delete nahi hui hai — Add1 ne ise Step 4 mein already copy kar liya tha — yeh sirf ab "current" R1 nahi rahi. Do sachai ek saath exist karti hain:

Add1 abhi bhi Mult1 ki taraf point karta hai (usne woh promise past mein freeze kar liya tha).
Status table ab Add2 ki taraf point karti hai (present ka sach).

Yahi coexistence hai jis tarah se ek akela naam ek saath do alag values safely mean kar sakta hai. Yahi WAW ("write-after-write") hazard ko khatam karta hai: baad wala write quietly newest binding ban jaata hai.

PICTURE. R1 row ko redraw kiya gaya hai: nickname visibly Mult1 se Add2 mein badal jaata hai. Add1 ki dashed wire abhi bhi stubbornly Mult1 ki taraf point karti hai (faded draw ki gayi) — past ka ek snapshot. Ek naya arrow R1 → Add2 point karta hai.

KYA. Line 4 (ADD R8, R1, R9) desk Add3 le leta hai. Yeh $Status [R 1]$ padhta hai — jo ab Add2 kehta hai.

$Add3 : {O p = ADD, V_{j} = ?, Q_{j} = Add2, V_{k} = [R 9], Q_{k} = 0}$

$Q_{j} = Add2$ — Add3 sahi taur par line 3 ke result ka wait karta hai, na ki line 1 ka.

KYUN. Yeh Step 5 mein overwrite ka payoff hai. Kyunki table update ki gayi thi, line 4 automatically sahi producer par depend karti hai. Koi special reasoning zaroorat nahi thi — table hi reasoning hai.

PICTURE. Ab hawa mein do dashed wires latki hain: Add1 → Mult1 (purani R1) aur Add3 → Add2 (nayi R1). Woh alag desks ki taraf point karti hain. Picture prove karti hai ki dono readers ek saath sahi hain.

Step 7 — Shout: Mult1 Khatam Hota Hai Aur Broadcast Karta Hai

KYA. Mult1 computing khatam karta hai. Apna result Common Data Bus (CDB) par rakhta hai — ek shared wire jise sab sunte hain — apne nickname Mult1 ke saath tagged.

Har desk apne dono inputs par yeh tiny check chalaata hai:

$if Q_{j} = (tag on CDB) \Rightarrow V_{j} \leftarrow (value on CDB), Q_{j} \leftarrow 0$

Term by term padhein:

$Q_{j} = tag on CDB$ — "kya mera promise wahi hai jo abhi pay kiya ja raha hai?"
$V_{j} \leftarrow value$ — number pakad lo.
$Q_{j} \leftarrow 0$ — promise faad do; yeh input ab ek real value hai.

Broadcast kyun karte hain? Mult1 issue hone ke waqt, hum nahi jaante the ki iske output ki zaroorat kise padegi (line 4 abhi issue bhi nahi hui thi). Point-to-point wiring mein har desk ko har doosre desk se pre-connect karna padta — woh $O (n^{2})$ wires hote. Ek shared bus kisi bhi number ke listeners ko free mein subscribe karne deta hai.

PICTURE. Orange CDB wire (Mult1, 42) carry karte hue jal uthti hai. Add1 ki dashed wire solid green ho jaati hai — usne match kiya, 42 capture kiya, aur $Q_{j}$ clear kar diya. Status table row R1 kuch nahi karti: yeh Add2 hold karti hai, Mult1 nahi, toh shout ko ignore karti hai (woh value register file ke liye ab "dead" hai).

Step 8 — Doosra Shout: Add2 Khatam Hota Hai, Register File Update Hoti Hai

KYA. Baad mein, Add2 khatam hota hai aur (Add2, value) broadcast karta hai. Ab do listeners react karte hain:

Add3 match karta hai ( $Q_{j} = Add2$ ): value capture karta hai, tag clear karta hai — Add3 ab run kar sakta hai.
Register file $Status [R 1]$ check karti hai; yeh Add2 ke barabar hai, toh cup R1 mein sach mein likhti hai aur row ko wapas green kar deti hai.

$if Status [R 1] = (tag on CDB) \Rightarrow R 1 \leftarrow value, Status [R 1] \leftarrow \emptyset$

KYUN. Sirf latest binding ko architectural cup ko touch karne ki permission hai. Kyunki Add2 R1 ka latest owner tha (Step 5 mein set hua), yahi woh write hai jo baahri duniya ko visible hoti hai. Mult1 ki value kabhi cup R1 tak nahi pahunchti — bilkul sahi, kyunki original program mein line 3 ne line 1 ko overwrite kiya tha.

PICTURE. CDB (Add2, val) carry karta hai. Add3 ki dashed wire solid ho jaati hai; R1 cup nayi juice se bhar jaata hai aur uski status row wapas green ho jaati hai. Program order honoured hai chahe execution scrambled thi.

Ek-Picture Summary

KYA. Tag Mult1 ki poori zindagi dikhata ek frame: issue par mint hua → Add1 ke andar freeze hua → status table mein Add2 ne supersede kiya → CDB par pay kiya → Add1 ne capture kiya → register file ne ignore kiya. Overlaid: tag Add2 ki parallel zindagi, jo actually cup R1 tak pahunchti hai.

KYUN. Jo hazards hum le kar shuru hue the woh sab ab visibly khatam hain:

RAW → ek dashed wire (subscription) ban gaya jo value shout karne par fill hota hai.
WAW → "status row overwrite karo; latest owner jeetega" ban gaya.
WAR → pehle wala reader pehle hi apni value freeze kar chuka tha, toh baad wala write use disturb nahi kar sakta.

Recall Feynman Retelling — aise kaho jaise kisi dost ko explain kar rahe ho

Registers labelled cups hain, lekin ek cup overwrite ho sakta hai, isliye R1 jaisa naam ek jhoothi hai — alag times par alag numbers ka matlab. Fix: jab bhi koi instruction ek register write karne wali ho, hum cup par trust karna band kar dete hain aur ek choti table mein ek nickname likh dete hain — "fresh R1 desk Mult1 se aa rahi hai." Jo bhi instruction us waqt R1 padhti hai woh uss nickname ko promise ke roop mein copy kar leti hai. Jab R1 par doosra write aata hai, hum sirf table ka nickname naye desk mein change kar dete hain; jo koi pehle hi purana nickname copy kar chuka tha woh rakh leta hai (unhone past freeze kar liya), jo ab padh raha hai use naya milta hai. Desks compute karte hain jis second dono inputs ke liye real numbers ho jaate hain — kisi bhi order mein. Jab ek desk khatam hota hai, woh apna result aur apna nickname ek shared wire par shout karta hai; har desk jo woh nickname promise ke roop mein hold kar raha tha woh number pakad leta hai aur promise faad deta hai. Register cup sirf usi desk se write hota hai jis par table currently point karti hai — latest writer — toh baahri duniya exactly program ka final answer dekhti hai, chahe andar sab kuch out of order chala.

Connections

Parent: Reservation stations — poora mechanism jise yeh page step by step draw karta hai.
5.3.04-Scoreboarding — centralized dependency tracking; yahan ke distributed desks se contrast karo.
5.3.07-Reorder-buffer — is tag-passing ke upar precise exceptions add karta hai.
5.2.03-Register-renaming — "fresh cup per write" idea, formalized.
4.6.02-Pipeline-hazards — RAW/WAR/WAW, woh dushman jinhe humne khatam kiya.
5.3.09-Load-store-queues — is trick ka memory-side cousin.