2-bit saturating counter predictors: Worked examples

This page is the exhaustive drill room for 2-bit saturating counters. Before you read a single example, make sure you already know from the parent note that a 2-bit counter is a tiny machine with four states, and that the most-significant bit (MSB) — the leftmost bit — is the whole prediction:

Recall The one rule you must have before starting

The 2-bit state is written as two binary digits, e.g. 10. The left digit is the MSB. ==If MSB = 1, predict TAKEN. If MSB = 0, predict NOT-TAKEN.== "Taken" means the branch jumps; "not-taken" means execution falls through. Update: taken → +1 (add one, but never go above 11), not-taken → −1 (subtract one, but never go below 00).

Definition The symbols and words we use everywhere below

Read this key once — every example reuses it.

T = the branch outcome was Taken (it jumped). N = the branch outcome was Not-taken (it fell through). A stream like TTTN means "taken, taken, taken, not-taken" in that order.
The four states are 00 (Strongly Not-Taken), 01 (Weakly Not-Taken), 10 (Weakly Taken), 11 (Strongly Taken).
The program counter (PC) is the register holding the memory address of the instruction currently executing — for a branch, it is the branch's own address.
A bit-slice like PC[3:2] means "the piece of that binary address made of bit number 3 and bit number 2" (bits are numbered from 0 at the right). So PC[1:0] is the lowest two bits, and PC[3:2] is the next two up. We use bit-slices to turn a big address into a small table index.

If any of those words feel shaky, go back to Branch Prediction Fundamentals and 1-Bit Branch Predictors first.

The scenario matrix

A 2-bit counter is driven by exactly one thing: a stream of outcomes (each T or N). Every situation you will ever meet is one shape of that stream. Here is every shape class this topic can throw at you.

Cell	Scenario class	What makes it "extreme"	Covered by
C1	Long run of one direction	Tests saturation (does it clip at `11`/`00`?)	Ex 1
C2	Biased loop (many T, one N, repeat)	Tests hysteresis — the reason 2-bit exists	Ex 2
C3	Cold start, wrong initial guess	Tests first-execution behaviour	Ex 3
C4	Alternating T N T N (adversarial)	The degenerate worst case: 0% accuracy	Ex 4
C5	Both boundaries in one trace (`00`↔`11`)	Tests both saturation floors	Ex 5
C6	Nested loops (two counters at once)	Real multi-branch word problem	Ex 6
C7	Phase change (bias flips mid-stream)	Limiting behaviour — hysteresis becomes a cost	Ex 7
C8	Aliasing collision (two branches, one entry)	Exam twist — indexing & interference	Ex 8

The eight examples below fill every cell. Each one gives you a Forecast line — cover the rest of the example and guess the answer first. That guess is where the learning happens.

Figure s01 below is the reference picture you will use in every example. It shows all four states laid out on one number line, and it labels the amber dashed line as the MSB flip boundary — the place where the prediction changes from NT to T:

Figure — 2-bit saturating counter predictors

Read it as a number line: states 00–11 run left to right, and the amber dashed line labelled "MSB flip boundary" sits between 01 and 10. Whenever a trace crosses that line, the prediction changes — watch for it in Ex 4 and Ex 5.

C1 — Saturation under a long run

Start 01 → MSB = 0 → predicts NT. First outcome is T. Prediction wrong → miss 1. Update taken: 01 + 1 = 10. Why this step? We always predict before seeing the outcome, then update. The first prediction used the initial state, which guessed NT.
10 → MSB = 1 → predicts T. Outcome T → correct. Update: 10 + 1 = 11. Why this step? One correct taken pushed us into the "taken half" already.
11 → predicts T. Outcome T → correct. Update: 11 + 1 = 11 (clipped!). Why this step? This is saturation: 11 is the maximum, adding one keeps it at 11. It does not wrap to 00.
Outcomes 4, 5, 6: all T, all correct, all stay at 11.

Result: exactly 1 miss (the cold first guess), final state 11.

C2 — Hysteresis: the biased loop (the headline case)

2-bit trace, steady state (start each loop at 11):

7 × T: 11→11 every time (saturated). All correct. Why this step? Each taken outcome is a "+1" that clips at 11, so the whole body of the loop is free hits.
Exit N: 11 predicts T, outcome N → miss. Update: 11 − 1 = 10. Why this step? One anomaly only nudges us to 10 (still MSB = 1). This is hysteresis — the "strongly taken" reservoir absorbs the single N.
Next loop's first T: 10 predicts T, outcome T → correct. Update 10→11. Why this step? Because we stayed in the taken half, re-entry is a hit. This is the whole point of 2-bit.

2-bit misses per loop = 1 (only the exit).

