2-bit saturating counter predictors

5.3.8 · Hardware › Advanced Microarchitecture

1-Bit Predictors Ki Problem

Ek 1-bit predictor har branch ke liye ek bit store karta hai: 0 = not-taken, 1 = taken. Jab bhi branch resolve hoti hai, agar galat the to bit flip kar do.

Yeh loops ke liye kyun fail hota hai:

for (i = 0; i < 10; i++) { ... }  // branch: if (i < 10) goto loop

• Iterations 0–9: branch TAKEN (pehli miss ke baad correct prediction)
• Iteration 10: branch NOT-TAKEN (loop exit) → misprediction 1
• Agli baar jab loop chale, predictor ab "not-taken" kehta hai → entry par misprediction 2

Predictor oscillate karta rehta hai, jisse 2 misses per loop instance milte hain sirf 1 ki jagah. Ise aliasing ya ping-ponging kehte hain.

Prediction rule: Agar MSB = 1 (states 10 ya 11), to TAKEN predict karo. Agar MSB = 0, to NOT-TAKEN predict karo.

Update rule:

• Branch taken: increment karo (11 par saturate karo)
• Branch not-taken: decrement karo (00 par saturate karo)

Counter extremes par "saturate" karta hai—yeh overflow nahi kar sakta. Yeh hysteresis (jaldi change hone ki resistance) akele anomalies ko prediction reverse karne se rokti hai.

State Transition Diagram

Har state mein hota hai:

• Prediction: current guess (T/NT)
• Do arcs: actual outcome = Taken (increment) ya Not-Taken (decrement)

Notice karo: ST (11) se, prediction not-taken mein flip karne ke liye do consecutive not-takens chahiye. Yahi key anti-aliasing property hai.

Derivation: 2 Bits Loops Ko Kyun Fix Karta Hai

1-bit loop behavior (10 iterations, "predict-taken" mein start):

1. Pehla iteration: miss (predictor galat tha), T mein flip karo
2. Iterations 1–9: correct (sab taken)
3. Iteration 10 (exit): miss, NT mein flip karo
4. Agla loop entry: miss, T mein flip karo
5. Total: 3 misses per loop (pehla entry + exit + agla entry)

2-bit loop behavior (state 01 WNT mein start):

1. Pehla iteration (taken): 01→10 (WT), miss
2. Iterations 1–9 (taken): 10→11 (ST), sab correct
3. Iteration 10 (not-taken): 11→10 (WT), miss lekin predictor ABHI BHI taken kehta hai
4. Agla loop entry (taken): 10→11 (ST), correct
5. Total: 2 misses per loop (pehla entry + exit), 33% improvement

Yeh kyun kaam karta hai: "Strongly" states (00, 11) momentum reservoirs ki tarah kaam karte hain. Loop exit (10 takens mein 1 not-taken) counter ko sirf ST→WT tak move karta hai, not-taken predict karne tak nahi. Jab loop re-enter karta hai, counter abhi bhi "taken" half (WT) mein hai, isliye koi misprediction nahi hoti.

for (int i = 0; i < 3; i++) {       // Branch A
    for (int j = 0; j < 2; j++) {   // Branch B
        // work
    }
}

Branch B (inner loop exit):

• State trace: ST (11) se start karo
• j=0: taken, 11→11 (ST mein raho) ✓
• j=1: taken, 11→11 ✓
• Exit: not-taken, 11→10 (WT) ✗
• Agla i, j=0: taken, 10→11 ✓ ← koi miss nahi (yahi fayda hai)

Branch B ka total: 3 exits = 3 misses (unavoidable), lekin 0 re-entry misses (3 save kiye).

Branch A (outer loop exit):

• ST se start karo
• i=0: taken, 11→11 ✓
• i=1: taken, 11→11 ✓
• i=2: taken, 11→11 ✓
• Exit: not-taken, 11→10 ✗
• Agla program: vary karta hai, lekin agar yeh code dobara jaldi chale to aksar WT/ST mein rahte hain

Total misses: 3 (inner exits) + 1 (outer exit) = 4 misses. Ek 1-bit predictor 3 aur re-entry misses add karta →7 total.

Scenario: Branch TTTN (7 taken, 1 not-taken) execute karta hai, repeat karta hai.

Yeh step kyun? Iteration 7 par, dono predictors exit ko mispredict karte hain. Lekin 1-bit puri tarah NT mein flip ho jaata hai, jisse iteration 8 par miss hoti hai. 2-bit counter sirf WT mein move karta hai (abhi bhi T predict karta hai), isliye iteration 8 correct hai.

Steady state: 1-bit mein 2 misses/loop hain, 2-bit mein 1 miss/loop hai (unavoidable exit).

Implementation: Counter Table Ko Index Karna

Ek bimodal predictor 2-bit counters ki ek table hai jo branch PC se index hoti hai:

