Speculative execution

What Is Speculative Execution?

Speculative execution is a CPU optimization where instructions are executed before the processor knows they're actually needed. The CPU makes predictions about:

Which branch a conditional jump will take
What value a memory load will return (value prediction)
Whether a branch will even be taken at all

WHY it exists: Modern CPUs have deep pipelines (15-20+ stages). Waiting for a branch to resolve creates a pipeline bubble—wasted cycles where execution units sit idle. By speculating, the CPU keeps all units busy.

HOW it works:

Predict the branch outcome using a branch predictor (saturating counters, perceptron predictors, etc.)
Fetch and execute instructions from the predicted path
Checkpoint architectural state before speculation
Verify the prediction when the branch resolves
Commit if correct, rollback (squash) if wrong

The Mechanics: How Speculation Flows

1. Branch Prediction

The branch predictor (a hardware table indexed by PC) guesses the outcome. Modern predictors use:

2-bit saturating counters: Track history (strongly taken, weakly taken, weakly not-taken, strongly not-taken)
Global history: Pattern of last N branches XORed with PC
Tournament predictors: Multiple algorithms compete, best one selected

2. Speculative Fetch & Execute

Instructions from the predicted path enter the pipeline. They:

Read registers from the Register Alias Table (RAT) (renaming avoids false dependencies)
Execute in reservation stations (out-of-order)
Store results in the Reorder Buffer (ROB)—a circular queue ordered by program order

Key point: Results are calculated but NOT written to architectural registers yet.

3. Branch Resolution

When the branch instruction finishes (condition evaluated), the CPU checks: $\text{Prediction Correct?} = (\text{Predicted Target} == \text{Actual Target})$

4. Commit or Squash

Correct prediction: Instructions in ROB commit to architectural state (write registers, memory). ROB entries freed.
Misprediction: All instructions after the branch are squashed—ROB entries discarded, pipeline flushed, fetch restarts at correct target.

Formula Misprediction Penalty

The cost of a misprediction: $\text{Penalty (cycles)} = \text{Pipeline Depth} + \text{Refetch Latency}$

Derivation:

When a branch mispredicts at stage $N$ of an $N$ -stage pipeline, allN-1$ instructions behind it are wrong.
Each must be flushed (1 cycle to invalidate).
Fetching the correct path takes $\approx 1$ - $3$ cycles (instruction cache hit).
Total: If pipeline depth =15, penalty $\approx 15 + 2 = 17$ cycles.

Why this matters: At 95% accuracy, 5% of branches pay this penalty. For branch-heavy code (every 5-7 instructions), this is $\approx 0.05 \times \frac{1}{6} \times 17 \approx 0.14$ cycles per instruction overhead—significant but worth it vs. always stalling.

Worked Examples

Worked example Example 1: Simple Conditional Branch

if (x > 10) {
    y = x * 2;  // Path A
} else {
    y = x + 5;  // Path B
}
z = y + 3;

Prediction: CPU guesses x > 10 is TRUE (based on history).

Step-by-step:

Fetch x > 10 comparison. Speculate Path A while comparison calculates.
Execute y = x * 2 speculatively—result goes to ROB, not architectural register y.
Comparison resolves: If x = 15, prediction correct!
- Why this step? We verify speculation doesn't violate program semantics.
Commit y = 30 to architectural state.
Execute z = y + 3 = 33 (can start early because y is in ROB). If wrong (x = 8):
Comparison resolves to FALSE.
Squash y = x * 2 from ROB.
Flush pipeline stages after branch.
Re-fetch Path B, execute y = x + 5 = 13.
Why this step? Architectural state must reflect the correct path—speculation is invisible to the program.

Worked example Example 2: Loop with Predictable Pattern

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

Branch: i < 100 at the end of each iteration.

Prediction: 2-bit counter starts "weakly taken". After 2 iterations, becomes "strongly taken".

Iterations 0-98: Predict taken (correct), no penalty.
Iteration 99: Predict taken, but i = 100 now—misprediction!
Why this step? Predictors work on patterns. This loop is 99% predictable; the exit is the only miss.

Performance:

Without speculation: Stall 15 cycles × 100 iterations = 1500 cycles wasted.
With speculation: 1 misprediction × 17 cycles = 17 cycles wasted.
Speedup: $\frac{1500}{17} \approx 88\times$ fewer stall cycles.

Worked example Example 3: Unpredictable Branch (Random Data)

if (rand() % 2 == 0) {
    process_even();
} else {
    process_odd();
}

Prediction: Random 50/50 outcomes—predictor accuracy $\approx 50\%$ .

Result: Half the time, pay misprediction penalty.

Cost per branch: $0.5 \times 17 = 8.5$ cycles average.
Why this step? Speculation hurts here! Better to stall (say, 2 cycles until branch resolves) than pay8.5 cycles on average.

Real CPUs: Some have "confidence estimators"—if predictor is uncertain, they stall instead of speculating.

Common Mistakes

Common mistake Mistake 3: "Speculative execution only affects performance, not correctness"

Why this feels right: The CPU promises to maintain architectural state correctly—speculation is invisible.

Steel-man: From the program's perspective, this was true pre-2018.

The reality: Spectre attacks (2018) showed speculative execution leaves traces in microarchitectural state (cache timings). A malicious program can:

Train the branch predictor to mispredict.
Speculatively access secret data (e.g., kernel memory).
The access is squashed, but it pulls data into cache.
Measure cache timing to infer the secret.