1-bit trace, steady state (a 1-bit predictor stores just one bit: 1=predict T, 0=predict NT, and it becomes whatever the last outcome was). Start each loop with the bit = 1:

7 × T: bit is 1 → predicts T, outcome T → correct each time. Update: bit stays 1. Why this step? With one bit there is no reservoir — but while outcomes agree with the bit, it simply stays put and keeps hitting.
Exit N: bit 1 predicts T, outcome N → miss. Update: bit becomes 0. Why this step? One bit has no hysteresis — a single N flips the entire prediction immediately.
Next loop's first T: bit 0 predicts NT, outcome T → miss. Update: bit becomes 1. Why this step? Because the exit already flipped the bit to NT, the re-entry taken is now mispredicted. This is the extra miss the 2-bit counter avoided in its step 3.

1-bit misses per loop = 2 (exit + re-entry).

C3 — Cold start with the wrong initial guess

Init 00:

00 predicts NT, outcome T → miss. Update taken: 00 + 1 = 01. Why this step? MSB of 00 is 0, so we guessed NT, but the branch was taken — wrong. A taken outcome is "+1", moving 00→01.
01 predicts NT, outcome T → miss. Update taken: 01 + 1 = 10. Why this step? 01 still has MSB 0, so still predicts NT and still misses. The "+1" now crosses into the taken half, 01→10.
10 predicts T, outcome T → correct. Update taken: 10 + 1 = 11. Why this step? Only now (MSB = 1) does the guess match reality — it took two takens to climb out of the not-taken half. → 2 cold misses.

Init 10:

10 predicts T, outcome T → correct. Update taken: 10 + 1 = 11. Why this step? Starting already in the taken half, the very first prediction is right; the taken outcome is a "+1" to 11.
11 predicts T, outcome T → correct. Update taken: 11 + 1 = 11 (clipped). Why this step? Saturation — 11 is the ceiling, so "+1" stays at 11.
11 predicts T, outcome T → correct. Stays 11. Why this step? Same saturated hit; the counter never leaves the strongly-taken state. → 0 cold misses.

Why this matters: real branches are ~60–70% taken, so guessing "taken" from the start (init 10) wins on the common case. This is why the parent note warns against defaulting to 00.

C4 — The degenerate worst case: perfect alternation

Trace it out:

Step	State (pred)	Outcome	Right?	Next state
1	`10` (T)	T	✓	`11`
2	`11` (T)	N	✗	`10`
3	`10` (T)	T	✓	`11`
4	`11` (T)	N	✗	`10`

Why this step (row 1)? At 10 the MSB is 1, so we predict T; the outcome is T, so we increment 10→11. A correct taken always pushes the counter up. Why this step (row 2)? At 11 we still predict T, but the outcome is N, so we decrement 11→10. Crucially the counter lands on 10, which is still in the taken half (see figure s01) — it never reaches the amber flip boundary, so the prediction never switches to NT. Why the loop is trapped: rows 3–4 repeat rows 1–2 exactly. The single T pushes up, the single N pushes back down, and the counter oscillates 10↔11 forever without crossing the MSB flip boundary.

The counter is trapped bouncing 10↔11, always predicting T, but the true answer is T only half the time.

C5 — Both boundaries: from `11` all the way to `00`

11 predicts T, outcome N → miss. 11→10.
10 predicts T, outcome N → miss. 10→01. ← prediction now flips: MSB became 0. Why this step? Crossing from 10 to 01 moves us across the amber MSB flip boundary in figure s01 — this is the exact moment the guess changes from T to NT.
01 predicts NT, outcome N → correct. 01→00.
00 predicts NT, outcome N → correct. 00−1 = 00 (clipped at the floor!).
00 predicts NT, outcome N → correct.

Result: it took two N's to flip the prediction (hysteresis in the other direction), and 00 saturates just like 11 did — subtracting one keeps it at 00, never wrapping to 11.

C6 — Word problem: nested loops, two live counters

Worked example Ex 6 · Real code, two branches at once

for (i = 0; i < 3; i++)      // Branch A (outer)
    for (j = 0; j < 4; j++)  // Branch B (inner)
        work();

Both counters start at 11. Branch B fires its condition 5 times per inner loop (4 taken + 1 exit) and does this 3 times. Branch A fires 4 times total (3 taken + 1 exit). Count total 2-bit misses.

Forecast: total misses across A and B for one full run of this nest?

Branch B, one inner loop = TTTTN, starting each time at 11 (because re-entry lands it back at 11 — same mechanism as Ex 2):

