THE BRANCH PREDICTION guess the branch before you know it — and pay when wrong
A pipelined processor must fetch the next instruction before it knows whether a branch is taken, so it guesses. The classic predictor is a 2-bit saturating counter per branch: four states (strongly/weakly not-taken, weakly/strongly taken); a taken branch nudges the state up, a not-taken nudges it down, and the top bit is the prediction. Two bits give hysteresis — one anomaly does not flip the prediction — so a loop that is taken 99% of the time mispredicts only at its exit. A wrong guess flushes the pipeline: the cost of speculation.
THE TECHNIQUE 2-bit saturating counter; mispredict flushes the pipeline
A branch outcome pattern drives a 2-bit saturating predictor. The demo runs the counter and counts mispredictions — the pipeline flushes: live demo
HISTORY & CREDIT James E. Smith, 1981
“The CPU waits to see if the branch is taken.” — it cannot afford to; it guesses and runs ahead, and pays a flush only when wrong. The 2-bit counter is why that guess is usually right: it remembers the trend, not just the last time. cited
1981 · James E. Smith — “A Study of Branch Prediction Strategies” (ISCA): the 2-bit saturating counter, still the textbook baseline. 1991–93 · Yeh & Patt — two-level adaptive prediction using branch history — the leap to modern predictors. now · TAGE and perceptron predictors push accuracy past 99%; the 2-bit counter is where every course starts.
Two bits buy hysteresis: the prediction only flips after two surprises, so the odd exit of a hot loop costs one miss, not two. Speculation is cheap exactly because the counter refuses to overreact. Smith 1981
RECOMMEND FOR I-13 mispredictions over a loop pattern, computed
On the canonical compiler, the 2-bit predictor over the pattern 1110 repeated three times (from a cold state) mispredicts 5 times — the warm-up plus each loop exit:
$ i13 run branchpred.i13 # 2-bit saturating counter over 1110 x3
mispredicts = 5 -- cold-start warm-up + one miss at each loop exit
Recommend: branch prediction is N/A for I-13 — and pointedly so. It is a hardware pipeline trick, and i13's IVM is an interpreter that resolves each branch before it acts. There is nothing to speculate: ARRIVAL ≠ EXECUTION, EXECUTION ≠ COMMIT is the opposite stance — i13 refuses to run ahead of what it has confirmed. A CPU guesses and pays for wrong guesses; i13's whole design is to never guess. The predictor is the perfect foil for the creed: speculation is exactly what i13 was built to not do.