vault

Two-Bit Saturating Counter

14 min read

Two-Bit Saturating Counter

The two-bit saturating counter is the smallest dynamic branch predictor that meaningfully outperforms naive one-bit history. Each counter is a four-state finite state machine (Strongly Not Taken, Weakly Not Taken, Weakly Taken, Strongly Taken). The sign bit of the counter (the high bit) is the prediction; taken outcomes increment, not-taken outcomes decrement, both saturating at the endpoints. The extra bit gives hysteresis: one wrong prediction is not enough to flip the predicted direction, only enough to nudge the counter toward the boundary. This single property kills the pathology of the one-bit predictor, where every loop exit causes two consecutive mispredictions (Smith 1981, Wikipedia: Branch predictor). A small table of these counters, indexed by hashed PC bits, achieves around 85% to 93% accuracy on real workloads and has been the workhorse of CPU front ends since the Pentium and DEC EV5.

Mental Model

A two-bit counter is a biased coin with memory: it has a current best guess (the high bit) and a confidence (the low bit). A correct prediction shifts confidence toward the current guess; a wrong prediction shifts confidence the other way. Only after two consecutive wrong predictions does the guess actually flip. This is what makes it the right tool for loops: a for (i=0; i<1000; i++) exit, which is taken 999 times and not-taken once, costs the predictor just one misprediction. The counter is “Strongly Taken” going in, drops to “Weakly Taken” on the not-taken exit, and is back to “Strongly Taken” after the first taken branch of the next outer iteration. A naive one-bit predictor pays two mispredictions per loop entry: one on the exit, one on the first iteration of the next entry.

stateDiagram-v2
    direction LR
    SN: 00<br/>Strongly<br/>Not Taken
    WN: 01<br/>Weakly<br/>Not Taken
    WT: 10<br/>Weakly<br/>Taken
    ST: 11<br/>Strongly<br/>Taken

    SN --> WN: taken
    WN --> WT: taken
    WT --> ST: taken
    ST --> ST: taken (saturate)

    ST --> WT: not taken
    WT --> WN: not taken
    WN --> SN: not taken
    SN --> SN: not taken (saturate)

    note left of SN
        predict
        NOT TAKEN
    end note
    note right of ST
        predict
        TAKEN
    end note

The four-state FSM of a single 2-bit saturating counter. What it shows: the high bit (left bit) is the prediction; transitions move one step per branch outcome and saturate at the endpoints. The insight to take: crossing the prediction boundary (from 01 to 10 or from 10 to 01) requires two consecutive disagreements with the current prediction, which is the source of the counter’s resilience against single-outlier outcomes such as a loop exit.

Why Two Bits Beat One Bit

Smith’s 1981 paper, the foundational analysis of dynamic prediction, lays this out empirically (Smith 1981). His “Strategy 6” maintains one bit per hashed branch PC, set to whatever the most recent outcome was. “Strategy 7” extends that to twos-complement counters and predicts on the sign bit. Smith writes: “Note that strategy 6 is actually a special case of strategy 7 with a count of one bit. Also, using a count tends to cause a ‘vote’ when more than one branch instruction hashes to the same count. … [Strategy 7’s] accuracy is quite good; in fact, it is usually as good as or better than any strategies looked at thus far. Also, a count of 2 bits often gives better accuracy than a count of one bit, but going to larger counters than 2 bits does not necessarily give better results.”

The pathology of the one-bit predictor is sometimes called the “one-off-flip-flap” problem. Take any branch with a strong dominant bias and an occasional opposite outcome: if (rare_event) ..., taken 1% of the time. A one-bit predictor on this branch, set to “predict not taken” most of the time, gets the dominant case right at 99%. But every time the rare-taken case happens, the bit flips to “predict taken,” so the next time the branch executes (which is almost certainly the dominant not-taken case) it mispredicts. The predictor pays two mispredictions per rare event instead of one. The two-bit predictor pays only one, because the rare taken event moves it from “Strongly Not Taken” to “Weakly Not Taken” but the prediction is still “not taken.”

The loop case is structurally identical and more important because loops are everywhere. Consider:

for (int i = 0; i < N; i++) {
    /* loop body */
}

