Speculative execution: Visual walkthrough — Hardware deep dive

Parent: Speculative execution · Read this alongside the Hinglish version.

This page builds one number from nothing: the average extra cost per branch when a CPU guesses which way the code will go. We will draw every piece before we use it. By the end you will be able to say, for any branch, whether guessing is a good bet.

Nothing here needs prior knowledge of pipelines. If a word looks new, we draw it first.

Step 1 — What a "branch" even is

WHAT. A program is a list of instructions the CPU runs one after another. Most of the time it just walks straight down the list. But sometimes it hits a fork in the road: an if. Do we go left or right? That fork is called a branch.

WHY. The CPU cannot go both ways. It must pick one road. But — and this is the whole story — it does not yet know which road is correct, because the answer depends on a value that is still being computed.

PICTURE. Look at the figure. The blue line is the stream of instructions flowing down. At the yellow diamond (the branch) it splits. One road is taken, one is not taken. Only later, when the red clock finishes ticking, does the CPU learn which road was right.

Step 2 — The pipeline: why waiting is expensive

WHAT. A modern CPU does not do one instruction at a time. It runs an assembly line: while instruction 5 is being decoded, instruction 4 is being executed, instruction 3 is writing its result, and so on. Each station on the line is a pipeline stage. The number of stations is the pipeline depth, which we call $D$ .

WHY draw $D$ . Every symbol we use later is built from $D$ . So we anchor it now: $D$ is just the count of boxes in the assembly line. Real CPUs have $D \approx 15$ to $20$ .

PICTURE. The figure shows $D = 6$ boxes. An instruction enters the left box and marches one box to the right every clock tick. It takes $D$ ticks to fall off the right end. The branch's answer only appears near the far right box (red) — many ticks after we first met the branch on the left.

The problem is now visible: from Step 1 the answer comes at the end of the line, but from Step 2 we needed to pick a road at the start. There are $D$ ticks of gap. If we freeze the whole assembly line and wait for the answer, those $D$ ticks pass with no useful work leaving the line. That empty, work-free gap is what we call a pipeline bubble.

Step 3 — The gamble: guess instead of wait

