Exercises — Branch target buffer (BTB)

Answer: (b) — target address, yaani "kahan jump karna hai".

• (a) branch predictor's kaam hai (direction).
• (c) execute stage mein compute hota hai.
• (d) decode chahiye, aur yahi woh step hai jo BTB skip karwata hai. BTB sirf yeh batata hai: "Agar taken ho, toh kahan?"

Lookup fetch stage mein hota hai, current program counter (PC — us instruction ka address jo hum abhi fetch kar rahe hain) use karke. Yeh Instruction Cache (I-Cache) access ke parallel mein run karta hai. Dono ek hi PC se ek hi time pe indexed hote hain, isliye target decode se pehle aa jaata hai — koi waiting nahi.

• $256=2^8$, toh humein 8 index bits chahiye.
• Instructions 4 bytes = $2^2$ hain, toh aligned instructions ke liye PC bits $[1:0]$ hamesha $00$ hote hain — yeh branches ko distinguish karne ki koi information carry nahi karte. Hum inhe skip karte hain aur bits $[9:2]$ use karte hain.

Instructions ka fraction jo taken branches hain: $0.20\times 0.60=0.12$ Har 2 cycles bharta hai: $0.12\times 2=\boxed{0.24\text{ cycles/instruction lost}}$

Probability ki taken branch bachta hai = $h\times a=0.90\times 0.95=0.855$. Probability ki bharta hai = $1-0.855=0.145$. Saari instructions mein taken-branch fraction = $0.12$ (from 2.1). $\text{Lost}=0.12\times 0.145\times 2=\boxed{0.0348\text{ cycles/instruction}}$

$\frac{0.24-0.0348}{0.24}=\frac{0.2052}{0.24}=0.855=\boxed{85.5\%}$ Notice karo yeh exactly $h\times a$ ke barabar hai — escape probability. Yeh coincidence nahi hai: jo cheez badi hai woh yeh hai ki ab har taken branch $ha$ probability se bachta hai.

Index = PC$[7:2]$ = bits 7 down to 2.

• 0x1080 = ...0001 0000 1000 0000. Bits $[7:2]$ = 100000 = 0x20.
• 0x1880 = ...0001 1000 1000 0000. Bits $[7:2]$ = 100000 = 0x20. Same index → dono ek BTB slot share karte hain. Alternating execution:

1. 0x1080 slot 0x20 mein tag 0x1080 likhta hai.
2. 0x1880 use tag 0x1880 se overwrite karta hai.
3. Wapas 0x1080 pe: index slot 0x20 hit karta hai, lekin tag 0x1880 ≠ 0x1080 → miss, full penalty. Phir woh wapas overwrite karta hai. Har iteration mein dono branches miss karte hain: 100% miss rate jabki dono perfectly predictable hain. Correctness preserve hoti hai (tag check galat target refuse karta hai), lekin speed collapse ho jaati hai. Neeche figure dekho.

BTB ko 2-way set-associative banao: ab har index 2 entries hold karta hai (dekho Cache Organization). 0x1080 aur 0x1880 dono set 0x20 pe map karte hain lekin alag ways mein rehte hain, toh koi bhi doosre ko evict nahi karta. Result: warm-up ke baad dono har iteration hit karte hain — thrashing khatam, koi size increase nahi chahiye (halaanki sets ki same number ke liye total entries double ho jaati hain).

$\frac{1\times 3+999\times 0}{1000}=\frac{3}{1000}=\boxed{0.003\text{ cycles/execution}}$ Cold miss ek one-time cost hai jo bahut saare hits pe amortise ho jaati hai. Isliye BTBs loops mein shine karte hain: expensive learning ek baar hoti hai, phir hazaaron free reuses follow karte hain.

Plain BTB ek target per branch PC store karta hai. Lekin ek akela ret instruction wapas jaata hai jis bhi caller ne function invoke kiya — har baar ek alag address. BTB sirf last return address rakha hai, toh ek alag caller se next return mispredict karta hai. Fix: Return Address Stack (RAS) — ek small hardware stack. Har call apna return address push karta hai; har ret use pop karta hai. Kyunki calls/returns matched parentheses ki tarah nest hote hain, RAS sahi target deta hai chahe yeh har baar badle — kuch aisa jo single-target BTB entry nahi kar sakti.

Escape probability $=ha$. Har factor improve karne ka marginal gain:

• $h$ ko 0.99 se improve karna: at most $+0.01$ possible → escape $\le a\times 0.01=0.008$ rise karta hai.
• $a$ ko 0.80 se improve karna: room up to $+0.20$ → escape $h\times 0.20=0.198$ tak rise karta hai. $a$ bottleneck hai — yeh 1 se bahut door hai jabki $h$ almost saturate ho chuka hai. Predictor pe kharch karo. General rule: jis factor ki value 1 se sabse zyada door ho uspe invest karo, kyunki $ha$ apne weaker term se bound hota hai.

Delay slot branch latency ka ek cycle hide karta hai hamesha next sequential instruction run karke — useful work regardless of direction. Lekin agar branch target jaanne mein ek se zyada cycle lage (deep pipeline, decode + target calc = 2 cycles), toh ek single delay slot use cover nahi kar sakta. BTB target fetch cycle mein supply karta hai, remaining gap cover karta hai. Toh haan — BTB phir bhi help karta hai fixed-size delay slot se jo remaining penalty cover nahi ho paati usse remove karke.

(a) Taken-branch fraction $=0.25\times 0.70=0.175$. (b) Escape $=ha=0.92\times 0.90=0.828$; pay $=1-0.828=0.172$. (c) Added CPI $=0.175\times 0.172\times 4=0.1204$. (d) Final CPI $=1.0+0.1204=\boxed{1.1204}$.

Added CPI $=0.175\times (1-ha)\times 4=0.05$. $0.7\times (1-0.92a)=0.05⟹1-0.92a=\frac{0.05}{0.7}=0.0714\dots$ $0.92a=0.9286⟹a=\frac{0.9286}{0.92}=\boxed{1.0093}$ Kyunki $a>1$ impossible hai, yeh target $h=0.92$ ke saath unreachable hai. 0.05 tak pahunchne ke liye $h$ bhi badhana hoga (ya $P$ ghatana). Yahi mastery lesson hai: product $ha$ cap karta hai ki penalty kitni kam ho sakti hai, aur koi single knob apni 1 ki ceiling ke baad kisi over-ambitious target ko rescue nahi kar sakta.

(a) No BTB: added CPI $=0.175\times 1.0\times 4=0.70$. (b) With BTB (from 5.1c): added CPI $=0.1204$. Penalty CPI removed $=0.70-0.1204=0.5796$. Fraction removed $=0.5796/0.70=0.828=\boxed{82.8\%}$ — phir exactly $ha$, escape probability. BTB ka poora benefit usi ek product mein collapse ho jaata hai.