Branch prediction (static and dynamic): Exercises — Hinglish deep dive

5.3.7 · D4 · Hardware › Advanced Microarchitecture › Branch prediction (static and dynamic)

Shuru karne se pehle, ek number jo hum har jagah reuse karenge — mispredictions ka average cycles-per-instruction cost:

Level 1 — Recognition

Exercise 1.1

Har scheme ko uski defining property se match karo.

Predict Not-Taken (PNT)
Predict Taken (PT)
BTFNT
1-bit BHT
2-bit saturating counter

Options: (a) hamesha PC+4 fetch karta hai, (b) hamesha target fetch karta hai, (c) branch-target-vs-PC direction use karta hai, (d) har branch ka last outcome store karta hai, (e) apna guess badalne ke liye do consecutive mispredictions chahiye.

Recall Solution

1 → (a): PNT hamesha fall-through leta hai, yaani next sequential instruction PC+4. 2 → (b): PT hamesha target address leta hai. 3 → (c): BTFNT taken predict karta hai jab target peeche ho (backward = ek loop), warna not-taken. 4 → (d): 1-bit Branch History Table simply us branch ka last outcome yaad rakhta hai. 5 → (e): 2-bit counter mein hysteresis hota hai — ek galat guess sirf ise nudge karta hai, prediction badalne ke liye do chahiye.

Exercise 1.2

Ek branch ka target address 0x0040 hai aur branch instruction 0x00A0 par hai. BTFNT ke under, CPU taken predict karega ya not-taken?

Recall Solution

Target 0x0040, branch address 0x00A0 se chhota hai, toh jump backward hai. BTFNT rule: backward ⇒ Predict Taken. Yeh loop case hai — branch loop ke top par wapas jump karta hai.

Level 2 — Application

Exercise 2.1

Ek program mein 20% branches hain. Branches 8% time galat predict hote hain. Flush penalty 12 cycles hai. Average CPI calculate karo.

Recall Solution

Seedha master formula mein plug karo: $CPI = 1 + P_{branch} 0.20 \times P_{mispredict} 0.08 \times Penalty 12$ Left se right multiply karo: $0.20 \times 0.08 = 0.016$ , phir $0.016 \times 12 = 0.192$ . $CPI = 1 + 0.192 = 1.192$ Matlab: mispredictions ideal 1 CPI ke upar 19.2% overhead add karte hain.

Exercise 2.2

Same machine, lekin tum ek better predictor lagaate ho jo mispredict rate ko 8% se 3% kar deta hai. Naya CPI kya hai, aur total execution time kitne percentage drop hua?

Recall Solution

Naya CPI: $CPI_{new} = 1 + 0.20 \times 0.03 \times 12 = 1 + 0.072 = 1.072$ Execution time CPI ke proportional hai (same instruction count, same clock). Speed-up ratio: $\frac{CPI _{old}}{CPI _{new}} = \frac{1.192}{1.072} \approx 1.1119$ Time saved = $1 - \frac{1.072}{1.192} = 1 - 0.8993 = 0.1007$ , yaani runtime mein lagbhag 10.1% ki kami.

Exercise 2.3

Ek loop par 1-bit predictor trace karo jo pattern T, T, T, T, NT run karta hai ek baar (4 taken, phir exit). BHT entry 0 (Not-Taken) se start karti hai. Saare 5 events ke liye prediction, correct?, aur next state fill karo. Accuracy kya hai?

Recall Solution

Rule reminder: jo bit keh rahi hai woh predict karo; phir bit ko actual outcome par set karo.

Event	Actual	State before	Predict	Correct?	State after
1	T	0 (NT)	NT	❌	1 (T)
2	T	1 (T)	T	✅	1 (T)
3	T	1 (T)	T	✅	1 (T)
4	T	1 (T)	T	✅	1 (T)
5	NT	1 (T)	T	❌	0 (NT)

Correct = 5 mein se 3 ⇒ accuracy = 60%. Pehle (cold start) aur aakhri (exit) events par galat — yeh do boundaries hain.

Level 3 — Analysis

Exercise 3.1

2-bit saturating counter ko same pattern T, T, T, T, NT par trace karo (2.3 wala hi loop), 00 (Strongly Not-Taken) se start karo. Iska accuracy 2.3 ke 1-bit result se compare karo. Phir argue karo ki agar loop doosri baar enter ki jaaye to kya hota hai.

Recall Solution

Encoding: 00=SNT, 01=WNT, 10=WT, 11=ST. Taken predict karo agar counter $\geq$ 10. T par increment (cap 11), NT par decrement (floor 00).

