Reservation stations: Exercises — Hinglish deep dive

5.3.6 · D4 · Hardware › Advanced Microarchitecture › Reservation stations

Ek instruction issue hoti hai aur uski reservation station end up hoti hai: {Op=ADD, Vj=?, Vk=40, Qj=Mult1, Qk=0}. Simple shabdon mein bolo ki yeh station exactly kiska wait kar rahi hai aur use kya pata hai.

Recall Solution 1.1

Fields ko ek ek karke padho.

Qk=0 → doosra operand ready hai; uski value Vk=40 mein hai.
Qj=Mult1 → pehla operand ready nahi hai; station Mult1 use produce karegi. Abhi tak koi number nahi hai, isliye Vj blank hai (?).

Shabdon mein: "Main ek ADD hoon. Mera doosra input (40) mere paas already hai. Main station Mult1 ka wait kar raha hoon ki woh pehla input broadcast kare. Jaise hi woh karta hai, main woh value Vj mein capture karta hoon, Qj=0 set karta hoon, aur dono operands ready hone par (Qj=Qk=0) main ALU (arithmetic logic unit) mein fire karta hoon."

Exercise 1.2 (L1)

Register status table dikhata hai Status[R6] = empty aur Status[R7] = Add2. Instruction SUB R8, R6, R7 issue ho rahi hai. Vj, Vk, Qj, Qk fill karo.

Recall Solution 1.2

Har source register ko status table ke against match karo.

Source 1 hai R6. Status[R6] = empty → value register file mein hai → use Vj mein copy karo, Qj = 0 set karo.
Source 2 hai R7. Status[R7] = Add2 → value pending hai, Add2 produce karega → Qk = Add2 set karo, Vk blank chhodo.

Result: {Op=SUB, Vj=R6_val, Vk=?, Qj=0, Qk=Add2}.

Level 2 — Application

Exercise 2.1 (L2)

Ek clean machine diya gaya hai (saare registers register file mein ready hain), is sequence ko issue karo aur har issue ke theek baad RS contents aur status-table changes do:

1. MUL  R1, R2, R3
2. ADD  R4, R1, R5

Maano Mult1 free multiply station hai aur Add1 free add station.

Recall Solution 2.1

MUL issue (cycle 1). R2 aur R3 dono status table mein empty hain → dono operands ready hain. Mult1: {Op=MUL, Vj=R2_val, Vk=R3_val, Qj=0, Qk=0}. Phir Status[R1] = Mult1 set karo (R1 ki next value ab Mult1 se aayegi).

ADD issue (cycle 2). Source R1: Status[R1] = Mult1 → pending → Qj = Mult1, Vj blank. Source R5: empty → ready → Vk = R5_val, Qk = 0. Add1: {Op=ADD, Vj=?, Vk=R5_val, Qj=Mult1, Qk=0}. Phir Status[R4] = Add1 set karo.

Yeh ek pure RAW dependency hai (Add1 ko sachchi mein Mult1 ka jawab chahiye), aur tag Mult1 use exactly capture karta hai.

Exercise 2.2 (L2)

Exercise 2.1 continue karo. Kisi baad ke cycle mein Mult1 finish ho jaata hai aur apna result = 12 Common Data Bus (CDB) par broadcast karta hai. Dikhaao Add1 mein aur register file mein kya changes hote hain.

Recall Solution 2.2

Har station CDB (shared broadcast wire) tag ko apne Qj aur Qk ke against snoop karta hai.

Add1.Qj = Mult1 match karta hai → capture karo: Vj ← 12, phir Qj ← 0. Ab Add1: {Op=ADD, Vj=12, Vk=R5_val, Qj=0, Qk=0} → dono ready → execute karne ke liye eligible.
Register file: Status[R1] = Mult1 match karta hai → R1 ← 12 likhho, Status[R1] empty kar do.
Mult1 free ho jaata hai (Busy=0).

Exercise 2.3 (L2)

Ek machine mein 64 total reservation stations hain. Har operand tag field ko kitne bits chahiye? Agar baad mein design 128 stations tak double ho jaaye, toh kitne bits?

Recall Solution 2.3

Ek tag ko stations mein se ek ko naam dena hota hai, isliye hum sirf itne bits chahte hain jo unhe count kar sakein. Rule shabdon mein: tag bits = bits ki sabse chhoti whole number jo har station ko label kar sake — yaani station count ke base-2 logarithm ko next whole number tak round up karo.

