Register renaming: Visual walkthrough — Hinglish deep dive

5.3.4 · D2 · Hardware › Advanced Microarchitecture › Register renaming

Yeh Register renaming ka picture-first deep dive hai. Hum poora idea ek blank slate se build karte hain: koi bhi jargon use nahi hota jab tak usse draw na kar liya jaye. Agar koi word scary lage, ruko — uske liye thoda neeche ek chalkboard picture hai.

Chalo pehle kuch basic words define karte hain, seedhe words mein.

Hum ek chhote se program ko poora follow karenge. Ise abhi mile:

I1:  R1 = R2 + R3
I2:  R4 = R1 * R5
I3:  R1 = R6 + R7
I4:  R8 = R1 - R9

Label R1 par nazar rakho. Teen alag instructions ise use karna chahti hain, lekin unka matlab alag-alag numbers se hai. Yahi collision hai jise hum ab theek karne wale hain.

Step 1 — Label R1 par collision draw karo

KYA. Hum chaar instructions ko ek timeline par rakhte hain aur jo bhi ek hi register ko touch karte hain unke beech arrows draw karte hain.

KYUN. Problem fix karne se pehle tumhe use dekhna hoga. Har arrow equally bura nahi hota — hum real arrows ko fake waalon se alag karna chahte hain, aur ek picture mein yeh fark clearly dikhta hai.

PICTURE.

Arrows padho:

Blue arrow (I1 → I2): I2 ko woh number chahiye jo I1 ne abhi R1 mein banaya. Agar I1 khatam nahi hua, I2 ke paas multiply karne ke liye kuch nahi. Yeh ek Read After Write (RAW) dependency hai — ek real wali, jise true dependency kehte hain.
Pink arrow (I2 → I3): I3 write karta hai R1 mein jab I2 abhi bhi R1 read kar raha hai. Agar I3 bahut jaldi write kar de, I2 galat number read karega. Yeh ek Write After Read (WAR) dependency hai.
Yellow arrow (I1 → I3): I1 aur I3 dono R1 mein write karte hain. Yeh ek Write After Write (WAW) dependency hai.

Step 2 — Dekho kyun false arrows time waste karte hain

KYA. Hum program ko har arrow maanke schedule karte hain, phir measure karte hain kitne cycles lagte hain.

KYUN. Yeh prove karne ke liye ki false arrows expensive hain, hum "sabkuch maano" aur "ideal" ko compare karte hain. Unka fark exactly woh speed hai jo hum table par chhod rahe hain.

PICTURE.

D = decode (instruction samajhna), E = execute (maths karna).
Top block: pink WAR arrow maano → I3 ko wait karna padta hai I2 ka, bhaale woh independent ho. Chain kheench jaati hai.
Bottom block: agar pink aur yellow arrows gayab ho jaayein, I3 I2 ke saath execute ho sakta hai. Poora run jaldi khatam hota hai.

Top block mein waiting boxes sirf ek naam ki wajah se hai, data ki wajah se nahi. Yahi hai hamara aage badhne ka reason.

Step 3 — Core idea: names aur boxes alag cheezein hain

KYA. Hum "register" ke ek concept ko do alag concepts mein tod dete hain.

KYUN. Trap yeh hai ki R1 ka matlab hai "label jo programmer ne type kiya" aur "physical box jisme number rehta hai" — dono ek saath. Jab tak yeh dono ek hi cheez hain, do instructions R1 mein likhne ke liye ek box ke liye ladenge. Inhe alag karo aur larai khatam.

PICTURE.

RAT ek phone book ki tarah hai: ek label dial karo, box number milo. Jab do instructions "write R1" karna chahti hain, hum simply label ko doosri baar ek nayi box ki taraf point kar dete hain. Ab woh alag-alag boxes mein likhti hain — koi larai nahi.

Step 4 — Renaming recipe, ek instruction ek baar

KYA. Hum idea ko ek fixed 4-move procedure mein badal dete hain jo hardware har instruction par run karta hai jab woh decode hoti hai.

KYUN. Ek recipe mechanical honi chahiye — koi cleverness nahi, koi guessing nahi — kyunki silicon ko yeh ek second mein lakhon baar karna hota hai. Har move ek zaroorat ka jawab deta hai.

Formula Ek instruction rename karo

Rdest = Rsrc1 op Rsrc2

move 1: ek nayi box lo P_{n e w} \leftarrow FreeList.pop()

move 2: dekho inputs sach mein kahaan rehte hain P_{sr c 1} = RAT [R_{sr c 1}], P_{sr c 2} = RAT [R_{sr c 2}]

move 3: label ko nayi box ki taraf repoint karo RAT [R_{d es t}] \to P_{n e w}

move 4: jo box replace ki woh likh lo ROB [tail] = {R_{d es t}, P_{o l d}, P_{n e w}}

Term by term:

$P_{n e w}$ — bilkul naya box jisme yeh instruction apna answer likhegi.
$RAT [R_{sr c}]$ — "is source ki current value kaun si box mein hai?" (Kisi pehli instruction ne use move kiya hoga.)
$P_{o l d}$ — woh box jis par label is instruction se pehle point kar raha tha. Hum uska naam rakhte hain taaki undo kar sakein, aur baad mein recycle kar sakein.
$ROB$ — Reorder Buffer, ek queue jo in-flight instructions ko program order mein yaad rakhta hai.

PICTURE.

I1: R1 = R2 + R3 ke liye chaar moves follow karo: P0 pop karo, R2→P11 aur R3→P12 lookup karo, R1→P0 repoint karo, aur ROB mein note stash karo {R1, old=P10, new=P0}.

