Register renaming: Exercises — Hinglish deep dive

5.3.4 · D4 · Hardware › Advanced Microarchitecture › Register renaming

Yeh note Register renaming ka self-testing companion hai. Har problem ko solution kholne se pehle khud solve karo. Problems paanch rungs pe chadhti hain: L1 Recognition → L2 Application → L3 Analysis → L4 Synthesis → L5 Mastery. Yahan use kiye gaye har symbol parent note mein build kiye gaye hain; agar koi term naya lage, toh neeche diye intuition boxes mein woh re-anchor kiya gaya hai.

Teen hazard names yaad karo taaki questions cleanly padhein:

RAW (Read-After-Write) = true dependency — B ko genuinely A ki value chahiye.
WAR (Write-After-Read) = false — B ek aisa naam reuse karta hai jise A abhi bhi read kar raha tha.
WAW (Write-After-Write) = false — ek naam par do writers; sirf aakhri wala matter karta hai.

Renaming WAR aur WAW ko khatam karta hai; yeh RAW ko khatam nahi kar sakta (dekho Instruction-Level Parallelism (ILP)).

Level 1 — Recognition

Exercise 1.1

Neeche diye instruction pairs ke beech har dependency ko classify karo.

I1: ADD R1, R2, R3
I2: SUB R4, R1, R5
I3: MUL R1, R6, R7

(a) I1→I2 on R1 (b) I2→I3 on R1 (c) I1→I3 on R1.

Recall Solution

(a) I1 writes R1, I2 reads R1 → RAW (true). I2 ko I1 ka result chahiye. (b) I2 reads R1, I3 writes R1 → WAR (false). I3 sirf naam reuse karta hai. (c) I1 writes R1, I3 writes R1 → WAW (false). Architecturally sirf baad wala write survive karta hai. Renaming (b) aur (c) ko remove karta hai; (a) rehta hai.

Exercise 1.2

Sahi ya galat: "Register renaming un architectural registers ki sankhya badhata hai jinhein programmer name kar sakta hai."

Recall Solution

Galat. ISA fixed rehta hai (jaise 16 named registers). Renaming behind the scenes physical lockers add karta hai — software ko yeh dikhta hi nahi. Parent note ka [!mistake] "Why not just add architectural registers?" dekho.

Exercise 1.3

Kaunsi structure is sawaal ka jawaab deti hai "R2 ki current value abhi kahan hai?" — RAT, ROB, ya Free list?

Recall Solution

RAT (Register Alias Table). ROB in-flight instructions ko commit/recovery ke liye track karta hai; free list unused physical registers rakhti hai.

Level 2 — Application

8 architectural registers use karo initial RAT Ri → P(i+9) ke saath (toh R1→P10, R2→P11, …, R9→P18) aur free list [P0, P1, P2, P3, …] order mein pop karte hue.

Exercise 2.1

Is pair ko rename karo. Har ek ke liye sources, allocated destination, RAT update, aur ROB entry do.

I1: ADD R2, R3, R4
I2: ADD R5, R2, R2

Recall Solution

I1: ADD R2, R3, R4

Sources: RAT[R3]=P12, RAT[R4]=P13.
Allocate: pop P0.
Execute: P0 ← P12 + P13.
RAT update: R2 → P0.
ROB[0] = {R2, old=P11, new=P0}.

I2: ADD R5, R2, R2

Sources: RAT[R2]=P0 (I1 ne abhi-abhi ise rename kiya — yeh ek RAW hai, correctly capture hua), RAT[R2]=P0 phir se.
Allocate: pop P1.
Execute: P1 ← P0 + P0.
RAT update: R5 → P1.
ROB[1] = {R5, old=P14, new=P1}.

Exercise 2.2

Upar I1 aur I2 ko (order mein) commit karne ke baad, kaun se physical registers free list mein wapas jaate hain?

Recall Solution

Commit par har instruction apne architectural destination ka woh old physical register free karti hai jo pehle use hota tha.

Commit I1: R2 ka old locker P11 free karo.
Commit I2: R5 ka old locker P14 free karo. Freed set = {P11, P14}. (P0 aur P1 busy rehte hain — woh live R2 aur R5 hold karte hain.)

Exercise 2.3

x86-64 ke liye $N_{a r c h} = 16$ architectural registers aur $N_{R O B} = 224$ -entry reorder buffer ke saath, parent formula se minimum physical register file size compute karo: $N_{p h y s} \geq N_{a r c h} + N_{R O B} .$

Recall Solution

