Branch prediction (static and dynamic): Worked examples

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

Yeh Branch Prediction (Static and Dynamic) ka worked-examples deep dive hai. Parent note ne machines sikhaye the — static rules, 1-bit table, 2-bit saturating counter, correlating predictors. Yahan hum un sabhi machines ko har us situation se guzarte hain jo unhe mil sakti hai aur hits haath se count karte hain.

Shuru karne se pehle, ek plain-language refresher taaki koi bhi symbol bina samjhaye na aaye:

Neeche sab kuch bas in words ki tables bharnaaha aur end mein divide karna hai. Yahi poora game hai.

Scenario matrix

Har branch-prediction question is grid ka ek cell hai. Hum sab ko hit karenge.

#	Case class	Kya special hai	Worked in
A	Forward branch, rarely taken	Static PNT / BTFNT aasaani se jeetta hai	Ex 1
B	Backward branch, loop taken	Static PT / BTFNT jeetta hai; ceiling set karta hai	Ex 1
C	Word problem: CPI cost	Accuracy ko real slowdown mein badlo	Ex 2
D	1-bit predictor, short loop	Cold-start aur exit dono galat → oscillation	Ex 3
E	2-bit predictor, short loop	Hysteresis; warm vs. cold re-entry	Ex 4
F	2-bit predictor, long loop (limit)	Accuracy → theoretical ceiling	Ex 5
G	Degenerate: alternating T,NT,T,NT	Worst case — har predictor thrash karta hai	Ex 6
H	Correlating predictor	Outcome doosre branch par depend karta hai	Ex 7
I	Zero / trivial input: loop 0 ya 1 baar chalta hai	Pattern ka edge; "cold start" ka matlab	Ex 8
J	Exam twist: aliasing (do branches, ek BHT slot)	Ek counter share karna dono ko corrupt karta hai	Ex 9

(PNT = Predict-Not-Taken, PT = Predict-Taken, BTFNT = Backward-Taken-Forward-Not-Taken — sab upar box mein define hain.)

Neeche ki figures do state machines dikhati hain jinpar hum baar baar rely karte hain — inhe open rakhna.

Figure — Branch prediction (static and dynamic)

Worked examples

Example 1 — Static BTFNT ek real loop par (cells A + B)

Worked example Statement

for (int i = 0; i < 100; i++) {   // branch L: i < 100  (backward jump)
    if (arr[i] < 0) break;        // branch F: negative?  (forward jump)
}

Array arr mein 100 values hain, sabhi positive. BTFNT use karke (Backward → predict Taken, Forward → predict Not-Taken), har branch ke liye kitni predictions correct hain, aur overall accuracy kya hai?

Forecast: abhi guess karo — loop branch ya if branch zyada accurate hoga?

Step 1 — Har branch ko direction ke hisaab se classify karo. Yeh step kyun? BTFNT purely is par decide karta hai ki "target address branch se pehle (backward) hai ya baad mein (forward)?" Loop ka back-edge upar top ki taraf jump karta hai → backward → predict Taken. break neeche/bahar jump karta hai → forward → predict Not-Taken.

Step 2 — Loop branch L count karo. Yeh step kyun? Loop body i = 0…99 ke liye chalta hai. Pehle 99 checks mein i < 100 condition true hai → Taken; 100wen check mein i = 100 false hai → Not-Taken.

Har baar Taken predict kiya.
99 Taken checks par correct, 1 final NT par galat. $L accuracy = \frac{99}{100} = 0.99$

Step 3 — Forward branch F count karo. Yeh step kyun? Saari values positive hain, isliye arr[i] < 0 hamesha false hai → break Not-Taken hai har baar. BTFNT ne Not-Taken predict kiya. Yeh har iteration mein ek baar, 100 baar chalta hai. $F accuracy = \frac{100}{100} = 1.00$

Step 4 — Combine karo. Yeh step kyun? Overall accuracy total-correct over total-branches hai, fractions ka average nahi (inke counts alag hain — lekin yahan dono counts 100 hain). $Accuracy = \frac{99 + 100}{100 + 100} = \frac{199}{200} = 0.995$

