⭐ Register Renaming

1. Definition

Register renaming is a hardware technique used to eliminate false data dependencies (name dependencies) between instructions in a pipelined processor, enabling out-of-order execution and dynamic scheduling.

It resolves WAR (Write After Read) and WAW (Write After Write) hazards by mapping architectural registers (program-visible registers) to physical registers dynamically.

2. Purpose

1. Avoid false dependencies (name hazards):

   • WAR (Write After Read): A later instruction writes to a register before an earlier instruction reads it.
   • WAW (Write After Write): Two instructions write to the same register in program order.

2. Enable out-of-order execution:

   • Instructions can execute as soon as their true data dependencies (RAW) are resolved.

3. Maximize instruction-level parallelism (ILP):

   • Multiple instructions can execute simultaneously without waiting for unrelated writes to registers.

3. Types of Data Hazards

4. Mechanism

a) Architectural vs Physical Registers

• Architectural register: Program-visible (e.g., R1, R2)
• Physical register: Actual hardware register in the CPU
• Idea: Map multiple physical registers to a single architectural register to remove false dependencies.

b) Renaming Process

1. Instruction Decode: Identify destination register.
2. Assign a free physical register to the destination.
3. Update mapping table: Logical → Physical.
4. Execute instruction using physical register.
5. Commit results in program order to maintain precise state.

5. Example

Original instruction sequence:

I1: R1 = R2 + R3
I2: R1 = R4 + R5
I3: R6 = R1 + R7

• Without renaming:

  • I2 cannot execute until I1 finishes (WAW hazard).

• With renaming:

  • I1 → P1 (physical register)
  • I2 → P2 (new physical register)
  • I3 reads the correct version of R1 depending on program order (RAW dependency preserved)

Effect: I1 and I2 can execute in parallel, avoiding unnecessary stalls.

6. Hardware Support

• Register Alias Table (RAT): Maintains mapping from architectural → physical registers
• Free List: Keeps track of available physical registers
• Reorder Buffer (ROB): Ensures instructions commit in program order and updates architectural registers

7. Advantages

1. Eliminates false dependencies (WAR & WAW).
2. Enables out-of-order execution for higher ILP.
3. Reduces pipeline stalls, improving throughput.
4. Supports dynamic scheduling in superscalar processors.

8. Limitations

1. Requires additional hardware resources (physical registers, mapping tables).
2. Complexity in tracking free registers and precise commit order.
3. Works only for name hazards; true data hazards (RAW) still limit execution.

9. Example in Pipeline Context

Cycle 1: Decode I1, assign R1 → P1
Cycle 2: Decode I2, assign R1 → P2 (no stall)
Cycle 3: Execute I1 on P1, Execute I2 on P2
Cycle 4: I3 executes using correct version of R1

• Pipeline remains busy, with no unnecessary stalls caused by WAW or WAR hazards.

10. Exam Summary

• Register Renaming: Map architectural registers to multiple physical registers to eliminate false dependencies (WAR & WAW).
• Enables: Out-of-order execution and dynamic scheduling.
• Mechanisms: Register Alias Table (RAT), free list, reorder buffer (ROB).
• Benefit: Higher instruction-level parallelism, fewer pipeline stalls.