Noesis
5.3.6 · D5 · HinglishAdvanced Microarchitecture

Question bank — Reservation stations

2,809 words13 min read↑ Read in English

5.3.6 · D5 · Hardware › Advanced Microarchitecture › Reservation stations

Shuru karne se pehle, neeche use hone wale har symbol ko scratch se build karte hain — isse skip mat karo, traps isi par depend karte hain.

Teen plain-word anchors jo dhyan mein rakhne chahiye:

  • Ek tag ek desk ka naam (ek RS) hai jo ek value produce karega — kabhi register ka naam nahin.
  • Common Data Bus (CDB) woh shout hai: ek broadcast wire jo (tag, value) carry karta hai jisko har desk aur register file ek saath sunta hai.
  • Snooping ka matlab hai CDB par passively sunna aur broadcast tag ko apne Qj/Qk se compare karna.

Neeche ki figure yeh sab ek picture mein fix kar deti hai — jab traps work karo toh isme wapis dekho.

Figure — Reservation stations

"Spot the error" section ek tiny self-contained trace par depend karta hai. Yahan woh poora diya gaya hai taaki tumhe yeh page kabhi chhodni na pade:

Figure — Reservation stations

True or false — justify

Har answer mein reason dena zaroori hai, sirf T/F nahin.

Ek RS aisi instruction hold kar sakta hai jiske operands abhi compute nahin hue.
True — yahi toh poora point hai. Woh tags (Qj/Qk) store karta hai jo un desks ko point karte hain jo woh operands produce karenge, aur CDB shout ka wait karta hai, pipeline stall karne ki bajaye.
Reservation stations har tarah ka hazard eliminate kar dete hain.
False — renaming sirf false register hazards WAR aur WAW remove karti hai; true RAW dependencies remove nahin hoti balki tag-and-capture machinery dwara correctly enforce hoti hain. Memory-aliasing, control (branch), aur structural (RS-full) hazards bhi bani rehti hain. Memory disambiguation ke liye 5.3.09-Load-store-queues dekho.
Register renaming, akele, RAW hazards bhi remove kar deti hai.
False — RAW ek genuine data dependency hai (tumhe actual value chahiye), isliye usse rename nahi kiya ja sakta. Renaming sirf false name-collisions WAR aur WAW khatam karti hai; RS tab bhi consumer ko stall karta hai jab tak producer broadcast nahi karta.
Qj mein stored tag ek physical register ka number hai.
False — tag producing reservation station ka naam hai, jo transient hoti hai aur write-back ke baad free ho jaati hai. Classic Tomasulo mein RS khud flight ke dauran renamed register ki tarah kaam karta hai.
Do alag reservation stations ek hi tag ka ek saath wait kar sakte hain.
True — kai consumers ek hi Qj/Qk tag hold kar sakte hain; jab woh tag broadcast hota hai, sablog simultaneously value capture karte hain. Yahi exactly wajah hai ki broadcasting point-to-point delivery se behtar hai.
Classic Tomasulo ek hi cycle mein do functional-unit results write back kar sakta hai.
False — ek single CDB hai, isliye ek cycle mein sirf ek hi result broadcast hota hai; simultaneous completions ek structural hazard create karte hain jo arbitration se resolve hoti hai.
Ek baar operand value Vj mein aa jaaye, toh corresponding Qj fir bhi matter karta hai.
False — readiness Qj = 0 se decide hoti hai (koi pending tag nahin). Non-zero Qj aur stored Vj mutually exclusive hain; value capture karna Qj ko 0 set karta hai.
Register status table do alag registers ko ek hi RS tag ki taraf point kar sakti hai.
False — har RS exactly ek result produce karta hai, isliye zyada se zyada ek register ka status entry kisi given tag ko "next producer" naam de sakta hai. Kai consumers tag hold kar sakte hain, lekin sirf ek register status slot usse bind karta hai.
Ek empty register-status entry ka matlab hai "is register mein kabhi koi value nahin thi".
False — empty entry ka matlab hai current value already register file mein hai aur ready hai padhne ke liye; uske liye kuch pending nahin hai.
Agar kisi functional unit se attached saare reservation stations busy hain, toh instruction issue stall ho jaata hai.
True — yeh RS resource par structural hazard hai; free desk ke bina, decode allocate nahin kar sakta, isliye issue block ho jaata hai chahe FU idle ho.
RS tags ke through renaming ke liye register values ko physically copy karke idhar-udhar lejana padta hai.
False — renaming pointing se hoti hai: status table record karta hai ki kaunsa tag register ki next value produce karega. Values sirf ek baar move hoti hain, CDB broadcast par.

