Register renaming — Hinglish notes

5.3.4 · Hardware › Advanced Microarchitecture

Overview

Register renaming ek microarchitectural technique hai jo false dependencies (WAR aur WAW hazards) ko instructions ke beech architectural registers ko physical registers ke ek bade pool mein map karke eliminate karta hai. Yeh out-of-order execution ko allow karta hai ki woh higher instruction-level parallelism achieve kare bina programmer-visible registers ki chhoti sankhya se limited hue.

The Problem: False Dependencies

False Dependencies Performance Ko Kyun Hurt Karte Hain

Is x86 assembly sequence ko dekho:

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)

Renaming ke bina:

I3 tab tak start nahi ho sakta jab tak I2 R1 read na kar le (WAR hazard)
I3 tab tak start nahi ho sakta jab tak I1 finish na ho jaaye (WAW hazard)
Chahe I3 I1 aur I2 ki computation se bilkul independent ho!

False dependencies execution ko serialize kar dete hain jabki instructions actually parallel mein run kar sakti hain.

Common mistake "Zyada Architectural Registers Kyun Nahi Use Karte?"

Kyun sahi lagta hai: Agar 16 ki jagah 128 registers hote, toh compilers register names reuse karne se bach sakti thi, false dependencies eliminate ho jaati. Kyun galat hai:

ISA compatibility: Architectural registers add karna binary compatibility tod deta hai. Sabhi existing software ko recompile karna padega.
Instruction encoding: Zyada registers = har instruction mein zyada bits = bada code size.
Compiler limitations: 128 registers ke saath bhi, complex code mein false dependencies create hongi hi. Compiler static allocation karta hai; woh runtime execution order predict nahi kar sakta.
Context switch overhead: Har interrupt par 128 registers save/restore karna expensive hai. Fix: Register renaming yeh hardware mein transparently solve karta hai. ISA chhota rehta hai (16 registers), lekin microarchitecture peeche se 100+ physical registers use karta hai. Dono duniya ka best.

Register Renaming Kaise Kaam Karta Hai

The Renaming Algorithm

Instruction decode par:

Source operands ko RAT se read karo taaki pata chale kaunse physical registers mein current values hain
Free list se ek naya physical register allocate karo destination ke liye
RAT ko update karo taaki architectural destination naye physical register par map ho
ROB mein old mapping record karo exceptions par recovery ke liye

Instruction commit par (in-order):

Instruction complete hoti hai aur architecturally visible ho jaati hai
Woh old physical register jo pehle is architectural register se mapped tha woh free list mein wapas free ho jaata hai
Program order mein next instruction par move karo

Formula Register Renaming Mapping

Maano $R_{a r c h}$ ek architectural register hai aur $R_{p h y s}$ ek physical register hai.

Initial state: $RAT [R_{a r c h}] \to R_{p h y s}^{o l d}$

Instruction Rdest ← Rsrc1 op Rsrc2 rename karne ke baad:

Allocate: $R_{p h y s}^{n e w} \leftarrow FreeList.pop()$
Read sources: $P_{sr c 1} = RAT [R_{sr c 1}], P_{sr c 2} = RAT [R_{sr c 2}]$
Rename destination: $RAT [R_{d es t}] \to R_{p h y s}^{n e w}$
Commit ke liye record karo: $ROB [tail] = {R_{d es t}, R_{p h y s}^{o l d}, R_{p h y s}^{n e w}}$ Commit par: $FreeList.push (R_{p h y s}^{o l d})$ Yeh steps kyun?

Step 1: Hume is instruction ke result ke liye ek unique physical location chahiye
Step 2: Hume dhundhna hai ki sources ki current values kahaan hain (kisi aur instruction ne unhe rename kar diya hoga)
Step 3: Future instructions jo $R_{d es t}$ read karengi unhe ab naya result milega, purani value nahi
Step 4: Agar exception aaye, toh hum old mapping restore kar sakte hain; old register tab tak free nahi kar sakte jab tak sure na ho ki instruction commit karti hai
Commit: Commit hone ke baad, koi bhi instruction kabhi purani value nahi maangegi (program order yeh guarantee karta hai)

Worked Example: Code Ko Rename Karna

Chalo apne pehle wale example ko 8 architectural registers (R1-R8) aur 32 physical registers (P0-P31) ke saath rename karte hain.

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) — Kyun? Yeh current physical registers hain jo R2 aur R3 ki values hold karte hain
Allocate: P0 free list se — Kyun? R1 ki nayee value ke liye ek fresh location chahiye
Execute: P0 ← P11 + P12
Update RAT: R1→P0 — Kyun? R1 ke future reads ko yahi result milna chahiye, purana P10 nahi
Save old: ROB[0] = {R1, P10→P0} — Kyun? Exception recovery ke liye aur P10 kab free karein yeh jaanne ke liye

Instruction 2: MUL R4, R1, R5

