2-bit saturating counter predictors: Exercises — Hinglish deep dive

5.3.8 · D4 · Hardware › Advanced Microarchitecture › 2-bit saturating counter predictors

Shuru karne se pehle, ek shared picture. Neeche ke har problem mein 2-bit saturating counter ko usi tarah padha jaata hai. Is figure ko samne rakhna.

Figure — 2-bit saturating counter predictors

Recall Rules, ek jagah par (sirf tab kholo agar bhool gaye ho)

2-bit counter ek number hai 0 se 3 tak, do bits mein dikhaya jaata hai:

00 = 0 Strongly Not-Taken (SNT)
01 = 1 Weakly Not-Taken (WNT)
10 = 2 Weakly Taken (WT)
11 = 3 Strongly Taken (ST)

Predict karo: top bit (yaani "MSB") $1$ hai → predict Taken; top bit $0$ hai → predict Not-Taken. Equivalently: state $\geq 2$ Taken predict karta hai. Branch resolve hone ke baad update karo: Taken → 1 add karo lekin 3 se zyada mat jaao (saturate); Not-Taken → 1 subtract karo lekin 0 se neeche mat jaao.

Naye ho? Pehle yeh padhlo: Branch Prediction Fundamentals, 1-Bit Branch Predictors, aur parent 2-Bit Saturating Counter Predictors.

Neeche har jagah yeh notation use hogi:

T = branch actually taken tha, N = actually not-taken tha.
✓ = prediction outcome se match ki (hit), ✗ = miss.
Trace is tarah likhte hain: state --outcome--> newstate.
Bit-slice notation $PC [a : b]$ ka matlab hai "program counter ke bits position $a$ se $b$ tak, inclusive, ek binary number ki tarah padhe", jahan bit $0$ lowest bit hai. Toh $PC [13 : 2]$ woh 12-bit chunk hai jo neeche ke 2 bits hatane aur agli 12 rakhne se milta hai.

Level 1 — Recognition

L1.1 — Charon states ke naam batao

Har 2-bit value ke liye, uska poora naam aur yeh batao ki woh Taken predict karta hai ya Not-Taken.

Recall Solution

Bits	Number	Name	Top bit	Prediction
00	0	Strongly Not-Taken	0	Not-Taken
01	1	Weakly Not-Taken	0	Not-Taken
10	2	Weakly Taken	1	Taken
11	3	Strongly Taken	1	Taken

Prediction sirf top bit par depend karti hai — isliye states 0 aur 1 dono Not-Taken predict karte hain, aur 2 aur 3 dono Taken predict karte hain.

L1.2 — Update ka ek step

Counter state 10 (WT) mein hai. Branch Not-Taken resolve hota hai. Naya state kya hai, aur kya humne sahi predict kiya?

Recall Solution

10 se prediction: top bit 1 hai → Taken predict kiya. Actual tha Not-Taken → ✗ miss. Update: not-taken matlab 1 subtract karo: $2 - 1 = 1$ → naya state 01 (WNT). Trace: 10 --N--> 01.

Level 2 — Application

L2.1 — Ek chhota trace chalao

State 01 (WNT) se shuru karo. Branch outcomes yeh hain, order mein: T, T, N, T. Har step ke liye prediction, hit hai ya miss, aur naya state batao. Kul kitne misses?

Recall Solution

Step	Outcome	State before	Predict	Hit?	State after
1	T	01	NT	✗	10
2	T	10	T	✓	11
3	N	11	T	✗	10
4	T	10	T	✓	11

Misses = 2 (steps 1 aur 3). Notice karo ki step 3 ka single N humein sirf 11 se 10 par le gaya — hum abhi bhi Taken predict kar rahe hain, toh step 4 hit hai.

L2.2 — Bimodal index compute karo

Ek branch PC = 0x00401A3C par hai. Bimodal table mein $k = 12$ hai (toh $2^{12} = 4096$ entries) aur $PC [13 : 2] mod 2^{12}$ se index hoti hai. Index nikalo. (Yaad karo $PC [13 : 2]$ = neeche ke 2 bits hatao, phir agli 12 rakhlo.)

Recall Solution

Aligned instructions ke liye PC ke low 2 bits hamesha 00 hote hain, toh hum unhe hatate hain (2 se right shift). Phir $2^{12}$ se modulo = lowest 12 bits rakhna. $PC = 0x00401A3C = 4, 201, 020$ 2 se right shift: $4, 201, 020 \div 4 = 1, 050, 255$ . Low 12 bits rakhna: $1, 050, 255 mod 4096 = 1679$ . Index = 1679 (jo 0x68F hai). table[1679] par counter is branch ke behaviour ko track karta hai.

Agar indexing naya lag raha hai toh yeh padho: BTB (Branch Target Buffer) usi PC-slicing idea ka use karta hai.

Level 3 — Analysis

