How CPUs Predict the Future: Branch Prediction & Out-of-Order Execution

A modern CPU does not execute instructions one by one like a recipe. Modern processors use instruction pipelining.

1. The Hazard of Conditional Branches

When the CPU encounters an if (x > 0) branch in code, the condition might depend on memory being fetched from RAM (which takes 200 clock cycles).

If the CPU halted and waited, performance would plummet. Instead, the CPU predicts the outcome and speculatively executes ahead!

2. 2-Bit Saturating Counters

Hardware branch predictors use state machines (e.g. Strongly Taken, Weakly Taken, Weakly Not Taken, Strongly Not Taken) and Two-Level Adaptive Predictors with global branch history registers to achieve >97% accuracy.

3. Pipeline Flushes & Speculation Costs

If the prediction is correct: Zero latency penalty!
If the prediction was wrong: The CPU must discard all speculatively executed instructions (Pipeline Flush) and restart at the correct address.

Understand hardware fundamentals in our CPU Execution & Arithmetic Target!