2-bit saturating counter predictors: Exercises — Hardware deep dive

Before we start, one shared picture. Every problem below reads a 2-bit saturating counter the same way. Keep this figure in view.

Figure — 2-bit saturating counter predictors

Recall The rules, in one place (open only if you forgot)

A 2-bit counter is a number from 0 to 3, shown as two bits:

00 = 0 Strongly Not-Taken (SNT)
01 = 1 Weakly Not-Taken (WNT)
10 = 2 Weakly Taken (WT)
11 = 3 Strongly Taken (ST)

Predict: top bit (the "MSB") is $1$ → predict Taken; top bit is $0$ → predict Not-Taken. Equivalently: state $\geq 2$ predicts Taken. Update after the branch resolves: Taken → add 1 but never go above 3 (saturate); Not-Taken → subtract 1 but never go below 0.

New here? Build the ground first: Branch Prediction Fundamentals, 1-Bit Branch Predictors, and the parent 2-Bit Saturating Counter Predictors.

Notation used everywhere below:

T = the branch was actually taken, N = actually not-taken.
✓ = the prediction matched the outcome (a hit), ✗ = a miss.
We write a trace as state --outcome--> newstate.
Bit-slice notation $PC [a : b]$ means "the bits of the program counter from position $a$ down to position $b$ , inclusive, read as a binary number", where bit $0$ is the lowest bit. So $PC [13 : 2]$ is the 12-bit chunk you get by throwing away the bottom 2 bits and keeping the next 12.

Level 1 — Recognition

L1.1 — Name the four states

State, for each 2-bit value, its full name and whether it predicts Taken or Not-Taken.

Recall Solution

Bits	Number	Name	Top bit	Prediction
00	0	Strongly Not-Taken	0	Not-Taken
01	1	Weakly Not-Taken	0	Not-Taken
10	2	Weakly Taken	1	Taken
11	3	Strongly Taken	1	Taken

The prediction only depends on the top bit — that is why states 0 and 1 both predict Not-Taken, and 2 and 3 both predict Taken.

L1.2 — One step of update

The counter is in state 10 (WT). The branch resolves Not-Taken. What is the new state, and did we predict correctly?

Recall Solution

Prediction from 10: top bit is 1 → predicted Taken. Actual was Not-Taken → ✗ miss. Update: not-taken means subtract 1: $2 - 1 = 1$ → new state 01 (WNT). Trace: 10 --N--> 01.

Level 2 — Application

L2.1 — Run a short trace

Start in state 01 (WNT). The branch outcomes are, in order: T, T, N, T. For each step give the prediction, whether it was a hit or miss, and the new state. How many misses total?

Recall Solution

Step	Outcome	State before	Predict	Hit?	State after
1	T	01	NT	✗	10
2	T	10	T	✓	11
3	N	11	T	✗	10
4	T	10	T	✓	11

Misses = 2 (steps 1 and 3). Notice step 3's single N only pulled us from 11 to 10 — we still predict Taken, so step 4 is a hit.

L2.2 — Compute a bimodal index

A branch sits at PC = 0x00401A3C. The bimodal table has $k = 12$ (so $2^{12} = 4096$ entries) and is indexed by $PC [13 : 2] mod 2^{12}$ . Find the index. (Recall $PC [13 : 2]$ = drop the bottom 2 bits, then keep the next 12.)

Recall Solution

The low 2 bits of the PC are always 00 for aligned instructions, so we drop them (shift right by 2). Then modulo $2^{12}$ = keep the lowest 12 bits. $PC = 0x00401A3C = 4, 201, 020$ Shift right 2: $4, 201, 020 \div 4 = 1, 050, 255$ . Keep low 12 bits: $1, 050, 255 mod 4096 = 1679$ . Index = 1679 (which is 0x68F). The counter at table[1679] tracks this branch's behaviour.

Prerequisite reading if the indexing feels new: BTB (Branch Target Buffer) uses the same PC-slicing idea.