WHAT. Instead of freezing for $D$ ticks (Step 2's bubble), the CPU guesses which road the branch takes and starts marching instructions from the guessed road down the assembly line immediately.

WHY this and not waiting. If we wait, we eat the full bubble — $\approx D$ ticks every single branch. If we guess and we are usually right, we lose those ticks only on the rare wrong guess. That is the entire bet of Speculative execution.

PICTURE. Two timelines. Top (green): "wait" — a big empty gap of $D$ bubble ticks before work resumes. Bottom (blue): "guess" — no gap, work flows straight through. The blue path is shorter whenever the guess is right.

But if we compute results before we're sure they're needed, we need a safe place to park those results — somewhere they don't yet count as official. That place is the Reorder buffer (ROB).

Step 4 — What a wrong guess costs (the penalty $P$ )

WHAT. Suppose the guess was wrong. Every instruction we sent down the road behind the branch is garbage. We must throw them all out — this act is called squashing — and refill the pipeline from the correct road.

WHY these two pieces. The cost has exactly two parts, and we draw each:

The pipeline was full of wrong work up to depth $D$ — that whole line must drain and refill: $\approx D$ ticks.
Fetching the first correct instruction from memory/cache takes a small extra $R$ ticks (the refetch latency, usually $1$ – $3$ ).

PICTURE. The figure marks the branch in yellow at the front, shows the $D - 1$ red (wrong) instructions behind it being squashed, then the green correct instructions streaming in after a short $R$ gap.

$P$ is what you pay only when wrong. If you are right, you pay $0$ . Hold onto that asymmetry — it is why the gamble can pay off.

Step 5 — The average cost per branch (the central result)

WHAT. Now we combine "how often we are wrong" with "what wrong costs." Call the chance of a wrong guess $m$ (the misprediction rate). It is a number between $0$ and $1$ : $m = 0.05$ means wrong $5%$ of the time.

WHY multiply. We want the average penalty over many branches. Average = (chance of the bad event) × (cost of the bad event) + (chance of good event) × ( $0$ ). The good event contributes nothing, so only one term survives.

PICTURE. A weighing scale. On the wrong-guess side sits a fraction $m$ of the branches, each carrying the full weight $P$ . On the right-guess side sits fraction $1 - m$ , weightless. The balance point — the average — is $m \times P$ .

Plug in the parent's numbers. $m = 0.05$ , $P = 17$ : $\overset{ˉ}{C} = 0.05 \times 17 = 0.85 ticks per branch.$

Compare to always waiting, which costs the full $P \approx 17$ ticks every branch. Speculation turned $17$ into $0.85$ — a $20 \times$ reduction. That is the win, derived from zero.

Step 6 — The break-even line: when guessing STOPS winning

WHAT. Guessing is not always good. If we didn't guess we'd instead pay a small fixed wait, which we call $W$ ticks — the stall cost, the number of ticks lost if we simply freeze until the branch resolves (a couple of ticks, since resolving is faster than a full flush). Guessing wins only when its average cost $\overset{ˉ}{C}$ is smaller than that stall cost: $miss rate m penalty P < stall cost if we wait instead W .$

WHY set them equal. The tipping point — the break-even misprediction rate $m_{*}$ — is where the two are equal. Above it, waiting is actually cheaper. $m_{*} P = W ⟹ m_{*} = \frac{W}{P} .$

PICTURE. A graph over the full range $m \in [0, 1]$ (a rate can be anything from never-wrong to always-wrong, so we draw all of it). The blue rising line is guessing's cost $m P$ . The green flat line is the fixed stall cost $W$ . They cross at $m_{*}$ . Left of the crossing, blue is lower — guess. Right of it, green is lower — wait.

With $W = 2$ , $P = 17$ : break-even $m_{*} = 2/17 \approx 0.12$ . So once a branch mispredicts more than $\approx 12%$ of the time, stop guessing.

Step 7 — The degenerate cases

WHAT & WHY. We must not leave any corner unshown. Look at the endpoints of everything we built.

$m = 0$ (perfect prediction). $\overset{ˉ}{C} = 0 \times P = 0$ . Speculation is free — the ideal a loop approaches.
$m = 1$ (always wrong). $\overset{ˉ}{C} = P$ . Every branch pays full penalty; identical in time to never speculating, but with the extra risk of the security leaks below. Worst case.
$R \to 0$ (instant refetch, e.g. the correct instruction is already in a tiny front-end buffer). Then $P = D + R \to D$ : the penalty is dominated purely by draining the pipe, and break-even $m_{*} = W / D$ .
$R \to \infty$ (correct path missing from cache, long memory fetch). Then $P \to \infty$ , so any nonzero $m$ makes $\overset{ˉ}{C}$ huge and break-even $m_{*} = W / P \to 0$ — guessing is almost never worth it when refetch is catastrophic.
$W \to 0$ (waiting is free — branch resolves instantly if we just stall). Then break-even $m_{*} = W / P \to 0$ : there is nothing to save by guessing, so you should never speculate. (In real CPUs $W$ is never truly $0$ because resolving still costs the bubble; this is the limiting boundary.)
$D \to$ large (very deep pipe). $P = D + R$ grows, so $\overset{ˉ}{C} = m P$ grows and break-even $m_{*} = W / P$ shrinks. Deeper pipelines demand better predictors — a real design tension in Superscalar architecture and Instruction-level parallelism (ILP).
The hidden leak. Even a squashed wrong guess (Step 4) can touch memory and warm the cache. That trace is invisible to the program but measurable from outside — the door that Cache side-channel attacks walk through. Our formula counts time, not safety; the safety cost is separate.

PICTURE. Six mini-panels, one per case (including the $R \to 0$ , $R \to \infty$ , $W \to 0$ limits), plus a small cache icon for the leak.

The one-picture summary

Everything on this page is one chain: guess a road → hold work in the Reorder buffer (ROB) → check → squash and pay $P = D + R$ only if wrong → average that to $\overset{ˉ}{C} = m P$ → compare to the stall cost $W$ . The final figure lays the whole chain on one canvas, with the break-even line as the verdict.

Recall Feynman retelling — say it out loud

The CPU is a long assembly line, $D$ boxes deep. When it hits an if, the answer is not ready, so freezing to wait leaves a $D$ -tick bubble — the line runs but finishes nothing. To dodge that, the CPU guesses a road and keeps the line full, parking the unconfirmed results in the ROB where they aren't official yet. If the guess was right, it lost nothing. If wrong, it squashes the whole line — drops those ROB slots and pipeline work — and refills, costing $P = D + R$ ticks. Since it's wrong only a fraction $m$ of the time, the typical cost per branch is just $m \times P$ . For a normal branch that's tiny (like $0.85$ ticks), way better than freezing for $17$ . But if a branch is basically a coin flip ( $m = 0.5$ ), that average balloons to $8.5$ ticks — worse than just waiting a couple of ticks $W$ — so a smart CPU stops guessing past the break-even point $m_{*} = W / P$ . And there's a twist the time-math can't see: even a thrown-away guess leaves a footprint in the cache, which is how Spectre-style attacks read secrets.

Recall

The two ingredients of the misprediction penalty $P$ ? ::: Pipeline depth $D$ (drain and refill) plus refetch latency $R$ . What is a pipeline bubble? ::: A stretch of ticks where the pipeline moves but finishes no useful instruction — a stall, costing $\approx D$ ticks per unhandled branch. What does it mean to squash an instruction? ::: Cancel it before commit — free its ROB slot and discard its pipeline work so it never touches official state. The average wasted ticks per branch? ::: $\overset{ˉ}{C} = m \times P = m (D + R)$ . Why do correct guesses vanish from the average? ::: They cost $0$ ticks, so the $(1 - m)$ term contributes nothing. Break-even misprediction rate? ::: $m_{*} = W / P$ , where $W$ is the stall cost of just waiting instead. What does the time formula NOT capture? ::: The security leak — squashed guesses still warm the cache (Spectre / side channels).