Event	Actual	Counter before	Predict	Correct?	Counter after
1	T	00 (SNT)	NT	❌	01 (WNT)
2	T	01 (WNT)	NT	❌	10 (WT)
3	T	10 (WT)	T	✅	11 (ST)
4	T	11 (ST)	T	✅	11 (ST)
5	NT	11 (ST)	T	❌	10 (WT)

Correct = 5 mein se 2 ⇒ 40% is cold pass par — 1-bit ke 60% se zyada kharab! Reason: 2-bit counter ko taken predict karna shuru karne ke liye do taken events chahiye, toh ek extra warm-up event waste hota hai.

Doosra entry 10 (WT) se shuru hota hai, jo exit ke baad bacha tha:

Event	Actual	Before	Predict	Correct?	After
1	T	10 (WT)	T	✅	11
2	T	11 (ST)	T	✅	11
3	T	11 (ST)	T	✅	11
4	T	11 (ST)	T	✅	11
5	NT	11 (ST)	T	❌	10

Correct = 5 mein se 4 ⇒ 80%. Hysteresis ne ab loop "sikh liya" hai: sirf exit miss hota hai. Neeche state figure dekho.

Figure — Branch prediction (static and dynamic)

Exercise 3.2

Ek loop 100 taken iterations phir 1 not-taken exit run karta hai, aur poora loop kai baar enter hota hai. Ek warmed-up 2-bit counter use karke, 101-event pass mein kitne mispredictions hote hain, aur steady-state accuracy kya hai?

Recall Solution

Ek baar warm up hone ke baad, counter 100 taken iterations bhar 11 (ST) par baithe rehta hai — sab correct. Sirf ek exit NT mispredict hota hai (predicted T at 11), counter 10 par aa jaata hai. Re-entry par pehla taken event use wapas 11 push kar deta hai, toh cold-start penalty nahi agle passes par.

Mispredictions per pass = 1 (sirf exit). $Accuracy = \frac{100}{101} \approx 0.9901 = 99.0%$ Yeh classic "2-bit predictors lambe loops ke liye perfect hain" result hai: loop jitna lamba, utna zyada single exit miss amortise hota hai.

Level 4 — Synthesis

Exercise 4.1

Tumhe ek workload ke liye do predictors mein se choose karna hai jahan branches 25% instructions hain aur misprediction penalty 10 cycles hai.

Predictor A (2-bit bimodal): 6% mispredict rate, negligible extra area.
Predictor B (correlating, 2-level): 2.5% mispredict rate, lekin ek global-history lookup add karta hai jo base CPI ko 1.00 se 1.05 kar deta hai (second table access ke liye extra pipeline stage).

Kaun sa lower CPI deta hai?

Recall Solution

Predictor A: $CPI_{A} = 1.00 + 0.25 \times 0.06 \times 10 = 1.00 + 0.15 = 1.15$ Predictor B: base cost ab 1.05 hai, 1.00 nahi: $CPI_{B} = 1.05 + 0.25 \times 0.025 \times 10 = 1.05 + 0.0625 = 1.1125$ Compare karo: $1.1125 < 1.15$ . Predictor B jeetha hai apne zyada base cost ke baavjood, kyunki misprediction savings ( $0.15 \to 0.0625$ , yaani $0.0875$ ki kami) $0.05$ base penalty se zyada hain. Net advantage $= 1.15 - 1.1125 = 0.0375$ CPI.

Exercise 4.2

Same workload ke liye, Predictor B ka break-even mispredict rate $m$ dhundho — woh accuracy jis par B aur A tie karte hain. Is se upar, B apne extra base cost ke laayak nahi hai.

Recall Solution

Dono CPIs barabar set karo: $1.05 + 0.25 \times m \times 10 = 1.15$ $2.5 m = 1.15 - 1.05 = 0.10$ $m = \frac{0.10}{2.5} = 0.04 = 4%$ Toh B ko apna mispredict rate 4% se neeche rakhna hoga apne 0.05-CPI overhead ko justify karne ke liye. Exactly 4% par dono tie karte hain; diye gaye 2.5% par B aaram se aage hai.

Level 5 — Mastery

Exercise 5.1

Woh nested pattern consider karo jo correlating predictors ko motivate karta hai:

if (a > 0) {      // B1
    if (b > 0) {  // B2 — only runs when B1 taken
        ...
    }
}

1000 runs mein, a > 0 50% time true hota hai. Jab B1 taken hota hai (500 runs), b > 0 90% time true hota hai; baaki 500 runs mein B2 kabhi execute nahi hota. Ek bimodal (per-branch, no history) predictor B2 ke liye ek fixed bias choose karta hai. Ek correlating predictor B1 ke outcome par key kar sakta hai. B2 ke executed instances par dono ki best-case accuracy calculate karo, aur gap explain karo.

