Branch target buffer (BTB): Worked examples — Hinglish deep dive

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

Yeh page ek drill hai. Parent note mein explain kiya gaya tha ki BTB kya hai; yahan hum har tarah ki situation ko ek BTB pe throw karte hain aur haath se solve karte hain. Shuru karne se pehle, ek reminder plain words mein taaki baad mein kuch bhi surprise na ho.

Definition Teenon words jo hum baar baar use karenge

PC (program counter) :: us instruction ka address jise hum fetch karne waale hain. Isse ek bookmark ki tarah socho jo code ki ek line pe point kar raha hai.
Fetch :: PC pe baithe instruction ko grab karna. Yeh pehle hota hai jab hum samjhein ki instruction kya hai.
Decode :: instruction ko padhna taaki pata chale woh kya karta hai. Yahan pehli baar ek branch reveal karta hai ki woh ek branch hai — aur yeh fetch ke 1–2 cycles baad hota hai. Yahi gap hi BTB ke exist karne ki poori wajah hai.
BTB hit :: humne current PC ko BTB mein lookup kiya aur ek stored entry mili jiska tag match karta hai. "Maine yeh branch pehle dekha hai aur mujhe yaad hai yeh kahan jump hua tha."
BTB miss :: koi matching entry nahi mili. "Kabhi nahi dekha, ya evict ho gaya." Default action: maan lo yeh branch nahi hai aur $PC + 4$ pe chalo.

Definition Index aur tag — ek PC ko kaise split karte hain

BTB ek choti si cache hai, isliye woh har PC ko bits ke do pieces mein tod deta hai. Maano BTB mein $64$ entries hain aur instructions $4$ bytes wide hain (toh kisi bhi PC ke lowest $2$ bits hamesha $0$ hote hain).

Index batata hai ki kaunsa slot check karna hai. $64$ slots ke saath humein $lo g_{2} 64 = 6$ index bits chahiye, jo 2 alignment bits ke thoda upar li jaati hain: PC ke bits [7:2].
Tag PC ke index se upar wale baaki bits hai — yahan bits [31:8], yaani $32 - 8 = 24$ tag bits. Yeh slot ke andar store hota hai taaki baad mein hum confirm kar sakein "haan, yeh slot sach mein meri branch ka hai, kisi doosre ka nahi jo usi slot mein land hua."

Ek line mein: $PC = [tag ∣ index ∣ 2 alignment bits]$ . Ek hit ke liye dono zaruri hain — slot occupied ho aur uska stored tag current PC ke tag ke barabar ho. Hum is split ko Example 5 mein concretely use karte hain.

Hum prerequisite ideas pe bhi depend karte hain: Pipeline Hazards (kyun ek galat PC cycles cost karta hai), Instruction Cache (I-Cache) (BTB ke saath parallel mein fetch hota hai), Return Address Stack (RAS) aur Speculative Execution (jinhein BTB feed karta hai), aur Cache Organization (kyun aliasing hoti hai). Hinglish version: 5.3.09 Branch target buffer (BTB) (Hinglish).

Scenario matrix

BTB ek choti si yes/where machine hai. Sirf kuch dimensions hi outcome decide karte hain, isliye hum har case class enumerate kar sakte hain. Har row ek cell hai jise humein kam se kam ek worked example se cover karna hai.

Cell	Kya yeh ek branch hai?	BTB mein hai? (hit/miss)	Predictor kya kehta hai	Prediction sahi hai?	Outcome jo humein dikhana hai
A	haan	miss (cold, pehli baar)	—	—	full penalty, phir BTB update
B	haan	hit	taken	sahi	0-cycle, happy path
C	haan	hit	not taken	sahi	$PC + 4$ pe fall through, 0 penalty
D	haan	hit	taken	galat (branch not taken)	mispredict flush
E	haan	hit, galat tag (aliasing)	—	—	forced miss → penalty
F	nahi (plain add)	miss	—	—	$PC + 4$ sahi, koi nuksaan nahi
G	haan, indirect (target badalta hai)	hit but stale target	taken	target galat	sahi direction, galat address
H	zero/degenerate: branch to self ( $PC + 0$ ) / empty BTB	—	—	—	limiting behaviour
W	real-world word problem	mix	mix	mix	average penalty compute karo
X	exam twist	hit	taken	sahi lekin BTB 1 cycle late	"bubble" even on a hit

Aath lettered cells logic cases hain; W throughput problem hai; X gotcha hai. Neeche ke examples inhe sab cover karte hain.

Example 1 — Cell A: cold miss, branch ki pehli baar sighting

Worked example Ek branch jise abhi tak kisine nahi dekha