L3.1 — Loop miss count, head-to-head

Ek loop apna back-edge branch T T T T T T T T T N (9 taken, phir exit ke liye 1 not-taken) run karta hai, aur poora loop teen baar back-to-back run hota hai, toh actual stream woh 10-pattern 3× repeat hai. Dono predictors "warm" start karte hain: 1-bit predictor 1 hold karta hai (predict T), 2-bit counter 11 (ST) hold karta hai. Dono ke liye total misses count karo.

Recall Solution

2-bit counter. 9 T's ke dauran woh 11 par baithe rehta hai (already saturated) → sab ✓. Exit N 11 --N--> 10 karta hai, ek miss, lekin 10 abhi bhi T predict karta hai. Agle loop ka pehla T 10 --T--> 11 karta hai, ek hit. Toh 3 loop instances mein se har ek mein exactly 1 miss hota hai (uska exit). $2-bit misses = 3 \times 1 = 3$

1-bit predictor. 9 T's ke dauran woh 1 hold karta hai → sab ✓. Exit N: T predict karo, actual N → miss, 0 par flip. Agle loop ka pehla T: N predict karo, actual T → miss, wapas 1 par flip. Toh har instance mein exit miss aur re-entry miss dono hote hain = 2 misses — sivaaye bilkul aakhri instance ke jiske baad koi "next loop" nahi hai, toh uske baad re-entry miss nahi. Instance 1: exit miss + re-entry miss = 2. Instance 2: 2. Instance 3: sirf exit miss = 1. $1-bit misses = 2 + 2 + 1 = 5$

2-bit counter ki jeet re-entry misses avoid karne mein hai — yahan 2 re-entry misses.

L3.2 — Woh counter jise tum fix nahi kar sakte

Ek branch perfectly hamesha ke liye alternate karta hai: T N T N T N …. 2-bit counter ko 11 (ST) se start karo. Lambe run mein, kitne fraction predictions sahi hongi?

Recall Solution

Trace karo: 11 --T--> 11 T par T predict karte hue ✓; 11 --N--> 10 N par T predict karte hue ✗; 10 --T--> 11 T par T predict karte hue ✓; 11 --N--> 10 ✗ … Counter 11 aur 10 ke beech oscillate karta hai aur hamesha Taken predict karta hai. Toh yeh har T par sahi hai aur har N par galat → exactly 50% sahi. 2-bit counter alternation capture nahi kar sakta; yeh sirf track karta hai ki konsa direction majority mein hai, aur yahan koi bhi direction majority mein nahi hai. Isliye parent note "random ya adversarial patterns" ke baare mein warn karta hai.

Level 4 — Synthesis

L4.1 — Initial state design karo

Ek benchmark mein branches lagbhag 65% taken hote hain, aur saare dynamic branches mein se 40% pehli baar execute ho rahe hain (cold). Tum har counter ko ek fixed state se initialise kar sakte ho. Konsa start state — 00, 01, 10, ya 11 — expected cold-start misses minimize karta hai, aur woh expected cold miss rate kya hai?

Recall Solution

Branch ke pehle execution par counter abhi bhi apni init value par hai, toh prediction us value ke top bit se fixed hai. Abhi tak koi history nahi hai.

Init 00 ya 01 → top bit 0 → Not-Taken predict karo. Cold branch par tum sirf tab sahi ho jab woh actually not-taken ho: probability $0.35$ . Toh cold miss rate $= 0.65$ .
Init 10 ya 11 → top bit 1 → Taken predict karo. $0.65$ probability se sahi. Cold miss rate $= 0.35$ .

Taken-predicting init chunna chahiye (10 ya 11) jo 65% majority se match kare. Expected cold miss rate $= 0.35$ . 10 aur 11 mein se, 10 (weakly taken) usual choice hai: 11 jaisi hi first-guess, lekin genuinely not-taken branch sirf ek confirming outcome mein correct ho jaati hai, toh faster correct hota hai. Yahi parent note ki "init to WT" advice hai.

L4.2 — Storage budget

Tumhe counter table ke liye 1 KB (= $1024 \times 8 = 8192$ bits) budget mili hai. Har entry ek 2-bit counter hai. Kitni entries fit hongi, aur $k$ (index width) kya hai agar entries $= 2^{k}$ ho?

Recall Solution

Entries $= \frac{8192 bits}{2 bits/entry} = 4096$ entries. Kyunki $4096 = 2^{12}$ , index width $k = 12$ bits hai. Yahi parent note ka "4K-entry, 1 KB" bimodal predictor hai — numbers loop close karte hain.

Level 5 — Mastery

L5.1 — Aliasing: do branches, ek entry