Level 3 — Analysis

L3.1 — Loop miss count, head-to-head

A loop runs its back-edge branch as T T T T T T T T T N (9 taken, then 1 not-taken to exit), and the whole loop runs three times back-to-back, so the true stream is that 10-pattern repeated 3×. Both predictors start "warm": the 1-bit predictor holds 1 (predict T), the 2-bit counter holds 11 (ST). Count total misses for each.

Recall Solution

2-bit counter. During the 9 T's it sits at 11 (already saturated) → all ✓. The exit N does 11 --N--> 10, a miss, but 10 still predicts T. The next loop's first T does 10 --T--> 11, a hit. So each of the 3 loop instances costs exactly 1 miss (its exit). $2-bit misses = 3 \times 1 = 3$

1-bit predictor. During the 9 T's it holds 1 → all ✓. Exit N: predict T, actual N → miss, flips to 0. Next loop's first T: predict N, actual T → miss, flips back to 1. So each instance costs the exit miss and a re-entry miss = 2 misses — except the very last instance has no "next loop", so no re-entry miss after it. Instance 1: exit miss + re-entry miss = 2. Instance 2: 2. Instance 3: exit miss only = 1. $1-bit misses = 2 + 2 + 1 = 5$

The 2-bit counter's win is the re-entry misses it avoids — 2 of them here.

L3.2 — The counter you cannot fix

A branch alternates perfectly forever: T N T N T N …. Start the 2-bit counter in 11 (ST). Over a long run, what fraction of predictions are correct?

Recall Solution

Walk it: 11 --T--> 11 predicting T on a T ✓; 11 --N--> 10 predicting T on an N ✗; 10 --T--> 11 predicting T on a T ✓; 11 --N--> 10 ✗ … The counter oscillates between 11 and 10 and always predicts Taken. So it is correct on every T and wrong on every N → exactly 50% correct. A 2-bit counter cannot capture alternation; it only tracks which direction is the majority, and here neither direction is the majority. This is why the parent warns about "random or adversarial patterns".

Level 4 — Synthesis

L4.1 — Design the initial state

Branches in a benchmark are taken about 65% of the time, and 40% of all dynamic branches are executing for the first time (cold). You may initialise every counter to one fixed state. Which start state — 00, 01, 10, or 11 — minimises expected cold-start misses, and what is that expected cold miss rate?

Recall Solution

On a branch's first execution the counter is still at its init value, so the prediction is fixed by that value's top bit. There is no history yet.

Init 00 or 01 → top bit 0 → predict Not-Taken. On a cold branch you're right only when it's actually not-taken: probability $0.35$ . So cold miss rate $= 0.65$ .
Init 10 or 11 → top bit 1 → predict Taken. Right with probability $0.65$ . Cold miss rate $= 0.35$ .

Choose a Taken-predicting init (10 or 11) to match the 65% majority. Expected cold miss rate $= 0.35$ . Between 10 and 11, 10 (weakly taken) is the usual choice: same first-guess as 11 but only one confirming outcome away from committing, so a genuinely not-taken branch is corrected faster. This is exactly the parent note's "init to WT" advice.

L4.2 — Storage budget

You are given a 1 KB (= $1024 \times 8 = 8192$ bits) budget for the counter table. Each entry is a 2-bit counter. How many entries fit, and what is $k$ (the index width) if entries $= 2^{k}$ ?

Recall Solution

Entries $= \frac{8192 bits}{2 bits/entry} = 4096$ entries. Since $4096 = 2^{12}$ , the index width is $k = 12$ bits. This is the "4K-entry, 1 KB" bimodal predictor from the parent note — the numbers close the loop.

Level 5 — Mastery

L5.1 — Aliasing: two branches, one entry