Fix: Modern CPUs have mitigations:

Speculation barriers (lfence on x86) prevent speculative memory access.
Flushing predictors on context switches.
Retpolines replace indirect branches.

This is a correctness issue for security-sensitive code.

Connections to Other Concepts

Branch prediction algorithms: The "brain" behind speculation—how predictions are made
Out-of-order execution: Speculation enables OO by providing instructions to execute
Reorder buffer (ROB): The data structure that makes speculation safe (staging area for results)
Pipeline hazards: Speculation eliminates control hazards (branch stalls)
Cache side-channel attacks: Spectre/Meltdown exploit speculative memory access
Instruction-level parallelism (ILP): Speculation exposes more ILP by looking past branches
Superscalar architecture: Multiple execution units need work—speculation keeps them fed

Recall Explain It to a 12-Year-Old

You're playing a video game where you walk through doors. Behind each door is either a treasure room or a trap. There's a sign that usually tells you which, but reading the sign takes 5 seconds.

Without speculation: You stop, read the sign, then walk through. Slow!

With speculation: You guess based on what the last10 doors were (if 9 were treasures, you guess treasure). You start walking before the sign loads. If you're right, you save 5 seconds! If wrong, you quickly back out (costs 2 seconds to turn around).

The CPU does this with code. It guesses which way your if statement will go and starts doing the work early. If it guesses right (95% of the time!), your program runs faster. If wrong, it quickly undoes the mistake and tries the other path. The bet pays off because being right is way more common than being wrong.

Flashcards

#flashcards/hardware

What is speculative execution? :: A CPU optimization where instructions are executed before the processor knows they're actually needed, based on predictions about branch outcomes. Results go to a reorder buffer and only commit to architectural state if the prediction was correct.

Why does speculative execution exist?

To avoid pipeline bubbles from branch stalls. Modern CPUs have deep pipelines (15-20 stages); waiting for every branch to resolve would leave execution units idle. Speculation keeps them busy.

What is the difference between architectural state and microarchitectural state?

Architectural state (registers, memory, flags) is visible to software and must be maintained correctly. Microarchitectural state (ROB, caches, branch predictors) is internal implementation detail. Speculation modifies microarchitectural state immediately but only commits to architectural state after verification.

What happens when a branch is mispredicted?

All instructions fetched from the wrong path are squashed (discarded from the reorder buffer), the pipeline is flushed, and fetching restarts from the correct target. This costs approximately pipeline_depth + refetch_latency cycles.

Calculate misprediction penalty for a 15-stage pipeline with 2-cycle refetch :: 15 (flush wrong instructions) + 2 (fetch correct path) = 17 cycles

Why can unpredictable branches make speculation hurt performance?

If a branch is 50/50 random, the predictor is wrong ~50% of the time. Paying the misprediction penalty (e.g., 17 cycles) half the time averages to 8.5 cycles—worse than just stalling for the branch to resolve (~2 cycles).

What is the Reorder Buffer (ROB) and why is it needed for speculation?

A circular queue that holds speculative instruction results in program order. It allows the CPU to execute instructions out-of-order but commit them in-order, ensuring correct architectural state even if speculations are wrong. Results stay in ROB until the instruction is verified to be on the correct path.

How do Spectre attacks exploit speculative execution?

They train the branch predictor to mispredict, causing the CPU to speculatively access secret data (e.g., kernel memory). Though the access is squashed, it leaves traces in cache timing that can be measured to infer the secret value.

What is a speculation barrier and when is it used?

An instruction (e.g., lfence on x86) that prevents speculative execution past that point. Used in security-sensitive code to ensure memory accesses aren't executed speculatively, mitigating Spectre-style attacks.

Why is speculation a "bet" that usually pays off?

Modern branch predictors achieve 95%+ accuracy. Being right 95% of the time means you save pipeline_depth cycles on95% of branches and only pay misprediction_penalty on 5%—the net gain is huge for predictable code patterns.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, speculative execution ek bahut smart trick hai jo modern CPUs use karte hain. Socho tumhara code ek if-else statement mein aayi—CPU ko branch resolve hone ka wait karna padta hai (15-20 cycles!). Lekin CPU bolti hai, "Main kyun wait karun? Main predict kar leti hoon ki if condition TRUE hogi aur pehle se hi uska kaam shuru kar deti hoon." Agar prediction sahi nikli (95% time yahi hota hai), toh tune15 cycles bach liye! Agar galat nikli, toh jaldi se wo kaam cancel kar deti hai aur sahi path se restart karti hai—isme thoda penalty lagta hai, but overall bet worth it hai.

Actual implementation mein CPUek Reorder Buffer (ROB) use karti hai—ek temporary storage jahan speculative results rakhte hain. Jab tak branch verify nahi ho jata, koi bhi result architectural registers mein nahi jata. Agar prediction correct nikli, ROB se results commit ho jate hain registers mein. Agar wrong nikli, toh ROB ke sare entries ko squash kar dete hain (discard) aur pipeline flush ho jaati hai. Is technique se loops, predictable branches, aur regular patterns wale code ka performance aasmaan chhoo jata hai—isliye ajkal har high-performance CPU speculation use karta hai. Lekin dhyan rahe, security issues bhi hain (Spectre attacks), jahan attacker speculation ka fayda utha ke secrets leak kar sakta hai cache timing se!