One-Bit Branch Predictor
You'll learn: How the simplest dynamic branch predictor works by remembering only the last outcome of each branch.
The Core Idea
A one-bit branch predictor is the most basic form of dynamic branch prediction. It maintains a single bit of history for each branch instruction—essentially remembering "did this branch take last time?" If the branch was taken before, predict taken; if not taken before, predict not taken.
Think of it like a weather forecaster who only remembers yesterday: "It rained yesterday, so I predict rain today."
How It Works
Each branch instruction gets an entry in a Branch History Table (BHT) with one bit:
- Bit = 1: Last time, branch was taken → predict taken
- Bit = 0: Last time, branch was not taken → predict not taken
When the branch actually executes, update the bit to reflect the actual outcome.
The Problem with Loops
One-bit predictors struggle with loop behavior. Consider a loop that iterates 10 times:
for (i = 0; i < 10; i++) {
// loop body
}
The branch at the loop end is taken 9 times, then not taken once to exit. A one-bit predictor will:
- Mispredict twice per loop: once when entering (predicts not-taken but takes), and once when exiting (predicts taken but doesn't)
For alternating patterns (taken, not-taken, taken, not-taken...), it mispredicts every single time—always guessing the opposite of what happens next.
Accuracy: 50% in Worst Cases
In loops and alternating branches, one-bit predictors can achieve accuracy as low as 50%—no better than random guessing or static prediction.
Key Takeaway: A one-bit branch predictor remembers only the last branch outcome, making it simple but prone to mispredictions on loops and any pattern that doesn't repeat the same outcome consecutively.