Recall Verify

Directions: back-edge backward hai, break forward hai → BTFNT dono ke natural bias se match karta hai. Sanity: accuracy 1 se zyada nahi ho sakti aur yahan $199/200 = 0.995 \leq 1$ . ✅

Example 2 — Accuracy ko slowdown mein badalna (cell C, word problem)

Step 1 — CPI penalty model likho. Yeh step kyun? Har instruction 1 cycle leti hai plus kabhi kabhi extra: sirf branches misfire kar sakte hain, aur sirf woh fraction jo mispredict karte hain penalty bharta hai. $CPI = 1 + P_{branch} \times P_{mispredict} \times Penalty$

Step 2 — Numbers padhke nikalao. Yeh step kyun? "92% accurate" ka matlab mispredict rate $1 - 0.92 = 0.08$ hai. 0.92 mat daalo — accuracy correct fraction hai, penalty galat fraction par lagti hai. $P_{branch} = 0.25, P_{mispredict} = 0.08, Penalty = 8$

Step 3 — Compute karo. Yeh step kyun? Ab hum teeno numbers Step 1 ke model mein substitute karte hain — yahan abstract formula ek actual cycle count banta hai jis par hum act kar sakte hain. $CPI = 1 + 0.25 \times 0.08 \times 8 = 1 + 0.16 = 1.16$

Step 4 — Slowdown mein convert karo. Yeh step kyun? CPI 1.16 vs ideal 1.00 matlab har instruction 16% zyada cycles leti hai. $Slowdown = \frac{1.16 - 1}{1} = 0.16 = 16%$

Recall Verify

Units: (branches/instr)(mispred/branch)(cycles/mispred) = cycles/instr, cycles/instr mein ek CPI mein add hota hai — consistent. Extreme check: agar accuracy 100% hoti, term = 0, CPI = 1 (koi loss nahi). ✅ Answer 16%.

Example 3 — 1-bit predictor ek 3-iteration loop par (cell D)

Step 1 — Actual outcomes list karo. Yeh step kyun? 3 iterations = branch Taken 3 baar (top par wapas), phir exit par ek baar Not-Taken → sequence T, T, T, NT.

Step 2 — State machine chalao. Yeh step kyun? Rule (s01 dekho): current bit predict karo, phir bit ko actual outcome par set karo.

Iter	Actual	State before	Predict	Correct?	State after
0	T	0	NT	❌	1
1	T	1	T	✅	1
2	T	1	T	✅	1
Exit	NT	1	T	❌	0

Step 3 — Count karo. Yeh step kyun? Accuracy correct-over-total hai, isliye hum ✅ rows (2) ko sab rows (4) se tally karte hain — trace tabhi number banta hai jab hum yeh division karte hain. $Accuracy = \frac{2}{4} = 0.50$

Step 4 — Dono failures explain karo. Yeh step kyun? Matrix demand karta hai ki hum har miss name karein. Miss #1 cold start hai (bit 0 tha). Miss #2 exit hai (loop 3× taken, toh bit 1 tha, lekin exit NT hai). Ek 1-bit predictor dono pay karta hai har loop mein jise woh exit karta hai — yahi oscillation flaw hai.

Recall Verify

Char mein se do misses → $2/4 = 0.5$ . Length $n$ ka har loop 1-bit predictor ko exactly 2 misses karta hai (start + exit) agar ek baar enter kiya, toh accuracy $= (n - 1) / (n + 1)$ ; $n = 3$ ke liye yeh $2/4$ hai. ✅

Example 4 — 2-bit predictor, cold vs. warm loop (cell E)

Step 1 — Pehli entry trace. Yeh step kyun? Rule: Taken predict karo agar counter $\geq 10$ (yaani binary mein do ya zyada); T par increment karo (cap 11), NT par decrement karo (floor 00).

