2-bit saturating counter predictors: Worked examples

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

Yeh page 2-bit saturating counters ke liye exhaustive drill room hai. Koi bhi example padhne se pehle, ensure karo ki tum parent note se yeh already jaante ho ki ek 2-bit counter ek chhoti si machine hai jiske paas chaar states hain, aur most-significant bit (MSB) — sabse left wala bit — poori prediction hai:

Recall Ek rule jo shuru karne se pehle tumhare paas hona chahiye

2-bit state do binary digits ke roop mein likhi jaati hai, e.g. 10. Left digit MSB hai. ==Agar MSB = 1 hai, toh predict TAKEN. Agar MSB = 0 hai, toh predict NOT-TAKEN.== "Taken" matlab branch jump karta hai; "not-taken" matlab execution fall through hoti hai. Update: taken → +1 (ek add karo, lekin 11 se upar kabhi mat jao), not-taken → −1 (ek subtract karo, lekin 00 se neeche kabhi mat jao).

Definition Symbols aur words jo hum neeche har jagah use karte hain

Yeh key ek baar padho — har example ise reuse karta hai.

T = branch outcome Taken tha (yeh jump kiya). N = branch outcome Not-taken tha (yeh fall through kiya). TTTN jaisi stream ka matlab hai "taken, taken, taken, not-taken" usi order mein.
Chaar states hain: 00 (Strongly Not-Taken), 01 (Weakly Not-Taken), 10 (Weakly Taken), 11 (Strongly Taken).
program counter (PC) woh register hai jo currently executing instruction ki memory address hold karta hai — ek branch ke liye, yeh branch ki apni address hai.
bit-slice jaise PC[3:2] ka matlab hai "us binary address ka woh piece jo bit number 3 aur bit number 2 se bana hai" (bits right side se 0 se number hote hain). Toh PC[1:0] sabse neeche ke do bits hain, aur PC[3:2] unse agle do upar hain. Hum bit-slices ka use karte hain ek badi address ko ek chhote table index mein convert karne ke liye.

Agar un words mein se koi bhi shaky lagta hai, toh pehle Branch Prediction Fundamentals aur 1-Bit Branch Predictors par wapas jao.

Scenario matrix

Ek 2-bit counter exactly ek cheez se drive hota hai: outcomes ki ek stream (har ek T ya N). Har situation jo tum kabhi bhi miloge woh us stream ki ek shape hoti hai. Yeh har shape class hai jo yeh topic tumpe throw kar sakta hai.

Cell	Scenario class	Ise "extreme" kya banata hai	Covered by
C1	Ek direction ka lamba run	Saturation test karta hai (kya yeh `11`/`00` par clip karta hai?)	Ex 1
C2	Biased loop (bahut saare T, ek N, repeat)	Hysteresis test karta hai — 2-bit ke existence ka reason	Ex 2
C3	Cold start, galat initial guess	First-execution behaviour test karta hai	Ex 3
C4	Alternating T N T N (adversarial)	Degenerate worst case: 0% accuracy	Ex 4
C5	Ek hi trace mein dono boundaries (`00`↔`11`)	Dono saturation floors test karta hai	Ex 5
C6	Nested loops (ek saath do counters)	Real multi-branch word problem	Ex 6
C7	Phase change (mid-stream bias flip hota hai)	Limiting behaviour — hysteresis ek cost ban jaata hai	Ex 7
C8	Aliasing collision (do branches, ek entry)	Exam twist — indexing & interference	Ex 8

Neeche ke aath examples har cell fill karte hain. Har ek tumhe ek Forecast line deta hai — example ka baaki hissa cover karo aur pehle answer guess karo. Woh guess hi woh jagah hai jahan learning hoti hai.

Figure s01 neeche reference picture hai jo tum har example mein use karoge. Yeh chaaon states ko ek number line par dikhata hai, aur amber dashed line ko MSB flip boundary label karta hai — woh jagah jahan prediction NT se T mein change hoti hai:

Figure — 2-bit saturating counter predictors

Ise ek number line ki tarah padho: states 00–11 left se right tak chalte hain, aur amber dashed line jis par "MSB flip boundary" likha hai 01 aur 10 ke beech mein baithti hai. Jab bhi koi trace us line ko cross karta hai, prediction change hoti hai — Ex 4 aur Ex 5 mein dhyan rakhna.

C1 — Ek lambe run ke under saturation