The conditional branch at the loop bottom (taken if i < N) is taken N-1 times and not taken once per execution of the outer loop. A one-bit predictor:

  • enters at “predict taken” (still set from last execution).
  • predicts correctly for N-1 iterations.
  • mispredicts the exit; flips to “predict not taken.”
  • on next entry, mispredicts the first iteration; flips back to “predict taken.”
  • predicts correctly for the remaining N-2 iterations.

Two mispredictions per outer-loop trip. A two-bit predictor:

  • enters at “Strongly Taken.”
  • predicts correctly for N-1 iterations; counter saturates at ST (11).
  • mispredicts the exit; counter moves to WT (10), still predicts taken.
  • on next entry, predicts taken correctly; counter saturates back to ST.

One misprediction per outer-loop trip. For a loop iterating millions of times the saving rounds to “two mispredictions versus one” per outer trip, an immaterial difference; but for tight short loops nested inside larger loops (an everyday code pattern, including matrix and image processing), the saving compounds and yields the 5-percentage-point accuracy jump from 85% to 90%+ that the literature documents.

The asymmetry can be stated formally. If a branch has stable bias p (probability of taken) approaching 1, the one-bit predictor’s miss rate is 2 * (1 - p) (each rare event costs two mispredictions). The two-bit predictor’s miss rate is 1 - p (each rare event costs one). The ratio is exactly two. The cost in hardware is exactly one extra bit per counter.

Mathematical Analysis of Loop Performance

Generalizing the loop analysis: for a loop whose backward branch is taken N-1 times and not taken once per traversal, on a stream of K traversals:

Total branch executions:  K * N
One-bit mispredictions:   2 * K              (exit + first re-entry)
Two-bit mispredictions:   K                  (exit only, if N >= 2)
One-bit miss rate:        2 / N
Two-bit miss rate:        1 / N

For N = 100, the one-bit predictor has a 2% miss rate, the two-bit a 1%. For N = 10, it is 20% versus 10%. The percentages may look small but they are on every branch, and integer code is roughly 15% to 20% branches.

For a random Bernoulli branch with p = 0.5 (no bias either way), neither predictor does better than 50% accuracy: the two-bit counter random-walks between states and predicts essentially nothing useful. Smith’s paper identifies this case implicitly by showing that the most variable accuracy in his benchmark suite came from programs (SORTST, SINCOS) with the least predictable branches. The two-bit counter shines on biased branches; truly unpredictable branches need correlation with other branch outcomes, which is what the two-level adaptive predictors (Yeh-Patt, gshare, TAGE) provide.

The pathological case for the two-bit counter is the alternating-pattern branch: TNTNTNTN… It has bias p = 0.5 and zero per-execution correlation; the counter ends up in WT or WN and predicts wrong every other time, giving 50% accuracy. This is the case two-level predictors with sufficient history get right: a one-bit history is enough to predict the next outcome from the previous one.

The Counter Table: PC-Indexed, Direct-Mapped, Aliased

A real predictor instantiates not one counter but a table of them, typically 256 to 16384 entries, indexed by the low bits of the branch’s PC. The structure is called a Branch History Table (BHT) or, when used as the base predictor of a two-level scheme, a Pattern History Table (PHT) (Wikipedia: Branch predictor).

The lookup is direct-mapped: take log2(table_size) bits of the PC (usually starting at bit 2, since branches are 4-byte aligned in RV32; for RV32IMC with 2-byte alignment for compressed branches, bit 1), use them as the index, read out the 2-bit counter, predict on its high bit. No tag, no associativity, no hit/miss distinction. If the table has 1024 entries, that is 1024 * 2 = 2048 bits = 256 bytes of storage. Compare to a TAGE-class predictor (~256 Kbits, Seznec L-TAGE) for a sense of scale; the 2-bit counter table is roughly three orders of magnitude smaller.

The price of the no-tag design is aliasing: two unrelated branches whose PCs share their low bits collide in the same counter entry. The collision can be neutral (both branches taken-biased, both predicted correctly), constructive (a usually-not-taken branch’s counter is held at “not taken” by a usually-not-taken neighbor), or destructive (a usually-taken and a usually-not-taken branch both lose accuracy because the counter is bounced between high and low states). Destructive aliasing is the dominant source of miss-rate on a small PHT. Bigger tables reduce aliasing; smarter hashing functions (XORing higher PC bits, or XORing PC with global history as in gshare) reduce it further.

