What happens when a branch is mispredicted?

The processor has speculatively fetched and partly executed instructions on the wrong path. On detecting the misprediction, it discards (squashes) that speculative work and restarts fetching from the correct target, paying a penalty roughly proportional to how deep the pipeline is.

How accurate are modern branch predictors?

Modern dynamic predictors typically exceed 95 percent accuracy on common workloads by combining local and global branch history. This high accuracy is what makes deep, wide pipelines worthwhile, since each misprediction wastes many cycles of speculative work.

Branch Prediction

Branch prediction lets a pipelined processor guess the outcome and target of a branch before it is resolved, so it can keep fetching and executing instructions along the likely path instead of stalling.

Definition

Branch prediction is a microarchitectural technique that forecasts whether a conditional branch will be taken and where it will go, allowing the processor to speculatively fetch and execute instructions along the predicted path and to discard that work if the prediction proves wrong.

Scope

This topic covers techniques for predicting control flow: static prediction, dynamic predictors based on branch history (one- and two-bit counters, correlating and tournament predictors), branch target buffers, and the cost of mispredictions. It treats how prediction enables deep pipelines and speculation. It excludes the broader speculative-execution machinery and recovery (out-of-order execution) and the basic control hazard itself (pipelining and hazards).

Core questions

Why do branches stall deep pipelines, and how does prediction help?
How do dynamic predictors use branch history to improve accuracy?
What is a branch target buffer and what does it provide?
What is the penalty of a misprediction, and how is it recovered?

Key concepts

static vs dynamic prediction
one- and two-bit saturating counters
branch history and correlation
tournament predictors
branch target buffer
misprediction penalty
speculative fetch

Key theories

History-based dynamic prediction: Branch outcomes are highly correlated with their own and other branches' past behavior; predictors that record history in saturating counters and combine local and global history (correlating and tournament predictors) achieve very high accuracy.

Mechanisms

A predictor consults history to guess a branch's direction and a branch target buffer to guess its target, letting the front end keep fetching speculatively. Two-bit saturating counters track recent outcomes per branch; correlating predictors add global history; tournament predictors choose dynamically between local and global schemes. On a misprediction, the speculative instructions are squashed and fetch restarts at the correct address, incurring a penalty proportional to pipeline depth.

Clinical relevance

Accurate branch prediction is essential to modern deep, wide pipelines: with mispredictions costing many cycles, predictors exceeding 95 percent accuracy are needed to sustain high performance. Branch prediction structures have also become security-relevant, as their speculative behavior underlies transient-execution attacks such as Spectre.

History

Simple static and one-bit dynamic predictors gave way to two-bit saturating counters, then to correlating and two-level adaptive predictors in the early 1990s, and to tournament and neural-style predictors in high-performance cores. As pipelines deepened, predictor sophistication grew correspondingly to keep misprediction penalties tolerable.

Key figures

James E. Smith
Yale Patt
Tse-Yu Yeh
John L. Hennessy

Seminal works

hennessy2019
patterson2020

Frequently asked questions

What happens when a branch is mispredicted?: The processor has speculatively fetched and partly executed instructions on the wrong path. On detecting the misprediction, it discards (squashes) that speculative work and restarts fetching from the correct target, paying a penalty roughly proportional to how deep the pipeline is.
How accurate are modern branch predictors?: Modern dynamic predictors typically exceed 95 percent accuracy on common workloads by combining local and global branch history. This high accuracy is what makes deep, wide pipelines worthwhile, since each misprediction wastes many cycles of speculative work.