Start 01 → MSB = 0 → NT predict karta hai. Pehla outcome T hai. Prediction galat → miss 1. Update taken: 01 + 1 = 10. Yeh step kyun? Hum hamesha outcome dekhne se pehle predict karte hain, phir update karte hain. Pehli prediction ne initial state use ki, jisne NT guess kiya tha.
10 → MSB = 1 → T predict karta hai. Outcome T → correct. Update: 10 + 1 = 11. Yeh step kyun? Ek sahi taken ne humein pehle se "taken half" mein push kar diya.
11 → T predict karta hai. Outcome T → correct. Update: 11 + 1 = 11 (clipped!). Yeh step kyun? Yeh saturation hai: 11 maximum hai, ek add karne se yeh 11 par hi rehta hai. Yeh 00 par wrap nahi karta.
Outcomes 4, 5, 6: sab T, sab correct, sab 11 par rehte hain.

Result: exactly 1 miss (cold first guess), final state 11.

C2 — Hysteresis: biased loop (headline case)

2-bit trace, steady state (11 par har loop start karo):

7 × T: 11→11 har baar (saturated). Sab correct. Yeh step kyun? Har taken outcome ek "+1" hai jo 11 par clip karta hai, toh loop ka poora body free hits hai.
Exit N: 11 T predict karta hai, outcome N → miss. Update: 11 − 1 = 10. Yeh step kyun? Ek anomaly humein sirf 10 tak nudge karti hai (still MSB = 1). Yeh hysteresis hai — "strongly taken" reservoir single N ko absorb karta hai.
Agle loop ka pehla T: 10 T predict karta hai, outcome T → correct. Update 10→11. Yeh step kyun? Kyunki hum taken half mein rahe, re-entry ek hit hai. Yahi 2-bit ka poora point hai.

2-bit misses per loop = 1 (sirf exit).

1-bit trace, steady state (ek 1-bit predictor sirf ek bit store karta hai: 1=predict T, 0=predict NT, aur yeh jo bhi last outcome tha woh ban jaata hai). Har loop mein bit = 1 se start karo:

7 × T: bit 1 hai → T predict karta hai, outcome T → har baar correct. Update: bit 1 rehta hai. Yeh step kyun? Ek bit mein koi reservoir nahi hai — lekin jab tak outcomes bit se agree karte hain, yeh simply wahi rehta hai aur hits karta rehta hai.
Exit N: bit 1 T predict karta hai, outcome N → miss. Update: bit 0 ban jaata hai. Yeh step kyun? Ek bit mein koi hysteresis nahi — ek single N poori prediction ko immediately flip kar deta hai.
Agle loop ka pehla T: bit 0 NT predict karta hai, outcome T → miss. Update: bit 1 ban jaata hai. Yeh step kyun? Kyunki exit ne bit ko NT par flip kar diya tha, re-entry taken ab mispredicted hai. Yeh extra miss hai jo 2-bit counter ne apne step 3 mein avoid kiya tha.

1-bit misses per loop = 2 (exit + re-entry).

C3 — Cold start galat initial guess ke saath

Init 00:

00 NT predict karta hai, outcome T → miss. Update taken: 00 + 1 = 01. Yeh step kyun? 00 ka MSB 0 hai, toh humne NT guess kiya, lekin branch taken tha — galat. Ek taken outcome "+1" hai, 00→01 move karta hai.
01 NT predict karta hai, outcome T → miss. Update taken: 01 + 1 = 10. Yeh step kyun? 01 ka MSB abhi bhi 0 hai, toh abhi bhi NT predict karta hai aur abhi bhi miss karta hai. "+1" ab taken half mein cross karta hai, 01→10.
10 T predict karta hai, outcome T → correct. Update taken: 10 + 1 = 11. Yeh step kyun? Sirf ab (MSB = 1) guess reality se match karta hai — not-taken half se bahar nikalne mein do takens lage. → 2 cold misses.

Init 10:

10 T predict karta hai, outcome T → correct. Update taken: 10 + 1 = 11. Yeh step kyun? Pehle se taken half mein start karte hue, pehli prediction hi sahi hai; taken outcome "+1" hai jo 11 tak jaata hai.
11 T predict karta hai, outcome T → correct. Update taken: 11 + 1 = 11 (clipped). Yeh step kyun? Saturation — 11 ceiling hai, toh "+1" 11 par hi rehta hai.
11 T predict karta hai, outcome T → correct. 11 par rehta hai. Yeh step kyun? Same saturated hit; counter kabhi strongly-taken state nahi chhodta. → 0 cold misses.

Yeh kyun matter karta hai: real branches ~60–70% taken hote hain, toh shuru se "taken" guess karna (init 10) common case mein jeetta hai. Isliye parent note 00 par default karne ke against warn karta hai.

C4 — Degenerate worst case: perfect alternation

Ise trace karo:

Step	State (pred)	Outcome	Right?	Next state
1	`10` (T)	T	✓	`11`
2	`11` (T)	N	✗	`10`
3	`10` (T)	T	✓	`11`
4	`11` (T)	N	✗	`10`

Yeh step kyun (row 1)? 10 par MSB 1 hai, toh hum T predict karte hain; outcome T hai, toh hum 10→11 increment karte hain. Ek sahi taken hamesha counter ko upar push karta hai. Yeh step kyun (row 2)? 11 par hum abhi bhi T predict karte hain, lekin outcome N hai, toh hum 11→10 decrement karte hain. Crucially counter 10 par land karta hai, jo abhi bhi taken half mein hai (figure s01 dekho) — yeh kabhi amber flip boundary tak nahi pahuncha, toh prediction kabhi NT par switch nahi hui. Loop kyun trapped hai: rows 3–4, rows 1–2 exactly repeat karte hain. Single T upar push karta hai, single N wapas neeche push karta hai, aur counter MSB flip boundary cross kiye bina forever 10↔11 oscillate karta hai.

Counter 10↔11 bounce karte hue trapped hai, hamesha T predict karta hai, lekin sach mein answer sirf aadhe time T hota hai.

C5 — Dono boundaries: `11` se `00` tak

11 T predict karta hai, outcome N → miss. 11→10.
10 T predict karta hai, outcome N → miss. 10→01. ← prediction ab flip hoti hai: MSB 0 ho gaya. Yeh step kyun? 10 se 01 mein cross karna humein figure s01 mein amber MSB flip boundary ke par le jaata hai — yeh exact moment hai jab guess T se NT change hota hai.
01 NT predict karta hai, outcome N → correct. 01→00.
00 NT predict karta hai, outcome N → correct. 00−1 = 00 (floor par clipped!).
00 NT predict karta hai, outcome N → correct.

Result: prediction flip karne mein do N's lagte hain (doosri direction mein hysteresis), aur 00 bilkul 11 ki tarah saturate karta hai — ek subtract karne se yeh 00 par rehta hai, 11 par wrap nahi karta.

C6 — Word problem: nested loops, do live counters

Worked example Ex 6 · Real code, ek saath do branches

for (i = 0; i < 3; i++)      // Branch A (outer)
    for (j = 0; j < 4; j++)  // Branch B (inner)
        work();

Dono counters 11 par start hote hain. Branch B apni condition har inner loop mein 5 baar fire karta hai (4 taken + 1 exit) aur yeh 3 baar karta hai. Branch A total 4 baar fire karta hai (3 taken + 1 exit). Total 2-bit misses count karo.

Forecast: is nest ke ek full run mein A aur B mein total misses?

Branch B, ek inner loop = TTTTN, har baar 11 par start karta hai (kyunki re-entry ise 11 par wapas land karati hai — same mechanism as Ex 2):

4×T at 11 → sab correct, 11 par rehta hai. Yeh step kyun? 11 saturated hai: har taken outcome ek "+1" hai jo 11 par clip karta hai, toh loop ke chaar body iterations free hits hain.
exit N: 11→10, 1 miss, abhi bhi T predict karta hai. Yeh step kyun? Akela not-taken exit 11→10 decrement karta hai. Woh single anomaly hysteresis se absorb ho jaata hai — counter taken half mein rehta hai, toh yeh agli entry par koi cost nahi deta.
Agle inner loop ka pehla T: 10→11, correct (re-entry bachaya!). Yeh step kyun? Kyunki humne pichla inner loop 10 par end kiya (MSB flip boundary se neeche nahi), agle inner loop ka pehla taken correctly predict hota hai aur humein seedha 11 par wapas push karta hai. Yeh bachaya hua re-entry miss hai.

Toh Branch B 1 miss per inner loop × 3 loops = 3 misses cost karta hai, aur 0 re-entry misses.

Branch A = TTTN from 11:

3×T at 11 → correct, 11 par rehta hai. Yeh step kyun? Same saturation logic: teen outer-loop-continue iterations sab "+1" clips at 11 hain.
exit N: 11→10, 1 miss. Yeh step kyun? Outer loop sirf ek baar exit karta hai, toh hum exactly ek misprediction pay karte hain jab counter 11→10 drop karta hai. Is run mein koi re-entry nahi hai, toh koi aur cost nahi.

Branch A 1 miss cost karta hai.

Total = 3 + 1 = 4 misses.

C7 — Limiting behaviour: jab hysteresis ek tax ban jaata hai

Ex 5 ki logic se: 11 start karke, prediction ko NT mein move karne mein 2 not-takens lagte hain (11→10→01). Toh 10 new-phase executions mein se, pehle 2 misses hain, phir sab correct.

