Foundations — 2-bit saturating counter predictors

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

Parent note 2-bit saturating counter predictors padhne se pehle, usmein aane wala har symbol pehle se tumhare dimaag mein ek picture ban chuka hona chahiye. Yeh page har ek ko kuch nahi se banata hai, uss order mein jismein ek doosre par depend karte hain. (Humne upar jaanbujhkar bit aur pipeline words use nahi kiye — inhe neeche, sections 4 aur 2 mein define kiya gaya hai, inhe use karne se pehle.)

1. "Branch" kya hota hai?

Ek branch koi bhi instruction hai jo badal sakti hai ki aage kaun si instruction chalegi. Normally CPU line 1 chalata hai, phir 2, phir 3 — seedha neeche. Branch ek fork hai: "agar koi condition true hai, toh kahin aur jump karo; warna seedhe chalte raho."

Picture: ek road jo split hoti hai. Figure s01 mein fork dekho — green road "Taken" hai (hum loop ke top par jump karte hain), red road "Not-Taken" hai (hum fall through karke exit karte hain). Har branch inhi forks mein se ek hoti hai. Yahi cheez predictors predict karte hain. Wider view ke liye Branch Prediction Fundamentals dekho.

Topic ko isko kyun chahiye: poora counter ek hi yes/no question ka jawab dene ke liye exist karta hai — kaun si road? — usi fork ke liye baar baar.

2. Guessing kyun matter karti hai? Pipeline

Modern CPUs ek instruction finish hone se pehle doosri shuru nahi karte. Yeh ek assembly line ki tarah kaam karte hain — ek pipeline — jismein kai instructions ek saath chal rahi hoti hain, har ek alag stage par.

Fix: road ko guess karo, aur line ko usi road par chalte raho. Agar guess sahi nikla, kuch nahi gaya. Agar galat nikla, toh galat tarike se fetch ki gayi instructions ko throw away karo (ek misprediction penalty) aur restart karo. Pipeline Hazards dekho.

Topic ko isko kyun chahiye: yahi motivation hai. Pipelines ke bina, prediction ka koi matlab nahi hota.

3. Symbols T, N, aur outcome string

Parent note TTTN jaisi cheezein likhta hai aur "iterations 0–9 taken" keh ta hai. Inhe theek se pin down karte hain.

Picture: traffic lights ki ek row, green = $T$, red = $N$, ek sentence ki tarah padho. Ek loop jo 10 baar chalta hai phir exit karta hai produce karta hai $\underset{10}{\underbrace{TTT\dots T}}N$ — das green phir ek red.

Topic ko isko kyun chahiye: counter ka kaam hai abhi tak ki history dekhna aur agla letter predict karna.

4. Bits, aur ek 2-bit number padhna

Ek bit ek single 0 ya 1 hai — ek light switch, off ya on. Do bits side by side mila ke ek 2-bit number banta hai.

$\underset{\text{MSB (worth }2)}{\boxed{1}}\underset{\text{LSB (worth }1)}{\boxed{0}}=2\times 1+1\times 0=2$

MSB yahan kyun matter karta hai: parent ka prediction rule hai "agar MSB = 1, toh predict Taken". Toh sirf baaya bit guess decide karta hai; daaya bit sirf record karta hai hum kitne sure hain. Yeh soch apne paas rakhna — figure s02 ise visual banata hai.

Topic ko isko kyun chahiye: counter ek 2-bit number hi hai. Note ki ek bhi line padhe bina in chaar patterns ko padhe nahi ja sakta.

5. Ek counter jo upar aur neeche ja sakta hai

Ek counter yahan bas wahi 2-bit number hai, lekin badalne ke rules ke saath.

Picture: chaar notch wala ek slider, figure s02 mein dikhaya gaya hai. Taken slider ko daaye dhakelta hai; Not-Taken baaye dhakelta hai; dono ends par diwaaren ise girne se rokti hain. Do daaye notch "predict Taken" painted hain, do baaye "predict Not-Taken".

Topic ko isko kyun chahiye: "saturating counter" literally topic ka naam hai. Increment, decrement, diwaaren, aur ek defined starting notch — yahi iski poori mechanism hai.

6. Hysteresis — ek word mein "grudge"

Picture: sochna ek heavy door spring par hai. Ek tap se nahi khulti; tumhe push karte rehna padta hai. Strong states ($00$ aur $11$) woh heavy door hain. $11$ (Strongly Taken) se, ek single $N$ tumhe sirf $10$ tak girata hai — abhi bhi "Taken" side par. Prediction actually flip karne ke liye tumhe do $N$'s ek saath chahiye.

Topic ko isko kyun chahiye: yeh akela word explain karta hai kyun 2 bits 1 bit se behtar hai. Ek 1-bit predictor mein zero hysteresis hai — ek surprise use flip kar deta hai, aur loops ise har pass mein do baar flip karate hain.

7. Program-counter, indexing, aur modulo

Parent note bohot saare counters store karta hai — har branch ke liye ek — ek table mein. Sahi wala dhundhne ke liye yeh branch ka address use karta hai.

Picture: $2^k$ mailboxes ki ek deewar. PC ek lamba naam hai; hum ise shorten karte hain (2 bits drop karo, $k$ bits rakho) ek box number tak, aur woh box is branch ka 2-bit counter rakhta hai.

Topic ko isko kyun chahiye: indexing ke bina pure program ke liye sirf ek counter hoga, jo useless hai. BTB (Branch Target Buffer) parallel kaam karta hai kahan taken branch jump karta hai yeh yaad rakhne ka.

8. Charon states ko saath mein rakhna

Ab har piece exist karta hai, toh parent note ke state names finally plain English mein padhte hain:

Figure s03 finished state machine hai: chaar boxes, har ek mein ek $T$-arrow (increment, daaye jao) aur ek $N$-arrow (decrement, baaye jao), ends par walls loop back ke saath. Beech mein dashed line prediction boundary hai — uske daaye Taken guess karte hain, baaye Not-Taken. Parent note jo bhi derive karta hai woh sab inhi arrows par walks hain, cold-start notch $10$ se shuru hokar.

Topic ko isko kyun chahiye: yeh diagram hi predictor hai. Poora note sirf loops, nested loops, aur cold starts ke liye inhi arrows par paths trace karna hai.

Prerequisite map

Equipment checklist

Daaya side cover karo aur khud ko test karo. Agar koi line surprise karti hai, uska section upar dobara padho.