Do branches same counter par map karte hain (destructive aliasing). Branch X ek loop body hai, strongly biased taken. Branch Y us loop ka exit test hai, biased not-taken. Jab loop run hota hai toh yeh interleave karte hain: ek loop instance mein tum X X X X Y dekhte ho (chaar body iterations, har ek taken, phir exit not-taken), 3× repeat hota hai, sab same shared counter par hit karte hain. Shared counter 11 (ST) se start karo. Kitne misses hote hain, aur yeh X aur Y dono ke private counter hone se kaise compare karta hai?

Recall Solution

Shared counter (aliasing). X taken hai, Y (exit) not-taken hai; dono ek hi 2-bit state par collide karte hain. Ek instance X X X X Y ko 11 se trace karo:

11 --T(X)--> 11 ✓, 11 --T--> 11 ✓, 11 --T--> 11 ✓, 11 --T--> 11 ✓ (chaar X hits)
11 --N(Y)--> 10 : T predict kiya, actual N → ✗ (Y ka exit miss)

Har instance 10 par khatam hota hai, aur agle instance ka pehla X 10 --T--> 11 ek hit hai. Toh har instance mein sirf Y ka exit miss: 3 instances mein total $= 3$ misses.

Private counters. X akela har instance mein T T T T dekha → 11 par bana raha → 0 misses. Y akela har instance mein ek baar N dekha, 11 se shuru, aur koi confirming T wapas upar nahi aata: 11 --N--> 10 (T predict kiya, actual N → ✗), phir 10 --N--> 01 (T predict kiya, actual N → ✗), phir 01 --N--> 00 (NT predict kiya, actual N → ✓). Toh 3 instances mein Y ke private misses hain ✗, ✗, ✓ = 2 misses; X = 0. Total private $= 2$ .

Comparison: shared mein 3 misses, private mein 2 — collision ki cost 1 extra miss thi. Yahan aliasing ne hurt kiya: Y ke not-taken outcomes ko X ke taken-heavy counter par park karne se counter hamesha "strongly taken" par re-arm hota rehta hai, toh Y kabhi apna not-taken bias nahi seekh paata aur har baar exit mispredicts (3×), jabki private counter ke saath Y not-taken ki taraf drift karta hai aur eventually ek exit sahi predict karta hai. Damage us hisaab se scale karta hai jitna do branches ka bias oppose karta hai ek dusre ko; bade tables ya history-based schemes (Gshare Predictor, Two-Level Adaptive Predictors) collisions reduce karte hain.

L5.2 — Flip cost prove karo

State diagram par arcs count karke dikhao ki ST se start karte hue 2-bit counter ki prediction "predict Taken" se "predict Not-Taken" flip karne ke liye kam se kam 2 consecutive not-taken outcomes chahiye, aur N-bit case se compare karo.

Recall Solution

Prediction top bit se set hoti hai. "Predict Taken" ⇔ state $\in {10, 11}$ ; "predict Not-Taken" ⇔ state $\in {00, 01}$ . Boundary 10 aur 01 ke beech hai.

Sabse deep Taken state 11 (ST) se, har N 1 subtract karta hai: 11 --N--> 10 --N--> 01. Prediction top bit tabhi change hota hai jab hum 10 se 01 cross karte hain — yeh doosra N hai. Toh 2 consecutive N chahiye. Ek N (11→10) prediction unchanged rakhta hai.
N-bit generalisation: ek $N$ -bit saturating counter ke $2^{N}$ states hote hain; prediction boundary middle mein hoti hai, toh top state se tumhe boundary cross karne ke liye $2^{N - 1}$ steps walk karne padte hain. $N = 2$ ke liye: $2^{1} = 2$ ✓. $N = 3$ ke liye: flip karne ke liye $2^{2} = 4$ consecutive N — yahi parent note ki warning hai ki 3-bit counters phase changes mein zyada dheere adapt karte hain.

Toh "predictor kitna stubborn hai" wala number $2^{N - 1}$ hai, aur $N = 2$ jo ek modest 2 deta hai woh anti-aliasing aur adaptability ke beech sweet spot hai.

Recall Self-check: inhe memory se fill karo

N-bit counter ka prediction flip cost kaise scale karta hai? ::: Isko extreme state se $2^{N - 1}$ consecutive opposite outcomes chahiye. Counters ko 00 ki jagah 10 (WT) se init kyun karo? ::: Branches ~65% taken hote hain; Taken-predicting init majority se match karta hai aur cold-start misses kam karta hai. Kya 2-bit predictor loop exit miss save karta hai? ::: Nahi — woh re-entry miss save karta hai; exit dono 1-bit aur 2-bit ke liye miss hota hai. Konsa pattern 2-bit counter ko 50% accuracy tak defeat karta hai? ::: Perfect alternation T N T N …, kyunki koi bhi direction majority mein nahi hai. 4K table ke liye bimodal index? ::: $PC [13 : 2] mod 2^{12}$ = low 2 bits hatao, baaki ke low 12 rakhlo.