Foundations — 2-bit saturating counter predictors

Before you can read the parent note 2-bit saturating counter predictors, every symbol it throws at you must already be a picture in your head. This page builds each one from nothing, in the order they depend on each other. (We deliberately avoid the words bit and pipeline above — they get defined below, in sections 4 and 2, before we lean on them.)

1. What is a "branch"?

A branch is any instruction that can change which instruction runs next. Normally the CPU runs line 1, then 2, then 3 — straight down. A branch is a fork: "if some condition is true, jump somewhere else; otherwise keep going straight."

The picture: a road that splits. Look at the fork in figure s01 — the green road is "Taken" (we jump up to the loop top), the red road is "Not-Taken" (we fall through and exit). Every branch is one of these forks. This is the thing predictors predict. See Branch Prediction Fundamentals for the wider view.

Why the topic needs it: the whole counter exists to answer one yes/no question — which road? — over and over for the same fork.

2. Why does guessing matter? The pipeline

Modern CPUs don't finish one instruction before starting the next. They work like an assembly line — a pipeline — with several instructions in flight at once, each at a different stage.

The fix: guess the road, and keep the line moving down that road. If the guess was right, we lost nothing. If wrong, we throw away the wrongly-fetched instructions (a misprediction penalty) and restart. See Pipeline Hazards.

Why the topic needs it: this is the motive. Without pipelines, prediction would be pointless.

3. The symbols T, N, and the outcome string

The parent writes things like TTTN and "iterations 0–9 taken". Let's pin these down.

The picture: a row of traffic lights, green = $T$, red = $N$, read like a sentence. A loop that runs 10 times then exits produces $\underset{10}{\underbrace{TTT\dots T}}N$ — ten greens then one red.

Why the topic needs it: the counter's job is to look at the history so far and predict the next letter.

4. Bits, and reading a 2-bit number

A bit is a single 0 or 1 — one light switch, off or on. Two bits side by side make a 2-bit number.

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

Why the MSB matters here: the parent's prediction rule is "if MSB = 1, predict Taken". So the left bit alone decides the guess; the right bit only records how sure we are. Hold that thought — figure s02 makes it visual.

Why the topic needs it: the counter is a 2-bit number. You cannot read a single line of the note without reading these four patterns.

5. A counter that can go up and down

A counter here is just that 2-bit number, but with rules for changing it.

The picture: a slider with four notches, shown in figure s02. Taken pushes the slider right; Not-Taken pushes it left; the walls at both ends stop it from falling off. The two right notches are painted "predict Taken", the two left notches "predict Not-Taken".

Why the topic needs it: "saturating counter" is literally the name of the topic. Increment, decrement, the walls, and a defined starting notch are its entire mechanism.

6. Hysteresis — the "grudge" in one word

The picture: think of a heavy door on a spring. One tap doesn't open it; you need to keep pushing. The strong states ($00$ and $11$) are that heavy door. From $11$ (Strongly Taken), a single $N$ only drops you to $10$ — still on the "Taken" side. You need two $N$'s in a row to actually flip the prediction.

Why the topic needs it: this single word explains why 2 bits beats 1 bit. A 1-bit predictor has zero hysteresis — one surprise flips it, and loops make it flip twice per pass.

7. Program-counter, indexing, and modulo

The parent stores many counters — one per branch — in a table. To find the right one it uses the branch's address.

The picture: a wall of $2^k$ mailboxes. The PC is a long name; we shorten it (drop 2 bits, keep $k$ bits) to a box number, and that box holds this branch's 2-bit counter.

Why the topic needs it: without indexing there is only one counter for the whole program, which is useless. The BTB (Branch Target Buffer) does the parallel job of remembering where the taken branch jumps to.

8. Putting the four states together

Now every piece exists, so the parent's state names finally read as plain English:

Figure s03 is the finished state machine: four boxes, each with a $T$-arrow (increment, move right) and an $N$-arrow (decrement, move left), with the walls looping back at the ends. The dashed line down the middle is the prediction boundary — right of it we guess Taken, left we guess Not-Taken. Everything the parent note derives is a walk along these arrows, starting from the cold-start notch $10$.

Why the topic needs it: this diagram is the predictor. The whole note is just tracing paths through it for loops, nested loops, and cold starts.

Prerequisite map

Equipment checklist

Cover the right side and test yourself. If any line surprises you, re-read its section above.