Speculative execution: Exercises — Hardware deep dive

This page is a self-test ladder. Each rung asks harder questions about Speculative execution — from "can you name the part?" up to "can you design the mitigation?". Cover the solution, try it, then reveal.

Before we start, a one-screen refresher of the vocabulary we will keep reusing. If any word feels unfamiliar, that is exactly what these exercises will drill.

We measure everything in cycles (one tick of the CPU clock) and in CPI = cycles per instruction. Numbers we compute are checked in ===VERIFY===.

Building the penalty formula (read this first)

Every exercise below prices a wrong guess in cycles, so we must first understand where that price comes from. Picture the pipeline as a conveyor belt of $N$ stages; a branch instruction rides near the far end, but the instructions it "gates" were fetched right behind it and are already streaming down the belt.

Formula Misprediction penalty — derived

$Penalty = PipelineDepth + RefetchLatency$

Why exactly these two terms? Walk the wrong-path recovery step by step (see figure below):

The branch mispredicts. Behind it on the belt sit up to $N - 1$ wrong-path instructions (one per remaining stage), and the branch itself occupies one more slot while its condition is being resolved. That is $(N - 1) + 1 = N$ slots of work sunk into the wrong path — this is why the depth term is exactly $N$ , not $N - 1$ : the branch's own resolve slot supplies the "+1" that rounds $N - 1$ up to a full $N = 15$ .
Those wrong instructions are invalidated (squashed) — cheap flag flips, folded into the same recovery, so they add no separate cycles.
Now the belt is empty and we must refill it starting from the correct address. Nothing useful commits until the first correct instruction has travelled in — that startup cost is the refetch latency, the second term ( $2$ ).

Adding the sunk wrong-path work ( $N = 15$ ) to the refill startup ( $2$ ) gives $Penalty = 15 + 2 = 17$ cycles.

Figure s01 — a conveyor belt of 15 rounded coral boxes shows the wrong-path work filling every stage (the depth term, 15 cycles); a red arrow labels this block "PipelineDepth = 15". Two mint boxes to the right, tagged by a mint arrow "RefetchLatency = 2 cycles", show the refill startup before correct work resumes. The bold caption underneath reads "Penalty = 15 + 2 = 17 cycles". Read it left-to-right: wrong work first, then the small refill, summing to the penalty.

Definition Stall cost

$s$ — two different events that happen to both cost 2 If instead of guessing we simply wait, the pipeline pauses only until the branch's condition is computed and the correct address is known. Crucially, no wrong-path instructions are ever fetched, so there is nothing to squash and no belt-full of garbage — the big depth term $N$ never appears. All you pay is the short redirect: the branch resolves, the fetcher is pointed at the (already-known-correct) next address, and the first correct instruction is fetched. On this machine that redirect wait is $s = 2$ cycles.

Why does this "resolve-and-redirect" wait come out numerically equal to the refetch latency (also 2)? They are conceptually different events: the refetch latency is "go to the instruction cache and fetch the corrected target after a wrong guess", while the stall redirect is "point the fetcher at the correct target we were never wrong about and fetch it". But both end in the same physical act — a single instruction-cache access that hits — and on this machine one I-cache hit plus feeding its result to the front of the belt takes $2$ cycles. So they match because the dominant cost in each is one and the same I-cache-hit fetch, not by coincidence of definition. If the I-cache missed, both would grow together.

Keep the two prices apart in your head even though the numbers tie: $s$ is paid every branch if you stall (a cheap redirect, no wrong work); $P$ is paid only on wrong guesses if you speculate (a whole belt of wrong work, $N + 2$ ).

We now have the two quantities every exercise uses: $P = Penalty = 17$ and $s = stall cost = 2$ , on a machine with $N = 15$ .

Level 1 — Recognition

(Can you name and classify the pieces?)

Exercise 1.1

Sort each item into architectural or microarchitectural state: (a) general-purpose register rax, (b) the ROB, (c) the L1 data cache, (d) main memory, (e) the branch-predictor counter table.

Recall Solution

The test is: can a normal program read this directly?

Architectural (program can see): (a) rax, (d) main memory.
Microarchitectural (hidden helper): (b) ROB, (c) L1 cache, (e) predictor table.

Cache is the sneaky one: a program cannot read the cache directly, but it can time memory accesses and infer what is cached. That timing leak is the seed of every Spectre-style side-channel attack.

Exercise 1.2

Match each stage of speculation to its purpose:

Predict — 2. Checkpoint — 3. Execute — 4. Verify — 5. Commit/Squash. Purposes: (A) run instructions from the guessed path; (B) guess the branch outcome; (C) make architectural state real or undo it; (D) save state so we can roll back; (E) compare the real branch result to the guess.

Recall Solution

1→B, 2→D, 3→A, 4→E, 5→C. The order matters: you checkpoint before you execute, because you cannot roll back to a state you never saved.

Level 2 — Application

(Plug numbers into the machinery.)