64 stations: kyunki $64 = 2 \times 2 \times 2 \times 2 \times 2 \times 2$ (chhe twos), exactly 6 bits se saare 64 label ho jaate hain.
128 stations: kyunki $128 = 2 \times 64$ (saat twos), tumhe 7 bits chahiye.

Toh station count double karne par exactly ek bit per tag add hoti hai — har extra bit se double stations naam mil sakti hain.

Level 3 — Analysis

Exercise 3.1 (L3)

Parent note se full four-instruction sequence chalao aur issue time par explain karo kyun instruction 4 Add2 par depend karti hai aur Mult1 par nahi:

1. MUL R1, R2, R3
2. ADD R4, R1, R5      ; RAW on R1
3. SUB R1, R6, R7      ; WAW on R1
4. ADD R8, R1, R9      ; RAW on new R1

Definitions se station-naming rule use karo: instruction 2 pehli free add station Add1 mein jaati hai, instruction 3 agli free add station Add2 mein, instruction 4 agli Add3 mein.

Recall Solution 3.1

Status[R1] ko ek moving pointer ki tarah track karo "koun R1 ki current value produce karta hai."

Inst 1 ke Mult1 mein issue hone ke baad: Status[R1] = Mult1.
Inst 2 Add1 mein issue hoti hai, Status[R1] = Mult1 padhti hai, toh Add1.Qj = Mult1. Yeh tab-ke-waqt-wala producer snapshot karta hai.
Inst 3 (SUB R1,…) Add2 mein issue hoti hai. Kyunki woh R1 likhti hai, hum Status[R1] = Add2 overwrite karte hain. Yeh hai WAW resolution: sabse naya writer R1 ka producer ban jaata hai.
Inst 4 Add3 mein issue hoti hai, Status[R1] = Add2 padhti hai → Add3.Qj = Add2.

Kyun 4 Add2 par depend karta hai, Mult1 par nahi: jab inst 4 status table padhta hai, tab tak inst 3 pointer overwrite kar chuka tha. Status table hamesha ek register ki latest binding name karta hai, isliye inst 4 correctly inst 3 ke result ka wait karta hai. Inst 2, jisne pointer pehle padha tha, ab bhi purana Mult1 tag rakhta hai — exactly wahi value jo use milni chahiye, kyunki program order mein inst 2, R1 ko inst 3 ke rewrite karne se pehle padhta hai.

Neeche wala figure kaise padhen. Dono producers "ek R1 value" ke left mein baithe hain: Mult1 (upar, cyan) aur Add2 (neeche, amber). R1 ke dono consumers right mein hain: Add1 (inst 2, upar) aur Add3 (inst 4, neeche). Cyan arrow ko upar se follow karo — yeh dikhata hai ki inst 2 early pointer value Mult1 snapshot kar raha hai. Amber arrow ko neeche se follow karo — yeh dikhata hai ki inst 4 later pointer value Add2 snapshot kar raha hai. Beech waala box single Status[R1] pointer hai; cyan line woh hai jo usne early padha, amber line woh hai jo use overwrite kiya gaya. Ek hi register naam, do alag producers — purely kab har consumer ne pointer padha, isse decide hota hai.

Exercise 3.2 (L3)

Exercise 3.1 mein, jab Mult1 finally broadcast karta hai, register file use ignore karti hai. Prove karo ki yeh sahi hai — ki R1 ko Mult1 ki value nahi leni chahiye.

Recall Solution 3.2

Jab Mult1 broadcast karta hai, register file Status[R1] check karti hai. Lekin inst 3 already Status[R1] = Add2 set kar chuka hai, isliye tag Mult1 match nahi karta → register file kuch nahi karta.

Kyun sahi hai: program order kehta hai inst 3 (R1 = R6-R7) R1 ko inst 1 (R1 = R2*R3) ke baad likhta hai. R1 ki architectural final value inst 3 ka result honi chahiye. Agar register file Mult1 ka late broadcast accept karti, toh woh inst 3 ki value clobber kar deti — ek WAW violation. Yeh mismatch hi woh mechanism hai jo inst 1 ki write ko register file ke nazariye se "dead" banata hai.

Meanwhile Add1.Qj = Mult1 ne match kiya, toh inst 2 correctly abhi bhi purana R1 receive karta hai — kyunki inst 2 legitimately R1 ko inst 3 ke overwrite karne se pehle padhta hai.

Level 4 — Synthesis