0x1004: beq 0x2000    ; taken this time
0x1008: add r3,r4,r5
0x2000: mul r6,r7,r8  ; target

BTB empty hai. Pehli baar kya hota hai trace karo.

Forecast: aage padhne se pehle cycles mein penalty guess karo. (Hint: machine ko abhi pata nahi ki beq ek branch hai.)

Cycle 0 — PC = 0x1004, fetch beq. BTB lookup parallel mein chalta hai → miss.
- Yeh step kyun? Miss pe BTB ka default answer hai "branch nahi hai," toh woh fetch ko sequentially jaari rehne deta hai.
Cycle 1 — PC = 0x1008, fetch add ( $PC + 4$ guess). Saath hi beq decode pe pahunchti hai aur reveal karti hai: branch, target 0x2000.
- Yeh step kyun? Decode woh sabse pehla moment hai jab hardware ek unseen branch ka target compute kar sakta hai.
Cycle 1 (end) — humne jo add fetch ki woh wrong path pe thi. Use flush karo.
- Yeh step kyun? Humne speculatively $PC + 4$ pe fetch kiya tha; kyunki branch taken hai, woh kaam bekar hai — ek control hazard.
Cycle 2 — 0x2000 se fetch karo. BTB likho: entry 0x1004 → 0x2000 ke liye.
- Yeh step kyun? Ab target store karna agli baar 0-cycle jump kharidta hai.

Penalty = 2 cycles (step 2 mein wasted fetch + redirect). Timeline dekho.

Figure mein kya dekhna hai: isse cycle ke hisaab se left-to-right padho. Top row mein blue boxes useful fetches hain; cycle 1 pe orange box woh add hai jo humne galat guess pe fetch ki; red arrow dikhata hai ki woh orange box flush ho rahi hai. Blue beq fetch (cycle 0) aur green target fetch (cycle 2) ke beech ka gap exactly woh 2-cycle hole hai jo miss ne pipeline mein toda.

Verify: branch fetch karne se leke sahi target fetch karne tak cycles = cycle 2 − cycle 0 = 2. Ek same-cycle machine cycle 0 mein hi redirect kar leti, toh delta = 2 cycles. ✓ (VERIFY mein check kiya gaya)

Example 2 — Cell B: happy path (0-cycle taken branch)

Worked example Doosri baar — BTB hit, predicted taken, sahi

Wahi beq 0x2000, ab BTB mein already hai, aur predictor ki history kehti hai taken.

Forecast: kitne stall cycles? Example 1 se compare karo.

Cycle 0 — PC = 0x1004, fetch beq. BTB lookup → hit, tag match karta hai, target 0x2000 isi cycle return hota hai.
- Yeh step kyun? BTB read fetch cycle ke andar hi khatam ho jaati hai (yeh ek choti si cache hai, Instruction Cache (I-Cache) ke parallel mein read hoti hai).
Cycle 0 — predictor (ek alag 2-bit counter, Speculative Execution) kehta hai taken. Toh Next PC ← 0x2000, 0x1008 nahi.
- Yeh step kyun? BTB kahan supply karta hai, predictor whether supply karta hai. Dono answers decode se pehle aa jaate hain.
Cycle 1 — 0x2000 fetch karo. Koi add kabhi fetch nahi hua; kuch flush nahi karna.
- Yeh step kyun? Kyunki redirect cycle 0 mein hi hua, agla fetch already sahi hai.

Penalty = 0 cycles. Yahi BTB ka poora payoff hai.

Verify: cycle(correct target fetched) − cycle(branch fetched) = 1 − 0 = 1, jo normal pipeline spacing hai (ek fetch per cycle), yaani koi extra bubble nahi. Example 1 se savings = 2 − 0 = 2 cycles. ✓

Example 3 — Cell C: hit lekin predictor kehta hai not taken

Worked example BTB ke paas target hai, lekin hum sahi se fall through karte hain

0x1004: beq 0x2000 BTB mein hai (target pata hai). Is baar real data mein r1 ≠ r2 hai, aur predictor ne seekha hai "zyaadatar not taken."

Forecast: kya stored target use hoga?

Cycle 0 — beq fetch karo, BTB hit, target 0x2000 available.
Cycle 0 — predictor kehta hai not taken. Next PC ← 0x1008 ( $PC + 4$ ). BTB target ignore kiya jaata hai.
- Yeh step kyun? BTB hit ka matlab sirf yeh hai "agar taken, toh yahaan jao." Predictor usse gate karta hai. GPS route jaanta hai; driver ne turn na lene ka faisla kiya.
Cycle 1 — 0x1008 fetch karo. Sahi, koi flush nahi.