Sources: P0 (R1), P14 (R5) — Kyun? I1 ne R1 ko P0 rename kar diya, toh hum P0 se read karte hain
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) — Kyun? Kisi bhi instruction ne abhi tak R6 ya R7 ko touch nahi kiya
Allocate: P2
Execute: P2 ← P15 + P16 — Yeh safe kyun hai? P2 bilkul P0 se independent hai. I2 abhi bhi P0 se read karta hai, I3 P2 mein write karta hai. Koi conflict nahi!
Update RAT: R1→P2 — Kyun? Ab R1 ke future reads ko I3 se nayi value milegi
Save old: ROB[2] = {R1, P0→P2}

Instruction 4: SUB R8, R1, R9

Sources: P2 (R1), P18 (R9) — Kyun? I3 ne abhi R1 ko P2 rename kiya, toh hum latest value read karte hain
Allocate: P3
Execute: P3 ← P2 - P18
Update RAT: R8→P3
Save old: ROB[3] = {R8, P17→P3}

Key insight: I1, I2, aur I3 teeno architectural register R1 use karte hain, lekin woh alag physical registers (P0, P0, P2) use karte hain. WAR aur WAW hazards eliminate ho jaate hain kyunki P0 aur P2 alag storage locations hain.

Worked example Execution Timeline

Renaming ke bina (false dependencies se serialize hua):

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

Renaming ke saath (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) Kyun? I2 I1 ke result ka wait karta hai (true RAW), lekin I3 I2 ka wait nahi karta (false WAR eliminate ho gaya). I4 sirf I3 ka wait karta hai (true RAW).

Physical Register File Ka Size

Kyun?

$N_{a r c h}$ : Hume kam se kam ek physical register chahiye har architectural register ki committed state ke liye
$N_{R O B}$ : ROB mein har in-flight instruction ne ek physical register allocate kiya hoga jo abhi commit nahi hua
Practice mein: $N_{p h y s} \approx N_{a r c h} + N_{R O B} slack$

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

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

Agar physical registers khatam ho jaayein toh kya hoga?

Instruction decode stall kar jaata hai jab tak koi register free na ho
Isse register pressure ya register starvation kehte hain
Yeh un codes mein dikhta hai jisme bahut saari live values hoti hain (bahut variables wale bade loops)

Common mistake "Zyada Physical Registers Hamesha Performance Improve Karte Hain"

Kyun sahi lagta hai: Agar 256 registers achhe hain, toh 512 aur bhi achhe honge!

Kyun galat hai: Diminishing returns + hardware costs:

Access time: Bade register files ke read/write latencies zyada hote hain. 512-entry register file 256-entry se 10-20% slow ho sakti hai.
Area aur power: Register files bade structures hote hain (parallel reads/writes ke liye multi-ported). Size double karna chip area aur power significantly badhata hai.
Limited benefit: Zyaatar code mein itna ILP nahi hota ki 256+ registers use ho sakein. ROB size usually bottleneck hoti hai.
Free list management: Badi free lists ko zyada complex allocation logic chahiye.

Sweet spot: Modern designs 150-256 physical registers use karte hain. Isse aage jaana specialized workloads ki madad karta hai lekin typical cases ko hurt karta hai.

Out-of-Order Execution Ke Saath Integration

The pipeline:

Memory se instructions Fetch karo
Decode & Rename: RAT ke zariye architectural registers → physical registers mein translate karo
Dispatch: Physical register tags ke saath reservation stations par bhejo
Execute: Physical registers ready hone par out-of-order execution karo
Complete: Physical register mein result likho, Common Data Bus (CDB) par tag broadcast karo
Retire/Commit: In-order commit architectural state update karta hai, old physical registers free karta hai

Yeh order kyun?

Rename early (decode stage mein) taaki turant parallelism expose ho sake
Physical registers ke saath out-of-order execute karo taaki false dependencies na aayein
Precise exceptions maintain karne aur registers safely free karne ke liye in-order commit karo

Worked example Forwarding Ke Saath Register Renaming

Dekho:

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

Forwarding ke bina:

ADD cycle 1 ke end mein P0 likhta hai
MUL cycle 2 ke start mein P0 read karta hai
1 cycle latency

Result forwarding (bypass) ke saath:

ADD cycle 1 mein result compute karta hai
Result seedha MUL ke execution unit ko CDB ke zariye forward hota hai
MUL cycle 2 mein execute karna shuru kar sakta hai register file write ka wait kiye bina
Effectively register write latency hide ho jaati hai

Physical registers better forwarding kyun enable karte hain? Physical register tag (P0) result ko uniquely identify karta hai. P0 ka wait kar rahi koi bhi instruction use CDB se turant grab kar sakti hai, architectural register names se independent.

Precise Exceptions aur Recovery