For Levels 2–3 use the baseline machine from the derivation above: pipeline depth $N = 15$ , penalty $P = 17$ cycles, stall cost $s = 2$ cycles.

Exercise 2.1

A program runs $1000$ branches. The predictor is $95%$ accurate. How many cycles are wasted on mispredictions?

Recall Solution

Mispredicted branches: $1000 \times (1 - 0.95) = 50$ . Each costs $17$ cycles → $50 \times 17 = 850$ cycles. Answer: $850$ cycles wasted.

Exercise 2.2

The loop from the parent note:

for (int i = 0; i < 100; i++) sum += array[i];

The i < 100 branch is taken $99$ times and not-taken once (the exit). Consider two different design strategies and their own stall costs:

(a) "in-order, drain-on-branch" — an old-style in-order core that cannot rename or reorder, so on every branch it must drain the whole pipeline before re-steering. Draining an $N = 15$ -stage belt costs the full pipeline depth $= 15$ cycles per branch. (This is a stronger stall than our modern $s = 2$ : this machine cannot even overlap the resolve with useful work.)
(b) speculation on the modern machine — pay the $P = 17$ -cycle penalty only on the single misprediction (the loop exit).

Compute the total stall cycles for (a) and (b), then give the ratio (a)/(b).

Recall Solution

Why 15 here but $s = 2$ elsewhere? The $s = 2$ redirect assumes a modern out-of-order front end that only needs a quick re-steer. The (a) machine is deliberately a different, older design that drains all 15 stages on every branch — it has no cheap redirect, so its per-branch stall equals the whole depth $N = 15$ . We compare the worst realistic non-speculative machine against speculation to show the full payoff. (a) $100 \times 15 = 1500$ stall cycles. (b) $1 \times 17 = 17$ stall cycles. Ratio $= 1500/17 \approx 88.2$ . Speculation removes ~ $88 \times$ the stall cost here because the loop is almost perfectly predictable.

Exercise 2.3

A branch on random data (rand() % 2 == 0) is predicted correctly $50%$ of the time. What is the average penalty per execution of this branch, and how does it compare to simply stalling the $s = 2$ cycles (defined above) until the branch resolves?

Recall Solution

Expected penalty $= 0.5 \times 17 = 8.5$ cycles per branch. A plain stall costs only $s = 2$ cycles. Here speculation is $8.5 - 2 = 6.5$ cycles worse on average. For a 50/50 branch, not speculating wins.

Level 3 — Analysis

(Reason about trade-offs and rates.)

Exercise 3.1

A branch-heavy program executes one branch every $6$ instructions. Predictor accuracy is $95%$ , penalty $17$ cycles. Compute the extra CPI (cycles per instruction) added by mispredictions.

Recall Solution

Fraction of instructions that are branches: $\frac{1}{6}$ . Of those, $5%$ mispredict. Extra cycles per instruction: $branch freq \frac{1}{6} \times miss rate 0.05 \times penalty 17 = 0.1417 CPI .$ So roughly $0.14$ extra cycles per instruction — real, but far cheaper than stalling on every branch.

Exercise 3.2

Two predictor designs are offered for the same workload (branch every $6$ instructions):

Design A: accuracy $92%$ , pipeline depth $12$ → penalty $12 + 2 = 14$ .
Design B: accuracy $97%$ , pipeline depth $20$ → penalty $20 + 2 = 22$ . Which adds less misprediction overhead per instruction?

Recall Solution

Extra CPI $= \frac{1}{6} \times (1 - acc) \times penalty$ .

A: $\frac{1}{6} \times 0.08 \times 14 = 0.18 \overline{6}$ CPI.
B: $\frac{1}{6} \times 0.03 \times 22 = 0.11$ CPI. Design B wins ( $0.11 < 0.187$ ). The deeper pipeline (bigger penalty) is more than offset by the much lower miss rate. Deep pipelines only pay off when the predictor is good enough.

Exercise 3.3

The parent note links speculation to out-of-order execution via the ROB. Explain in 2–3 sentences why the ROB is what makes rollback possible, and what would break if speculative results were written straight to rax.

Recall Solution

The ROB holds speculative results in program order but not yet committed — a staging area. On a misprediction, the CPU simply discards the wrong ROB entries; architectural registers were never touched, so nothing to undo. If results were written straight to rax, a wrong guess would overwrite the real value with garbage and there would be no clean copy to restore — speculation would corrupt the program. The ROB is the checkpoint that separates computed from committed.

Level 4 — Synthesis

(Combine ideas into a security/design argument.)

Exercise 4.1 — The Spectre gadget

A malicious program wants to read a secret byte it is not allowed to read. It uses the sequence below. Label each step as architectural or microarchitectural, and explain why the secret still leaks even though step 3 is squashed.

Train the branch predictor to expect "in-bounds".
Pass an out-of-bounds index so the guard branch mispredicts into the forbidden path.
Speculatively load secret, then load probe[secret * 256].
Branch resolves → all of step 3 is squashed.
Attacker times reads of probe[0], probe[256], ... to see which is fast.

