Reservation stations

What Problem Do They Solve?

Traditional in-order pipelines stall when:

1. RAW hazards: Instruction needs a result that's not ready
2. WAR/WAW hazards: False dependencies on register names
3. Structural hazards: Multiple instructions want the same execution unit

Why not just use a centralized instruction queue? A single queue creates a bottleneck—every instruction must check every other instruction's dependencies. Reservation stations distribute this work: each station independently tracks only its own operands.

Architecture Components

Key Structures

1. Reservation Stations (RS): Bufers holding waiting instructions

   • Op: Operation to perform (ADD, MUL, LOAD, etc.)
   • Vj, Vk: Source operand values (when available)
   • Qj, Qk: Tags of reservation stations producing operands (when pending)
   • Busy: Station occupied flag
   • A: Address field (for loads/stores)

2. Common Data Bus (CDB): Broadcast network

   • Functional units broadcast results with their RS tag
   • All RS and register file snoop simultaneously
   • Why broadcast? Avoids $O(n^2)$ point-to-point connections

3. Register Status Table: Maps each register to the RS tag producing its next value

   • Empty entry = value ready in register file
   • Tag present = waiting for that RS

Tomasulo's Algorithm Flow

Stage 1: Issue

• Decode instruction
• Allocate a free reservation station
• If operand in register file: copy value to Vj/Vk
• If operand pending: copy producing RS tag to Qj/Qk
• Update register status to point to this RS (for WAW elimination)

Stage 2: Execute

• Wait until Qj = Qk = 0 (all operands ready)
• Issue to functional unit
• Load/store: compute address when base ready, then access memory

Stage 3: Write Result

• Broadcast on CDB with RS tag
• All RS check Qj/Qk—if match, capture value and clear tag
• Register file updates if status matches this RS tag
• Free the reservation station

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: Issue MUL

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

Cycle 2: Issue ADD (inst 2)

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

Cycle 3: Issue SUB (inst 3)

• Allocate RS: Add2
• Add2: {Op=SUB, Vj=R6_val, Vk=R7_val, Qj=0, Qk=0}
• Key: Status[R1] = Add2 (overwrites Mult1!)
  • Why this matters: Inst 4 will now wait for Add2, not Mult1

Cycle 4: Issue ADD (inst 4)

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

Cycle 10: Mult1 completes

• Broadcasts on CDB with tag Mult1
• Add1 captures result: Qj=0, V<result>
• Register file ignores (Status[R1] ≠ Mult1)
  • Why ignore? The WAW means this is a "dead" value

Cycle 12: Add2 completes

• Broadcasts with tag Add2
• Add3 captures: Qj=0
• Register file writes R1 (Status[R1] = Add2 matches)

Common Mistakes

Active Recall Checks

Connections

• 5.3.05-Dynamic-scheduling: Reservation stations enable dynamic scheduling
• 5.3.04-Scoreboarding: Earlier centralized approach; RS distribute dependency tracking
• 5.3.07-Reorder-buffer: Modern extension to RS for precise exceptions
• 5.2.03-Register-renaming: RS implement dynamic renaming; explicit PRF is alternative
• 4.6.02-Pipeline-hazards: RS eliminate certain classes of pipeline stalls
• 5.3.09-Load-store-queues: Memory equivalent of RS for disambiguation

Design Tradeoffs

RS Count per FU:

• More RS → more parallelism, larger area/power
• Too few → issue stalls despite free FUs
• Typical: 5-10 RS per integer, 8-15 for FP

CDB Width:

• One bus: simple, cheap structural bottleneck
• Multiple: higher 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
• Every operand field needs this overhead

#flashcards/hardware

What do reservation stations decouple? :: Instruction issue from execution—instructions can be issued even when operands aren't ready, waiting in RS until operands arrive.

Concept Map

Hinglish (regional understanding)