Visual walkthrough — Branch target buffer (BTB)

5.3.9 · D2 · Hardware › Advanced Microarchitecture › Branch target buffer (BTB)

Yeh page parent result ko — kyun ek Branch Target Buffer 1–2 cycle branch penalty ko 0 cycle penalty mein badal deta hai — bilkul scratch se rebuild karta hai, ek step mein ek picture. Hum assume karte hain ki aapko pipelines ke baare mein abhi kuch nahi pata. Har word use hone se pehle earn kiya gaya hai.

Naye ho? Pehle Branch target buffer (BTB) parent note padho, ya ise Hinglish mein padho.

Step 1 — "PC" kya hota hai aur instructions ek line mein kyun aate hain?

KYA. Ek processor ek program chalata hai: instructions ke naam se jaani jaane wali chhoti commands ki ek lambi list, jo memory mein store hoti hai. Har instruction ek numbered slot mein hoti hai jise address kehte hain. Processor ek number maintain karta hai jo kehta hai "main abhi kaun si instruction fetch kar raha hun" — woh number hai Program Counter (PC).

KYUN. Branches ke baare mein har baat yeh sawaal hai ki "PC mein aage kaunsa number daalu?" Toh jump karne ki baat karne se pehle, hume PC ko aage crawl karte hue picture karna hoga.

PICTURE. Figure dekho. Instructions addresses 0x1000, 0x1004, 0x1008, … par rehti hain — chaar ka gap isliye kyunki har instruction 4 bytes wide hoti hai. Default move yeh hai:

${\text{PC}}_{\text{next}}=\underset{\text{where I am now}}{\underbrace{\text{PC}}}+\underset{\text{one instruction wide}}{\underbrace{4}}$

• $\text{PC}$ — current address jo fetch ho raha hai.
• $+4$ — bilkul agle instruction par step karna (yeh "boring" case hai).

Step 2 — Branch ek aisi instruction hai jo PC ko kahin door badal deti hai

KYA. Ek branch ek special instruction hai jo kehti hai "PC+4 ki jagah, kisi target address par jump karo." Ek conditional branch jaise beq 0x2000 ("branch if equal") 0x2000 par tabhi jump karti hai jab condition hold kare; warna PC+4 par fall through ho jaati hai.

KYUN. Yahi puri problem hai. Next-PC ab obvious nahi hai — yeh depend karta hai (a) kya yeh branch bhi hai? aur (b) kya yeh taken hai? aur (c) yeh kahan jaati hai? Teen unknowns, aur processor abhi jawab chahta hai.

PICTURE. Laal arrow "taken" path hai jo 0x1004 se 0x2000 tak leap karta hai. Grey arrow "not taken" fall-through hai 0x1008 tak.

