Two-Bit Saturating Counter Predictor
What You'll Learn: You'll discover how a two-bit predictor adds "confidence" to branch predictions, reducing mispredictions by requiring two mistakes before switching direction.
The Problem with One-Bit Predictors
Remember the one-bit branch predictor from the previous lesson? It flips its prediction after every single misprediction. This means if a branch slightly misbehaves even once, the predictor immediately changes its mind — which can be too reactive, especially for branches that are usually predictable but occasionally deviate.
Adding Hysteresis with Two Bits
A two-bit saturating counter uses four states instead of two, creating a form of hysteresis (resistance to change). Think of it like a thermostat that doesn't turn on/off with every tiny temperature fluctuation — it needs a bigger change to switch states.
The Four States
- Strongly Not Taken (00)
- Weakly Not Taken (01)
- Weakly Taken (10)
- Strongly Taken (11)
The predictor treats "strong" states (00, 11) as predictions and requires two consecutive mispredictions to flip from "taken" to "not taken" (or vice versa).
How It Works
- When branch is taken: Counter increments (saturates at 11)
- When branch is not taken: Counter decrements (saturates at 00)
- Prediction: Based on the high-order bit (0 = predict not taken, 1 = predict taken)
Why This Helps
If a loop normally iterates 10 times, the one-bit predictor mispredicts twice (last iteration + first iteration of next loop). The two-bit predictor only mispredicts once — the final iteration doesn't immediately flip the prediction from "strongly taken" to "not taken"; it moves to "weakly taken," so the next loop entry still predicts correctly.
Key Takeaway: The two-bit saturating counter predictor adds confidence through four states, requiring two mispredictions before changing prediction direction, dramatically improving accuracy for loops and mostly-predictable branches.