Branch prediction is the processor’s strategy for guessing, before a conditional branch is actually resolved, whether the branch will be taken and where it will go. A pipelined processor fetches instructions several cycles ahead of where it is executing. When it reaches a conditional branch, such as the test at the bottom of a loop, it does not yet know which way to go, so it cannot know which instruction to fetch next. Rather than stall and wait, the processor predicts the outcome and continues fetching down the predicted path. If the guess is right, no time is lost; if it is wrong, the wrongly fetched instructions are discarded and the pipeline refills, costing a misprediction penalty.
The foundational study is James E. Smith’s 1981 paper “A Study of Branch Prediction Strategies,” presented at the International Symposium on Computer Architecture. Smith evaluated a range of predictors against instruction trace data and compared their accuracy, establishing the quantitative approach that the field still uses. Among his contributions was the saturating counter, a small state machine, typically two bits, that remembers the recent direction of a branch and resists changing its prediction on a single anomaly, which makes it robust for loops that are taken many times and then fall through once.
Predictors come in two broad families. Static prediction makes a fixed guess based on the instruction itself or simple heuristics, for example always predicting that backward branches (loop edges) are taken. Dynamic prediction, the kind Smith analyzed, learns from the branch’s runtime behavior using history stored in hardware tables. Later designs added correlating and two-level predictors that key their guess on the pattern of recent branches, achieving accuracies well above ninety-five percent on typical code.
A related structure is the branch target buffer, a cache that records, for branches seen before, the address the branch jumped to last time. The target buffer lets the processor not only predict that a branch is taken but also begin fetching from the correct target in the same cycle, without waiting to compute the address. Indirect branches and function returns get their own specialized predictors, such as a return-address stack.
Accurate branch prediction is what makes deep pipelines and wide superscalar machines worthwhile, since both lose large amounts of work on a misprediction. It is also a key enabler of speculative execution, because the processor speculates down the predicted path. That same speculative machinery, driven by manipulable branch predictors, is what the Spectre attacks abused to coax processors into leaking data through cache side effects.