jahan $k$ table size exponent hai (jaise, $k=12$ → 4096 entries).

PC[1:0] drop kyun karte hain? Instructions 4-byte aligned hote hain (RISC) ya variable-length (x86 lekin branch targets align karte hain), isliye low 2 bits hamesha 00 hote hain. Unhe use karna index space waste karta hai. PC[n:2] unique branches ki better coverage deta hai.

Storage cost: $2^k\times 2\text{ bits}$. Example: 4K-entry table = $4096\times 2=8\text{ Kbit}=1\text{ KB}$.

PC = 0x00401A3C (hexadecimal) par branch, 4K-entry table ($k=12$):

Step 1: Relevant bits extract karo

• PC = 0x00401A3C = 0b000_0000_0100_0000_0001_1010_0011_1100
• PC[31:2] = 0b0000_0100_0000_0001_1010_0011_11 (2 se right shift karo)

Step 2: Modulo $2^{12}=4096$

• Lower 12 bits rakho: 0b0001_1010_0011_11 = 0x6AF = 1711
• Index = 1711

Yeh step kyun? Modulo $2^k$ bitwise AND ke barabar hai $(2^k-1)$ ke saath, jo hardware mein simple bit-slicing ke roop mein implement hota hai. Table[1711] par counter is branch ke behavior ko track karta hai.

Aliasing: Multiple branches same index par map ho sakti hain (destructive interference). Agar branch A (loop exit, NT biased) aur branch B (loop body, T biased) collide karein, to counter thrash karta hai. Solution: badi tables ya tagged predictors (baad ka topic).

Common Mistakes

Fix: Accuracy gain pattern-dependent hoti hai. Ek branch jo TNTN alternate karti hai (jaise if (x % 2)), uske liye 2-bit predictor bhi 0% accuracy achieve karta hai—yeh hamesha majority direction predict karta hai. 2-bit counter loops aur biased branches ke liye help karta hai, random ya adversarial patterns ke liye nahi.

Measured gain: Misprediction rate mein typical improvement 5-10 percentage points hoti hai (jaise 10%→5%), accuracy double nahi hoti.

Fix: Branches heavily taken ki taraf biased hoti hain (SPEC benchmarks mein 60-70%). 10 (WT) ya 11 (ST) se initialize karna predictor ko warm-start karta hai, cold-start misses reduce karta hai. Kai commercial predictors compromise ke roop mein 10 (weakly taken) se init karte hain.

Yeh step kyun matter karta hai: Branch ki pehli execution par, cold predictor (state 00) mispredict karta hai agar branch taken hai. 10 init ke saath, majority case ke liye sahi guess milta hai.

Code check:

def update_counter(state, taken):
    if taken:
        return min(state + 1, 3)  # saturate at 11 (3)
    else:
        return max(state - 1, 0)  # saturate at 00 (0)

Advanced: 3-Bit Ya N-Bit Kyun Nahi?

Empirical result (Smith 1981, McFarling 1993): 2-bit predictors 3-bit ki 1/2 cost par 95% benefit achieve karte hain. Modern predictors zyada complex schemes (gshare, TAGE) mein 2-bit building blocks use karte hain.

Ab 4 sticky notes ek row mein use karo: "super-sure NO", "kinda NO", "kinda YES", "super-sure YES". Jab woh soccer khele, right move karo. Jab skip kare, left move karo. Agar woh ek baar skip kare, to tum sirf "super YES" se "kinda YES" par aate ho—tum agli baar ke liye ABHI BHI YES predict karte ho! Tum NO predict karna tabhi shuru karte ho jab woh do baar lagaataar skip kare. Yeh tumhe ek weird din par overreact karne se rokta hai. Yahi kaam 2-bit counter CPU ke liye karta hai jab yeh guess karta hai ki code kis taraf jayega.

Alternative: "Weak-Strong" states. Beech ke do states (01, 10) "weak" hain (ek aur push se flip ho jaate ho), bahar ke do (00, 11) "strong" hain (fortress states).

Connections

• Branch Prediction Fundamentals – motivate karta hai ki prediction kyun matter karti hai (pipeline flush cost)
• 1-Bit Branch Predictors – predecessor; aliasing problem explain karta hai
• Two-Level Adaptive Predictors – underlying PHT mechanism ke roop mein 2-bit counters use karta hai
• BTB (Branch Target Buffer) – predictors ke saath milkar target addresses cache karta hai
• Pipeline Hazards – branch misprediction ek control hazard hai
• Gshare Predictor – 2-bit counters ko global history XOR PC se index karta hai

#flashcards/hardware

2-bit saturating counter mein char states kya hain? :: 00 (Strongly Not-Taken), 01 (Weakly Not-Taken), 10 (Weakly Taken), 11 (Strongly Taken)

Concept Map