Control hazards and pipeline flushes: Worked examples

This page is the "drill ground" for the parent topic. We take every kind of situation a branch can create in a pipeline and grind through it with numbers. If you have not yet met the words pipeline, stage, flush, or bubble, pause and read 5.2.01-Pipelining-fundamentals and the parent note first — here we assume those pictures and go straight to arithmetic.

The scenario matrix

Every cell below is a distinct case class. The 8 worked examples that follow each announce which cell(s) they cover, and together they hit all of them.

Cell	Case class	What makes it different
A	Branch not taken, predict-not-taken	The lucky case: prediction correct, zero flush
B	Branch taken, resolves in EX	2 bubbles — the classic penalty
C	Branch taken, resolves in ID	1 bubble — early resolution
D	Degenerate: pipeline with resolve-in-IF	0 bubbles — the limiting "no penalty" case
E	Mixed program CPI with branch fraction $f$	Average-case performance formula
F	2-bit predictor state walk (loop)	Sign/direction of counter over many iterations
G	Real-world word problem	Speedup lost to mispredictions
H	Exam twist: nested / back-to-back branches	Two branches in flight at once

Symbols used everywhere (defined once):

Example B (and D, C) — where does the penalty come from?

Forecast: Guess before reading — bigger $n$ means more or fewer bubbles? Write your three numbers now.

Figure — Control hazards and pipeline flushes

Steps.

Fetch happens in stage 1 (IF). Why this step? The very moment the branch is fetched, next cycle we already fetch the following (straight-line) instruction. Fetching never pauses.
Count belt slots strictly after IF up to and including the resolve stage. Why? Each cycle between "branch in IF" and "branch resolved" loads exactly one new straight-line instruction into IF. Those are the doomed ones. The count is $n - 1$ .
Plug $n$ :
- Resolve in IF ( $n = 1$ ): $b = 1 - 1 = 0$ . → Cell D, the limiting no-penalty case.
- Resolve in ID ( $n = 2$ ): $b = 2 - 1 = 1$ . → Cell C.
- Resolve in EX ( $n = 3$ ): $b = 3 - 1 = 2$ . → Cell B, the classic.

Verify: In the parent's cycle table (BEQ resolves in EX), exactly ADD@104 and SUB@108 became bubbles — that is 2, matching $b = 3 - 1 = 2$ . ✓ Units: a count of instructions/cycles, dimensionless. ✓

Recall Quick recall

Penalty for resolve in stage $n$ ::: $b = n - 1$ bubbles. Why is resolve-in-IF (b=0) only theoretical? ::: You can't know the branch outcome in the same cycle you fetch it — you haven't even decoded it yet.

Example A — the lucky path: prediction correct, zero flush

Forecast: Zero? One? Two?

Steps.

We speculatively fetched PC+4, PC+8 while the branch flowed IF→ID→EX. Why? Predict-not-taken means "keep going straight" — exactly what fetching PC+4 does.
Branch resolves not-taken in EX. Why does this matter? The straight-line instructions we fetched were the right ones. Nothing to undo.
Bubbles inserted $= 0$ . Penalty $= 0$ cycles.

Verify: Prediction ("not taken") = outcome ("not taken") ⇒ correct ⇒ $b = 0$ . Sanity: this is why predict-not-taken is free on straight-line code and only costs when a branch is genuinely taken. ✓

Example E — average CPI of a real program

Forecast: Slowdown bigger or smaller than 20%? Jot a guess.

Steps.

Penalty per branch (average) $= p_{t} \cdot b = 0.60 \times 2 = 1.2$ cycles. Why multiply? Only taken branches flush; not-taken ones cost 0, so we weight by $p_{t}$ .
Penalty spread over ALL instructions $= f \times (p_{t} \cdot b) = 0.20 \times 1.2 = 0.24$ . Why multiply by $f$ ? Only a fifth of instructions are branches; the average extra cost per instruction dilutes accordingly.
Effective CPI $= ideal CPI + penalty per instr = 1 + 0.24 = 1.24$ .
Slowdown $= \frac{1.24 - 1}{1} = 0.24 = 24%$ .

$CPI_{eff} = 1 + f p_{t} b = 1 + 0.20 \times 0.60 \times 2 = 1.24$

Verify: Units: cycles/instruction, dimensionless slowdown. Sanity: if $p_{t} = 0$ (never taken) CPI→1 (free), and if $f = 1, p_{t} = 1, b = 2$ then CPI $= 3$ (every instruction stalls fully) — both extremes make sense. ✓

Example C — early resolution saves a bubble

Forecast: Better or worse than 1.24?

Steps.

New penalty $b = n - 1 = 2 - 1 = 1$ bubble. Why? Resolve one stage earlier ⇒ one fewer wrong-path instruction fetched.
$CPI_{eff} = 1 + f p_{t} b = 1 + 0.20 \times 0.60 \times 1 = 1.12$ .
Improvement vs Example E $= 1.24 - 1.12 = 0.12$ CPI saved.

Verify: Halving $b$ (2→1) halves the branch penalty term ( $0.24 \to 0.12$ ), so CPI drops from 1.24 to 1.12. ✓ This is the payoff of early-resolve hardware — see 5.2.09-Branch-prediction-techniques for pushing this further.