Penalty = 0 cycles, aur baad mein decode/execute pe direction confirm ho jaata hai.

Verify: use kiya gaya next-PC $0 x 1004 + 4 = 0 x 1008$ hai, BTB target 0x2000 nahi. Toh next-PC ≠ target. ✓

Example 4 — Cell D: hit, predicted taken, lekin branch not taken hai

Worked example Galat direction — ek asli misprediction

Wahi setup Example 2 jaisi (predictor taken kehta hai) lekin actual data branch ko fall through kara deta hai.

Forecast: galti kahan discover hogi, aur kitne cycles waste honge?

Pehle pipeline geometry fix karo taaki timing unambiguous ho. Maano front-end mein exactly teen stages hain jin se branch order mein guzarta hai: fetch (stage 1), decode (stage 2), execute (stage 3). Branch ki direction (taken ya not) sirf tab pata chalta hai jab woh execute hota hai. Toh sach pata chalne se pehle hum jitne speculative fetches karte hain woh fetch aur execute ke beech ke stages ki sankhya ke barabar hai.

Cycle 0 — BTB hit, predictor "taken" → Next PC ← 0x2000 speculatively.
Cycle 1 — 0x2000 pe instruction speculatively fetch karo. Yeh pehla wrong-path fetch hai.
- Yeh step kyun? Speculative Execution predicted path pe aage badhta rehta hai; woh abhi nahi jaanta ki guess galat hai.
Cycle 2 — beq execute pe pahunchta hai, r1,r2 compare karta hai, not equal milta hai → branch not taken. 0x2000 se fetch kiya hua sab galat tha.
- Yeh step kyun? Direction sirf execute (stage 3) pe verify hoti hai; predictor ek guess tha.
Cycle 2 (end) — wrong-path fetches flush karo, 0x1008 pe fetch restart karo.

Penalty = fetch aur execute ke beech stages ki sankhya − 0 useful = 2 cycles. Concretely: cycle 0 pe branch fetch se corrected fetch tak, pipeline cycles 1 aur 2 mein kiya hua kaam discard karta hai → 2 cycles squashed front-end work.

Note: yahan BTB ki galti nahi thi — uska stored target 0x2000 target ke roop mein sahi tha. Predictor ne galat direction guess ki. BTB sahi, predictor galat.

Verify: misprediction penalty = (execute stage index) − (fetch stage index) = 3 − 1 = 2 cycles front-end work discarded. ✓

Example 5 — Cell E: aliasing (sahi index, galat tag)

Worked example Do branches ek hi BTB slot mein collide karte hain

BTB mein 64 entries hain, toh (upar diye index/tag definition se) index hai PC bits [7:2] aur tag hai bits [31:8]. Do branches:

0x1080: beq target_A
0x1880: beq target_B

Forecast: kya 0x1880 ke baad 0x1080 ko re-execute karna hit hoga ya miss?

Har ek ka index compute karo. Index hai "64 slots mein se kaunsa," toh humein PC bits [7:2] chahiye. "Bits [7:2] grab karo" ke liye ek saaf arithmetic recipe hai:
- Pehle address ko $4$ se integer-divide karke low 2 alignment bits drop karo. "Integer division" matlab divide karo aur remainder phenko — likha jaata hai $⌊ x /4 ⌋$ , jahan notation $⌊ \cdot ⌋$ (floor kehlaata hai) ka matlab hai "nearest whole number pe round down karo." Yeh is liye karte hain kyunki woh 2 bits hamesha $0$ hoti hain aur koi information nahi rakhtiN.
- Phir result ke sirf lowest $6$ bits rakho, kyunki $2^{6} = 64$ hai aur sirf $64$ slots hain. "Lowest 6 bits rakho" exactly hai " $64$ se divide karne ke baad bachha hua remainder," likha jaata hai $(\dots) mod 64$ . Symbol $mod$ (modulo) ka matlab hai "bacha hua remainder" — jaise $70 mod 64 = 6$ . Hum isse isliye use karte hain kyunki slot number $63$ se waapas $0$ pe wrap around karna chahiye. $index = ⌊ \frac{PC}{4} ⌋ mod 64$
- 0x1080 ke liye: $⌊ 0x1080 /4 ⌋ = 0x420 = 1056$ , aur $1056 mod 64 = 32$ .
- 0x1880 ke liye: $⌊ 0x1880 /4 ⌋ = 0x620 = 1568$ , aur $1568 mod 64 = 32$ .
- Yeh step kyun? Same index ⇒ same physical slot ⇒ do branches ek entry ke liye ladte hain.
0x1080 run karo: slot 32 ← {tag = bits[31:8] of 0x1080, target A}.
0x1880 run karo: slot 32 ← {tag of 0x1880, target B}. A ko overwrite karta hai (uska tag alag hai, lekin slot same hai).
0x1080 dobara run karo: index 32 → entry present hai, lekin stored tag(0x1880) ≠ tag(0x1080) → miss.
- Yeh step kyun? Tag check correctness protect karta hai (hum kabhi B ke target pe A ke liye jump nahi karte) speed ka hit lose karke.

