Noesis
5.3.6 · D3 · HinglishAdvanced Microarchitecture

Worked examples — Reservation stations

4,025 words18 min read↑ Read in English

5.3.6 · D3 · Hardware › Advanced Microarchitecture › Reservation stations

Yeh page Reservation stations ka exhaustive drill room hai. Parent note ne aapko machinery sikhayi thi; yahan hum use har tarah ki situation ke against run karte hain jo ek reservation-station (RS) system face kar sakta hai. Shuru karne se pehle, ek waada: neeche har symbol parent note mein paida hua tha, lekin jab bhi hum use karte hain hum use fir se anchor karte hain, taaki jo reader bhool gaya ho woh picture se dubara build kar sake.

The scenario matrix

Har reservation-station problem actually inhi cells mein se ek hoti hai. Neeche hamare examples inhe sab cover karte hain, aur har example us cell ke saath label hai jo woh hit karta hai.

# Cell (case class) Kya tricky banata hai Example
C1 Dono operands issue par pehle se ready Degenerate: bilkul koi wait nahi Ex 1
C2 Ek operand pending (single RAW) Ek IOU hold karna padta hai Ex 2
C3 Dono operands pending Do IOUs, arrival ka order Ex 3
C4 Do consumers ek hi result ke Ek broadcast, kai captures Ex 4
C5 WAW (write-after-write) same register par Status overwrite / "dead" value Ex 5
C6 WAR (write-after-read) false dependency Renaming ise kyun vanish kar deta hai Ex 6
C7 Structural hazard: RS full / do units same cycle mein finish System stalls, limits Ex 7
C8 Load/store address ready nahi (degenerate operand path) Memory, two-phase execute Ex 8
C9 Word problem (real-world sizing) Tag bits / RS sizing count karo Ex 9
C10 Exam twist: kya OoO committed result badalta hai? Correctness vs. ordering Ex 10

Neeche ki figure ek station ki anatomy draw karti hai — Op, Vj/Qj, Vk/Qk, Busy fields — saath mein woh CDB jo yeh snoop karta hai aur ready gate. Ise dekhte raho: neeche har example bas yahi picture hai alag-alag numbers fill hone ke saath. Magenta "snoop" arrow dekho jo bus se wapas station mein jaata hai (yahi Capture hai) aur violet ready gate neeche (Qj = 0 AND Qk = 0 → execute). Corner legend mein das cells C1–C10 listed hain taaki dekh sako har example kaun sa slot fill karta hai.

Figure — Reservation stations

Example 1 — Cell C1: dono operands ready (the degenerate case)

Forecast: padhne se pehle guess karo — kya yeh instruction kabhi wait karni padegi?

  1. Issue. Ek free station allocate karo, use Add1 kaho. Kyunki Status[R1] empty hai, value copy karo: Vj = 5, Qj = 0. Kyunki Status[R2] empty hai, Vk = 8, Qk = 0. Yeh step kyun? Status table empty hai ⇒ koi producer desk pending nahi ⇒ hum real numbers seedha le lete hain, IOUs nahi.
  2. Readiness check. Qj = 0 aur Qk = 0 → station usi cycle mein ready hai jis cycle mein issue hua. Yeh step kyun? Readiness define hai dono IOUs cleared hone se. Snoop karne ke liye kuch nahi hai.
  3. Execute. 5 + 8 = 13 compute karo. Phir tag Add1 ke saath CDB par 13 Write karo. Yeh step kyun? RS ka poora point yahi hai ki no-dependency instruction zero waiting cost pay karta hai — yeh ek plain pipeline ki tarah behave karta hai.

Verify: R3 = 5 + 8 = 13. Units: sab plain register values hain (dimensionless integers), sum ek value hai → consistent. Koi IOU kabhi set nahi hua, toh "degenerate" cell ko sach mein koi CDB snoop chahiye nahi.

Example 2 — Cell C2: ek pending operand (single RAW)

Forecast: (ii) ka kaun sa field IOU hold karega — Qj ya Qk? Aur R4 mein aakhir mein kaun sa number aayega?

  1. Issue (i). Station Mult1: Vj=4, Vk=6, Qj=0, Qk=0. Status[R1] = Mult1 set karo. Kyun? R1 ki next value ab desk Mult1 se aayegi; phone book mein yahi likhna chahiye.
  2. Issue (ii). Uska operand 1 R1 hai. Status[R1] = Mult1 lookup karo (empty nahi!) → IOU store karo: Qj = Mult1. Operand 2 R5 hai, empty → Vk = 10, Qk = 0. Kyun? R1 ready nahi, toh value ki jagah hum kaun produce karega yeh record karte hain. Yahi renaming hai: (ii) ab tag Mult1 par depend karta hai, naam R1 par nahi.
  3. Mult1 finish karta hai: 4 * 6 = 24, CDB par (Mult1, 24) broadcast karta hai. Kyun? Ek loudspeaker announcement; har desk snoops karta hai.
  4. Add1 capture karta hai. Uska Qj = Mult1 shouted tag se match karta hai → Vj = 24, Qj = 0 set karo. Ab Qj=Qk=0 → execute karo 24 + 10 = 34. Kyun? Capture woh moment hai jab IOU real ingredient mein badal jaata hai.