$N_{p h y s} \geq 16 + 224 = 240$ . Designers 256 tak round up karte hain (power of 2) taaki physical register index exactly 8 bits ho.

Level 3 — Analysis

Exercise 3.1

Parent ke 4-instruction sequence ke liye, timeline par mark karo ki kaun se waits true hain (renaming ke baad bhi survive karte hain) aur kaun se false hain (eliminate ho jaate hain).

I1: ADD R1, R2, R3
I2: MUL R4, R1, R5
I3: ADD R1, R6, R7
I4: SUB R8, R1, R9

Recall Solution

I1→I2 on R1: RAW true → I2, I1 ka wait karta hai. Survive karta hai.
I2→I3 on R1: WAR false → eliminate ho gaya (I2 reads P0, I3 writes P2).
I1→I3 on R1: WAW false → eliminate ho gaya (different lockers P0 vs P2).
I3→I4 on R1: RAW true → I4, I3 ka wait karta hai. Survive karta hai. Toh sirf do edges bachte hain: I1→I2 aur I3→I4. Yeh do independent chains banate hain jo parallel mein run karti hain — yahi kaaran hai ki parent ka timeline 9 cycles se 6 par aa jaata hai.

Exercise 3.2

Ek in-order machine us sequence ke liye 9 cycles leta hai; renamed out-of-order machine 6 leta hai. Speedup compute karo.

Recall Solution

$Speedup = \frac{9}{6} = 1.5 \times .$ Yeh gain purely do RAW chains ko overlap karne se aata hai; renaming ne false edges remove karke legal permission di.

Exercise 3.3

Maano free list tab empty hai jab decode ek aisi instruction par pahunchta hai jo ek register likhti hai. Kya hota hai, aur is condition ko kya kehte hain?

Recall Solution

Decode stall karta hai — instruction ko rename nahi kiya ja sakta kyunki koi fresh physical register allocate nahi ho sakta. Pipeline tab tak wait karti hai jab tak koi purani instruction commit na kare aur apna old register free list par wapas push na kare. Is condition ko register pressure kehte hain. Yeh Out-of-Order Execution par ek structural limit hai, koi data dependency nahi.

Level 4 — Synthesis

Exercise 4.1

Tum ek core design kar rahe ho. Tum jaante ho ki har in-flight instruction jo ek register likhti hai, decode se commit tak ek physical register consume karti hai. Tumhare paas $N_{a r c h} = 32$ architectural registers hain aur tum kam se kam $N_{R O B} = 192$ instructions in-flight rakhna chahte ho, jinmein historically ~75% ek register likhti hain. Do (a) safe minimum $N_{p h y s}$ jo kabhi stall na kare chahe har ROB entry likhe, aur (b) ek leaner estimate agar sirf 75% likhein.

Recall Solution

(a) Worst case (har in-flight instruction likhti hai): $N_{p h y s} = N_{a r c h} + N_{R O B} = 32 + 192 = 224.$ Yeh instruction mix ki parwah kiye bina register exhaustion se stall guarantee nahi hone deta.

(b) 75% writers ke liye provision ( $192 \times 0.75 = 144$ in-flight allocations): $N_{p h y s} \approx 32 + 144 = 176.$ Leaner, sasta silicon — lekin agar kisi code region mein 75% se zyada register-writing instructions hoon, toh decode stall karega. Real designs workload traces ke base par 176 aur 224 ke beech koi point choose karte hain; 224 no-stall guarantee hai.

Exercise 4.2

Renaming ko Branch Prediction ke saath combine karo. Ek mispredicted branch ka matlab hai ki branch ke baad decode ki gayi har instruction speculative thi aur use squash karna hoga. ROB records {Rdest, old, new} use karte hue, describe karo ki RAT aur free list ko pre-speculation state mein kaise restore kiya jaata hai.

Recall Solution

ROB ko backwards tail se branch tak walk karo, aur har squashed entry {Rdest, old, new} ke liye:

RAT[Rdest] ← old — woh mapping restore karo jo is (ab-cancelled) write se pehle exist karti thi.
Free list.push(new) — fresh locker sirf ek speculative instruction ke liye allocate kiya gaya tha jo kabhi commit nahi hogi, toh ise reclaim karo. Branch ke upar ki saari entries process karne ke baad, RAT aur free list exactly wahi hain jo branch decode hone ke waqt thi. Yahi kaaran hai ki parent ke algorithm ka step 4 old mapping record karta hai: yeh undo log hai. Committed instructions (branch ke neeche) untouched rehti hain — recovery precise hai.