Spot the error

Har line mein ek flawed claim ya broken trace step hai; reveal mein kya galat hai aur kyun bataya gaya hai. Sabka reference upar wale trace se hai.

"Issue ke dauran, hum RS allocate karne se pehle tab tak wait karte hain jab tak dono operands ready na ho jaayein."
Galat — allocation pehle hoti hai, operand readiness ki parwah kiye bina; Qj = Qk = 0 ka wait Execute stage mein hota hai. Issue kabhi bhi operand availability par block nahin hota, sirf free RS par.
"Jab Mult1 finish karta hai, register file hamesha R1 likhti hai."
Galat — register file tabhi likhti hai jab Status[R1] abhi bhi Mult1 ke barabar ho. I3 ne use Add2 se overwrite karne ke baad (ek WAW), Mult1 ki value dead hai aur file use ignore karti hai.
"Instruction I2 eventually instruction I3 ki nayi R1 capture karta hai."
Galat — I2 ne Mult1 tag apne issue time par snapshot kiya tha, I3 ke exist karne se pehle. Woh hamesha Mult1 ki value ka wait karta hai; temporal ordering tag capture par freeze ho jaati hai.
"Kyunki tags registers ko rename karte hain, tag width architectural registers ki count ke barabar hoti hai."
Galat — tag width hai, stations ki sankhya ke hisaab se sized, architectural registers ki nahin.
"Ek RS us waqt free ho jaata hai jab woh functional unit par execute karna shuru karta hai."
Galat — woh sirf Write Result ke baad free hota hai (jab woh CDB par broadcast karta hai). Execute-start par free karne se result consumers ke capture karne se pehle drop ho jaata.
"Hum results point-to-point sirf un RSs ko broadcast karte hain jinhe chahiye, bus wires bachaate hain."
Galat — issue time par hum abhi sabhi future consumers nahin jaante (dependencies dynamic hain), isliye hume sabko broadcast karna padta hai; wahi unknown consumer set shared bus ki wajah hai.
"CDB snoop karne ka matlab hai har RS har cycle mein CDB se poochha karta hai ki uska operand ready hai ya nahin."
Galat — snooping passive hai: har RS single broadcast ko sunta hai aur broadcast tag ko apne Qj/Qk se compare karta hai. Koi polling request nahin hoti.

Why questions

Mechanism explain karo, sirf rule restate mat karo.

Reservation stations dependency tracking kyun distribute karte hain, ek central queue use karne ki bajaye?
Ek central queue har instruction ko baaki har instruction ki dependencies check karaati hai ( interaction); har RS ko apne operand fields dene se ek station sirf apne do tags track karta hai, isliye kaam local instruction ke saath scale karta hai, poore window ke saath nahin. 5.3.04-Scoreboarding se compare karo.
Status[R1] ko baad ki write par overwrite karna WAW hazard kyun eliminate karta hai?
Kyunki status table hamesha ek register ke latest producer ka naam rakhti hai; ek baar overwrite hone ke baad (I3 → Add2), pehle producer ka completion (Mult1) status se match nahin karta, isliye uska result silently discard ho jaata hai — purani write invisible ho jaati hai.
WAR hazard tag capture se automatically kyun eliminate ho jaata hai?
Ek earlier reader ne apne issue time par ya toh old value ya old producing tag grab kar liya hota hai; ek later writer sirf future readers ke liye status binding change karta hai, isliye woh kisi value ko clobber nahin kar sakta jis par earlier reader depend karta tha. Yeh 5.2.03-Register-renaming mein renaming idea hai.
CDB par tag ke saath value kyun carry karni chahiye, sirf value hi nahin?
Value akele ambiguous hai — kai desks alag-alag producers ka wait kar rahi ho sakti hain. Tag har snooping RS ko decide karne deta hai ki kya yeh shout mere liye hai apne Qj/Qk se match karke.
Reservation stations out-of-order completion kyun enable kar sakte hain lekin fully out-of-order commit safely kyun nahin?
RS instructions ko execute karne aur results write karne deta hai jaise operands aate hain (kisi bhi order mein), lekin precise exceptions ke liye results program order mein retire karne padte hain — yahi wajah hai ki ek 5.3.07-Reorder-buffer RS machinery ke upar add ki jaati hai.
Doosra CDB add karne se design mein cost linearly se zyada kyun badhti hai?
Har extra bus ko har RS ke har operand field aur register file dwara snoop kiya jaana chahiye, isliye wiring aur comparator count (buses × stations) ke saath badhti hai, ek blow-up, saath hi arbitration logic bhi chahiye ki kaunsa FU kaunsa bus use kare.
Ek load apna address Execute stage mein kyun compute karta hai, Issue par nahin?
Base register issue par abhi pending ho sakta hai; address computation tab tak wait karni padti hai jab tak base operand ka tag clear na ho jaaye (Qj = 0), bilkul kisi bhi arithmetic operand ki tarah, memory access shuru hone se pehle.