Verify: R4 = (4*6) + 10 = 34. Sanity: (ii) exactly tab tak wait kiya jab tak (i) ne apni value produce ki aur ek cycle bhi zyada nahi — correct RAW behaviour.

Example 3 — Cell C3: dono operands pending

Forecast: kya (iii) cycle 5, cycle 8, ya beech mein kahin execute karta hai?

  1. Issue (iii). Status[R1]=Mult1, Status[R4]=Sub1. Dono non-empty → do IOUs: Qj=Mult1, Qk=Sub1. Abhi koi V nahi. Kyun? Dono sources in-flight hain; station ek saath do IOUs hold karta hai — yeh bilkul legal hai.
  2. Cycle 5: Sub1 broadcast karta hai (Sub1, 15). (iii) snoops: Qk match karta hai → Vk=15, Qk=0. Lekin Qj=Mult1 abhi bhi ≠ 0. Kyun? Ek IOU cleared, ek bacha ⇒ abhi ready nahi. Readiness ke liye dono chahiye.
  3. Cycle 8: Mult1 broadcast karta hai (Mult1, 9). Qj match karta hai → Vj=9, Qj=0. Ab dono zero → execute karo 9 + 15 = 24. Kyun? Station last-arriving operand se gate hota hai. Arrival ka order matter nahi kiya, sirf maximum.

Verify: R7 = (3*3) + (20-5) = 9 + 15 = 24. Timing sanity: execution max(5, 8) = 8 par shuru ho sakti hai, slower producer se control hota hai. ✔

Example 4 — Cell C4: ek result ke do consumers

Forecast: kya Mult1 ek baar ya do baar shout karta hai?

  1. Issue (ii): Qj = Mult1 (R1 ka wait), Vk=1.
  2. Issue (iii): Status[R1] lookup karta hai. Woh abhi bhi Mult1 hai (kisi ne overwrite nahi kiya) → Qj = Mult1, Vk=4. Kyun? Register read karna uska status entry nahi badalta. Toh dono consumers legitimately same IOU hold karte hain.
  3. Mult1 broadcast karta hai (Mult1, 14) — EK BAAR. Dono Add1 aur Sub1 same cycle mein same shout snoop karte hain → dono capture karte hain Vj=14, dono Qj clear karte hain. Point-to-point ki jagah broadcast kyun? Issue par humein nahi pata tha kitni desks ko R1 chahiye. Ek announcement kitne bhi listeners ko serve karta hai — yahi reason hai CDB ek bus hai.

Verify: R4 = 14 + 1 = 15, R6 = 14 - 4 = 10. Dono ek broadcast se derive hue — ek shout, do captures. ✔

Example 5 — Cell C5: WAW hazard aur "dead" value

Forecast: kya (i) ka 6 kabhi R1 mein land karta hai?

  1. Issue (i): Status[R1] = Mult1.
  2. Issue (ii): woh bhi R1 likhta hai. Overwrite karo Status[R1] = Add1. Phone book ab kehta hai "R1 ka newest producer Add1 hai." Kyun? Yahi WAW fix hai: latest writer register-status entry jeet jaata hai. (i) ka R1 par claim ab invisible hai.
  3. Issue (iii): Status[R1] = Add1 read karta hai → Qj = Add1 (NOT Mult1), aur R7 ready hai toh Vk = 8, Qk = 0. Kyun? (iii) program order mein (ii) ke baad aata hai, toh use (ii) ka R1 dekhna chahiye. Status table ne automatically sahi tag diya.
  4. Mult1 finish karta hai (6), broadcast karta hai (Mult1, 6). Register file check karta hai: kya Status[R1] == Mult1? Nahi, woh Add1 hai. Toh register file ise ignore karta hai. Kyun? Yahi "dead value" hai. Kisi ka bhi Qj/Qk = Mult1 nahi tha, toh R1 ke liye yeh simply drop ho jaata hai. Correct — (i) ki write overwrite ho gayi thi.
  5. Add1 finish karta hai (30), broadcast karta hai (Add1, 30). Register file check karta hai: kya Status[R1] == Add1? Haan. Toh woh R1 = 30 likhta hai. Usi broadcast mein, (iii) ka station snoops karta hai, Qj = Add1 match dekh ke Vj = 30 capture karta hai, Qj clear karta hai. Yeh step kyun? Register file tab hi likhta hai jab broadcasting tag register ki current status entry se match kare — yahi guarantee karta hai ki register latest binding (Add1) rakhe, stale wala (Mult1) nahi. Aur (iii) usi shout par capture karta hai kyunki uske IOU mein Add1 tha; ek broadcast register file aur har waiting consumer dono ko serve karta hai ek saath (same mechanism jaise Ex 4).

