Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 67 ยท CPU Design

Branch Prediction

See how CPUs guess the outcome of branches, compare static, 1-bit, 2-bit and history-based predictors, and measure their accuracy on loop traces in Python.

A pipelined processor wants to fetch a new instruction every cycle. A conditional branch ruins that plan: until the branch is resolved, the front of the pipeline does not know whether the next instruction comes from the next address or from the jump target. Waiting costs several cycles every time, and roughly one instruction in five is a branch. The solution is to guess, keep fetching down the guessed path, and throw the work away if the guess turns out wrong.

In this lesson you will compare static and dynamic predictors, build 1-bit and 2-bit counters, add history so the predictor can learn patterns, and measure each one on traces you generate yourself. It builds on pipeline hazards, where you met the branch penalty.

Why a wrong guess is expensive

Suppose a branch is resolved in the execute stage of a 5-stage pipeline. If the predictor guessed wrong, the two instructions behind it are already in flight and must be flushed. That is a misprediction penalty of 2 cycles. Modern cores have pipelines 15 to 20 stages deep and several instructions fetched per cycle, so a flush wastes dozens of instruction slots.

The effect on performance is easy to estimate:

TEXT
CPI = base CPI + (branch frequency x misprediction rate x penalty)

With a base CPI of 1, 20% branches, a 15-cycle penalty and a 5% misprediction rate, CPI becomes 1 + 0.20 x 0.05 x 15 = 1.15. At a 20% misprediction rate it becomes 1.6. The same program runs 40% slower purely because of guesses. This is why predictors are some of the most carefully tuned parts of a CPU.

Static prediction

A static predictor decides without looking at what happened before. Common rules:

  • Always not taken: keep fetching sequentially. Simple, and right for forward branches around rarely used code such as error handling.
  • Always taken: right for loop back-edges, which are taken every time except the last.
  • Backward taken, forward not taken (BTFN): if the target address is lower than the branch, it is a loop, so predict taken; otherwise predict not taken. It needs no storage at all and is often 65 to 75% accurate on real programs.
  • Compiler hints: the compiler marks a branch as likely or unlikely (for example __builtin_expect in GCC and Clang, or branch hint bits in some ISAs).

Static prediction works as a fallback the first time a branch is seen. Everything better remembers history.

Dynamic prediction: remember what happened

A dynamic predictor keeps a small table indexed by the low bits of the branch address. Each entry remembers recent behaviour of that branch. Because branches are very repetitive, the past is a good guide to the future.

The 1-bit predictor

The simplest entry is one bit: "what did this branch do last time?" Predict the same again.

This is fine for branches that are almost always one way, but it fails on loops. Consider a loop that runs 10 times and is then re-entered. The back-edge branch is taken 9 times and not taken once. A 1-bit predictor is wrong at the exit (it predicted taken) and wrong again on the first branch of the next run (it still remembers "not taken"). That is two mispredictions per loop execution, even though the loop is perfectly regular.

The 2-bit saturating counter

The standard fix is a 2-bit counter that counts from 0 to 3 and stops at both ends (saturates):

  • 0 = strongly not taken, 1 = weakly not taken
  • 2 = weakly taken, 3 = strongly taken

Predict taken when the counter is 2 or 3. Each taken outcome adds 1, each not-taken outcome subtracts 1.

flowchart LR
  S0["0: strongly<br/>not taken"] -->|taken| S1["1: weakly<br/>not taken"]
  S1 -->|taken| S2["2: weakly<br/>taken"]
  S2 -->|taken| S3["3: strongly<br/>taken"]
  S3 -->|not taken| S2
  S2 -->|not taken| S1
  S1 -->|not taken| S0

A 2-bit counter needs two surprises in a row before it changes its prediction.

After a long run of taken branches the counter sits at 3. The single not-taken at the loop exit moves it to 2, which still predicts taken, so the next loop entry is predicted correctly. One misprediction per loop execution instead of two.

Experiment: static versus dynamic

The trace below describes a loop's back-edge branch. Each trace entry is a pair of branch address and whether it was taken. We try four predictors on loops of different lengths.

Python Compare four predictors on loop traces

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output carefully. For a loop of 10 iterations, "always taken" scores 90%, the 1-bit predictor 80% and the 2-bit predictor 89.5%. The 2-bit counter loses only the very first prediction while it warms up. Short loops hurt the 1-bit predictor most: with 4 iterations it drops to 50%, because it is wrong on two of every four branches. For a 100-iteration loop everybody looks good, since the single exit branch barely matters.