4×T at 11 → all correct, stays 11. Why this step? 11 is saturated: every taken outcome is a "+1" that clips back to 11, so the four body iterations are free hits.
exit N: 11→10, 1 miss, still predicts T. Why this step? The lone not-taken exit decrements 11→10. That single anomaly is absorbed by hysteresis — the counter stays in the taken half, so it does not cost us on the next entry.
next inner loop first T: 10→11, correct (re-entry saved!). Why this step? Because we ended the previous inner loop at 10 (not below the MSB flip boundary), the first taken of the next inner loop is predicted correctly and pushes us straight back to 11. This is the saved re-entry miss.

So Branch B costs 1 miss per inner loop × 3 loops = 3 misses, and 0 re-entry misses.

Branch A = TTTN from 11:

3×T at 11 → correct, stays 11. Why this step? Same saturation logic: the three outer-loop-continue iterations are all "+1" clips at 11.
exit N: 11→10, 1 miss. Why this step? The outer loop only exits once, so we pay exactly one misprediction as the counter drops 11→10. There is no re-entry within this run, so no further cost.

Branch A costs 1 miss.

Total = 3 + 1 = 4 misses.

C7 — Limiting behaviour: when hysteresis becomes a tax

From Ex 5's logic: starting 11, it takes 2 not-takens to move the prediction to NT (11→10→01). So of the 10 new-phase executions, the first 2 are misses, then all correct.

2-bit misses on phase change = 2.
1-bit misses on phase change = 1 (one N flips it immediately).

C8 — Exam twist: aliasing collision at one table index

Before the example, we need one clean rule for turning a PC into a table index.

Definition The bimodal index rule

A bimodal predictor is a table of 2-bit counters. Let the table have $2^{k}$ entries, so we need a $k$ -bit number to pick a row; here $k$ is just "how many address bits we use as the index" (a design choice, e.g. $k = 12$ gives 4096 entries — it is not related to the PC's total width). The rule is:

Drop the lowest 2 bits PC[1:0]. On a machine with 4-byte instructions these two bits are always 00, so they carry no information — using them would waste index space.
Keep the next $k$ bits PC[k+1:2]. These $k$ bits ARE the index.

Written compactly, $index = ⌊ PC /4 ⌋ mod 2^{k}$ . The " $mod 2^{k}$ " (remainder after dividing by $2^{k}$ ) is what keeps only $k$ bits: it throws away everything above bit $k + 1$ . In hardware this whole thing is just wires — no divider needed, you literally slice out PC[k+1:2].

(a) Compute both indices with the rule above.

Write the PCs in binary: 0x1004 = 0001 0000 0000 0100, 0x1014 = 0001 0000 0001 0100. Why this step? The rule works on bits, so we need the binary form to read off PC[3:2].
Drop PC[1:0] (the low 00) and keep the next $k = 2$ bits PC[3:2].
- X 0x1004: PC[3:2] = 01 → index $= 1$ .
- Y 0x1014: PC[3:2] = 01 → index $= 1$ . Why this step? Dividing by 4 and taking $mod 4$ is exactly "keep bits 3 and 2". Both PCs happen to share those two bits, even though they differ higher up (bit 4).
They collide — both map to entry 1. This is destructive interference: two unrelated branches forced to share one counter.

(b) Trace the shared counter (start 10), interleaved T, N, T, N:

Step	Branch	State (pred)	Outcome	Right?	Next
1	X	`10` (T)	T	✓	`11`
2	Y	`11` (T)	N	✗	`10`
3	X	`10` (T)	T	✓	`11`
4	Y	`11` (T)	N	✗	`10`

Why this step (rows 1, 3)? X is genuinely taken, so at 10/11 (MSB = 1) the prediction T is right, and the "+1" pushes toward 11. Why this step (rows 2, 4)? Y is genuinely not-taken, but the shared counter is sitting in the taken half because X keeps dragging it up — so Y is predicted T and misses every time, and its "−1" only drops the counter back to 10.

The counter thrashes: X pushes it up, Y pulls it down, and it never leaves the taken half. X is always right, Y is always wrong — Y's real bias is completely masked by the collision.

Recall drills

Recall From

11, how many not-takens flip the prediction to NT? Two ::: 11→10 (still T), then 10→01 (now NT). One N is absorbed by hysteresis.

Recall Steady-state 2-bit accuracy on a perfect TNTN branch?

50% ::: no bias means no reservoir to lean on — the degenerate worst case.

Recall Why is init

10 better than 00 for a fresh branch? Most branches are taken (~65%) ::: guessing taken from step one wins the cold-start on the common case.

Recall On a genuine phase change, is 2-bit faster or slower to adapt than 1-bit?

Slower ::: 2-bit needs 2 mispredicts to flip; 1-bit needs 1. Hysteresis is a tax here.

Recall What does the bit-slice

PC[3:2] mean, and what is $k$ ? Bits 3 and 2 of the program counter address ::: $k$ is the number of index bits, giving a $2^{k}$ -entry table.