2-bit saturating counter predictors: Visual walkthrough

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

Yeh page 2-Bit Saturating Counter Predictors ka central result bilkul scratch se rebuild karta hai — pictures mein. Hum ek bhi word jaise "counter", "state", ya "saturate" use nahi karenge jab tak aap use dekh nahi lete. End tak aap machine ko draw kar sakte hain, trace kar sakte hain, aur prove kar sakte hain ki kyun 2 bits ek loop par 3 mistakes ko 2 mein badal deta hai.

Agar aapne yeh words pehle kabhi nahi sune, toh pehle Branch Prediction Fundamentals aur 1-Bit Branch Predictors padho — lekin main har cheez re-derive kar dunga jo aapko chahiye, toh aap yahaan se bhi shuru kar sakte hain.

Step 1 — "Branch" kya hota hai aur "predict" karne ka matlab kya hai?

KYA HAI. Ek branch ek program ke andar raaste ka ek morh hai. CPU ek goto-jaisi instruction tak pahunchta hai aur do raaston mein se ek lena padta hai: ya toh jump hota hai (hum isse Taken bolte hain, likha T) ya nahi hota (Not-Taken, likha NT).

KYUN guess karna padta hai. Ek modern CPU ek pipeline hai — yeh agli instruction par kaam shuru kar deta hai current ek khatam hone se pehle hi. Lekin ek branch par use abhi tak nahi pata ki raasta kidhar jaata hai. Rukne aur wait karne ki bajaye, yeh guess karta hai aur kaam karta rehta hai. Sahi guess ka koi cost nahi. Galat guess (ek misprediction) ka matlab hai kaam phek dena — expensive. Toh hamara poora goal yeh hai: kam galat guesses karo.

PICTURE. Morh, do raaste T aur NT, aur ek chhota sa box "predictor" jiska sirf yeh kaam hai ki CPU ko sach pata chalne se pehle whisper kare "baaye jao" ya "daaye jao".

Step 2 — Sabse simple guesser (1 bit) aur jis trap mein woh phasta hai

KYA HAI. Sabse chhoti possible memory one bit hai: 0 ka matlab "main NT predict karta hoon", 1 ka matlab "main T predict karta hoon". Rule yeh hai: branch resolve hone ke baad, agar aap galat the, toh bit flip karo.

KYUN yeh theek lagta hai. Ek branch ke liye jo hamesha same kaam karta hai, ek galat guess bit ko fix kar deta hai aur aap tab se sahi rehte hain. Sasta aur simple.

PICTURE. Ek loop dekhiye jo 10 baar chalta hai. Branch naun baar kehta hai "looping jari rakho? T", phir ek baar "bahar jao? NT" — phir loop baad mein phir shuru hota hai aur phir se "T" kehta hai. Single bit ko do boundaries par flip hote dekhiye.

Trap picture ke red flips mein hai. Exit bit ko 0 par force karta hai. Lekin agli baar jab loop chalta hai, pehla branch phir se T hai — aur bit abhi bhi 0 kehta hai. Toh aap bahar jaate waqt AUR wapas aate waqt miss karte hain. Yeh double-hit aliasing ya ping-ponging kehlata hai.

Step 3 — Woh idea jo ise fix karta hai: guesser ko momentum do

KYA HAI. Ek aise bit ki jagah jo single mistake par flip ho, ek chhota number use karo jo T par upar jaata hai aur NT par neeche, aur number ki sign (top half vs bottom half) prediction decide karne do. Ek akela NT number ko sirf nudge karta hai — prediction flip nahi hoti.

KYUN. Ek loop T,T,T,…,T,NT hai — end mein ek contrarian ke saath lambi agreement. Hum ek aisi memory chahte hain jo us akele NT ko noise maane, na ki apna mind badalne ki wajah. Yahi "ek badlaav ko resist karna" — hysteresis — ka matlab hai.

PICTURE. Ek ghati mein ball. Daayein push karna (T) use "predict T" ki taraf roll karta hai; baayein push karna (NT) use wapas roll karta hai. Dum daayein se ek akeli left-push doosri taraf nahi pahunchti.

