2-bit saturating counter predictors

The Problem With 1-Bit Predictors

A 1-bit predictor stores one bit per branch: 0 = not-taken, 1 = taken. After every branch resolves, flip the bit if you were wrong.

Why this fails for loops:

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

• Iterations 0–9: branch TAKEN (correct prediction after first miss)
• Iteration 10: branch NOT-TAKEN (exit loop) → misprediction 1
• Next time loop runs, predictor now says "not-taken" → misprediction 2 on entry

The predictor oscillates, giving 2mises per loop instance instead of just 1. This is called aliasing or ping-ponging.

Prediction rule: If MSB = 1(states 10 or 11), predict TAKEN. If MSB = 0, predict NOT-TAKEN.

Update rule:

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

The counter "saturates" at the extremes—it cannot overflow. This hysteresis (resistance to quick change) prevents single anomalies from reversing the prediction.

State Transition Diagram

Each state has:

• Prediction: the current guess (T/NT)
• Two arcs: actual outcome = Taken (increment) or Not-Taken (decrement)

Notice: from ST (11), you need two consecutive not-takens to flip prediction to not-taken. This is the key anti-aliasing property.

Derivation: Why 2 Bits Fixes Loops

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

1. First iteration: miss (predictor was wrong), flip to T
2. Iterations 1–9: correct (all taken)
3. Iteration 10 (exit): miss, flip to NT
4. Next loop entry: miss, flip to T
5. Total: 3 misses per loop (first entry + exit + next entry)

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

1. First iteration (taken): 01→10 (WT), miss
2. Iterations 1–9 (taken): 10→11 (ST), all correct
3. Iteration 10 (not-taken): 11→10 (WT), miss but predictor STILL says taken
4. Next loop entry (taken): 10→11 (ST), correct
5. Total: 2 misses per loop (first entry + exit), improvement of 33%

Why this works: The "strongly" states (00, 11) act as momentum reservoirs. The loop exit (1 not-taken amid 10 takens) only moves the counter from ST→WT, not all the way to predicting not-taken. When the loop re-enters, the counter is still in the "taken" half (WT), so no misprediction.

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: Start ST (11)
• j=0: taken, 11→11 (stay ST) ✓
• j=1: taken, 11→11✓
• Exit: not-taken, 11→10 (WT) ✗
• Next i, j=0: taken, 10→11 ✓ ← no miss (this is the win)

Total for Branch B: 3 exits = 3 misses (unavoidable), but 0 re-entry misses (saved3).

Branch A (outer loop exit):

• Start ST
• i=0: taken, 11→11 ✓
• i=1: taken, 11→11 ✓
• i=2: taken, 11→11 ✓
• Exit: not-taken, 11→10 ✗
• Next program: varies, but often we stay inWT/ST if this code runs again soon

Total mises: 3 (inner exits) + 1 (outer exit) = 4 misses. A 1-bit predictor would add3 more re-entry misses →7 total.

Scenario: Branch executes TTTN (7 taken, 1 not-taken), repeats.

Why this step? At iteration 7, both predictors mispredict the exit. But 1-bit flips fully to NT, causing a miss at iteration 8. The 2-bit counter only moves to WT (still predicts T), so iteration 8 is correct.

Steady state: 1-bit has 2 misses/loop, 2-bit has 1 miss/loop (the unavoidable exit).

Implementation: Indexing the Counter Table

A bimodal predictor is a table of2-bit counters indexed by branch PC:

where $k$ is the table size exponent (e.g., $k=12$ → 4096 entries).

Why drop PC[1:0]? Instructions are 4-byte aligned (RISC) or variable-length (x86 but branch targets align), so the low2 bits are always 00. Using them wastes index space. PC[n:2] gives better coverage of unique branches.

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

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

Step 1: Extract relevant bits

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

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

• Keep lower 12 bits: 0b0001_1010_0011_11 = 0x6AF = 1711
• Index = 1711

Why this step? Modulo $2^k$ is equivalent to bitwise AND with $(2^k - 1)$, implemented as simple bit-slicing in hardware. The counter at table[1711] tracks this branch's behavior.

Aliasing: Multiple branches can map to the same index (destructive interference). If branch A (loop exit, biased NT) and branch B (loop body, biased T) collide, the counter thrashes. Solution: larger tables or tagged predictors (later topic).

Common Mistakes

The fix: Accuracy gain is pattern-dependent. For a branch that alternates TNTN (like if (x % 2)), even a 2-bit predictor achieves 0% accuracy—it always predicts the majority direction. The 2-bit counter helps loops and biased branches, not random or adversarial patterns.

Measured gain: Typical improvement is 5-10 percentage points in misprediction rate (e.g., 10%→5%), not doubling accuracy.

The fix: Branches are heavily biased toward taken (60-70% in SPEC benchmarks). Initializing to 10 (WT) or 11 (ST) warm-starts the predictor, reducing cold-start misses. Many commercial predictors init to 10 (weakly taken) as a compromise.

Why this step matters: On a branch's first execution, a cold predictor (state 00) mispredicts if the branch is taken. With 10 init, you guess correctly for the majority case.

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: Why Not 3-Bit or N-Bit?

Empirical result (Smith1981, McFarling 1993): 2-bit predictors achieve 95% of the benefit at 1/2 the cost of 3-bit. Modern predictors use 2-bit building blocks in more complex schemes (gshare, TAGE).

Now use 4 sticky notes in a row: "super-sure NO", "kinda NO", "kinda YES", "super-sure YES". When they play soccer, you move right. When they skip, you move left. If they skip once, you only move from "super YES" to "kinda YES"—you still predict YES for next time! You only switch to predicting NO if they skip twice in a row. This stops you from overeacting to one weird day. That's what a 2-bit counter does for the CPU guessing which way code will go.

Alternative: "Weak-Strong" states. The middle two states (01, 10) are "weak" (one more push flips you), the outer two (00, 11) are "strong" (fortress states).

Connections

• Branch Prediction Fundamentals – motivates why prediction matters (pipeline flush cost)
• 1-Bit Branch Predictors – predecessor; explains the aliasing problem
• Two-Level Adaptive Predictors – uses 2-bit counters as the underlying PHT mechanism
• BTB (Branch Target Buffer) – works alongside predictors to cache target addresses
• Pipeline Hazards – branch misprediction is a control hazard
• Gshare Predictor – indexes 2-bit counters with global history XOR PC

#flashcards/hardware

What are the four states in a 2-bit saturating counter? :: 00 (Strongly Not-Taken), 01 (Weakly Not-Taken), 10 (Weakly Taken), 11 (Strongly Taken)

Concept Map

Hinglish (regional understanding)