Edge cases

Boundary aur degenerate scenarios jo main flow mein glossed over hote hain.

Ek instruction jiske dono operands already register file mein hain — Execute mein kya hota hai?
Woh issue hoti hai, immediately Qj = Qk = 0 paati hai (values issue par Vj/Vk mein baith gayi thin), aur next cycle mein hi execute kar sakti hai bina kisi wait ke; RS ek pure pass-through ki tarah kaam karta hai.
Ek instruction jo aisa register padhti hai jo kisi bhi in-flight instruction ne kabhi nahin likha.
Us register ke liye Status empty hai, isliye value issue par seedha register file se Vj/Vk mein copy ho jaati hai bina kisi tag ke — yeh safe default path hai.
Kya hoga agar ek producing RS aur ek consuming instruction ek hi cycle mein issue hon kisi bhi broadcast se pehle?
Consumer status table padhta hai, producer ka tag dekhta hai, aur use Qj/Qk mein store karta hai; woh future CDB shout ka wait karta hai. Abhi koi value exist nahin karti, isliye woh correctly tag se bind karta hai, value se nahin.
Do instructions ek hi register ko back-to-back likhti hain, aur pehle ka koi consumer nahin.
Pehla wala phir bhi execute karta hai aur broadcast karta hai, lekin kyunki uska status overwrite ho chuka hai (WAW) aur koi RS uska tag hold nahin karta, uska result kuch match nahin karta aur drop ho jaata hai — wasted work lekin correct state.
Ek instruction jiska result kisi ko nahin chahiye (dead value).
Woh phir bhi ek RS occupy karti hai, execute hoti hai, CDB par broadcast karti hai, aur apni station free karti hai; koi consumer use capture nahin karta aur register file tabhi likhti hai jab uska status match kare. Correctness preserve hoti hai; sirf resource briefly spend hota hai.
Ek functional unit ke liye RS pool size zero hai (degenerate design).
Us FU ko target karne wali koi instruction kabhi issue nahin ho sakti — har aisi decode permanently stall hoti hai, yeh dikhata hai ki RS count directly achievable parallelism ko bound karta hai (typical designs 5–10 integer, 8–15 FP use karte hain).
Ek branch mispredicts jab kai RS mid-flight hain.
Unke in-flight results wrong path par hain aur squash karne padte hain; RS akele yeh cleanly nahin kar sakta, yahi wajah hai ki recovery 5.3.07-Reorder-buffer aur branch-prediction machinery par depend karti hai, 4.6.02-Pipeline-hazards ke hisaab se.
Do loads same memory address par jahan ek older hai lekin apna address baad mein issue karta hai.
RS memory ko disambiguate nahin karte — woh sirf register tags track karte hain. Inhe order karne ke liye 5.3.09-Load-store-queues chahiye; yeh assume karna ki RS yeh handle karta hai classic memory-aliasing trap hai.
Recall Ek-line self-test

Woh ek fact batao jo is topic par sabse zyada ulta state kiya jaata hai. Ek tag ek reservation station (producer ki desk) ka naam hai, kabhi register number ka nahin — baaki sab isi se follow karta hai.

Connections