Step 4 — Number ko concrete banao: chaar states, ek 2-bit machine

KYA HAI. Do bits 00 se 11 tak count karte hain, yani numbers $0, 1, 2, 3$ . Hum inhe lean + strength se naam dete hain:

SNT 00 WNT 01 WT 10 ST 11

Symbols padna: S = Strongly, W = Weakly, N = Not, T = Taken. Vertical bar bottom half (00,01) ko top half (10,11) se alag karta hai.

Prediction rule — sirf top bit padho. Most-significant bit (MSB) hi lean hai:

predict = {T NT MSB = 1 (states 10, 11) MSB = 0 (states 00, 01)

MSB poori purani 1-bit predictor ka kaam kar raha hai; low bit nayi confidence memory hai.

Update rule — count karo. Outcome T par, 1 add karo lekin 11 se aage mat jao. Outcome NT par, 1 subtract karo lekin 00 se neeche mat jao. "End se aage nahi jaana" saturation hai: 11 + 1 = 11, 00 nahi. Yeh clip karta hai; wrap nahi karta.

KYUN exactly yeh chaar. Ek lean ke liye do states minimum hai jo ek akele surprise ko sirf confidence (ST→WT) cost karne de jaate hain jabki lean bani rahe (abhi bhi T). Kam states = confidence ke liye jagah nahi; zyada states = hum Step 8 mein dekhenge ki over-resist karta hai.

PICTURE. Chaar states ek row mein, MSB ke liye split line, +1/−1 arrows, aur do saturation walls jahan arrows wapas bounce karte hain.

Step 5 — Poora state machine draw karo (woh arcs jo matter karte hain)

KYA HAI. Har state ko uske do arcs do: ek actual outcome T ke liye (upar jao / 11 par raho) aur ek actual NT ke liye (neeche jao / 00 par raho).

KYUN draw karo. Is poore topic ka sabse important fact ek geometric wala hai jise aap literally point kar sakte hain: prediction change karne ke liye aapko middle line cross karni padegi, aur ek Strong state se uske liye do consecutive contrary outcomes chahiye, na ki ek.

PICTURE. Chaar states, aath arcs sab. Yellow = T arcs, pink = NT arcs. Beech mein dashed line hai "yahan prediction flip hoti hai". Notice karo ki ST se ek akela NT sirf WT tak pahunchta hai — abhi bhi line ke upar, abhi bhi T predict kar raha hai.

Recall

ST (11) se, prediction NT hone se pehle aapko kitne not-takens ki zaroorat hai? ::: Do — 11 → 10 (abhi bhi predict T) phir 10 → 01 (ab predict NT). State ka kaun sa bit actual prediction hai? ::: MSB (top bit).

Step 6 — Loop ko machine se guzaro (payoff, traced)

KYA HAI. Step 2 ka same 10-iteration loop lo, lekin counter 01 (WNT) par shuru karo aur trace karo. Same input T,T,…,T,NT, phir re-entry T.

KYUN 01 par shuru karein. Hum 1-bit predictor ke against ek fair fight chahte hain, jo NT lean se shuru hua tha. 01 bhi NT lean karta hai, toh dono equally "cold" se shuru karte hain.

PICTURE. Counter ka path chaar states par walk ki tarah draw kiya gaya hai, do misses par red bursts aur crucial re-entry par green tick ke saath.

Trace, term by term:

#	outcome	state move	predicted	result
1	T	`01 → 10`	NT	✗ miss (cold)
2–9	T	`10 → 11 → 11 …`	T	✓
10 (exit)	NT	`11 → 10`	T	✗ miss (exit)
next entry	T	`10 → 11`	T	✓ saved!

Jeet, bilkul exactly batayi. Exit ke akele NT ne sirf ST → WT kiya. WT ka MSB abhi bhi = 1 hai, toh yeh abhi bhi T predict karta hai. Jab loop wapas aata hai, pehla T sahi predict hota hai — Step 2 ki re-entry miss chali gayi.

Step 7 — Degenerate case: alternating `T,NT,T,NT` (kyun 2 bits magic nahi hai)

KYA HAI. Machine ko ek branch feed karo jo truly alternate karta hai, jaise if (i % 2): T, NT, T, NT, …, kaheen se bhi shuru karo.

KYUN dikhao. Ek achhi walkthrough woh bhi dikhani chahiye jahan tool fail karta hai, warna aap ise over-trust kar lenge. Momentum tabhi help karta hai jab koi majority ho jiske taraf momentum ho sake. Even split mein koi nahi hoti.

PICTURE. Counter middle line ke aage-peeche slosh karta hua, essentially har step par mispredicting — ghati mein ball kabhi settle nahi hota.

WT (10) se trace karo: predict T, actual NT → miss, 10→01. Predict NT, actual T → miss, 01→10. Yeh 10 ↔ 01 oscillate karta hai aur har baar miss karta hai. Lean hamesha sach se ek step peeche hota hai.

Step 8 — Doosra edge: 3 bits kyun nahi? (over-resistance)

KYA HAI. Ek 3-bit counter mein 8 states ( $0$ – $7$ ) hain, middle par split: $4$ – $7$ ke liye T predict karo, $0$ – $3$ ke liye NT. Top se (111) prediction flip karne ke liye aapko ab 100 se 011 tak girna padega — chaar consecutive contrary outcomes.

KYUN yeh hurt kar sakta hai. Programs mein phases hote hain: ek branch kuch der ek tarah behave karta hai, phir hamesha ke liye badal jaata hai. Phase change ke baad, extra hysteresis ka matlab hai predictor kai extra branches ke liye purana phase guess karta rehta hai — delayed adaptation. Aap loop-noise misses kum karne ke badle mein phase-change misses zyada le lete hain.

PICTURE. Do ladders side by side. 2-bit ladder ko line cross karne ke liye 2 rungs chahiye; 3-bit ko 4. Arrows dikhate hain ki 3-bit predictor real behavior switch ke baad bhi kai extra steps tak galat hai.

Ek-picture summary

Upar sab kuch ek frame mein: chaar states unke MSB-split ke saath, loop ka clean climb-and-hold path (2 misses), alternating branch ki death-oscillation, aur "Strong se ek NT sirf Weak tak pahunchta hai" fact circled as the true reason for the win.

Recall Feynman retelling (plain words mein wapas bolo)

Branch ek morh hai; CPU ko bet lagani padti hai kidhar jaana hai yeh jaane bina. Bewaqoof bettor ek sticky note rakhta hai ("baaye jao"/"daaye jao") aur jab bhi haarta hai use flip karta hai — toh ek loop use do baar jalata hai: ek baar jab loop khatam hota hai aur ek baar jab loop phir shuru hota hai, kyunki end par flip ne note ko restart ke liye galat taraf pointing chhod diya. Samajhdar bettor ek confidence dial four notches ke saath rakhta hai: strongly-no, weakly-no, weakly-yes, strongly-yes. Sirf woh half jismein yeh hai bet decide karta hai. Ek akela surprise sirf dial ko ek notch click karta hai, middle ke across nahi. Toh jab loop khatam hota hai, dial strongly-yes se weakly-yes par girta hai — abhi bhi "yes" — aur restart sahi predict hota hai. Teen mistakes do ho jaate hain. Lekin agar branch genuinely har baar flip-flop karta hai, dial sirf middle ke aage-peeche rock karta hai aur lagaataar haarta hai — momentum tabhi help karta hai jab lean karne ke liye koi real majority ho. Aur ek bada dial (teen bits) itni zyada change resist karta hai ki jab branch sach mein apni aadat badal leta hai, toh bettor kai extra rounds tak galat rehta hai. Do bits stubbornness ki Goldilocks amount hai.

🇮🇳 Prefer Hinglish? → 5.3.08 2-bit saturating counter predictors (Hinglish)