Recall Solution

B2 sirf unhi 500 runs par execute hota hai jab B1 taken tha. Unme se 90% baar yeh taken hota hai.

Bimodal on B2: yeh sirf 500 executed instances dekhta hai (B2 otherwise skip ho jaata hai, toh koi update nahi). Best fixed bias = Taken predict karo (majority). Executed instances par accuracy: $\frac{450}{500} = 0.90 = 90%$ Yahan bimodal B2 akele ke liye already theek karta hai, kyunki B2 ki apni history ek clean 90%-taken stream hai.

Jahan correlation actually kaam aata hai woh ek alag, aliasing-driven case hai. Maan lo B2 ka outcome perfectly B1 se determined ho: jab bhi B1 taken ⇒ B2 taken, jab (hypothetically) B1 not-taken lekin B2 phir bhi reach ho ⇒ B2 not-taken. Tab correlating predictor, B1 ke 1-bit global history par keyed, paata hai: $\frac{500}{500} = 1.00 = 100%$ jabki bimodal, do sub-streams ko ek counter mein blend karne par majboor hokar, majority mix par baith jaata hai. Gap = B1 aur B2 ke beech mutual information. Jab ek branch ka outcome recent branches se predictable ho, sirf ek history-indexed (correlating) predictor ise exploit kar sakta hai; ek per-address bimodal counter woh context throw kar deta hai.

Exercise 5.2

Design decision: ek 2-level predictor $h$ bits ka global history register use karta hai, $2^{h}$ counters ki table ko index karta hai, har ek 2 bits ka. (a) Storage ke kitne bits? (b) Agar $h$ ko 8 se 9 tak double karne se ek machine par mispredicts 3.0% se 2.7% tak aa jaaye jahan 25% branches hain aur 14-cycle penalty hai, to kya extra table CPI terms mein worth it hai? (Assume base CPI unchanged.)

Recall Solution

(a) Table mein $2^{h}$ entries hain, har ek 2 bits: storage $= 2 \times 2^{h} = 2^{h + 1}$ bits. $h = 8$ ke liye: $2^{9} = 512$ bits (64 bytes). $h = 9$ ke liye: $2^{10} = 1024$ bits (128 bytes).

(b) Mispredicts se CPI contribution $= P_{branch} \times m \times Penalty = 0.25 \times m \times 14 = 3.5 m$ .

$h = 8$ par: $3.5 \times 0.030 = 0.105$ added CPI.
$h = 9$ par: $3.5 \times 0.027 = 0.0945$ added CPI.

Savings $= 0.105 - 0.0945 = 0.0105$ CPI table double karne ke liye (64 → 128 bytes). Yeh "worth it" hai ya nahi yeh ek policy call hai, lekin marginal gain real hai aur storage mein sasta hai; classic diminishing-returns curve ka matlab hai ki agla doubling (h=9→10) aur bhi kam bachayega. Ise Cache Performance se relate karo — same "double the table, shrink the benefit" shape.

Common mistake L5 ka trap

Students assume karte hain ki correlating predictor hamesha bimodal se better hota hai, aur Exercise 5.1 mein bhi B2 ke liye bada win expect karte hain. Yeh sahi kyon lagta hai: parent note mein correlation ko bimodal ke baad "the upgrade" ki tarah introduce kiya gaya hai. Fix: correlation tabhi help karta hai jab branch ka outcome recent branches ke saath mutual information rakhe. Agar kisi branch ki apni local history already ek clean bias hai (jaise B2 ki isolated 90%-taken stream), ek bimodal counter use match karta hai — aur correlating predictor history-table aliasing ki wajah se worse bhi kar sakta hai (ek clean stream ko kai history contexts mein split karna, jahan se har ek ko warm up hone ke liye bahut kam samples milte hain). Sahi sawaal kabhi "kaun zyada fancy hai?" nahi hai, balki "kya yeh branch jo pehle hua usse correlate karta hai?"

Recall Quick self-check (cloze)

CPI penalty term mein multiply hone wale teen factors hain == $P_{branch}$ , $P_{mispredict}$ , aur Penalty. 2-bit counter mein hysteresis ek cold, short loop par accuracy cost karta hai lekin long, warm loop par jeetta hai. Correlating predictors bimodal ko tabhi beat karte hain jab branch recent branch history se correlate kare==.

1-bit predictor ek loop par kaunse do events hamesha miss karta hai?

Pehli iteration (cold start) aur exit (loop end).

Ek fancier predictor total CPI mein phir bhi kyon haar sakta hai?

Uska extra lookup har instruction ke liye base CPI badha sakta hai, jo mispredict savings se zyada ho sakta hai.