Iter	Actual	Ctr before	Predict	Correct?	Ctr after
0	T	00	NT	❌	01
1	T	01	NT	❌	10
2	T	10	T	✅	11
Exit	NT	11	T	❌	10
$First-entry accuracy = \frac{1}{4} = 0.25$

Step 2 — Yahan itna bura kyun? Yeh step kyun? Counter ko predict-Taken region mein climb karne ke liye do taken outcomes chahiye. Loop sirf 3 lamba hai, toh yeh exit se pehle m漢11 tak漢漢barely漢 pahunchta hai — woh hysteresis jo long loops ki help karta hai woh bahut chhote loops ko hurt karta hai.

Step 3 — Re-entry trace. Yeh step kyun? Exit ne counter 10 (Weakly Taken) par chhoda, 00 par wapas nahi. Toh counter warm hai — yeh already Taken predict karta hai.

Iter	Actual	Ctr before	Predict	Correct?	Ctr after
0	T	10	T	✅	11
1	T	11	T	✅	11
2	T	11	T	✅	11
Exit	NT	11	T	❌	10
$Re-entry accuracy = \frac{3}{4} = 0.75$

Recall Verify

Pehli entry 4 mein 1 correct → 0.25. Warm re-entry 4 mein 3 → 0.75, ek hi miss = sirf exit. Warm start hi 2-bit hysteresis ka poora point hai. ✅

Example 5 — 2-bit predictor, long-loop limit (cell F)

Step 1 — Mispredictions count karo. Yeh step kyun? Warm start = counter already 11 par. Toh saare 100 Taken checks Taken predict kiye hain → body par 0 misses. Sirf exit (NT vs predicted T) miss karta hai → 1 miss.

Step 2 — Accuracy. Branch 100 (body) + 1 (exit) = 101 baar evaluate hota hai, 1 galat. $Accuracy = \frac{100}{101} \approx 0.990$

Step 3 — Limit lo. Yeh step kyun? Matrix limiting behaviour chahta hai. Length $n$ ke warm predictor wale loop ke liye: $Accuracy (n) = \frac{n}{n + 1} ⟹ lim_{n \to \infty} \frac{n}{n + 1} = 1$

Step 4 — Interpret karo. Ek hi exit miss zyada se zyada correct body predictions par amortised hoti hai, isliye accuracy 100% ki taraf badhti hai. Long loops exactly wahi hain jahan dynamic prediction shine karta hai.

Recall Verify

$100/101 = 0.990099 \dots$ . Aur $n / (n + 1)$ monotonically 1 tak badhta hai; e.g. $n = 1000 \to 0.999$ . ✅

Example 6 — Degenerate worst case: alternating outcomes (cell G)

Step 1 — Tab tak trace karo jab tak repeat na ho. Yeh step kyun? Alternating data woh pathological input hai jise ek saturating counter resist karne ke liye design kiya gaya hai — toh yeh yahan learning ko bhi resist karta hai.

Step	Actual	Ctr before	Predict	Correct?	Ctr after
1	T	01	NT	❌	10
2	NT	10	T	❌	01
3	T	01	NT	❌	10
4	NT	10	T	❌	01

Step 2 — Cycle dhundho. Yeh step kyun? State 2 steps baad 01 par wapas aa jaati hai → upar wala pattern hamesha repeat hota hai. Har prediction galat hai. $Accuracy = \frac{0}{4} = 0%$

Step 3 — 1-bit predictor se compare karo. Yeh step kyun? Same stream par ek 1-bit predictor bhi har baar mispredict karta hai (yeh hamesha wahi predict karta hai jo abhi hua, jo next ka ulta hai). Toh dono 0% dete hain — random guessing (50%) se bhi bura. Yeh theoretical worst case hai; correlating predictors (Ex 7) iska ilaaj hain.

Recall Verify

01 → 10 → 01 cycle 0 correct predictions ke saath repeat hota hai → accuracy 0. 50% coin flip se bhi bura. ✅

Example 7 — Jab history matter karti hai: correlating predictor (cell H)

Worked example Statement