A common micro-optimization is to reduce the storage from 2 * 2^k bits to (2^k) + (2^k) bits by sharing the hysteresis bit across multiple PCs that map to the same direction bit. This is the “shared hysteresis” trick (Seznec L-TAGE §1: “in order to save storage space, the hysteresis bit is shared among several counters”). The accuracy loss is small; the storage win is roughly 25%.

Typical Accuracy Numbers

The published accuracy of a single 2-bit BHT on integer benchmarks is around 85% to 93%, depending on table size and benchmark mix:

  • Smith 1981 (Smith 1981) on six FORTRAN benchmarks (mostly numeric kernels, very loop-heavy): Strategy 7 with a 16-entry table of 3-bit counters achieved per-program accuracy in the high 80s to mid 90s.
  • SPEC ‘89 benchmarks (the era when 2-bit predictors became standard): the original Intel Pentium’s 2-bit predictor with 256 entries achieved approximately 93.5% accuracy (Wikipedia: Branch predictor).
  • Dan Luu’s reproduction (danluu.com) on a representative model: “2-bit (~90% accuracy, 1.38 CPI)” versus “1-bit (85% accuracy, 1.57 CPI)” and “BTFNT (~80% accuracy, 1.76 CPI).”
  • SPEC 2000 integer at 4 KB total budget (Jimenez and Lin 2001, Figure 3): a pure-counter PHT (gshare, which is itself just 2-bit counters indexed by PC XOR history) hits roughly 7% to 8% miss rate, i.e. 92% to 93% accuracy.

The headline number “~90%” is the safe summary for an engineer choosing a predictor budget. To do meaningfully better than that on hard workloads requires correlation across branches (two-level adaptive) or longer history (TAGE / perceptron); the 2-bit counter alone hits a wall a few percent below.

Hardware Cost

Per counter: 2 bits of state. Per BHT: 2 * table_size bits, with optional shared-hysteresis to save a third. Lookup: index a SRAM with PC bits, read one entry, extract the high bit. Update: read the entry, increment-or-decrement with saturation logic (two AND gates plus a 2-bit adder, or a tiny case-by-case combinational lookup), write the entry back.

For a 1024-entry BHT: 2 Kbits of state, single-cycle SRAM read in the fetch stage, single-cycle update on branch resolution. Total area is dominated by the SRAM macro; the control logic is a handful of gates. This is what makes the 2-bit counter the unbeatable baseline for low-end designs: it costs essentially nothing yet captures 90% of the achievable accuracy of any more complex scheme on typical embedded workloads.

The update path needs care in a deeper pipeline. The branch’s outcome is known at execute time, but its prediction was read at fetch time, possibly several branches earlier. A naive design updates the BHT on every commit, which means several other branches may have read stale state in the interim. For a small in-order pipeline this is fine (the latency is at most three cycles and the staleness rarely causes flips). For an aggressive out-of-order core, speculative update with rollback on misprediction is standard (Seznec 2006 §2.3 discusses circular history buffers for speculative update).

Verilog Sketch (Synthesizable)

The two-bit counter table is one of the cleanest small RTL exercises. A synthesizable Verilog skeleton, suitable for the definitely-not-esp32 core’s Verilator testbench:

module bht #(
    parameter int INDEX_BITS = 7              // 128-entry BHT
) (
    input  logic                     clk,
    input  logic                     rst_n,
    // Predict port: read in fetch stage
    input  logic [INDEX_BITS-1:0]    pred_idx,
    output logic                     pred_taken,
    // Update port: written in commit stage
    input  logic                     upd_valid,
    input  logic [INDEX_BITS-1:0]    upd_idx,
    input  logic                     upd_taken
);
    // 2-bit counters; bit [1] is the prediction, bit [0] is hysteresis
    logic [1:0] table_q [0:(1<<INDEX_BITS)-1];
 
    // Prediction: combinational read of the high bit
    assign pred_taken = table_q[pred_idx][1];
 
    // Update: saturating increment / decrement
    always_ff @(posedge clk) begin
        if (!rst_n) begin
            // Init all to weakly-taken (10) so loops start happy
            for (int i = 0; i < (1<<INDEX_BITS); i++) table_q[i] <= 2'b10;
        end else if (upd_valid) begin
            unique case ({table_q[upd_idx], upd_taken})
                {2'b00, 1'b0}: table_q[upd_idx] <= 2'b00; // SN, NT -> SN (sat)
                {2'b00, 1'b1}: table_q[upd_idx] <= 2'b01; // SN, T  -> WN
                {2'b01, 1'b0}: table_q[upd_idx] <= 2'b00; // WN, NT -> SN
                {2'b01, 1'b1}: table_q[upd_idx] <= 2'b10; // WN, T  -> WT
                {2'b10, 1'b0}: table_q[upd_idx] <= 2'b01; // WT, NT -> WN
                {2'b10, 1'b1}: table_q[upd_idx] <= 2'b11; // WT, T  -> ST
                {2'b11, 1'b0}: table_q[upd_idx] <= 2'b10; // ST, NT -> WT
                {2'b11, 1'b1}: table_q[upd_idx] <= 2'b11; // ST, T  -> ST (sat)
            endcase
        end
    end
endmodule

A few notes for the reader. The parameterization (INDEX_BITS) keeps the table size a compile-time constant so the synthesis tool maps it to a single block RAM (on a Gowin or Lattice FPGA the threshold is usually 1 to 4 Kbits before it pays to use BRAM instead of LUT-RAM; a 128 * 2 = 256-bit table will end up in distributed LUT RAM). The unique case covers all eight {state, outcome} pairs explicitly, which both synthesizes to a clean LUT and lets Verilator’s linter catch any missing case in simulation. The reset value of 2'b10 (“Weakly Taken”) is the bias-toward-loops heuristic; resetting to 2'b00 is also valid and slightly fairer for branchy code.

The index, in practice, is branch_pc[INDEX_BITS+1:2] for RV32 (skipping the two LSBs that are always zero for 4-byte-aligned instructions). For RV32IMC with 2-byte compressed branches, use branch_pc[INDEX_BITS:1].

Failure Modes

Bursty bias change. A two-bit counter takes two consecutive opposite outcomes to flip its prediction. A branch that abruptly switches bias (e.g., when a hash table starts colliding heavily) will pay two consecutive mispredictions to “learn” the new bias, plus any flapping while the workload is mixed. Larger counters (3-bit, 4-bit) increase hysteresis and slow learning further; this is why Smith concluded going beyond 2 bits “does not necessarily give better results.”

Destructive aliasing on small tables. A 128-entry BHT in a program with thousands of distinct static branches will see massive aliasing; many counters will be bounced between two unrelated branches’ biases and end up at WN or WT, predicting essentially randomly. Diagnostic: high miss rate that improves dramatically with table size doubling. Fix: bigger table, smarter hash, or move to a two-level predictor that hashes in history bits.

Unpredictable branches. Branches that genuinely depend on data with no detectable correlation (cryptographic hashes, random-number-driven control flow) cannot be predicted by any dynamic scheme. The 2-bit counter on such a branch will random-walk and predict at roughly the bias rate; the only fix is to remove the branch (predicate it, use conditional moves) or accept the cost.

Where It Sits in the Lineage

The two-bit counter is the base predictor of every modern hierarchical design. In a tournament predictor it is one of the two competitors. In TAGE it is the base table T0 consulted when no tagged table hits (Seznec 2006 §3.2: “Throughout this paper, the base predictor will be a simple PC-indexed 2-bit counter bimodal table”). In gshare it is the entry type of the PHT. Even perceptron predictors typically hybridize with a 2-bit counter PHT for branches that are not linearly separable (Jimenez and Lin 2001 §5.1: the “hybrid gshare/perceptron predictor” uses a 2K-byte choice table of 2-bit counters). For nearly half a century, the 2-bit saturating counter has remained the irreducible primitive of branch prediction. It is one of the rare structures in computer architecture where the right answer was found early and has held.

See Also

Graph View

Backlinks