Example F — the 2-bit predictor state walk

Forecast: 1 miss per loop? 2? Where does the counter land after the exit?

Steps.

Taken outcome ⇒ counter $\to min (3, c + 1)$ ; Not-taken ⇒ $\to max (0, c - 1)$ . Why saturating? Values clamp at 0 and 3 so a long run of "taken" builds confidence but can't overflow.
99 taken outcomes: counter is pinned at $3$ (already max, stays 3). Predict Taken each time ⇒ 0 misses. Why? $3 \geq 2$ ⇒ predict Taken = actual Taken. ✓
The exit (not-taken): predicted Taken (counter=3 $\geq 2$ ) but actual Not-taken ⇒ 1 misprediction. Counter $\to 3 - 1 = 2$ (Weakly Taken).
Second loop's first iteration (taken): counter $= 2 \geq 2$ ⇒ predict Taken = actual Taken ⇒ correct, counter $\to 3$ again.
Per loop total = 1 misprediction (the exit only). Two loops ⇒ 2 mispredictions total.

Verify: Compare to a 1-bit predictor: it would miss at both exit and next-entry = 2 per loop ⇒ 4 over two loops. The 2-bit halves it. Final counter after first exit $= 2$ . ✓ Matches parent's claim "1 misprediction per loop". See 5.2.09-Branch-prediction-techniques for two-level predictors that do even better.

Example G — word problem: speedup lost to mispredictions

Forecast: Do we still get near $5 \times$ , or does branching eat it?

Steps.

Effective CPI $= 1 + f p_{m} b = 1 + 0.25 \times 0.10 \times 2 = 1 + 0.05 = 1.05$ . Why $p_{m}$ here, not $p_{t}$ ? With a real predictor only the mispredicted branches flush — that fraction is $p_{m}$ .
Real speedup vs the 5-cycle non-pipelined machine $= \frac{5}{CPI _{eff}} = \frac{5}{1.05} \approx 4.76$ .
Fraction of ideal delivered $= \frac{4.76}{5} = 0.952 = 95.2%$ .

Verify: $5/1.05 = 4.7619...$ ; times pipeline is 95.2% of the promised $5 \times$ . Sanity: a perfect predictor ( $p_{m} = 0$ ) gives CPI 1 and full $5 \times$ ; a terrible one ( $p_{m} = 1$ ) gives CPI $1.5$ , speedup $3.33$ . Our answer sits sensibly between. ✓ Units: cycles cancel, speedup is dimensionless. ✓

Example H — exam twist: two branches back-to-back

Worked example A branch whose target is another branch (Cell H)

Predict-not-taken, resolve in EX ( $b = 2$ ). Instruction stream:

100: BEQ ... , 300   # Branch 1 — TAKEN
104: ADD            # wrong-path
108: SUB            # wrong-path
300: BEQ ... , 500   # Branch 2 (the correct target) — also TAKEN

Both branches are taken. How many total bubbles across the two branches, and how many cycles does it take to reach the first useful instruction after Branch 2?

Forecast: Do the penalties add? Overlap? Guess a bubble count.

Steps.

Branch 1 taken, resolves EX ⇒ 2 bubbles (ADD@104, SUB@108 flushed). Why? Standard $b = 2$ ; the predicted straight-line path was wrong.
After the flush, PC = 300; we fetch BEQ@300. This is now a fresh branch — the pipeline doesn't know it's a branch either, so predict-not-taken again fetches 304, 308.
Branch 2 taken, resolves EX ⇒ 2 more bubbles. Why don't they overlap? Branch 2 wasn't even in the pipeline until Branch 1 finished redirecting the PC; their penalties are sequential, not hidden.
Total bubbles $= 2 + 2 = 4$ .
Cycles to first useful post-Branch-2 instruction: each taken branch adds its $b = 2$ penalty before the correct target flows, so $2 + 2 = 4$ wasted cycles on top of normal flow.

Verify: Two independent taken branches with resolve-in-EX ⇒ $2 b = 2 \times 2 = 4$ bubbles total; penalties do not overlap because the second branch's fetch depends on the first's redirect. ✓ This chained cost is exactly what 5.2.11-Speculative-execution and good predictors (5.2.09-Branch-prediction-techniques) attack. Branch encoding details live in 4.3.08-Branch-instructions.

Recall Full self-test

Penalty for resolve in stage $n$ ? ::: $b = n - 1$ bubbles. Predict-not-taken, branch not taken — bubbles? ::: 0 (prediction correct). Master CPI formula? ::: $CPI_{eff} = 1 + f p_{m} b$ . Example E answer (f=0.20, p_t=0.60, b=2)? ::: CPI = 1.24, i.e. 24% slowdown. Move resolve EX→ID: new penalty? ::: b drops 2→1, CPI 1.24→1.12. 2-bit predictor, loop run twice, 99 taken + 1 exit each? ::: 2 mispredictions total (1 per exit). Example G real speedup (f=0.25, p_m=0.10, b=2, ideal 5×)? ::: CPI 1.05, speedup ≈ 4.76 (95.2% of ideal). Two back-to-back taken branches, resolve EX? ::: 4 bubbles total (penalties are sequential).