if (a == 2) x = 0;   // Branch B1
if (b == 2) y = 0;   // Branch B2
if (a == b)  ...      // Branch B3  <- B1 aur B2 par depend karta hai!

Test hamesha a = b = 2 use karta hai, aur yeh exact call do baar run hoti hai. Ek bimodal predictor (B3 ke liye ek 2-bit counter, 00 start) ko ek correlating predictor (global-history pattern per ek 2-bit counter; pattern last-two-branch outcomes B1,B2 hai, aur uske saare counters 00 start karte hain) se compare karo. B3 ko run 1 aur run 2 par trace karo.

Forecast: kya koi bhi predictor B3 ki pehli execution par sahi ho sakta hai?

Step 1 — B3 ka true outcome fix karo. Yeh step kyun? a = b = 2 ke saath: a==2 true hai (B1 Taken), b==2 true hai (B2 Taken), aur a==b true hai → B3 dono runs par Taken hai. Toh B3 ka outcome sequence T, T hai, aur B3 ko feed karne wali global history hamesha pattern (B1=T, B2=T) hai.

Step 2 — Bimodal trace (sirf B3 ka counter). Yeh step kyun? Ek bimodal predictor purely B3 ke address se index karta hai, toh yeh 00 par cold start karta hai aur sirf B3 ko isolate mein seek kar sakta hai.

Run	Actual	Ctr before	Predict	Correct?	Ctr after
1	T	00	NT	❌	01
2	T	01	NT	❌	10

Bimodal: abhi tak 0/2 correct — predict-Taken region tak pahunchne ke liye hi do Takens chahiye, toh dono early runs miss hote hain.

Step 3 — Correlating trace (history B1,B2 se select kiya counter). Yeh step kyun? Correlating predictor current global pattern ke saath tagged counter pick karta hai. Dono runs pattern (T,T) ke saath aate hain, toh dono ek hi (T,T) counter use karte hain — iska history run to run accumulate hoti hai.

Run	Pattern	Actual	(T,T) Ctr before	Predict	Correct?	Ctr after
1	(T,T)	T	00	NT	❌	01
2	(T,T)	T	01	NT	❌	10

Step 4 — Forecast ka jawab do + payoff naam karo. Yeh step kyun? B3 ki bilkul pehli execution par dono predictors miss karte hain — koi predictor woh outcome nahi jaanta jo usne kabhi dekha hi nahi (cold start anavoidable hai). Difference tab dikhe jab mixed contexts ho: agar kuch runs mein a≠b hota (pattern not (T,T)), toh correlating predictor us pattern ke liye ek alag counter rakhta hai, isliye (T,T)-context cleanly Taken ki taraf trained rehta hai. Bimodal predictor har context ko ek counter mein blend karta hai, toh mixed histories uski B3 accuracy ko neeche kheenchti hain. Pure repeating (T,T) context ke saath, ek baar shared counter 11 par saturate ho jaaye toh dono 100% reach karte hain — lekin sirf correlating design interleaved contexts mein survive karta hai.

Recall Verify

Logic: a=b=2 ⇒ (a==2) ∧ (b==2) ∧ (a==b) sab true ⇒ B1=B2=B3=Taken. Pehle run ki prediction cold at 00 = NT ≠ T ⇒ dono run 1 miss karte hain (forecast answered: nahi). ✅

Example 8 — Trivial inputs: loop 0 ya 1 baar chalta hai (cell I, degenerate)

Step 1 — Case (a), zero iterations. Yeh step kyun? Loop test ek baar check hota hai, false hai → NT. Cold counter 00 NT predict karta hai, toh yeh match karta hai.

Iter	Actual	Ctr before	Predict	Correct?	Ctr after
test	NT	00	NT	✅	00
$Accuracy = \frac{1}{1} = 1.00$
Cold predictor luck se match karta hai: SNT fall-through expect karta hai, aur zero-trip loop hai hi fall-through.

Step 2 — Case (b), ek iteration. Yeh step kyun? Body ek baar chalta hai → back-edge ek baar Taken, phir exit NT. Sequence T, NT.