Ek complication: Kya hoga agar instruction I3 exception cause kare, lekin I4 (jo program order mein baad mein aati hai) already execute ho gayi ho aur registers rename kar chuki ho?

Solution: ROB in-order state maintain karta hai.

Instruction $i$ par exception aane par:

ROB se $i$ ke baad ki saari instructions flush karo (architecturally yeh kabhi hue hi nahi)
ROB entries use karke instruction $i$ ki state par RAT restore karo
Flushed instructions dwara allocate kiye gaye saare physical registers free list mein wapas free karo
Architecturally precise state ke saath exception handler par branch karo

Connections

Instruction-Level Parallelism (ILP) — Register renaming false dependencies remove karke exploitable ILP badhata hai
Out-of-Order Execution — Renaming OoO ke liye zaruri hai; name dependencies eliminate kiye bina reorder nahi kar sakte
Tomasulo's Algorithm — Tomasulo register renaming ke saath reservation stations use karta hai (uske "tags" physical register identifiers hain)
Reorder Buffer (ROB) — ROB precise exceptions ke liye physical register allocations track karta hai
Scoreboarding — Purani technique jo false dependencies eliminate nahi kar sakti thi (sirf true dependencies track karta tha)
Memory Disambiguation — Memory addresses par apply ki gayi similar idea (store-load renaming)
Superscalar Execution — Multiple-issue superscalars ko simultaneously-decoded instructions ke beech name hazards avoid karne ke liye renaming chahiye
Branch Prediction — Mispredictions ko RAT restoration chahiye, exception handling ki tarah

Recall 12-Saal-Ke-Bachche Ko Samjhao

Socho tum homework kar rahe ho aur tumhare paas ek notebook hai jiska naam "Page 1" hai. Pehle tum apna math ka jawab Page 1 par likhte ho. Phir tumhe science ka jawab likhna hai, lekin tum use bhi "Page 1" kehna chahte ho kyunki yahi naam tum apne current answer ke liye use karte ho.

Problem: Tum math ka answer abhi mita nahi sakte kyunki tumhara dost abhi bhi use copy kar raha hai! Lekin tum science nahi likh sakte jab tak math mita na do. Tum stuck ho.

Register renaming ek magical notebook jaisa hai jahan "Page 1" sirf ek label hai jo kisi bhi real page ko point kar sakta hai ek bade stack mein. Jab tumhe science likhni hoti hai, notebook kehti hai "Theek hai, 'Page 1' ab real page 47 ko point karta hai" jabki tumhara math answer real page 23 par safe rehta hai. Tumhara dost abhi bhi page 23 se copy kar sakta hai, aur tum page 47 par usi waqt likh sakte ho!

Teacher (commit stage) eventually purani page 23 phek deta hai jab sabka kaam ho jaata hai. Tum same labels (R1, R2, R3) reuse karte rehte ho lekin notebook ke peeche hundreds of real pages hain, toh kabhi workspace khatam nahi hota.

#flashcards/hardware

Register renaming kya hai? :: Ek microarchitectural technique jo architectural registers ko physical registers ke ek bade pool mein map karta hai, false dependencies (WAR aur WAW hazards) eliminate karta hai jabki ISA dwara define ki gayi chhoti register set ka illusion maintain karta hai.

Teen types ki dependencies kya hain aur kaunsi false hain?

RAW (read-after-write) ek true dependency hai. WAR (write-after-read) aur WAW (write-after-write) false dependencies hain jo register name reuse ki wajah se hoti hain, actual data flow ki nahi.

Ek structure jo har architectural register ko uske current physical register par map karta hai. Decode par update hota hai jab koi instruction destination register likhti hai.

Physical registers free list mein kab wapas free hote hain?

Commit time par, program order mein. Woh old physical register jo pehle destination architectural register se mapped tha, naya mapping commit hone ke baad free ho jaata hai.

Precise exceptions aur architecturally correct state maintain karne ke liye. Agar exception aaye, toh hume us instruction par exact architectural state restore karni chahiye, baad ke saare renaming operations undo karke.

Typically kitne physical registers chahiye hote hain?

Kam se kam N_arch + N_ROB. Modern processors 150-256 physical registers use karte hain 16-32 architectural registers aur 100-224 ROB entries ke liye.

Agar processor ke physical registers khatam ho jaayein toh kya hota hai?

Instruction decode stall kar jaata hai jab tak commit par koi physical register free na ho. Isse register pressure ya register starvation kehte hain.

False dependencies eliminate karke, woh instructions jo sirf register names par conflict karti hain (data par nahi) parallel mein execute ho sakti hain. Yeh scheduler ke liye zyada instruction-level parallelism expose karta hai.

Architectural aur physical registers mein kya fark hai?

Architectural registers ISA dwara defined hote hain aur software ko visible hote hain (jaise x86 ke 16 GPRs). Physical registers hardware mein actual storage locations hote hain (typically 10-15× zyada) jinse architectural registers map hote hain.