Visual walkthrough — 2-bit saturating counter predictors
This page rebuilds the central result of 2-Bit Saturating Counter Predictors from the ground up — in pictures. We will not use a single word like "counter", "state", or "saturate" before you can see it. By the end you will be able to draw the machine, trace it, and prove why 2 bits turns 3 mistakes into 2 on a loop.
If you have never met these words, read Branch Prediction Fundamentals and 1-Bit Branch Predictors first — but I will re-derive everything you need, so you can also just start here.
Step 1 — What is a "branch" and what does it mean to "predict" it?
WHAT. A branch is a fork in the road inside a program. The CPU reaches a goto-like instruction and must go one of two ways: the jump happens (we call this Taken, written T) or it does not (Not-Taken, written NT).
WHY we must guess. A modern CPU is a pipeline — it starts working on the next instruction before it has finished the current one. But at a branch it does not yet know which way the road goes. Rather than freeze and wait, it guesses and keeps working. A right guess costs nothing. A wrong guess (a misprediction) means throwing away the work — expensive. So our whole goal is: make fewer wrong guesses.
PICTURE. The fork, the two roads T and NT, and a little box "predictor" whose only job is to whisper "go left" or "go right" before the CPU knows the truth.
Step 2 — The simplest guesser (1 bit) and the trap it falls into
WHAT. The smallest possible memory is one bit: 0 means "I predict NT", 1 means "I predict T". The rule: after the branch resolves, if you were wrong, flip the bit.
WHY it seems fine. For a branch that does the same thing forever, one wrong guess fixes the bit and you are correct ever after. Cheap and simple.
PICTURE. Look at a loop that runs 10 times. The branch says "keep looping? T" nine times, then "exit? NT" once — then the loop starts again later and says "T" again. Watch the single bit flip at the two boundaries.
The trap is in the picture's red flips. The exit forces the bit to 0. But the next time the loop runs, the very first branch is T again — and the bit still says 0. So you miss on the way out AND on the way back in. That double-hit is called aliasing or ping-ponging.
Step 3 — The idea that fixes it: give the guesser momentum
WHAT. Instead of a bit that flips on a single mistake, use a small number that goes up on T and down on NT, and let the number's sign (top half vs bottom half) decide the prediction. One stray NT only nudges the number — it does not flip the prediction.
WHY. A loop is T,T,T,…,T,NT — a long agreement with one contrarian at the end. We want a memory that treats that lone NT as noise, not as a reason to change its mind. That is exactly what "resist a single change" — hysteresis — means.
PICTURE. A ball in a valley. Pushing right (T) rolls it toward the "predict T" side; pushing left (NT) rolls it back. One left-push from the far-right does not reach the other side.
Step 4 — Make the number concrete: four states, a 2-bit machine
WHAT. Two bits count from 00 to 11, i.e. the numbers . We name them by lean + strength:
Reading the symbols: S = Strongly, W = Weakly, N = Not, T = Taken. The vertical bar splits the bottom half (00,01) from the top half (10,11).
Prediction rule — read the top bit only. The most-significant bit (MSB) is the lean:
The MSB is doing all the work of the old 1-bit predictor; the low bit is the new confidence memory.
Update rule — count. On outcome T, add 1 but never pass 11. On outcome NT, subtract 1 but never pass 00. "Never pass the end" is saturation: 11 + 1 = 11, not 00. It clips; it does not wrap.
WHY these exact four. Two states per lean is the minimum that lets a lone surprise cost only confidence (ST→WT) while keeping the lean (still T). Fewer states = no room for confidence; more states = we'll see in Step 8 it over-resists.
PICTURE. The four states in a row, the split line for the MSB, the +1/−1 arrows, and the two saturation walls where the arrows bounce back.
Step 5 — Draw the full state machine (the arcs that matter)
WHAT. Give every state its two arcs: one for actual outcome T (move up / stay at 11) and one for actual NT (move down / stay at 00).
WHY draw it. The single most important fact of this whole topic is a geometric one you can literally point at: to change the prediction you must cross the middle line, and from a Strong state that takes two contrary outcomes in a row, not one.
PICTURE. All four states, all eight arcs. Yellow = T arcs, pink = NT arcs. The dashed line down the middle is "the prediction flips here". Notice from ST a single NT only reaches WT — still above the line, still predicting T.
Recall
From ST (11), how many not-takens in a row do you need before the prediction becomes NT? ::: Two — 11 → 10 (still predict T) then 10 → 01 (now predict NT).
Which bit of the state is the actual prediction? ::: The MSB (top bit).
Step 6 — Run the loop through the machine (the payoff, traced)
WHAT. Take the same 10-iteration loop from Step 2, but start the counter at 01 (WNT) and trace it. Same input T,T,…,T,NT, then a re-entry T.
WHY start at 01. We want a fair fight vs the 1-bit predictor, which started leaning NT. 01 also leans NT, so both begin equally "cold".
PICTURE. The counter's path drawn as a walk over the four states, with red bursts on the two misses and a green tick on the crucial re-entry.
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! |
The win, stated exactly. The exit's lone NT only knocked ST → WT. WT still has MSB = 1, so it still predicts T. When the loop returns, the first T is predicted correctly — the re-entry miss of Step 2 is gone.
Step 7 — The degenerate case: alternating T,NT,T,NT (why 2 bits is not magic)
WHAT. Feed the machine a branch that truly alternates, like if (i % 2): T, NT, T, NT, …, starting anywhere.
WHY show it. A good walkthrough must show where the tool fails, or you will over-trust it. Momentum only helps when there is a majority to have momentum toward. An even split has none.
PICTURE. The counter sloshing back and forth across the middle line, mispredicting on essentially every step — the ball rocking in the valley, never settling.
Trace from WT (10): predict T, actual NT → miss, 10→01. Predict NT, actual T → miss, 01→10. It oscillates 10 ↔ 01 and misses every time. The lean is always one step behind the truth.
Step 8 — The other edge: why not 3 bits? (over-resistance)
WHAT. A 3-bit counter has 8 states (–), split at the middle: predict T for –, NT for –. To flip prediction from the top (111) you now need to fall past 100 to 011 — four contrary outcomes in a row.
WHY it can hurt. Programs have phases: a branch behaves one way for a while, then switches for good. After a phase change, extra hysteresis means the predictor keeps guessing the old phase for several extra branches — delayed adaptation. You trade fewer loop-noise misses for more phase-change misses.
PICTURE. Two ladders side by side. The 2-bit ladder needs 2 rungs to cross the line; the 3-bit needs 4. Arrows show the 3-bit predictor still wrong for extra steps after a real behavior switch.
The one-picture summary
Everything above in one frame: the four states with their MSB-split, the loop's clean climb-and-hold path (2 misses), the alternating branch's death-oscillation, and the "one NT from Strong only reaches Weak" fact circled as the true reason for the win.
Recall Feynman retelling (say it back in plain words)
A branch is a fork; the CPU has to bet which way before it knows. The dumb bettor keeps one sticky note ("go left"/"go right") and flips it whenever it loses — so a loop burns it twice: once when the loop ends and once when the loop starts again, because the flip at the end left the note pointing the wrong way for the restart. The smart bettor keeps a confidence dial with four notches: strongly-no, weakly-no, weakly-yes, strongly-yes. Only which half it's in decides the bet. A single surprise just clicks the dial one notch, not across the middle. So when the loop ends, the dial drops from strongly-yes to weakly-yes — still "yes" — and the restart is predicted right. Three mistakes become two. But if the branch genuinely flip-flops every single time, the dial just rocks across the middle forever and loses constantly — momentum only helps when there's a real majority to lean into. And a bigger dial (three bits) resists change so hard that when a branch truly changes its habits, the bettor stays wrong for several extra rounds. Two bits is the Goldilocks amount of stubbornness.
🇮🇳 Prefer Hinglish? → 5.3.08 2-bit saturating counter predictors (Hinglish)