Iter	Actual	Ctr before	Predict	Correct?	Ctr after
0	T	00	NT	❌	01
Exit	NT	01	NT	✅	00
$Accuracy = \frac{1}{2} = 0.50$

Step 3 — Edge interpret karo. Yeh step kyun? Yeh loop pattern ki boundaries hain. Ek 0-trip loop pessimistic cold state ko reward karta hai; ek 1-trip loop essentially ek akela unpredictable event hai. Dono mein counter "learn" karne ke liye enough repetition nahi hai — dynamic prediction sirf repetition ke saath pay off karta hai.

Recall Verify

(a) 1/1 = 1.0; (b) 1/2 = 0.5. General warm-limit formula $n / (n + 1)$ cold par apply nahi hoti — yeh cold-start boundary cases hain. ✅

Example 9 — Exam twist: BHT aliasing (cell J)

Step 1 — Dikhao ki woh collide karte hain. Yeh step kyun? BHT index byte offset ke upar low PC bits use karta hai. Yahan $0 x 1000$ aur $0 x 1010$ sirf ek bit mein differ karte hain jo 2-bit index window ke bahar hai, toh dono ek hi counter index karte hain — yahi aliasing hai (a.k.a. destructive interference).

Step 2 — Shared 1-bit state trace karo. Yeh step kyun? Har branch bit ko apne outcome se overwrite karta hai, phir doosra branch woh stale bit read karta hai.

Step	Branch	Actual	Bit before	Predict	Correct?	Bit after
1	X	T	0	NT	❌	1
2	Y	NT	1	T	❌	0
3	X	T	0	NT	❌	1
4	Y	NT	1	T	❌	0

Step 3 — Count karo. Yeh step kyun? Bit hamesha pichle, opposite branch se set hota hai, toh har prediction invert ho jaati hai. $Accuracy = \frac{0}{4} = 0%$

Step 4 — Fix. Yeh step kyun? Akele, X 100% hota (hamesha T) aur Y 100% hota (hamesha NT). Aliasing dono ko destroy karta hai. Ilaaj: zyada BHT entries (kam collisions), ya entries ko PC ke hisse ke saath tagging karo taaki collisions detect ho sakein — yeh table size aur accuracy ke beech ek real design trade-off hai.

Recall Verify

Isolated X: constant stream par predict-then-update 100% par converge karta hai. Same Y ke liye. Shared: alternation stored bit ko hamesha doosre branch ka outcome force karta hai → 0%. Sharing ne 100%+100% ko 0% mein badal diya. ✅

Recall

Recall Full coverage check

Kaun si ek flaw 1-bit predictor ko do baar miss karwati hai har loop mein? ::: cold start (pehla iter) aur loop exit — yeh "mostly taken" pattern hold nahi kar sakta. 2-bit predictor long loops par use kyun beat karta hai? ::: hysteresis: ek exit NT use 11 se sirf 10 tak drop karta hai, phir bhi Taken predict karta hai, toh re-entry ko koi relearning nahi chahiye. $n$ -iteration loop ke liye warm 2-bit accuracy kya hai? ::: $n / (n + 1)$ , $n \to \infty$ ke saath 1 ki taraf jaati hai. Kaun si input class saare single-counter predictors ko defeat karti hai? ::: alternating T, NT, T, NT — accuracy 0%; correlating predictor chahiye. Aliasing kya hai aur yeh bura kyun hai? ::: do branches ek BHT slot map karte hain aur ek doosre ki history overwrite karte hain, potentially dono ki accuracy 0% tak crash kar dete hain.

Connections

Speculation tabhi pay off karta hai kyunki prediction usually sahi hoti hai — dekho Speculative Execution.
Kam mispredicts = zyada usable deep pipelines = zyada Instruction-Level Parallelism (ILP) aur wider Superscalar Processors.
Mispredict flushes cache ko bhi wrong-path fetches se thrash karte hain.
Compiler Optimizations jaise loop unrolling aur BTFNT hint placement branch mix change karte hain jo predictor dekhta hai.