Two branches map to the same counter (destructive aliasing). Branch X is a loop body, strongly biased taken. Branch Y is that loop's exit test, biased not-taken. They interleave as the loop runs: in one loop instance you see X X X X Y (four body iterations, each taken, then the exit not-taken), repeated 3×, all hitting the same shared counter. Start the shared counter at 11 (ST). How many misses occur, and how does this compare to X and Y each owning a private counter?

Recall Solution

Shared counter (aliasing). X is taken, Y (the exit) is not-taken; they collide on one 2-bit state. Trace one instance X X X X Y from 11:

11 --T(X)--> 11 ✓, 11 --T--> 11 ✓, 11 --T--> 11 ✓, 11 --T--> 11 ✓ (four X hits)
11 --N(Y)--> 10 : predicted T, actual N → ✗ (Y's exit miss)

Each instance ends at 10, and the next instance's first X 10 --T--> 11 is a hit. So per instance only Y's exit misses: total over 3 instances $= 3$ misses.

Private counters. X alone sees T T T T each instance → stays 11 → 0 misses. Y alone sees N once per instance, starting 11, and never gets a confirming T to climb back: 11 --N--> 10 (predict T, actual N → ✗), then 10 --N--> 01 (predict T, actual N → ✗), then 01 --N--> 00 (predict NT, actual N → ✓). So Y's private misses across the 3 instances are ✗, ✗, ✓ = 2 misses; X = 0. Total private $= 2$ .

Comparison: shared gives 3 misses, private gives 2 — the collision cost 1 extra miss. Aliasing hurt here: parking Y's not-taken outcomes on X's taken-heavy counter keeps re-arming the counter to "strongly taken", so Y never gets to learn its own not-taken bias and mispredicts its exit every single time (3×), whereas with a private counter Y drifts toward not-taken and eventually predicts one exit correctly. The damage scales with how much the two branches' biases oppose each other; bigger tables or history-based schemes (Gshare Predictor, Two-Level Adaptive Predictors) reduce collisions.

L5.2 — Prove the flip cost

Show, by counting arcs on the state diagram, that flipping a 2-bit counter's prediction from "predict Taken" to "predict Not-Taken" requires at least 2 consecutive not-taken outcomes when starting from ST, and compare to the general N-bit case.

Recall Solution

Prediction is set by the top bit. "Predict Taken" ⇔ state $\in {10, 11}$ ; "predict Not-Taken" ⇔ state $\in {00, 01}$ . The boundary is between 10 and 01.

From the deepest Taken state 11 (ST), each N subtracts 1: 11 --N--> 10 --N--> 01. The prediction top bit only changes when we cross from 10 to 01 — that is the second N. So 2 consecutive N are needed. One N (11→10) leaves the prediction unchanged.
N-bit generalisation: an $N$ -bit saturating counter has $2^{N}$ states; the prediction boundary sits at the middle, so from the top state you must walk $2^{N - 1}$ steps to cross it. For $N = 2$ : $2^{1} = 2$ ✓. For $N = 3$ : $2^{2} = 4$ consecutive N to flip — this is exactly the parent note's warning that 3-bit counters adapt too slowly through phase changes.

So the "how stubborn is the predictor" number is $2^{N - 1}$ , and $N = 2$ giving a modest 2 is the sweet spot between anti-aliasing and adaptability.

Recall Self-check: fill these in from memory

How does an N-bit counter's prediction flip cost scale? ::: It needs $2^{N - 1}$ consecutive opposite outcomes from the extreme state. Why init counters to 10 (WT) rather than 00? ::: Branches are ~65% taken; a Taken-predicting init matches the majority and cuts cold-start misses. Does the 2-bit predictor save the loop exit miss? ::: No — it saves the re-entry miss; the exit still misses for both 1-bit and 2-bit. What pattern defeats a 2-bit counter to 50% accuracy? ::: Perfect alternation T N T N …, because neither direction is the majority. Bimodal index for a 4K table? ::: $PC [13 : 2] mod 2^{12}$ = drop low 2 bits, keep low 12 of the rest.