Step 5 — Poora program machine se chalaao

KYA. Hum 4-move recipe chaar saari instructions par apply karte hain aur dekhte hain RAT kaise badalta hai.

KYUN. Ek instruction mechanics prove karti hai; chaar cure prove karte hain — hum literally dekhna chahte hain pink aur yellow arrows gayab hote.

Start 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,…].

Instr	reads (boxes)	new box	RAT after	ROB note
I1 `R1=R2+R3`	P11, P12	P0	R1→P0	{R1, P10→P0}
I2 `R4=R1*R5`	P0, P14	P1	R4→P1	{R4, P13→P1}
I3 `R1=R6+R7`	P15, P16	P2	R1→P2	{R1, P0→P2}
I4 `R8=R1-R9`	P2, P18	P3	R8→P3	{R8, P17→P3}

PICTURE.

Magic R1 ke boxes mein hai:

I2 reads R1 aur paata hai P0 (I1 ka answer).
I3 writes R1 into P2 — ek alag box — toh woh P0 ko overwrite nahi kar sakta.
I4 reads R1 aur paata hai P2 (I3 ka answer).

Pink WAR arrow (I2 read vs I3 write) gone hai: woh touch karte hain P0 vs P2. Yellow WAW arrow (I1 write vs I3 write) gone hai: P0 vs P2. Sirf blue true arrows bachte hain.

Step 6 — Commit rule aur "bahut jaldi free mat karo" case

KYA. Hum describe karte hain ki ek used-up box free list mein kab jaati hai, aur jaldi karne ki galati kya hoti hai.

KYUN. Agar hum kabhi boxes recycle na karein toh woh khatam ho jaayenge. Lekin bahut jaldi recycle karo aur jo instruction abhi purani value chahti hai woh garbage read karegi. Commit rule isi ko balance karta hai.

PICTURE.

Picture danger case dikhati hai: agar jis second I3 ne R1 rename kiya hum P0 free kar dete, toh I2 — jo abhi bhi P0 chahta hai — P0 ko already kisi aur ko diya hua aur overwrite hua pa sakta. I2 ke commit tak P0 recycle na karna exactly isliye hai kyunki $P_{o l d}$ store kiya jaata hai aur baad mein free hota hai.

Step 7 — Degenerate case: boxes khatam ho jaana

KYA. Hum count karte hain kitne physical boxes chahiye, aur kya hota hai jab dhher khaali ho jaaye.

KYUN. Renaming tab hi kaam karta hai jab free list mein boxes hon. Agar move 1 (FreeList.pop()) khaali pile paata hai, toh poora trick ruk jaata hai. Isliye pile ka size sahi rakhna zaroori hai.

PICTURE.

Picture free list ko khaali hote dikhati hai; agla pop() kuch nahi paata, toh decode stall karta hai jab tak koi commit ek box wapas push na kare. Yeh backlog hai register pressure. Example: 16 labels + ek 224-entry ROB ⇒ ≥ 240 boxes chahiye; real chips 256 tak round up karte hain (indexing ke liye ek seedha power of two).

Ek picture mein summary

Ek label R1, teen writers, teen alag boxes P0, P2, P3 — false arrows dissolve ho jaate hain jabki true arrows rehte hain, aur independent kaam side by side chalta hai. Yahi engine Out-of-Order Execution, Tomasulo's Algorithm, aur Superscalar Execution ko feed karta hai; ek galat branch guess ko purane RAT mappings ROB se restore karke undo kiya jaata hai.

Recall Feynman retelling — apne words mein bolo

Hamare paas sirf kuch register labels the, toh alag-alag kaam baar baar ek hi label par clash karte the bhaale unka kaam alag-alag ho. Humne "label" aur "storage box" ko alag kar diya: labels kam rehte hain (taaki purane programs chala sakein), boxes bahut hain aur chhupe hue hain. Ek chhoti si phone book, RAT, yaad rakhti hai ki abhi har label kaun se box ki taraf point kar raha hai. Har instruction apne answer ke liye ek fresh box pakadti hai, apne inputs ke current boxes lookup karti hai, phir apne output label ko fresh box ki taraf repoint karti hai — aur jo box replace ki use note kar leti hai. Kyunki R1 ka har writer apna box paata hai, sirf woh connections bachte hain jo sach mein ek number carry karte hain. Hum ek box tab recycle karte hain jab jo instruction ne use replace kiya woh official ho jaaye, taaki koi kabhi woh box na padhe jo pehle hi kisi aur ko de diya gaya ho. Aur hum enough boxes rakhte hain — kam se kam labels plus in-flight instructions — warna machine ruk jaati hai. Yahi poora trick hai: bahar ek chhota sa instruction set, andar ek bada secret boxes ka dhher.

Recall Quick self-test

Kaun se arrows false hain aur kyun? ::: WAR aur WAW — yeh sirf naam ki clash hain, data ki zaroorat nahi; alag boxes mein rename karna inhe hata deta hai. Source operands label se directly use karne ki jagah RAT se kyun padhein? ::: Kyunki ek pehli instruction ne woh label kisi nayi box pe move kiya hoga; RAT woh box deta hai jo current value hold karta hai. $P_{o l d}$ ko rename par nahi balki commit par free kyun karein? ::: Program order mein pehli ek in-flight instruction abhi bhi purani box ki zaroorat ho sakti hai; sirf commit guarantee karta hai ki woh truly dead hai. 16 labels aur 224-entry ROB ke liye minimum physical registers? ::: $16 + 224 = 240$ (chips 256 tak round karte hain).