Register renaming

Overview

Register renaming is a microarchitectural technique that eliminates false dependencies (WAR and WAW hazards) between instructions by mapping architectural registers to a larger pool of physical registers. This allows out-of-order execution to achieve higher instruction-level parallelism without being limited by the small number of programmer-visible registers.

The Problem: False Dependencies

Why False Dependencies Hurt Performance

Consider this x86 assembly sequence:

ADD R1, R2, R3    # I1: R1 = R2 + R3
MUL R4, R1, R5    # I2: R4 = R1 * R5  (RAW on R1 - REAL)
ADD R1, R6, R7    # I3: R1 = R6 + R7  (WAW with I1, WAR with I2 - FALSE)
SUB R8, R1, R9    # I4: R8 = R1 - R9  (RAW on R1 - REAL with I3)

Without renaming:

I3 cannot start until I2 reads R1 (WAR hazard)
I3 cannot start until I1 finishes (WAW hazard)
Even though I3 is completely independent of I1 and I2's computation!

The false dependencies serialize execution when instructions could actually run in parallel.

Common mistake "Why Not Just Use More Architectural Registers?"

Why it feels right: If we had 128 registers instead of 16, compilers could avoid reusing register names, eliminating false dependencies. Why it's wrong:

ISA compatibility: Adding architectural registers breaks binary compatibility. All existing software would need recompilation.
Instruction encoding: More registers = more bits in every instruction = larger code size.
Compiler limitations: Even with 128 registers, complex code will still create false dependencies. The compiler does static allocation; it can't predict runtime execution order.
Context switch overhead: Saving/restoring 128 registers on every interrupt is expensive. The fix: Register renaming solves this in hardware transparently. The ISA stays small (16 registers), but the microarchitecture uses 100+ physical registers behind the scenes. Best of both worlds.

How Register Renaming Works

The Renaming Algorithm

At instruction decode:

Read the source operands from the RAT to find which physical registers hold the current values
Allocate a new physical register from the free list for the destination
Update the RAT to map the architectural destination to the new physical register
Record the old mapping in the ROB for recovery on exceptions

At instruction commit (in-order):

The instruction completes and becomes architecturally visible
The old physical register that was previously mapped to this architectural register is freed back to the free list
Move the next instruction in program order

Formula Register Renaming Mapping

Let $R_{arch}$ be an architectural register and $R_{phys}$ be a physical register.

Initial state: $\text{RAT}[R_{arch}] \rightarrow R_{phys}^{old}$

After renaming instruction Rdest ← Rsrc1 op Rsrc2:

Allocate: $R_{phys}^{new} \leftarrow \text{FreeList.pop()}$
Read sources: $P_{src1} = \text{RAT}[R_{src1}], \quad P_{src2} = \text{RAT}[R_{src2}]$
Rename destination: $\text{RAT}[R_{dest}] \rightarrow R_{phys}^{new}$
Record for commit: $\text{ROB}[\text{tail}] = \{R_{dest}, R_{phys}^{old}, R_{phys}^{new}\}$ At commit: $\text{FreeList.push}(R_{phys}^{old})$ Why these steps?

Step 1: We need a unique physical location for this instruction's result
Step 2: We must find where the current values of sources live (another instruction may have renamed them)
Step 3: Future instructions reading $R_{dest}$ will now get the new result, not the old value
Step 4: If an exception occurs, we can restore the old mapping; we can't free the old register until we're sure the instruction commits
Commit: Once committed, no instruction will ever need the old value again (program order guarantees this)

Worked Example: Renaming the Code

Let's rename our earlier example with8 architectural registers (R1-R8) and 32 physical registers (P0-P31).

Initial RAT state:

R1→P10, R2→P11, R3→P12, R4→P13, R5→P14, R6→P15, R7→P16, R8→P17, R9→P18
Free list: [P0, P1, P2, P3, P4, ...]

Instruction 1: ADD R1, R2, R3

Sources: P11 (R2), P12 (R3) — Why? These are the current physical registers holding R2 and R3's values
Allocate: P0 from free list — Why? Need a fresh location for R1's new value
Execute: P0 ← P11 + P12
Update RAT: R1→P0 — Why? Future reads of R1 should get this result, not the old P10
Save old: ROB[0] = {R1, P10→P0} — Why? For exception recovery and to know when to free P10

Instruction 2: MUL R4, R1, R5

Sources: P0 (R1), P14 (R5) — Why? I1 renamed R1 to P0, so we read from P0
Allocate: P1
Execute: P1 ← P0 * P14
Update RAT: R4→P1
Save old: ROB[1] = {R4, P13→P1}

Instruction 3: ADD R1, R6, R7