Result: ek forced miss → waapas Example 1 ki 2-cycle cold-miss penalty. Mitigation: bada BTB ya set-associativity.

Figure mein kya dekhna hai: dono PCs (blue 0x1080, orange 0x1880) ke arrows ek hi box — BTB slot 32 — mein funnel hote hain — yahi poora point hai: index unhe ek saath collapse kar deta hai. Box survivor dikhata hai (tag=0x1880, target B). Red arrow baad mein 0x1080 ka re-run hai jo us box se bounce kar raha hai kyunki tags match nahi karte: correctness bachi, speed gayi.

Verify: dono indices 32 ke barabar hain, aur tags alag hain ⇒ conflict. ✓

Example 6 — Cell F: bilkul branch nahi (common case jeet jaata hai)

Worked example Plain arithmetic, BTB miss, koi nuksaan nahi

0x3000: add r1,r2,r3   ; not a branch, never in BTB

Forecast: kya BTB miss kabhi non-branch ko hurt karta hai?

Cycle 0 — add fetch karo, BTB miss. Default next PC ← 0x3000 + 4 = 0x3004.
- Yeh step kyun? Miss ka matlab "sequential maano," jo non-branches ke liye bilkul sahi hai.
Cycle 1 — 0x3004, sachchi agali instruction, fetch karo.
Decode confirm karta hai add branch nahi hai. Koi correction zaruri nahi.

Penalty = 0. Zyaadatar instructions branches nahi hote, isliye miss default yahan free hone ke liye tuned hai.

Verify: use kiya gaya next-PC 0x3004 natural sequential PC ke barabar hai. Match ⇒ 0 penalty. ✓

Example 7 — Cell G: indirect branch with stale target

Worked example Sahi direction, galat address (indirect trap)

Ek indirect branch runtime par ek register se apna target compute karta hai:

0x5000: jmp [r9]     ; last time r9 = 0x6000, this time r9 = 0x7000

BTB ne pichhli baar se 0x5000 → 0x6000 store kiya tha. r9 ab 0x7000 rakhta hai.

Forecast: BTB hit karta hai aur predictor kehta hai "hamesha taken." Kya fetch kiya hua target sahi hai?

Cycle 0 — BTB hit, target 0x6000 return hua; jump unconditional hai toh direction trivially "taken" hai.
Cycle 1.. — 0x6000 se speculatively fetch karo.
Execute — real target [r9] = 0x7000 compute hota hai. 0x7000 ≠ 0x6000 → target misprediction.
- Yeh step kyun? BTB ek past target cache karta hai; ek indirect branch har baar alag choose kar sakta hai. Direction sahi thi, address stale tha.
Flush karo, 0x7000 refetch karo, aur BTB 0x5000 → 0x7000 update karo.

Penalty = redirect depth (≈ 2 cycles) har baar jab target badalta hai. Isliye real cores BTB ke upar indirect-target predictors add karte hain; ek plain BTB yahan thrash karta hai. (Function returns is se bachte hain kyunki woh BTB ki jagah Return Address Stack (RAS) use karte hain.)

Verify: stored target 0x6000 ≠ actual 0x7000 ⇒ mispredict. ✓

Example 8 — Cell H: degenerate / limiting inputs

Worked example Branch apne aap mein, aur empty BTB

Do edge cases.

(H1) Self-branch: 0x8000: jmp 0x8000 (ek infinite loop / spin).

Pehla run: cold miss, decode target 0x8000 dhundh leta hai, BTB ← 0x8000 → 0x8000.
Har baad ka run: BTB hit, Next PC ← 0x8000 usi cycle mein ⇒ loop 1 fetch/cycle ke saath 0 penalty ke saath spin karta hai.
- Yeh kyun matter karta hai? "Target" branch PC ke barabar hai — ek valid, non-pathological entry. Displacement = target − (PC+4) = 0x8000 − 0x8004 = −4, ek backward branch, exactly jaisa loops dikhte hain.

(H2) Empty / just-flushed BTB (cold start): har branch miss hai jab tak woh ek baar execute na ho. Toh kisi bhi program ki pehli pass apni saari branches pe cold-miss penalties bharti hai; steady state kaafi sasta hota hai. Yeh warm-up cost hai.

