Branch Prediction
Branch prediction guesses the outcome and target of a branch so a pipeline can keep fetching instead of stalling for the decision.
The Problem
A conditional branch is not resolved until several pipeline stages after it is fetched, yet the processor must fetch something on the very next cycle. Waiting for the outcome would stall the pipeline on every branch, and branches are common. Branch prediction lets the machine guess and keep going; if the guess is wrong, the speculatively fetched instructions are discarded.
Predicting the Direction
The simplest scheme predicts every branch the same way. Better is a dynamic predictor that learns from history. A one-bit predictor remembers the last outcome per branch; a two-bit saturating counter improves on it by requiring two consecutive mispredictions before it flips its guess, which handles the last iteration of a loop gracefully.
- Two-bit counter: strongly/weakly taken, weakly/strongly not-taken
- Correlating predictor: uses the outcomes of recent nearby branches
- Tournament predictor: picks between a local and a global predictor per branch
Global History and Modern Predictors
Real programs have correlated branches: the outcome of one often predicts another. A global history register records the recent taken/not-taken pattern and indexes a table of counters, capturing these correlations. State-of-the-art designs (such as TAGE-style predictors) combine many history lengths and reach accuracy well above 95 percent on typical code.
Predicting the Target
Knowing a branch is taken is not enough; the machine also needs its target address early. A branch target buffer caches recent branch targets so the correct address is available at fetch. A return address stack specially predicts function returns, which are highly regular. Indirect branches, whose target can vary, are the hardest and get their own predictors.
Every misprediction costs a pipeline flush, so on deep, wide processors prediction accuracy is one of the largest single levers on performance.