2-bit misses on phase change = 2.
1-bit misses on phase change = 1 (ek N ise immediately flip karta hai).

C8 — Exam twist: ek table index par aliasing collision

Example se pehle, humein PC ko table index mein convert karne ke liye ek clean rule chahiye.

Definition Bimodal index rule

Ek bimodal predictor 2-bit counters ki ek table hai. Maano table mein $2^{k}$ entries hain, toh hum ek row pick karne ke liye ek $k$ -bit number chahiye; yahan $k$ sirf "kitne address bits hum index ke roop mein use karte hain" hai (ek design choice, e.g. $k = 12$ 4096 entries deta hai — yeh PC ki total width se related nahi hai). Rule yeh hai:

Lowest 2 bits drop karo PC[1:0]. 4-byte instructions wali machine par yeh do bits hamesha 00 hote hain, toh woh koi information carry nahi karte — inhe use karna index space waste karega.
Agle $k$ bits rakho PC[k+1:2]. Yeh $k$ bits HI index hain.

Compactly likha: $index = ⌊ PC /4 ⌋ mod 2^{k}$ . " $mod 2^{k}$ " (yani $2^{k}$ se divide karne ke baad remainder) wahi hai jo sirf $k$ bits rakhta hai: yeh bit $k + 1$ se upar sab kuch throw away karta hai. Hardware mein yeh poori cheez sirf wires hai — koi divider nahi chahiye, literally PC[k+1:2] slice out karte ho.

(a) Upar ke rule se dono indices compute karo.

PCs ko binary mein likho: 0x1004 = 0001 0000 0000 0100, 0x1014 = 0001 0000 0001 0100. Yeh step kyun? Rule bits par kaam karta hai, toh humein PC[3:2] read karne ke liye binary form chahiye.
PC[1:0] (low 00) drop karo aur agle $k = 2$ bits PC[3:2] rakho.
- X 0x1004: PC[3:2] = 01 → index $= 1$ .
- Y 0x1014: PC[3:2] = 01 → index $= 1$ . Yeh step kyun? 4 se divide karna aur $mod 4$ lena exactly "bits 3 aur 2 rakho" hai. Dono PCs accidentally un do bits share karte hain, chahe woh upar (bit 4) differ karte hon.
Woh collide karte hain — dono entry 1 par map hote hain. Yeh destructive interference hai: do unrelated branches ek counter share karne ke liye force hain.

(b) Shared counter trace karo (10 start karo), interleaved T, N, T, N:

Step	Branch	State (pred)	Outcome	Right?	Next
1	X	`10` (T)	T	✓	`11`
2	Y	`11` (T)	N	✗	`10`
3	X	`10` (T)	T	✓	`11`
4	Y	`11` (T)	N	✗	`10`

Yeh step kyun (rows 1, 3)? X genuinely taken hai, toh 10/11 (MSB = 1) par prediction T sahi hai, aur "+1" 11 ki taraf push karta hai. Yeh step kyun (rows 2, 4)? Y genuinely not-taken hai, lekin shared counter taken half mein baitha hai kyunki X ise upar kheench raha hai — toh Y ko T predict kiya jaata hai aur har baar miss hota hai, aur uska "−1" sirf counter ko 10 par wapas drop karta hai.

Counter thrash karta hai: X ise upar push karta hai, Y ise neeche kheechtai hai, aur yeh taken half nahi chhodta. X hamesha right hai, Y hamesha wrong hai — Y ki real bias collision se completely mask ho jaati hai.

Recall drills

Recall

11 se, kitne not-takens prediction ko NT flip karte hain? Do ::: 11→10 (abhi bhi T), phir 10→01 (ab NT). Ek N hysteresis se absorb hota hai.

Recall Perfect TNTN branch par steady-state 2-bit accuracy?

50% ::: koi bias nahi matlab lean karne ke liye koi reservoir nahi — degenerate worst case.

Recall Fresh branch ke liye init

10 kyun 00 se better hai? Zyatar branches taken hote hain (~65%) ::: step one se taken guess karna common case par cold-start jeetta hai.

Recall Genuine phase change par, kya 2-bit 1-bit se faster ya slower adapt karta hai?

Slower ::: 2-bit ko flip karne ke liye 2 mispredicts chahiye; 1-bit ko 1. Hysteresis yahan ek tax hai.

Recall Bit-slice

PC[3:2] ka kya matlab hai, aur $k$ kya hai? Program counter address ke bits 3 aur 2 ::: $k$ index bits ki sankhya hai, jo $2^{k}$ -entry table deta hai.