Implement 2-Bit Saturating Counter Branch Predictor

Topic Overview

Saturating Counter States

A 2-bit saturating branch predictor keeps four states per branch: strongly not-taken (00), weakly not-taken (01), weakly taken (10), strongly taken (11). Correct predictions nudge one step toward taken/not-taken; mispredictions snap or reverse.

cCopy
Loading…

Why Two Bits Beat One

A single bit thrashes on loops: the final backward branch looks not-taken once, causing a mispredict every iteration. Two bits remember "usually taken" after warm-up.

For example, a for (i=0; i<1000; i++) back-edge transitions from SNT to ST over the first handful of iterations, then stays correct.

For this exercise, you will simulate a table of 2-bit counters keyed by PC and report accuracy on traces. This task asks you to beat a static always-taken baseline on mixed branch workloads.

Working Through the Exercise

Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.

• Trace first: walk one failing input by hand before changing random lines
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.

Your Task

Build the branch predictor itself. Compare a 1-bit predictor (remembers the last outcome) with a 2-bit saturating counter (needs to be wrong twice before it changes its mind) on the same branch history, using a table indexed by branch address. The 2-bit counter is the standard because it survives a single anomaly: the loop-exit branch that goes the other way once per iteration count.

Input

cCopy
Loading…

SPEC is a string of T/N characters, e.g. pattern 0x100 TTTN x3 is 12 branches at 0x100. A later entries line resizes and resets both tables; the statistics keep accumulating.

Predictors

Both index the table with (address >> 2) mod N, so different branches can collide in the same entry.

• 1-bit: each entry holds the last outcome, starting N (not taken). It predicts that outcome and is then overwritten with the actual one.
• 2-bit: each entry is a counter 0..3, starting at 1 (weakly not-taken). It predicts taken for 2 and 3. A taken outcome increments (max 3), a not-taken outcome decrements (min 0).

Output

For every branch:

cCopy
Loading…

The 2-bit part always shows the state transition. Branches from a pattern line don't print. After a pattern line:

cCopy
Loading…

At the end, for each predictor:

cCopy
Loading…

Accuracy has one decimal.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Two independent tables updated from the same outcome stream; the index function is shared.
2. Saturate the 2-bit counter: never let it wrap from 3 to 0 or 0 to 3.

Hidden tests cover an alternating TN pattern that defeats both, a TTNN pattern where the 1-bit predictor wins, two branch addresses that collide in a small table, and a second entries line that resets the predictors to a single entry.