Sources: P15 (R6), P16 (R7) — Why? No instructions have touched R6 or R7 yet
Allocate: P2
Execute: P2 ← P15 + P16 — Why this is safe? P2 is completely independent of P0. I2 still reads from P0, I3 writes to P2. No conflict!
Update RAT: R1→P2 — Why? Now future reads of R1 get the new value from I3
Save old: ROB[2] = {R1, P0→P2}

Instruction 4: SUB R8, R1, R9

Sources: P2 (R1), P18 (R9) — Why? I3 just renamed R1 to P2, so we read the latest value
Allocate: P3
Execute: P3 ← P2 - P18
Update RAT: R8→P3
Save old: ROB[3] = {R8, P17→P3}

Key insight: I1, I2, and I3 all use architectural register R1, but they use different physical registers (P0, P0, P2). The WAR and WAW hazards are eliminated because P0 and P2 are distinct storage locations.

Worked example Execution Timeline

Without renaming (serialized by false dependencies):

Cycle: 1    2    3    4    5    6    7    8    9
I1:    |D   |E-E-E|
I2:         |D---wait---|E-E-E-E|
I3:              |D---wait---|E-E-E|
I4:                   |D---wait------|E-E|

Total: 9 cycles

With renaming (parallel execution):

Cycle: 1    2    3    4    5    6
I1:    |D   |E-E-E|
I2:         |D   |---E-E-E-E|
I3:         |D   |E-E-E|
I4:              |D   |E-E-E|

Total: 6 cycles (1.5× speedup) Why? I2 waits for I1's result (true RAW), but I3 doesn't wait for I2 (false WAR eliminated). I4 only waits for I3 (true RAW).

Physical Register File Size

Why?

$N_{arch}$ : We need at least one physical register for each architectural register's committed state
$N_{ROB}$ : Each in-flight instruction in the ROB might have allocated a physical register that hasn't committed yet
In practice: $N_{phys} \approx N_{arch} + N_{ROB} \text{slack}$

Example: x86-64 with 16 architectural registers and 224-entry ROB

Minimum: 16 + 224 = 240 physical registers
Typical: 256 physical registers (power of 2 for indexing)

What if we run out of physical registers?

Instruction decode stalls until a register is freed
This is called register pressure or register starvation
Shows up in code with many live values (large loops with many variables)

Common mistake "More Physical Registers Always Improves Performance"

Why it feels right: If 256 registers are good, 512 must be better!

Why it's wrong: Diminishing returns + hardware costs:

Access time: Larger register files have longer read/write latencies. A 512-entry register file might be 10-20% slower than 256-entry.
Area and power: Register files are large structures (multi-ported for parallel reads/writes). Doubling size significantly increases chip area and power.
Limited benefit: Most code doesn't have enough ILP to use 256+ registers. The ROB size is usually the bottleneck.
Free list management: Larger free lists need more complex allocation logic.

The sweet spot: Modern designs use 150-256 physical registers. Going beyond this helps specialized workloads but hurts typical cases.

Integration with Out-of-Order Execution

The pipeline:

Fetch instructions from memory
Decode & Rename: Translate architectural registers → physical registers via RAT
Dispatch: Send to reservation stations with physical register tags
Execute: Out-of-order execution as physical registers become ready
Complete: Write result to physical register, broadcast tag on Common Data Bus (CDB)
Retire/Commit: In-order commit updates architectural state, frees old physical registers

Why this order?

Rename early (decode stage) to expose paralelism immediately
Out-of-order execute with physical registers to avoid false dependencies
In-order commit to maintain precise exceptions and free registers safely

Worked example Register Renaming with Forwarding

Consider:

ADD P0, P11, P12   # Cycle 1: execute
MUL P1, P0, P14    # Cycle 1: waiting for P0

Without forwarding:

ADD writes P0 at end of cycle 1
MUL reads P0 at start of cycle 2
1 cycle latency

With result forwarding (bypass):

ADD computes result in cycle 1
Result is forwarded directly to MUL's execution unit via CDB
MUL can start executing in cycle 2 without waiting for register file write
Effectively hides the register write latency

Why physical registers enable better forwarding? The physical register tag (P0) uniquely identifies the result. Any instruction waiting for P0 can grab it from the CDB immediately, regardless of architectural register names.

Precise Exceptions and Recovery

One complication: What if instruction I3 causes an exception, but I4 (which comes after in program order) has already executed and renamed registers?

The solution: The ROB maintains in-order state.

When exception at instruction $i$ :

Flush all instructions after $i$ from the ROB (they never happened architecturally)
Restore the RAT to the state at instruction $i$ using ROB entries
Free all physical registers allocated by flushed instructions back to free list
Branch to exception handler with architecturally precise state

Connections