Verify: final R1 = 10 + 20 = 30 (rakha gaya); (i) ki value 2*3 = 6 discard ho gayi; R6 = R1 - R7 = 30 - 8 = 22. ✔ (i) ki value kabhi R1 tak nahi pahunchi.

Example 6 — Cell C6: WAR false dependency dissolve ho jaati hai

Forecast: kya (ii) ko (i) ka wait karna padega?

  1. Issue (i): R1 ready hai → value seedhi le lo: Vj = 100. (i) ab apne khud ke station mein number 100 own karta hai. Kyun? Ek baar capture ho jaane ke baad, (i) naam R1 ko bilkul reference nahi karta — uske paas ek private copy hai.
  2. Issue (ii): R1 likhta hai → Status[R1] = Mult1. Yeh (i) ki 100 ki copy ko nahi touch karta. Kyun? (i) ne step 1 mein apna operand snapshot kar liya tha. (ii) ka R1 ke saath naya binding ek value ko corrupt nahi kar sakta jo pehle hi copy out ho chuki hai. "False" WAR dependency gayi.
  3. (ii) freely execute karo, chahe (i) se pehle bhi: 6*7 = 42 → R1 = 42.

Verify: R3 = 100 + R2 (purana R1=100 use karta hai), jabki R1 baad mein 42 ban jaata hai. Dono executions ka order ab matter nahi karta — yahi renaming ka faida hai. R2=1 lo → R3 = 101, R1 = 42. ✔

Example 7 — Cell C7: structural hazards (limits!)

Forecast: dono mein, machine ko kya karna chahiye?

  1. (a) — RS full. Koi free station nahi ⇒ teesra ADD issue nahi ho sakta aur front end stall karta hai kam se kam ek cycle ke liye. Yeh step kyun? RS data hazards eliminate karte hain, structural kabhi nahi. Agar buffer physically full hai, issue block hota hai — yahi scheme ki limiting/degenerate boundary hai.
  2. (b) — CDB contention. Ek bus = ek broadcast per cycle. Arbiter ek result choose karta hai (maano Mult1); Add1 ko apna result hold karna padega aur next cycle mein rebroadcast karna padega. Kyun? Classic Tomasulo mein ek akela CDB hai. Do simultaneous producers ek structural hazard hai; ek ek cycle lose karta hai. (Modern designs extra CDBs add karte hain — wiring cost par.)

Verify: counting check — 2 stations aur 2 busy ke saath, free stations = 2 - 2 = 0, toh 0 < 1 needed ⇒ stall. 1 CDB aur 2 ready broadcasters ke saath, 2 > 1 ⇒ ek exactly 2 - 1 = 1 cycle defer hota hai. ✔

Example 8 — Cell C8: load jiska address abhi ready nahi

Forecast: load apna address jaanne se pehle kya karta hai?

  1. Issue (i). Ek integer-ALU station allocate karo; use Add1 kaho. R3 aur R4 dono ready hain → Vj = 1000, Vk = 24, Qj = Qk = 0. Status[R2] = Add1 set karo. Yeh step kyun? Hume desk ka naam dena chahiye jo R2 produce karegi taaki load us par point kar sake. (i) ka allocation dikhaye bina, tag Add1 ek mystery hota.
  2. Issue (ii). R2 pending → Status[R2] = Add1 lookup karo → IOU store karo: Qj = Add1. Address field A abhi fill nahi ho sakta. Kyun? Load ka pehla kaam address computation hai; use pehle base value chahiye, toh woh base ko IOU ki tarah rakhta hai jaise koi bhi operand.
  3. Add1 finish karta hai aur broadcast karta hai (Add1, 1024) (kyunki 1000 + 24 = 1024). Load snoops karta hai, Qj = Add1 match karta hai → base value capture karta hai, Qj = 0. Yeh step kyun? Load address arithmetic shuru tab tak nahi kar sakta jab tak uska base number exist na kare; CDB shout exactly woh moment hai jab woh number available hota hai, aur Capture woh tarika hai jis se load use grab karta hai (same mechanism jaise har earlier example).
  4. Execute phase 1 — address. A = base + offset = 1024 + 0 = 1024. Phases mein kyun split? Memory access tab tak shuru nahi ho sakta jab tak address exist na kare. Address calc ek distinct sub-step hai, pure ALU op ki tarah nahi.
  5. Execute phase 2 — memory access, phir broadcast. Address A = 1024 par memory read karo, datum ko load ke result mein rakho, phir CDB par (load-tag, datum) broadcast karo. Yeh step kyun? Tab hi address jaana aur use karna safe hai; memory read load ka actual kaam hai, aur — kisi bhi producer ki tarah — use apna result CDB par announce karna hai taaki R5 ka koi bhi consumer use capture kar sake.