Recall Solution

Steps 1, 3, 5 operate on microarchitectural state (predictor + cache). Step 4's squash restores architectural state.
The leak survives because squash only undoes architectural effects (registers, memory). It does not evict the cache line that step 3 pulled in. probe[secret*256] stays cached.
In step 5 the attacker reads all $256$ possible probe slots; the one fast (cached) slot reveals secret. See the timing sketch below.

Figure s02 — a bar chart of eight probe slots (indices 0–7) with measured access time in cycles on the vertical axis. Seven bars stand tall near 120 cycles in lavender (evicted, slow); one bar at index 3 drops to about 42 cycles in mint (still cached, fast). A dashed coral "cache-hit threshold" line at 70 cycles separates them, and a coral arrow points at the short bar reading "fast = cached ⇒ secret is 3". The single fast slot's index is the leaked secret value.

This is the whole point of cache side channels: architectural rollback is not a security boundary because it forgets to undo the cache.

Exercise 4.2 — Which fix, and why

Match each mitigation to the exact step it disrupts: (A) lfence speculation barrier — (B) flushing predictor on context switch — (C) retpoline for indirect branches. Steps: (i) training the predictor across a privilege boundary; (ii) speculatively issuing the secret-dependent load; (iii) speculating through an indirect/call *reg branch.

Recall Solution

A → (ii): lfence stops execution proceeding speculatively past it, so the secret-dependent load never issues under speculation.
B → (i): clearing the predictor between contexts stops the attacker's training from carrying into the victim.
C → (iii): a retpoline replaces an indirect jump with a controlled ret-based trampoline the predictor cannot steer to an attacker target. Each fix attacks a different stage — which is why real CPUs deploy several together.

Level 5 — Mastery

(Design and defend a full decision.)

Exercise 5.1 — Speculate-or-stall decision rule

Derive the general condition under which speculation is worth it versus stalling. Reusing our two quantities: let $a$ = predictor accuracy, $P$ = misprediction penalty (cycles, $= 17$ here), $s$ = stall cost if we don't speculate (cycles, $= 2$ here). Then find the break-even accuracy $a^{*}$ , and say what happens exactly at that accuracy.

Recall Solution

Expected cost of speculating $= (1 - a) P$ (you only pay the penalty when wrong; correct guesses cost $0$ ). Cost of stalling $= s$ (always paid). Speculation wins when $(1 - a) P < s ⟹ a > 1 - \frac{s}{P} .$ Break-even: $a^{*} = 1 - \frac{s}{P} = 1 - \frac{2}{17} \approx 0.882$ . The tie case $a = a^{*}$ : here $(1 - a) P = s$ exactly — speculating and stalling cost the same on average, so neither is better and the choice is a wash (real designs then prefer stalling to avoid the security exposure of speculating). Strictly above $a^{*}$ , speculate; strictly below, stall.

Figure s03 — a line plot with predictor accuracy $a$ (0 to 1) on the horizontal axis and expected cost in cycles per branch on the vertical axis. A flat coral line sits at the constant stall cost $s = 2$ ; a sloped lavender line traces $(1 - a) P$ , falling from $17$ at $a = 0$ to $0$ at $a = 1$ . The two lines cross at the mint-dashed break-even $a^{*} \approx 0.882$ , marked with a slate dot. The mint-shaded region to the right of the crossing is labelled "speculate wins"; the left region is labelled "stalling wins".

Exercise 5.2 — Redesign a bad branch

You profile a hot branch: accuracy $55%$ , executed $1, 000, 000$ times, $P = 17$ , and stalling would cost $s = 2$ . (a) How many cycles does speculation waste vs. stalling? (b) Name two software rewrites (from the parent note) and say which one removes the branch entirely.

Recall Solution

(a) Speculating: $(1 - 0.55) \times 17 = 7.65$ cycles/branch → $7.65 \times 1 0^{6} = 7, 650, 000$ cycles. Stalling: $2 \times 1 0^{6} = 2, 000, 000$ cycles. Speculation wastes $7.65 M - 2 M = 5, 650, 000$ extra cycles. (Consistent with 5.1: $0.55 < 0.882$ , so speculation loses.) (b) Sort the data to make the branch biased/predictable, or write branchless code (cmov, bitwise select). The branchless rewrite removes the branch entirely, so there is nothing left to mispredict — the surest fix.

Exercise 5.3 — Tie it together

In one paragraph, connect Instruction-level parallelism (ILP), superscalar width, and speculation: why does a wider superscalar machine need better speculation?

Recall Solution

A superscalar core issues several instructions per cycle to exploit ILP — but branches occur every few instructions, so a wide machine hits a branch almost every cycle. Without accurate speculation it would stall constantly, and its extra issue slots would sit idle (the very hazard speculation exists to hide). Wider issue raises the cost of each stall (more idle slots) and raises the branch encounter rate, so the payoff of every 1% of predictor accuracy grows with width. Wide + deep machines and strong predictors are therefore inseparable.