Branch target buffer (BTB) — Hinglish notes

5.3.9 · Hardware › Advanced Microarchitecture

Overview

Branch Target Buffer (BTB) ek specialized cache hai jo recently execute hue branch instructions ke predicted target addresses store karta hai. Yeh branch predictors ke saath milkar kaam karta hai taaki branch instruction ko decode karne se pehle uska target predict kiya ja sake — iska matlab hai taken branches ke liye same-cycle prediction possible ho jaati hai.

Yeh kyun important hai: BTB ke bina, agar hum predict bhi kar lein ki branch liya jayega, tab bhi humein decode stage tak wait karna padta hai yeh jaanne ke liye ki kahan jump karna hai. Isse 1-2 cycle ki penalty aati hai. BTB humein predicted target se immediately fetch karne deta hai.

Core Intuition

BTB Kya Store Karta Hai

Yeh structure kyun?

Tag matching ensure karta hai ki hume sahi branch mili hai (koi alias nahi)
Target address key payload hai — "kahan jump karna hai"
Metadata branch predictor ke saath integration mein help karta hai (kuch architectures inhe combine karte hain)

BTB Kya Store NAHI Karta

BTB yeh store NAHI karta ki branch liya jayega ya nahi — yeh branch predictor ka kaam hai. BTB sirf yeh jawaab deta hai: "Agar taken ho, toh hum kahaan jayenge?"

BTB Operation Kaise Kaam Karta Hai

Fetch Stage Integration

Decision Tree

PC fetch stage pe aata hai
    ↓
BTB lookup (I-cache ke parallel mein)
    ↓
    ├─ BTB Miss → Default next PC use karo (PC+4)
    │             (Branch nahi hai, ya pehle kabhi dekha nahi)
    │
    └─ BTB Hit → Target address mil gayi
                ↓
                 Branch Predictor: Taken?
                    ├─ Predicted NOT taken → PC+4
                    └─ Predicted TAKEN → BTB target use karo

Critical insight: BTB lookup aur branch prediction parallel mein hote hain, same cycle mein. Processor decode ka wait nahi karta.

Derivation: BTB Branch Penalty Kyun Reduce Karta Hai

Chalo first principles se cycle savings derive karte hain.

Quantitatively yeh kyun matter karta hai: Agar 20% instructions branches hain, aur 60% branches taken hain:

BTB ke bina: $0.20 \times 0.60 \times 2 = 0.24$ cycles/instruction lost
BTB ke saath (95% accuracy): $0.20 \times 0.60 \times 0.05 \times 5 = 0.03$ cycles/instruction lost
IPC improvement: ~24% faster execution

Worked Examples

Worked example Example 1: Conditional Branch Pe BTB Hit

Code:

0x1000: cmp r1, r2
0x1004: beq 0x2000    ; Branch if equal
0x1008: add r3, r4, r5
...
0x2000: mul r6, r7, r8  ; Target

Pehli execution (BTB miss):

PC=0x1004: beq fetch karo, BTB miss
PC=0x1008: add fetch karo (default PC+4)
Decode stage: beq discover karo, target 0x2000 compute karo
Pipeline flush karo, 0x2000 se refetch karo
BTB update karo: Store karo PC=0x1004 → Target=0x2000

Doosri execution (BTB hit):

PC=0x1004: beq fetch karo, BTB hit (tag match karta hai)
Branch predictor: "Taken" (history se)
Same cycle: BTB target use karo → PC=0x2000
Next cycle: 0x2000 se fetch karo (koi flush nahi!) Har step kyun?

Pehli baar: Koi cached information nahi, decode karna padta hai
Update: Computed target store karo reuse ke liye
Doosri baar: BTB target decode se pehle provide karta hai, penalty avoid hoti hai

Worked example Example 2: BTB Miss vs. Not-a-Branch

Scenario A — Instruction ek branch hai:

0x3000: jmp 0x4000  ; Pehli baar dekh rahe hain

BTB miss → 0x3004 se fetch karo (galat!)
Decode jump discover karta hai → Flush karo, 0x4000 se fetch karo
Penalty: 2-3 cycles
Agली baar ke liye BTB update karo

Scenario B — Instruction branch NAHI hai:

0x3000: add r1, r2, r3  ; Regular instruction

BTB miss → 0x3004 se fetch karo (sahi!)
Koi penalty nahi Difference kyun?
BTB miss "not a branch" assume karta hai → sequentially continue karta hai
Agar galat ho, decode correct karta hai (penalty ke saath)
Agar sahi ho (zyaadatar instructions branches nahi hote), koi nuksaan nahi
Design philosophy: Common case ke liye optimize karo (non-branches)

Worked example Example 3: BTB Aliasing

Setup: BTB mein 64 entries hain, PC[7:2] se indexed

0x1080: beq target_A  ; Index = 0b1000 = 0x20
0x1880: beq target_B  ; Index = 0b1000 = 0x20 (same!)

Kya hota hai:

0x1080 execute karo → BTB[0x20] = {tag: 0x1080, target: target_A}
0x1880 execute karo → BTB[0x20] = {tag: 0x1880, target: target_B} (overwrite!)
0x1080 dobara execute karo:
- Index 0x20 → Entry mili
- Tag comparison: 0x1880 ≠ 0x1080 → Miss!
- Pehli encounter ki tarah treat karo → 2-cycle penalty Yeh kyun hota hai:

Limited BTB size ka matlab collisions hain
Tag check galat target rok leta hai (correctness preserved rahti hai)
Lekin speed benefit chali jaati hai (performance degrade hoti hai)
Mitigation: Bade BTBs, better hash functions, set-associative BTBs