Exercise 4.1 (L4)

Tumhe ek machine diya gaya hai jisme ek multiply station, ek add station, aur ek CDB hai. Consider karo:

1. MUL R1, R2, R3
2. MUL R4, R5, R6

Dono multiplies independent hain. Agar multiply 4 execute cycles leta hai aur dono back-to-back cycles mein issue hote hain, toh throughput yahan kya limit karta hai, aur ek single design change kya fix karta hai?

Recall Solution 4.1

Sirf ek multiply station ke saath, inst 2 issue nahi ho sakta jab tak inst 1 ka station free na ho (sirf write-result ke baad free hota hai). Bhale hi dono multiplies independent hain, woh station par serialize ho jaate hain, data par nahi.

Yeh reservation stations par structural hazard hai (parent note, Mistake 1: "agar RS full hai, toh issue stall karni padegi"). Fix: ek doosra multiply reservation station add karo taaki inst 2 issue ho sake aur parallel mein wait/execute kar sake. (Do stations se feed hone wala ek pipelined multiply unit dono ko in-flight rakh sakta hai; CDB abhi ek hi bus hai lekin results yahan 4 cycles apart finish hote hain, toh koi CDB conflict nahi.)

Exercise 4.2 (L4)

Design question: dono functional units same cycle mein finish hote hain aur dono single CDB (Common Data Bus) chahte hain. Conflict describe karo, phir ek modern fix do aur wiring terms mein uski cost.

Recall Solution 4.2

Conflict: classic Tomasulo mein ek CDB hai → sirf ek result per cycle broadcast ho sakta hai. Do simultaneous completions ek CDB par structural hazard hain; ek unit ko apna write-result ek cycle delay karna padega (arbitration winner choose karta hai).

Modern fix: ek doosra CDB add karo (generally $m$ buses). Ab per cycle $m$ results tak broadcast ho sakte hain.

Cost: har reservation-station operand field aur register file ko har bus snoop karna padega. $n$ snooping structures aur $m$ buses ke saath yeh $O (n \times m)$ comparators/wires hain — throughput area aur power se kharida jaata hai. Yahi tradeoff parent note flag karta hai.

Level 5 — Mastery

Exercise 5.1 (L5)

Corner case. Kya hota hai agar ek operand usi cycle available ho jaaye jab ek instruction issue ho rahi hai — yaani producing station usi cycle mein CDB par broadcast kar raha hai jab tum status table padh rahe ho? Dikhaao kyun ek naive implementation consumer ko deadlock kar sakta hai, aur standard fix bolo.

Recall Solution 5.1

Race. Issue ke dauran tum Status[R1] = Mult1 padhte ho aur Qj = Mult1 set karte ho. Lekin is same cycle Mult1 CDB par broadcast kar raha hai. Agar tumhari capture logic sirf CDB ko un stations ke against check karti hai jo cycle ke start par already Qj = Mult1 hold kar rahe the, toh naya issue hua station broadcast miss kar gaya. Uska Qj hamesha Mult1 rahega — Mult1 kabhi dobara broadcast nahi karega (woh free ho gaya). Consumer ek aisa tag wait karta rahega jo kabhi fire nahi ho sakta → deadlock (lost wakeup).

Standard fix: issue karte waqt, operand ka producing tag usi cycle mein broadcast ho rahe CDB tag ke against bhi compare karo. Agar match karte hain, toh broadcast value directly Vj mein capture karo aur turant Qj = 0 set karo (tag store karne ki jagah). Equivalently: status-table read aur CDB snoop "saath saath" hote hain, toh same-cycle broadcast ya toh forward ho jaata hai ya tag capture ho jaata hai aur agli cycle mein honor ho jaata hai. Kisi bhi case mein, koi wakeup lost nahi hota.

Exercise 5.2 (L5)

Degenerate input. Ek instruction hai ADD R5, R5, R5 (dono sources same register hain, jo destination bhi hai). Vj, Vk, Qj, Qk aur Status[R5] trace karo maante hue ki entry par Status[R5] = Mult1 hai, aur yeh ADD station Add1 mein issue hoti hai. Confirm karo ki koi corruption nahi hoti.

Recall Solution 5.2

Step 1 — issue, operands fill karo. Dono sources R5 hain, aur Status[R5] = Mult1 → pending. Toh hum dono operand slots ek hi producer se fill karte hain: Add1: {Op=ADD, Vj=?, Vk=?, Qj=Mult1, Qk=Mult1}.