Instruction-Level Parallelism (ILP) — Register renaming increases exploitable ILP by removing false dependencies
Out-of-Order Execution — Renaming is necessary for OoO; can't reorder without eliminating name dependencies
Tomasulo's Algorithm — Tomasulo uses reservation stations with register renaming (his "tags" are physical register identifiers)
Reorder Buffer (ROB) — ROB tracks physical register allocations for precise exceptions
Scoreboarding — Older technique that couldn't eliminate false dependencies (only tracked true dependencies)
Memory Disambiguation — Similar idea applied to memory addresses (store-load renaming)
Superscalar Execution — Multiple-issue superscalars need renaming to avoid name hazards between simultaneously-decoded instructions
Branch Prediction — Mispredictions require RAT restoration, similar to exception handling

Recall Explain to a 12-Year-Old

Imagine you're doing homework and you have a notebook called "Page 1." First, you write your math answer on Page 1. Then you need to write your science answer, but you also want to call it "Page 1" because that's just the name you use for your current answer.

The problem: You can't erase your math answer yet because your friend still needs to copy it! But you can't write science until you erase math. You're stuck.

Register renaming is like having a magical notebook where "Page 1" is just a label that can point to any real page in a huge stack. When you need to write science, the notebook says "Okay, 'Page 1' now points to real page 47" while your math answer stays safe on real page 23. Your friend can still copy from page 23, and you can write on page 47 at the same time!

The teacher (the commit stage) eventually throws away the old page 23 once everyone's done with it. You keep reusing the same labels (R1, R2, R3) but the notebook has hundreds of real pages behind the scenes, so you never run out of workspace.

#flashcards/hardware

What is register renaming? :: A microarchitectural technique that maps architectural registers to a larger pool of physical registers, eliminating false dependencies (WAR and WAW hazards) while maintaining the illusion of a small register set defined by the ISA.

What are the three types of dependencies and which are false?

RAW (read-after-write) is a true dependency. WAR (write-after-read) and WAW (write-after-write) are false dependencies caused by register name reuse, not actual data flow.

What is the Register Alias Table (RAT)?

A structure that maps each architectural register to its current physical register. Updated at decode when an instruction writes a destination register.

When are physical registers freed back to the free list?

At commit time, in program order. The old physical register that was previously mapped to the destination architectural register is freed once the new mapping is committed.

Why does register renaming require in-order commit?

To maintain precise exceptions and architecturally correct state. If an exception occurs, we must be able to restore the exact architectural state at that instruction by undoing all subsequent renaming operations.

How many physical registers are typically needed?

At least N_arch + N_ROB. Modern processors use 150-256 physical registers for16-32 architectural registers with 100-224 ROB entries.

What happens if the processor runs out of physical registers?

Instruction decode stalls until a physical register is freed at commit. This is called register pressure or register starvation.

How does register renaming enable out-of-order execution?

By eliminating false dependencies, instructions that only conflict on register names (not data) can execute in parallel. This exposes more instruction-level parallelism for the scheduler.

What is the difference between architectural and physical registers?

Architectural registers are defined by the ISA and visible to software (e.g., x86's 16 GPRs). Physical registers are the actual storage locations in hardware (typically 10-15× more numerous) that architectural registers map to.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Register renaming ek bahut smart hardware trick hai jo processor ko fast banati hai. Socho tumhare pas sirf 3-4 notebooks hain (architectural registers) lekin 20 homework assignments hain. Agar tum har baar same notebook "Math Book1" use karo aur pehle wali entry ko erase karna padta hai, toh bohot time waste hota hai waiting mein.

Register renaming kehta hai: "Arre, main tumhe ek bada sa cupboard dunga jismein 200 invisible notebooks hain (physical registers). Tum bas apni homework ko'Math Book 1' naam do, main khud decide karunga ki woh actually cupboard mein kis notebook pe jaye." Matlabek hi architectural register name (jaise R1) different times pe different physical locations (P0, P2, P5..) ko point kar sakta hai. Isse kya fayda? Jo false dependencies thi - jahan do instructions sirf naam ki wajah se conflict kar rahe the lekin actually unka kaam alag tha - woh gayab ho jati hain.

Out-of-order execution ke liye yeh bahut zaroori hai kyunki agar tum instructions ko sequence hatt ke run karna chahte ho (jo fast hai), toh pehle ensure karna padega ki ek instruction dosre ke actual result ko overwrite na kar de galti se. Physical registers se har instruction ko apna separate workspace milta hai, aur jab instruction finally commit hoti hai tab hi purani physical register wapas free hoti hai. Yeh technique modern processors ko 2-3x faster banati hai bina software ko change kiye!

Overview

The Problem: False Dependencies

Why False Dependencies Hurt Performance

How Register Renaming Works

The Renaming Algorithm

Worked Example: Renaming the Code

Physical Register File Size

Integration with Out-of-Order Execution

Precise Exceptions and Recovery

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Advanced Microarchitecture

Connections