Common Mistakes

Integration with Other Components

BTB + Branch Predictor Cooperation

Formula Combined Prediction Decision

if (BTB_hit AND predictor_says_taken):
    next_PC = BTB.target
elif (BTB_hit AND predictor_says_not_taken):
    next_PC = PC + 4
else:  // BTB miss
    next_PC = PC + 4  // Assume not a branch or not taken

Modern optimization: Kuch designs BTB entries ke andar simple predictors embed karte hain (jaise har entry mein 2-bit counter) taaki alag lookup avoid ho sake.

Return Address Stack (RAS) vs. BTB

Function calls/returns special hote hain:

Call: Target instruction mein hota hai (BTB bahut acha kaam karta hai)
Return: Target har call ke saath change hota hai (BTB constantly alias karta)

Solution: Returns ke liye dedicated Return Address Stack (RAS), baaki branches ke liye BTB. Kai designs ret instructions detect karte hain aur BTB ki jagah RAS query karte hain.

Advanced: Set-Associative BTB

Active Recall Practice

Recall Feynman Technique: Ek 12-saal ke bacche ko explain karo

Socho tum ek video game khel rahe ho jahan tum baar baar alag levels pe jump karte ho. Tumhara character automatically aage bhaagta hai, aur jab tum "jump portal" pe padte ho, tum naye level pe teleport ho jaate ho.

Problem yeh hai: Tumhara character itni tezi se bhaagta hai ki jab tak tumhara dimaag portal dekhe aur decide kare kahan jump karna hai, tab tak tum aage nikal chuke hote ho! Tumhe wapas jaana padta hai aur dobara try karna padta hai (slow!).

BTB ek cheat sheet ki tarah hai jo tum khelate waqt banate ho: "Red portal → Level 5, Blue portal → Level 12." Ab jab tum portal ke paas aate ho, tum immediately jump kar sakte ho kyunki tum pehle se jaante ho kahan jaata hai. Sign padhne ke liye slow hone ki zaroorat nahi!

Kabhi kabhi tumhari cheat sheet galat hoti hai (portal change ho gayi, ya tumne galat level likh diya), aur tum galat jagah jump kar jaate ho. Phir tumhe wapas jaana padta hai, notes fix karne padte hain, aur dobara try karna padta hai. Lekin zyaadatar baar tumhari cheat sheet sahi hoti hai, aur tum game mein super fast zoom karte ho!

Connections Branch Prediction Schemes: BTB "where" provide karta hai, predictors "whether" provide karte hain

Pipeline Hazards: BTB control hazards ko mitigate karta hai
Instruction Cache (I-Cache): BTB lookup I-cache access ke parallel hota hai
Return Address Stack (RAS): Function returns ke liye specialized BTB
Speculative Execution: BTB branch targets pe aggressive speculation enable karta hai
Cache Organization: BTB similar set-associative structures use karta hai
Branch Delay Slots: BTB ka purana alternative (delay software ko expose karo)

#flashcards/hardware

Branch Target Buffer (BTB) kya store karta hai? :: Recently execute hue branch instructions ke predicted target addresses (NOT ki branch taken hogi ya nahi — yeh predictor ka kaam hai).

Hum decode stage tak branch targets ke liye wait kyun nahi kar sakte?

Decode fetch ke 1-2 cycles baad hota hai. Wait karne se har taken branch pe guaranteed penalty aati hai, chahe perfectly predicted ho. BTB yeh wait eliminate karta hai.

BTB ko kaise index aur access kiya jaata hai?

PC ke lower bits se indexed kiya jaata hai (jaise bits [9:2] 256 entries ke liye). Sahi branch verify karne ke liye upper PC bits se tag compare hota hai. Hit pe target address return hota hai.

BTB miss pe kya hota hai?

Processor assume karta hai ki yeh branch nahi hai aur PC+4 (sequential) fetch karta hai. Agar yeh branch nikle, toh decode ke baad pipeline flush hota hai aur BTB update hota hai.

BTB aliasing kya hai aur kyun hoti hai?

Jab do alag branches ek hi BTB index pe map ho jaayein. Hoti hai kyunki BTB ki limited size hoti hai aur indexing ke liye sirf kuch PC bits use hote hain. Tag comparison aliasing detect karta hai (miss cause karta hai), lekin performance degrade hoti hai.

BTB hit + branch predictor "not taken" kehta hai → kya hota hai?

PC+4 se fetch karo (sequential). BTB target ignore hota hai. Target use karne ke liye dono conditions true honi chahiye: BTB hit AND predicted taken.

BTB branch penalty ko 2 cycles se 0 kyun reduce karta hai?

BTB fetch stage mein target address provide karta hai (decode se pehle), jisse branch predicted taken hone par immediately target se fetch ho sake. Koi decode wait nahi chahiye.

Function returns ke liye BTBs achhe se kaam kyun nahi karte?

Returns ke variable targets hote hain (call site pe depend karta hai). Alag calls alag return addresses push karti hain, jisse massive aliasing hoti hai. Dedicated Return Address Stack (RAS) use karo.

2-way set-associative BTB kya hota hai?

Har BTB index mein 1 ki jagah 2 entries hoti hain. Same index wale 2 alag branches coexist kar sakte hain. Aliasing reduce hoti hai, 2 parallel tag comparisons ki cost pe.

Modern processors mein typical BTB size?

L1 BTB ke liye 512-2048 entries (1-cycle access). Kuch ke paas bada L2 BTB bhi hota hai (4K-8K entries, 2+ cycles). Hit rate aur access latency ke beech trade-off.