Step 2 — issue, destination update karo. Kyunki R5 bhi destination hai, Status[R5] = Add1 overwrite karo (is station ka apna tag). Purani binding (Mult1) ka read pehle se hi Qj/Qk mein capture ho chuka hai; write ek brand-new binding (Add1) banata hai. Yeh do alag events hain, isliye interfere nahi karte.

Step 3 — Mult1 value $v$ broadcast karta hai. Station CDB tag ko dono Qj aur Qk ke against snoop karta hai. Dono Mult1 ke barabar hain, toh dono match karte hain → $v$ ko dono Vj aur Vk mein capture karo, dono Q fields clear karo: Add1: {Op=ADD, Vj=v, Vk=v, Qj=0, Qk=0} → dono ready → execute karne ke liye eligible. Register file Status[R5] check karta hai: ab yeh Add1 ke barabar hai, nahi Mult1 ke, toh correctly R5 ko Mult1 ke broadcast se nahi likhta (woh stale value hoti).

Step 4 — Add1 execute karta hai aur write back karta hai. Yeh $v + v = 2 v$ compute karta hai, tag Add1 ke roop mein broadcast karta hai. Register file Status[R5] = Add1 check karta hai → match → R5 ← 2v likhho, status entry clear karo. Add1 free ho jaata hai.

Kyun koi corruption nahi: R5 ka read issue par capture kiya gaya old binding tag (Mult1) use karta hai, jabki R5 ka write ek naya binding (Add1) banata hai. Bhale hi ek architectural register naam teen baar appear hota hai (do sources aur destination), rename cleanly "R5 ki woh value jo andar jaate waqt thi" ( $v$ , do baar) ko "R5 ki woh value jo bahar aate waqt hai" ( $2 v$ ) se alag karta hai. Koi slot kabhi overwrite hone ke baad padha nahi jaata. Yahi guarantee hai jo dynamic renaming deta hai — 5.2.03-Register-renaming dekho.

Exercise 5.3 (L5)

Cost synthesis. Ek CPU mein 40 integer RS + 24 floating-point (FP) RS hain. (a) Tag width kya hai? (b) Agar har RS entry do tags (Qj, Qk) plus ek ek 32-bit value (Vj, Vk) plus ek 6-bit Op field aur 1 Busy bit store karta hai, toh ek RS entry mein kitne bits hain? (c) Saare 64 RS mein total storage bits mein kya hai?

Recall Solution 5.3

(a) Tag width. Total RS $= 40 + 24 = 64$ . Kyunki $64 = 2^{6}$ (two ke chhe factors), bits ki sabse chhoti whole number jo 64 stations mein se har ek ko label kar sake woh 6 bits hai.

(b) Bits per entry. Har slot add karo:

Op: 6 bits
Qj, Qk: $2 \times 6 = 12$ bits (do tags, har ek 6 bits part (a) se)
Vj, Vk: $2 \times 32 = 64$ bits (do 32-bit values)
Busy: 1 bit

Total per entry $= 6 + 12 + 64 + 1 = 83$ bits.

(c) Total storage. Saare 64 stations mein se har ek ek 83-bit entry rakhta hai: $64 \times 83 = 5312 bits \approx 664 bytes .$

Result padhna: value fields (Vj, Vk) dominate karte hain — 83 mein se 64 bits sirf do operand values hain. Tags aur control bits comparison mein saste hain. Isliye datapath widen karna (32 → 64-bit operands) RS area mein zyada cost karta hai kuch aur stations add karne se.

Connections

5.3.6 (parent topic)
5.3.04-Scoreboarding — woh centralized ancestor jise in distributed stations ne improve kiya.
5.3.07-Reorder-buffer — jahan precise-exception handling is machinery mein bolt hoti hai.
5.2.03-Register-renaming — woh renaming jis par Exercise 5.2 depend karta hai.
4.6.02-Pipeline-hazards — har RAW/WAR/WAW mention ke peeche hazard taxonomy.
5.3.09-Load-store-queues — memory-side analogue jo RS se akele cover nahi hoti.

Recall Ek-line self-test

Kaunsa single test decide karta hai ki register file CDB broadcast par update hoga? ::: Kya broadcast tag register ki current Status[] entry se match karta hai — ek status-table match, is baat se independent ki stations ne value capture ki ya nahi.

Exercises — Reservation stations

Level 1 — Recognition

Exercise 1.1 (L1)