Verify: effective address = base + offset = (1000 + 24) + 0 = 1024. Yahi jagah hai jahan 5.3.09-Load-store-queues check karne ke liye over leta hai ki koi earlier store address 1024 alias karta hai ya nahi. ✔

Example 9 — Cell C9: word problem (hardware sizing)

Forecast: compute karne se pehle bit count guess karo.

  1. Total stations = 6 + 3 + 2 + 4 + 1 = 16. Kyun? Ek tag kisi bhi producing station ko uniquely identify kar sakna chahiye poori machine mein (CDB global hai, toh shout kahin se bhi aa sakti hai).
  2. Bits needed = ⌈log₂(16)⌉ = 4 bits. Log ka ceiling kyun? N distinct cheezein label karne ke liye ⌈log₂ N⌉ binary digits chahiye — on/off switches ki minimum sankhya jo kam se kam N patterns deti hai. Yahan 2⁴ = 16 patterns exactly 16 stations cover karte hain.
  3. Per-station tag storage. Har station do operand tags rakhta hai (Qj, Qk), har ek 4 bits → 2 × 4 = 8 bits of tag storage per station. Kyun? j aur k dono independently kisi station ko point karte IOU ho sakte hain, toh dono ko full tag field chahiye.

Verify: 2⁴ = 16 ≥ 16 distinct stations ✔, jabki 2³ = 8 < 16 kam hota ⇒ 4 minimal bit-width hai. Per-station tag storage = 2 × 4 = 8 bits. ✔

Example 10 — Cell C10: exam twist — kya out-of-order answer badalta hai?

Forecast: true ya false — OoO R8 mein alag value produce kar sakta hai?

  1. Independence check. (ii) (i) ke saath koi register share nahi karta → koi Q link nahi. Jab bhi operands present hote hain yeh execute ho jaata hai. Kyun? RS sirf real data dependencies serialize karte hain; unrelated instructions jab bhi operands present hon tab run karte hain.
  2. (iii) dono par gate karta hai. Qj = Mult1, Qk = Add1. Woh do finish times mein se baad wale ka wait karta hai, chahe kaun sa producer pehle aaya. Kyun? Correctness tag capture se aata hai, execution order se nahi. (iii) hamesha (i) aur (ii) ke actual results use karta hai.
  3. Result. R1 = 2*5 = 10, R4 = 1+1 = 2, R8 = 10 - 2 = 8. Kyun? (i) aur (ii) jis bhi order mein finish karein, (iii) ke do IOUs execute hone se pehle true values capture karte hain, toh woh 10 aur 2 par compute karta hai.

Verify: ek in-order machine wohi R8 = (2*5) - (1+1) = 8 compute karta hai. Out-of-order execution timing reorder karta hai, values kabhi nahi — woh guarantee (plus 5.3.07-Reorder-buffer precise exceptions ke liye) yahi reason hai trick safe hai. ✔

Recall Har example kaun sa cell cover karta hai?

C1 ready/ready — Ex 1 ::: koi wait nahi, immediate execute C2 single RAW — Ex 2 ::: ek IOU, ek baar capture C3 dono pending — Ex 3 ::: last-arriving operand se gate C4 do consumers — Ex 4 ::: ek broadcast, kai captures C5 WAW — Ex 5 ::: status overwrite, dead value drop C6 WAR — Ex 6 ::: operand snapshotted, dependency vanish C7 structural — Ex 7 ::: RS full stalls, ek CDB defer karta hai C8 load address — Ex 8 ::: two-phase execute C9 sizing — Ex 9 ::: ⌈log₂ N⌉ tag bits C10 OoO safety — Ex 10 ::: timing reorder karta hai values nahi

Connections