Foundations — Branch prediction (static and dynamic)

Before you can read the parent note on Branch Prediction, you need to genuinely own every symbol it throws at you. This page builds each one from nothing — plain words first, then a picture, then the reason the topic needs it.

1. What a "pipeline" actually is

A classic 5-stage pipeline has these stages, in order:

1. Fetch (F) — grab the instruction from memory.
2. Decode (D) — figure out what it is.
3. Execute (E) — do the arithmetic / compare.
4. Memory (M) — read or write data memory.
5. Writeback (W) — store the result in a register.

Look at the picture. Each row is one instruction; each column is one clock cycle (one "tick"). At cycle 5 the whole line is full: five different instructions are being worked on at once. This is why CPUs are fast — but it is also exactly why branches hurt, as we will see.

2. The Program Counter — PC

In the parent note's example, addresses go 100, 104, 108, .... They jump by 4 each time because each instruction is 4 bytes wide.

3. What a "branch" is

There are two possible outcomes for a conditional branch:

• Taken — the condition was true, so we jump to a new address called the target.
• Not-Taken — the condition was false, so we just fall through to PC+4.

The red arrow is the taken path (jump to the target). The black arrow is the not-taken fall-through. The CPU cannot walk down both — it must pick one to fetch before the compare finishes. That pick is the prediction.

4. Cycles, stalls, and the "penalty"

In the picture, the CPU predicted the wrong path and fetched three instructions (grey). When the branch resolves at Execute, those three are flushed (crossed out in red) — wasted work. The number of wasted cycles is the branch penalty.

5. Probability — reading $P_{\text{something}}$

The parent note writes things like $P_{\text{branch}}$ and $P_{\text{mispredict}}$. The letter $P$ just means "the fraction of the time this happens," a number between 0 and 1.

6. CPI — the score we are trying to lower

7. Accuracy — measuring a predictor

8. Bits, binary, and the modulo mod

The dynamic predictors index a table using bits of the PC. Three tiny ideas make this readable.

9. State machines — the arrows in the parent's diagrams

The 1-bit predictor has 2 states (0=predict Not-Taken, 1=predict Taken). The 2-bit predictor has 4 states (00→11). The arrows labelled T / NT say where to move when the branch turns out Taken or Not-Taken.

The red arrow highlights hysteresis: from Strongly-Taken (11), a single Not-Taken only steps back one to Weakly-Taken (10) — it still predicts Taken. This "stubbornness" is why a 2-bit counter survives a loop's one-time exit without flipping its whole opinion.

Prerequisite map

Each foundation on the left feeds into the parent topic on the right: you cannot understand why prediction pays off (the CPI equation) without pipelines and penalties, and you cannot understand how dynamic predictors remember without bits and state machines.

These foundations connect outward to Speculative Execution (acting on a guess), Instruction-Level Parallelism (ILP) and Superscalar Processors (why deep pipelines make branches costly), Cache Performance (fetching from the wrong path also pollutes caches), and Compiler Optimizations (where BTFNT hints are inserted).

Equipment checklist

Cover the right side and test yourself.