Reservation stations

5.3.6 · Hardware › Advanced Microarchitecture

Ye Kaunsi Problem Solve Karte Hain?

Traditional in-order pipelines stall ho jaate hain jab:

1. RAW hazards: Instruction ko ek aisa result chahiye jo ready nahi hai
2. WAR/WAW hazards: Register names par false dependencies
3. Structural hazards: Multiple instructions ek hi execution unit chahte hain

Sirf ek centralized instruction queue kyun nahi use karte? Ek single queue bottleneck create karti hai—har instruction ko har doosri instruction ki dependencies check karni padti hain. Reservation stations is kaam ko distribute karte hain: har station independently sirf apne operands track karta hai.

Architecture Components

Key Structures

1. Reservation Stations (RS): Waiting instructions hold karne wale buffers

   • Op: Perform karne wala operation (ADD, MUL, LOAD, etc.)
   • Vj, Vk: Source operand values (jab available ho)
   • Qj, Qk: Operands produce karne wale reservation stations ke tags (jab pending ho)
   • Busy: Station occupied flag
   • A: Address field (loads/stores ke liye)

2. Common Data Bus (CDB): Broadcast network

   • Functional units apne RS tag ke saath results broadcast karte hain
   • Saare RS aur register file ek saath snoop karte hain
   • Broadcast kyun? $O(n^2)$ point-to-point connections se bachta hai

3. Register Status Table: Har register ko us RS tag se map karta hai jo uski next value produce kar raha hai

   • Empty entry = value register file mein ready hai
   • Tag present = us RS ka intezaar hai

Tomasulo's Algorithm Flow

Stage 1: Issue

• Instruction decode karo
• Ek free reservation station allocate karo
• Agar operand register file mein hai: value Vj/Vk mein copy karo
• Agar operand pending hai: producing RS tag Qj/Qk mein copy karo
• Register status update karo taaki is RS ki taraf point kare (WAW elimination ke liye)

Stage 2: Execute

• Tab tak wait karo jab tak Qj = Qk = 0 na ho jaaye (saare operands ready)
• Functional unit ko issue karo
• Load/store: base ready hone par address compute karo, phir memory access karo

Stage 3: Write Result

• CDB par RS tag ke saath broadcast karo
• Saare RS Qj/Qk check karte hain—match hone par value capture karo aur tag clear karo
• Register file update hoti hai agar status is RS tag se match kare
• Reservation station free karo

Worked Example: Instruction Sequence

1. MUL R1, R2, R3    ; R1 = R2 * R3
2. ADD R4, R1, R5    ; R4 = R1 + R5  (RAW on R1)
3. SUB, R6, R7    ; R1 = R6 - R7  (WAW on R1)
4. ADD R8, R1, R9    ; R8 = R1 + R9  (RAW on new R1)

Cycle 1: MUL Issue karo

• RS allocate karo: Mult1
• Mult1: {Op=MUL, Vj=R2_val, Vk=R3_val, Qj=0, Qk=0}
• Status[R1] = Mult1

Cycle 2: ADD issue karo (inst 2)

• RS allocate karo: Add1
• R1 ready nahi → Add1: {Op=ADD, Vj=?, Vk=R5_val, Qj=Mult1, Qk=0}
• Status[R4] = Add1

Cycle 3: SUB issue karo (inst 3)

• RS allocate karo: Add2
• Add2: {Op=SUB, Vj=R6_val, Vk=R7_val, Qj=0, Qk=0}
• Key: Status[R1] = Add2 (Mult1 ko overwrite karta hai!)
  • Ye kyun matter karta hai: Inst 4 ab Add2 ka wait karega, Mult1 ka nahi

Cycle 4: ADD issue karo (inst 4)

• Add3: {Op=ADD, Vj=?, Vk=R9_val, Qj=Add2, Qk=0}
• Status[R1] = Add2 read karta hai (Mult1 nahi)

Cycle 10: Mult1 complete

• CDB par tag Mult1 ke saath broadcast karta hai
• Add1 result capture karta hai: Qj=0, V<result>
• Register file ignore karta hai (Status[R1] ≠ Mult1)
  • Ignore kyun? WAW ka matlab hai ye ek "dead" value hai

Cycle 12: Add2 complete

• Tag Add2 ke saath broadcast karta hai
• Add3 capture karta hai: Qj=0
• Register file R1 likhti hai (Status[R1] = Add2 match karta hai)

Common Mistakes

Active Recall Checks

Connections

• 5.3.05-Dynamic-scheduling: Reservation stations dynamic scheduling enable karte hain
• 5.3.04-Scoreboarding: Pehla centralized approach; RS dependency tracking distribute karte hain
• 5.3.07-Reorder-buffer: Precise exceptions ke liye RS ka modern extension
• 5.2.03-Register-renaming: RS dynamic renaming implement karte hain; explicit PRF alternative hai
• 4.6.02-Pipeline-hazards: RS pipeline stalls ki kuch classes eliminate karte hain
• 5.3.09-Load-store-queues: Disambiguation ke liye RS ka memory equivalent

Design Tradeoffs

RS Count per FU:

• Zyada RS → zyada parallelism, bada area/power
• Bahut kam → free FUs hone ke bawajood issue stalls
• Typical: Integer ke liye 5-10 RS, FP ke liye 8-15

CDB Width:

• Ek bus: simple, sasta structural bottleneck
• Multiple: zyada throughput, complex arbitration, $O(n\times m)$ wiring

Tag Bits:

• $\lceil {\log }_2(\text{total RS count})\rceil$ bits per tag
• Example: 64 total RS → 6-bit tags
• Har operand field ko ye overhead chahiye

#flashcards/hardware

Reservation stations kya decouple karte hain? :: Instruction issue ko execution se—instructions tab bhi issue ho sakti hain jab operands ready nahi hain, RS mein wait karti hain jab tak operands na aa jaayein.

Concept Map