branch prediction

A branch predictor is a guess about which fork in the road you will take. A program is full of branches — if-statements, loops, function calls — and at each one the CPU must decide which instructions to fetch next. But whether a branch is taken often is not known for several cycles, and a deep pipeline cannot afford to wait. So the hardware guesses the direction (and target) immediately and keeps going, betting it can correct itself cheaply on the rare occasions it is wrong.

Concretely, a branch predictor watches the history of past branches and bets that the future resembles the past. The simplest scheme remembers, for each branch, whether it went the same way last time. Better schemes use a small saturating counter per branch (a two-bit predictor), correlate a branch's behavior with the recent outcomes of other branches (a correlating predictor), or run several predictors and learn per-branch which one to trust (a tournament predictor). For the target address of a taken branch, a branch target buffer caches where the branch went last time so the next fetch can start there without waiting. Modern predictors are astonishingly good — often well above 95% accuracy on typical code.

Accuracy is everything in a deep, wide, speculative core, because a misprediction is expensive: every speculatively executed instruction on the wrong path must be squashed and the pipeline refilled from the correct path, costing perhaps a dozen or more cycles each time. So even a few percent of mispredictions noticeably dents performance. The honest caveat is that branches whose direction is essentially random (data-dependent in an unpredictable way) defeat any predictor — and prediction quality is one of the practical limits on how much ILP a core can actually sustain.