Level 5 — Mastery

Exercise 5.1

Renaming Tomasulo's Algorithm aur Scoreboarding ke saath interact karta hai. Tomasulo effectively reservation-station tags ke zariye rename karta hai; ek physical-register-file scheme RAT ke zariye rename karti hai. 16 architectural registers aur 8 reservation stations wali machine vs. 16 architectural + 96 physical registers wali machine ke liye, kaun zyada independent renamings of the same architectural register ek saath live rakh sakta hai, aur kyun?

Recall Solution

Distinct rename slots count karo.

Tomasulo (RS-tag renaming): simultaneous renamings ki sankhya reservation-station entries ki sankhya = 8 se bounded hai (har RS tag ek temporary name hai). Values RS entries ke andar broadcast hone tak rehti hain.
Physical register file: simultaneous renamings ki sankhya free physical registers se bounded hai, $96 - 16 = 80$ non-committed lockers tak.

Toh physical-register-file scheme kaafi zyada live renamings rakh sakta hai ( $\leq 80$ vs $\leq 8$ ). Yahi kaaran hai ki modern superscalar cores (dekho Superscalar Execution) RS-based value storage se large physical register files ki taraf gaye: zyada in-flight renamings ⇒ deeper reordering window ⇒ zyada exploitable ILP.

Exercise 5.2

Memory operations consider karo. Renaming register hazards handle karta hai, lekin same address par do stores/loads memory hazards create karte hain. Register renaming yeh kyun resolve nahi kar sakta, aur kaun sa mechanism sambhalna padta hai?

Recall Solution

Register renaming isliye kaam karta hai kyunki architectural register names decode par known hote hain — R1 literally instruction encoding mein hai, toh hardware use immediately ek fresh locker de sakta hai. Memory addresses execute time par compute hote hain (jaise [R2 + offset]), toh decode par hardware ko abhi tak pata nahi ki do memory instructions alias karti hain ya nahi. Woh unknown addresses ko non-conflicting "lockers" pre-assign nahi kar sakta. Yeh Memory Disambiguation se resolve hota hai — ek load/store queue jo addresses ko compute hone ke baad compare karti hai aur correct ordering enforce karti hai (ya speculate karke baad mein check karti hai).

Exercise 5.3

Ek core mein $N_{a r c h} = 16$ , physical file $N_{p h y s} = 128$ hai. Ek given instant par 16 physical registers committed architectural state hold karte hain aur 40 in-flight (uncommitted) writers ko allocated hain. (a) Free list par kitne hain? (b) Koi bhi commit hone se pehle ROB 30 aur register-writing instructions se bhar jaata hai. Kya decode stall karega? (c) Original instant se stall hone se pehle kitni zyada register-writing instructions rename ki ja sakti hain?

Recall Solution

(a) Free = total − committed − in-flight = $128 - 16 - 40 = 72$ . (b) 30 new writers ko 30 lockers chahiye; free list mein 72 ≥ 30 hain, toh koi stall nahi. Free list $72 - 30 = 42$ ho jaati hai. (c) Original instant se, decode tab tak rename kar sakta hai jab tak free list empty na ho: 72 additional register-writing instructions (maano beech mein koi commit kuch free nahi karta). 73wein write-instruction ko empty free list milegi aur woh stall karega — register pressure.

Recall Self-test one-liners (answer cover karo, yaad karo)

RAT kis sawaal ka jawaab deta hai ::: Abhi ek architectural register ki current value physically kahan hai. Commit par kaun sa physical register free hota hai ::: PURANA wala jis par architectural destination pehle mapped thi. Renaming kaun se hazards eliminate karta hai ::: WAR aur WAW (false); RAW kabhi nahi. $N_{p h y s}$ safe minimum ::: $N_{a r c h} + N_{R O B}$ . Renaming mein decode stall ka karan ::: Empty free list = register pressure. Mispredict RAT kaise restore karta hai ::: ROB old-mappings ko backwards replay karo aur har new register free list mein wapas push karo. Renaming memory hazards kyun fix nahi kar sakta ::: Addresses decode par unknown hote hain; disambiguation execute par hota hai.

Connections

Parent: Register renaming · Hinglish: 5.3.04 Register renaming (Hinglish) See also: Instruction-Level Parallelism (ILP) · Out-of-Order Execution · Tomasulo's Algorithm · Reorder Buffer (ROB) · Scoreboarding · Memory Disambiguation · Superscalar Execution · Branch Prediction