Note that "always taken" wins on this trace only because the trace contains nothing else. Real programs mix loops, if statements and data-dependent branches, and a predictor that learns per branch address beats any fixed rule.

Learning patterns with history

A counter only captures a bias ("mostly taken"). It cannot learn "taken, taken, not taken, repeat" or strict alternation. For that, the predictor keeps a branch history: a shift register holding the last k outcomes. The history, not just the address, selects which 2-bit counter to use.

flowchart LR
  A["Branch address"] --> T["History register<br/>last k outcomes"]
  T --> P["Pattern table<br/>of 2-bit counters"]
  P --> G["Prediction:<br/>taken or not"]
  G --> U["Resolve branch,<br/>update counter and history"]
  U --> T

A two-level predictor: first level records recent outcomes, second level maps each outcome pattern to a counter.

If the history is T T the table learns the next outcome is N; if it is T N the next is T. Each pattern gets its own counter, so a repeating pattern becomes perfectly predictable after a short warm-up.

Python History predictors learn repeating patterns

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The results show the idea clearly. A plain 2-bit counter scores 0% on strict alternation: it starts at 1, the taken outcome is guessed wrong, the counter moves to 2, the next outcome is not taken and it is guessed wrong again, and the cycle repeats forever. With one bit of history the same trace is predicted 99.2% correctly. The period-3 pattern needs two bits of history (97.5%); one bit is not enough (32.5%). The inner loop of 5 iterations needs four bits to see the whole pattern (94.2%).

The lesson: history length must cover the pattern. Real predictors pick lengths in the dozens of bits, and the best ones (TAGE-style designs in modern cores) combine several history lengths and choose the longest one that has proven reliable.

Other pieces of the front end

Predicting taken is only half of the job; the fetch unit also needs to know where to go.

  • Branch target buffer (BTB): a cache mapping a branch address to its target, so the next fetch address is known before the instruction is even decoded.
  • Return address stack: ret instructions go to a different place each time, but they always match the most recent call. A small hardware stack predicts them almost perfectly.
  • Indirect branch predictors: for jmp rax, virtual calls and switch tables, which have many possible targets.

What this means for your code

You rarely control the predictor, but you influence what it sees.

  • Branches that depend on random data are the worst case. Sorting an array before a loop that tests if (x >= 128) can make the loop several times faster, because the branch becomes a long run of not-taken followed by a long run of taken.
  • Loops with constant, predictable counts are essentially free to predict.
  • Replacing a hard-to-predict branch with arithmetic or a conditional-move instruction (branchless code) removes the guess altogether, at the price of always executing both sides. This is explored in Writing Cache- and CPU-Friendly Code.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does a 1-bit predictor mispredict twice per execution of a regular loop?

    After the exit it remembers 'not taken', so the first back-edge of the next run is mispredicted too. A 2-bit counter needs two surprises in a row and so avoids the second error.
  2. 2. A 2-bit saturating counter is at value 3 (strongly taken). One not-taken outcome occurs. What does it predict next?

    The counter drops to 2 (weakly taken), which is still in the taken half, so the next prediction is taken.
  3. 3. With base CPI 1, 25% branches, a 10-cycle penalty and a 4% misprediction rate, what is the CPI?

    CPI = 1 + 0.25 x 0.04 x 10 = 1.10. Branch frequency times misprediction rate gives the fraction of instructions that pay the penalty.
  4. 4. Which branch behaviour can a plain 2-bit counter NOT learn, but a history-based predictor can?

    A counter only captures a bias. A strictly alternating pattern needs the previous outcome as context, which is exactly what a history register provides.
  5. 5. What does the return address stack predict?

    Each return goes back to the most recent call site, so a small stack of call return addresses predicts it almost perfectly.

Summary

  • A misprediction flushes the pipeline; the cost is roughly branch frequency x misprediction rate x penalty extra CPI.
  • Static rules (always not taken, backward taken forward not taken) need no memory and serve as the first guess.
  • A 1-bit predictor mispredicts twice per loop run; a 2-bit saturating counter mispredicts once.
  • Adding branch history lets a predictor learn repeating patterns, as long as the history is long enough to cover the pattern.
  • Fetch also needs a branch target buffer, a return address stack and indirect predictors.
  • Predictable branches are cheap; data-dependent random branches are expensive, and branchless code can avoid them.

Next, see how processors go beyond pipelining with Superscalar, Out-of-Order and Speculative Execution.