Verify: self-branch displacement = 0x8000 − 0x8004 = −4 (backward). Aur ek self-branch ka used next-PC apne PC ke barabar hota hai. ✓

Example 9 — Cell W: real-world throughput problem

Worked example Average cycles lost per instruction

Ek program: 20% instructions branches hain; 60% branches taken hain; BTB 90% branch fetches pe sahi target deliver karta hai (toh 10% miss/alias/mispredict); har failure 2 penalty cycles cost karta hai.

Forecast: compute karne se pehle cycles-per-instruction (CPI) penalty guess karo.

Instructions ka fraction jo taken branches hain: $0.20 \times 0.60 = 0.12$
- Kyun? Sirf taken branches ko BTB ke redirect ki zarurat hai; not-taken wale free mein fall through karte hain (Cell C).
Unme se woh fraction jo fail karte hain (miss/alias/mispredict): $0.10$ . $0.12 \times 0.10 = 0.012$
Penalty cycles se multiply karo: $CPI penalty = 0.012 \times 2 = 0.024 cycles/instruction$

No BTB ke saath compare karo (har taken branch 2-cycle decode wait bharti hai): $0.12 \times 1.0 \times 2 = 0.24 cycles/instruction .$

Verify: with-BTB penalty $= 0.024$ ; without $= 0.24$ ; BTB $0.24 - 0.024 = 0.216$ CPI remove karta hai, branch penalty ka 10× reduction. ✓

Example 10 — Cell X: exam twist (hit pe bhi ek bubble)

Worked example "0-cycle" tabhi sach hai jab BTB read time pe khatam ho

Kuch designs BTB ko read karne aur fetch ko ek hi cycle mein redirect karne mein capable nahi hote — BTB result ek cycle late aata hai (ek 2-cycle BTB access). Is example mein sab kuch ek correct, predicted-taken hit hai; ek hi villain BTB latency hai.

0x1004: beq 0x2000, BTB mein hai, predictor sahi se kehta hai taken.

Forecast: agar ek perfect prediction phir bhi fetch ko ek cycle mein turn nahi kar sakta, toh penalty kya hai?

Cycle 0 — 0x1004 pe beq fetch karo. BTB lookup shuru hota hai lekin uska answer is cycle ready nahi hai. Fetch redirect karne ke liye kuch nahi hone se, front-end default leta hai → Next PC ← 0x1008.
- Yeh step kyun? Ek 2-cycle BTB bilkul agale fetch ko influence nahi kar sakta; fetch ko kuch toh guess karna hai, aur default sequential hai.
Cycle 1 — 0x1008 fetch karo (wrong path). Saath hi BTB ka answer aata hai: target 0x2000, predicted taken.
- Yeh step kyun? Stored, sahi answer branch fetch ke exactly ek cycle baad aata hai — ek fetch bahut der se.
Cycle 1 (end) — 0x1008 fetch wrong path pe hai. Woh ek fetch flush karo, fetch ko 0x2000 pe redirect karo.
- Yeh step kyun? Prediction sahi thi, toh jaise hi late target appear hota hai hum course correct karte hain — lekin ek wasted fetch already ho chuka hai.
Cycle 2 — 0x2000, true target, fetch karo.

Penalty = 1 cycle — ek single "bubble," halanki prediction perfect thi. Cells compare karo: ek single-cycle BTB (Example 2) deta hai $latency - 1 = 1 - 1 = 0$ ; yeh two-cycle BTB deta hai $2 - 1 = 1$ . Exam ke liye moral: BTB latency, sirf accuracy nahi, best-case penalty set karta hai.

Verify: penalty = BTB-latency − 1 = 2 − 1 = 1 cycle; aur ek single-cycle BTB deta hai 1 − 1 = 0, jo Example 2 se match karta hai. ✓

Recall Quick self-test

Single-cycle BTB ke saath Cell B best-case penalty ::: 0 cycles Predictor "not taken" ke saath BTB hit kaun sa next PC use karta hai ::: $PC + 4$ (target ignore hota hai) Do branches ek BTB slot share karte hain lekin tag mein differ — hit ya miss ::: miss (aliasing) Indirect branch, sahi direction, stale target — kiska dosh ::: BTB ka cached target stale hai (indirect predictor chahiye) 20% branches, 60% taken, 10% failure, 2-cycle penalty ke saath, CPI cost ::: 0.024 cycles/instruction 2-cycle-latency BTB, perfectly correct hit — penalty ::: 1 cycle (latency − 1)