${\text{PC}}_{\text{next}}=\{\begin{array}{ll}\text{target}& \text{if branch taken}\\ \text{PC}+4& \text{if not taken}\end{array}$

• $\text{target}$ — woh door ka address jahan branch jump karti hai (jaise 0x2000).
• cases brace — "condition ke hisaab se ek line choose karo."

Step 3 — Pipeline: processor ek saath kai instructions par kaam karta hai

KYA. Ek modern CPU ek pipeline hai — ek assembly line. Jab ek instruction execute ho rahi hai, agli decode ho rahi hai, aur uske aage waali fetch ho rahi hai. Inhe stages kehte hain Fetch → Decode → Execute.

KYUN. Yahi exactly kyun branches hurt karte hain. PC ko next address Fetch stage mein dena hota hai — lekin "yeh branch hai aur iska target yeh hai" yeh fact baad mein, Decode mein discover hota hai. Chahne ke moment aur jaanne ke moment ke beech ek time gap hota hai.

PICTURE. Teen coloured lanes left to right move kar rahi hain. Fetch stage 0 hai, Decode ek cycle baad, Execute do cycle baad. "Mujhe target chahiye" wala moment (Fetch) aur "maine target compute kiya" wala moment (Decode) ek wall se separated hain.

$\underset{\text{cycle }0}{\underbrace{\text{Fetch}}}\to \underset{\text{cycle }1\text{: target known here}}{\underbrace{\text{Decode}}}\to \underset{\text{cycle }2}{\underbrace{\text{Execute}}}$

Dekho Pipeline Hazards kyun yeh gap ek "control hazard" hai.

Step 4 — BTB ke bina: waste hone wale cycles (penalty)

KYA. Ek taken branch ko pipeline mein follow karo bina BTB ke. Cycle 0 mein hum branch fetch karte hain, lekin PC ko pata nahi ki yeh branch hai, toh woh PC+4 next fetch karta hai (galat instruction). Decode mein hi target pata chalta hai. Hume galat-fetched instructions ko flush (throw away) karna padta hai aur target se re-fetch karna padta hai.

KYUN. Woh throw-away cycles pure waste hain — branch penalty. Yahi woh number hai jis par BTB attack karega. Picture se inhe count karna hi derivation hai.

PICTURE. Cycle 0 branch fetch karta hai; cycle 1 ne galat PC+4 fetch kiya (crossed out); cycle 1 Decode mein target reveal hota hai; cycle 2 mein finally sahi target fetch hota hai. Crossed-out slots count karo.

${\text{Penalty}}_{\text{no BTB}}=\underset{\text{time to learn "it’s a branch"}}{\underbrace{\text{decode latency}}}+\underset{\text{compute where}}{\underbrace{\text{target calc}}}=1\text{–}2\text{cycles}$

• Har term ek wasted pipeline slot hai.
• Deeper pipelines mein yeh badhta hai — lekin 1–2 classic number hai.

Step 5 — BTB: ek notebook jo yaad rakhti hai "pichli baar, is PC ne yahan jump kiya tha"

KYA. Ek Branch Target Buffer ek chhota cache hai jo branch ke PC se keyed hota hai. Har entry mein ek tag (upper PC bits, yeh prove karne ke liye ki sahi branch hai) aur ek target (pichli baar woh branch kahan gayi thi) hota hai.

KYUN. Agar humne yeh branch ek baar pehle dekha hai aur uska target record kiya hai, toh agle baar hum ise Fetch stage mein lookup kar sakte hain — Decode ka intezaar nahi. Yahi trick hai: ek computation (slow, Decode mein) ko ek memory lookup (fast, Fetch mein) se replace karo.

PICTURE. Ek table. Hum PC ko do coloured slices mein split karte hain: low bits row (index) choose karti hain, high bits stored tag se check hoti hain. Agar tag match kare, toh stored target instantly serve ho jaata hai.

$\text{index}=\text{PC}[n:m],\text{hit}=(\text{BTB.tag}==\text{PC}[\text{upper}]),{\text{PC}}_{\text{next}}=\text{BTB.target}$

• $\text{PC}[n:m]$ — PC ke middle bits; itne chhote ki jaldi row name kar sakein.
• $\text{tag}$ — high bits; identity ka proof taaki do branches confuse na hon.
• $==$ — "kya yeh bit-strings identical hain?"
• $\text{BTB.target}$ — remembered destination, same cycle mein serve hota hai.

Step 6 — BTB ke saath: penalty zero ho jaati hai

KYA. Taken branch ko dobara replay karo, ab BTB hit aur sahi "taken" prediction ke saath. Cycle 0 mein hum branch fetch karte hain aur BTB hume target parallel mein de deta hai. Toh cycle 1 mein already target fetch ho jaata hai — koi galat PC+4 nahi, kuch flush nahi.

KYUN. Seedha Step 4 se compare karo. Wasted slots gayab ho jaate hain kyunki target jaldi aa gaya. Yahi difference hai, yahi saving hai.

PICTURE. Same pipeline jaise Step 4 mein, lekin crossed-out slot gone hai; target cycle 1 mein flow karta hai. Dono pictures apne dimag mein side by side rakhkho.

${\text{Penalty}}_{\text{with BTB}}=0(\text{if BTB hits and prediction correct})$

$\Delta ={\text{Penalty}}_{\text{no BTB}}-{\text{Penalty}}_{\text{with BTB}}=(1\text{–}2)-0=1\text{–}2\text{cycles saved}$

• $\Delta$ — cycles rescue kiye gaye har correctly-predicted taken branch par.

Step 7 — Edge case: cold miss (pehli baar is branch ko dekh rahe hain)

KYA. Bilkul pehli baar jab branch run hoti hai, BTB ne kabhi ise record nahi kiya. Lookup miss karta hai. Toh CPU assume karta hai "branch nahi, PC+4 use karo," seedha aage fetch karta hai, aur sirf Decode mein sach pata chalta hai — poori penalty, phir BTB update hoti hai agli baar ke liye.

KYUN. Jo kabhi dekha hi nahi, use yaad nahi kar sakte. Yeh case exist karna hi chahiye; ise ignore karna jhooth hoga. Khasiyat yeh hai ki miss default karta hai "seedha chalo," jo instructions ki badi majority ke liye free hai jo branches nahi hain (parent mein Example 2).

PICTURE. Do lanes. Top lane: ek real branch miss karti hai → galat fetch → flush → BTB write ho jaata hai (magenta write-arrow). Bottom lane: ek ordinary add miss karti hai → PC+4 sahi tha → zero cost.

$P(\text{first visit}):\text{penalty}=1\text{–}2\text{ cycles},\text{then }\text{BTB}[\text{index}]\leftarrow \{\text{tag},\text{target}\}$

• $\leftarrow$ — "store karo"; CPU abhi-compute-kiya-hua target reuse ke liye likhta hai.

Step 8 — Edge case: aliasing (do branches ek hi row ke liye ladte hain)

KYA. BTB mein limited rows hain, jo sirf low PC bits se choose hoti hain. Do alag branches jinke low bits match karte hain woh same row mein land karti hain. Doosri wali pehli ko overwrite kar deti hai. Jab pehli wapas aati hai, row mein koi aur hai — tag check fail → miss → phir penalty.

KYUN. Yeh dikhata hai ki tag decoration nahi hai: yeh correctness guarantee karta hai (hum kabhi galat target par jump nahi karte), jabki ek performance loss accept karta hai. Har real BTB is trade-off ke saath zinda rehta hai.

PICTURE. Do branches 0x1080 aur 0x1880 dono row 0x20 par index karti hain. Row ka content overwrite hote dekho (violet), phir re-entry par tag mismatch (red X).

$\text{index}(0x1080)=\text{index}(0x1880)=0x20\Rightarrow \text{collision};\text{tag}(0x1880)\ne \text{tag}(0x1080)\Rightarrow \text{miss}$

Ek-picture summary

Poori kahani yeh hai: jawab Decode mein paida hota hai, lekin Fetch mein chahiye — BTB ise yaad rakhta hai taaki woh jaldi aa jaaye. Yeh aakhri figure no-BTB timeline ko with-BTB timeline ke upar rakhta hai aur rescue kiye gaye cycles ko bright orange mein mark karta hai.

Prerequisites aur neighbours: Pipeline Hazards · Instruction Cache (I-Cache) · Cache Organization · Speculative Execution · Return Address Stack (RAS) · Branch Delay Slots · parent Branch target buffer (BTB).