Control hazards and pipeline flushes: Exercises — Hardware deep dive

These problems build from recognising what a flush is up to designing penalty budgets and predictor behaviour. Every solution is hidden inside a collapsible callout so you can test yourself first. If a term feels unfamiliar, re-read Control hazards and pipeline flushes — nothing here is used before it appears there.

Prerequisite muscles: 5.2.01-Pipelining-fundamentals (the five stages IF, ID, EX, MEM, WB), 4.3.08-Branch-instructions (what a branch is), and 5.2.05-Data-hazards-and-forwarding (bubbles as a concept).

Definition Two words we will lean on: CPI and control signals

CPI = cycles per instruction. It is the average number of clock cycles the processor spends per instruction over a whole program. A perfect pipeline runs one instruction every cycle, so its base $CPI = 1$ . Every flush adds wasted cycles, nudging CPI above 1. Lower CPI = faster machine (fewer cycles for the same work).

Control signals are the little on/off wires the decoder attaches to each instruction telling the datapath what to do. Two matter here:

RegWrite — a 1-bit wire; when 1 the instruction is allowed to write its result into a register, when 0 it writes nothing.
MemWrite — a 1-bit wire; when 1 the instruction may store to memory, when 0 it stores nothing.

A bubble is simply an in-flight instruction whose RegWrite and MemWrite have both been forced to 0 — it flows through the stages but changes nothing observable. That is how a flush is physically done.

Figure — Control hazards and pipeline flushes

Figure 1 — Pipeline timeline. The teal BEQ branch resolves in EX at cycle 3. The two orange instructions (ADD, SUB) fetched behind it in cycles 2 and 3 are on the wrong path; at cycle 4 they become hatched "BUB" bubbles. The horizontal distance between "where we fetch (IF)" and "where we resolve (EX)" is exactly the number of instructions thrown away.

Look at the figure: the branch is in teal, resolving in EX at cycle 3. The two orange boxes fetched behind it (cycles 2 and 3) are the wrong-path instructions. The gap between "where we fetch" (IF) and "where we resolve" (EX) is exactly the number of instructions we must throw away.

Intuition WHY the penalty is a

product of three numbers Every exercise below computes "extra cycles per instruction" as $P (branch) \times P (misprediction) \times (flush count) .$ Read it left to right as a chain of filters over a long stream of instructions:

Out of all instructions, only a fraction $P (branch)$ are branches — the rest never cause a control hazard.
Of those branches, only a fraction $P (misprediction)$ actually guess wrong — a correct guess wastes zero cycles.
Each wrong guess costs exactly (flush count) wasted cycles (the wrong-path instructions turned into bubbles).

Multiplying gives the average wasted cycles spread over every instruction. We multiply (not add) because each factor narrows down the previous group: branches among instructions, then mispredicts among branches, then cycles per mispredict. That average is precisely the amount CPI rises above its base of 1.

Level 1 — Recognition

Exercise 1.1

In a classic 5-stage RISC pipeline (IF, ID, EX, MEM, WB) where a branch resolves in the EX stage, how many instructions must be flushed when the branch is taken?

Recall Solution

The branch is fetched (IF) at cycle $t$ . It reaches EX at cycle $t + 2$ (IF→ID→EX is two hops). Meanwhile the fetcher ran ahead:

Cycle $t + 1$ : fetched the instruction now sitting in ID.
Cycle $t + 2$ : fetched the instruction now sitting in IF.

That is 2 instructions on the wrong path. Using the stage numbering from the top of the page ( $IF = 1$ , $EX = 3$ ): $flush count = (stage where resolved) - (stage where fetched) = 3 - 1 = 2$ Answer: 2 instructions.

Exercise 1.2

Fill in the blank: A flushed instruction is turned into a bubble, which means its control signals RegWrite and MemWrite are set to what value, and why?

Recall Solution

Both are set to 0 (recall the control-signal definition at the top of the page).

RegWrite = 0 → the instruction writes no register.
MemWrite = 0 → the instruction writes no memory.

Setting these to 0 makes the instruction architecturally invisible: it flows through the remaining stages like any other instruction, but changes nothing the programmer can observe. We do not delete it, because deleting a slot mid-flight would desynchronise the perfectly-clocked stages.

Level 2 — Application

Exercise 2.1

A program has 20% branch instructions. The pipeline resolves branches in EX (2-cycle penalty) and flushes on every taken branch. If 60% of branches are taken, what is the average extra cycles per instruction (the CPI penalty)?

Recall Solution

Only taken branches cost a flush (this design assumes predict-not-taken implicitly — a taken branch means the fetched not-taken instructions were wrong), so here $P (misprediction) = P (taken)$ . Apply the product rule from the intuition box: $penalty per instr = P (branch) \times P (taken) \times flush cycles$ $= 0.20 \times 0.60 \times 2 = 0.24 cycles/instruction$ Answer: 0.24 extra cycles per instruction (i.e. CPI rises from 1 to 1.24).

Exercise 2.2

Same machine as 2.1 but a hardware trick lets branches resolve in ID (1-cycle penalty). Recompute the CPI penalty, and state the percentage improvement over 2.1.

Recall Solution

Flush cycles drop from 2 to 1: $0.20 \times 0.60 \times 1 = 0.12 cycles/instruction$ Improvement: $\frac{0.24 - 0.12}{0.24} = 0.50 = 50%$ Answer: 0.12 cycles/instruction, a 50% reduction in branch penalty. Why: resolving one stage earlier means the fetcher has run ahead by only one wrong instruction instead of two, so exactly half the wasted work disappears.

Level 3 — Analysis

Exercise 3.1

A processor uses static predict-not-taken, 2-cycle EX resolution. Branches are 20% of instructions. Measurements show branches are taken 65% of the time. (a) What is the average branch penalty per instruction? (b) The architect proposes static predict-taken with target computed in ID (1-cycle penalty when the guess is wrong). Assume predict-taken is wrong exactly when the branch is not taken. Which scheme is better?

Recall Solution

(a) Predict-not-taken. Wrong whenever branch is taken (penalty 2): $0.20 \times 0.65 \times 2 = 0.26 cycles/instruction$

(b) Predict-taken. Wrong whenever branch is not taken ( $1 - 0.65 = 0.35$ ), penalty 1: $0.20 \times 0.35 \times 1 = 0.07 cycles/instruction$

Compare: $0.07 < 0.26$ , so predict-taken is better here — it both guesses the more common outcome and pays a smaller penalty (1 vs 2 cycles) when wrong. Answer: (a) 0.26; (b) 0.07 — predict-taken wins.

Exercise 3.2

Trace a 2-bit saturating counter (states: 00 Strongly-NT, 01 Weakly-NT, 10 Weakly-T, 11 Strongly-T; predict taken if state ≥ 10). It starts at 11 (Strongly Taken). A loop branch is taken 4 times then not-taken once (loop exit), and this whole pattern repeats. How many mispredictions occur per full loop pass in steady state?

Before solving, study the state machine in Figure 2 — it shows exactly how "taken" and "not-taken" outcomes push the counter left and right, and why the two middle "weak" states give it memory.

Figure 2 — The 2-bit saturating counter. Four states run left (Strongly Not-Taken, 00) to right (Strongly Taken, 11). Teal "taken" arrows push the state one step right; orange "not-taken" arrows push one step left; the ends saturate (stay put). The predictor guesses taken for the two right states (≥ 10) and not-taken for the two left states (≤ 01). A single wrong outcome only nudges one step, so it takes two consecutive wrong outcomes to cross the middle and flip the prediction.

Recall Solution

Walk the counter, using Figure 2 to track each step. "Predicts T" means state ≥ 10. Taken → count up (max 11); Not-taken → count down (min 00).

Actual	State before	Predict	Correct?	State after
T	11	T	✓	11
T	11	T	✓	11
T	11	T	✓	11
T	11	T	✓	11
NT (exit)	11	T	✗	10
T (re-enter)	10	T	✓	11

After the exit the counter only slips to 10 (still "taken", the right-hand teal region of Figure 2), so the very next taken iteration is predicted correctly and pulls it back to 11. Answer: exactly 1 misprediction per loop pass — the exit.

This is why 2 bits beats 1 bit: a single anomaly (the exit) can't flip the prediction, because two bits demand two consecutive wrong outcomes to change the trend.

Level 4 — Synthesis

Exercise 4.1

Design-budget problem. You have a 5-stage pipeline, base CPI = 1. Instruction mix: 20% branches, and among branches 70% taken. You may spend transistors on one of:

Option A: move branch resolution to ID → penalty 1 cycle on wrong guess, keep predict-not-taken.
Option B: add a dynamic predictor with 90% accuracy, keep 2-cycle EX resolution.

Compute the resulting CPI for each and pick the winner.

Recall Solution

Recall $CPI = 1 + branch penalty$ , and branch penalty $= P (branch) \times P (misprediction) \times flush count$ .

Option A (predict-not-taken, wrong only when taken, penalty 1): $penalty = 0.20 \times 0.70 \times 1 = 0.14$ $CPI_{A} = 1 + 0.14 = 1.14$

Option B (predictor wrong 10% of all branches regardless of direction, penalty 2): $penalty = 0.20 \times 0.10 \times 2 = 0.04$ $CPI_{B} = 1 + 0.04 = 1.04$

Compare: $1.04 < 1.14$ , so Option B (the dynamic predictor) wins. Its high accuracy (only 10% wrong) beats the cheaper-flush-but-still-often-wrong Option A. Answer: CPI_A = 1.14, CPI_B = 1.04 → choose Option B.

Exercise 4.2

Combine both improvements from 4.1: dynamic predictor at 90% accuracy and resolution moved to ID (penalty 1). Same mix (20% branches). What is the CPI, and what speedup does it give over the base machine that flushes 2 cycles on every taken branch (70% taken)?

Recall Solution

Base machine (no prediction, predict-not-taken, 2-cycle EX): $CPI_{ba se} = 1 + 0.20 \times 0.70 \times 2 = 1 + 0.28 = 1.28$

Combined machine (10% mispredict, 1-cycle penalty): $CPI_{co mb o} = 1 + 0.20 \times 0.10 \times 1 = 1 + 0.02 = 1.02$

Speedup (same clock, same instruction count → ratio of CPIs, since fewer cycles per instruction means proportionally less total time): $speedup = \frac{CPI _{ba se}}{CPI _{co mb o}} = \frac{1.28}{1.02} \approx 1.255$ Answer: CPI ≈ 1.02, speedup ≈ 1.25× (about 25% faster).

Level 5 — Mastery

Exercise 5.1

Using the 7-stage deep pipeline defined just above, a branch resolves in EX3 (stage 5) while fetch happens in stage 1. Instruction mix: 25% branches, 60% taken. A predictor has accuracy $a$ . (a) Write the general penalty formula in terms of the flush count $f$ , misprediction rate $(1 - a)$ , and branch fraction $b$ . (b) Find the minimum accuracy $a$ needed so the branch penalty per instruction is at most 0.05 cycles.

Recall Solution

(a) Flush count $f = (resolve stage) - (fetch stage) = 5 - 1 = 4$ instructions. A flush happens only on a misprediction, at rate $(1 - a)$ , and only for the branch fraction $b$ — the same three-factor product as every earlier exercise: $penalty = b \times (1 - a) \times f = 0.25 \times (1 - a) \times 4$

(b) Require penalty $\leq 0.05$ : $0.25 \times (1 - a) \times 4 \leq 0.05$ $1.0 \times (1 - a) \leq 0.05 \Rightarrow (1 - a) \leq 0.05$ $a \geq 0.95$ Answer: (a) penalty $= b (1 - a) f$ ; (b) need $a \geq 95%$ accuracy. Note the taken-fraction 60% never appears — with a directional predictor, what matters is whether the guess is right, not which way the branch actually went. Deep pipelines (large $f$ ) demand very accurate predictors precisely because each mistake costs 4 flushed slots.

Exercise 5.2

Cycle-count synthesis. The loop below runs its body 1000 times. The bottom branch BNE is taken 999 times (loops back) and not-taken once (exit). Resolution is in EX (2-cycle flush). Compare total flush cycles under (a) predict-not-taken and (b) a 2-bit predictor starting Strongly-Taken.

loop: ...          # loop body (no branches)
      BNE loop      # taken 999, not-taken 1

Recall Solution

(a) Predict-not-taken. The predictor always guesses "not taken", so it is wrong on every taken branch (999 of them), each costing 2 flush cycles. The single not-taken exit is predicted correctly (0 cost). $999 \times 2 = 1998 flush cycles$

(b) 2-bit predictor, starts Strongly-Taken (11). It predicts taken correctly for all 999 taken iterations (counter pinned at 11, never leaves the strongly-taken state). It mispredicts only the single exit (1 event), costing 2 cycles: $1 \times 2 = 2 flush cycles$

Answer: (a) 1998 cycles wasted, (b) 2 cycles wasted — a 999× reduction.

Concluding discussion: the 2-bit predictor is dramatically better for loops because it correctly guesses the common (taken) case, whereas predict-not-taken is exactly backwards for a backward-branching loop — it guesses wrong on essentially every iteration. This single example is why real machines never rely on predict-not-taken for loops and instead use dynamic prediction (or at minimum the "backward branches predicted taken" heuristic). Almost all of the 1998 wasted cycles simply vanish.

Recall Self-check summary (reveal after attempting all)

Branch penalty is always one product ::: $P (branch) \times P (misprediction) \times (flush count)$ Flush count formula ::: (resolve stage index) − (fetch stage index) What CPI means ::: average cycles per instruction; base 1, raised by every flush Why 2-bit beats 1-bit in loops ::: one anomaly (loop exit) can't flip a 2-bit prediction, so re-entry is still predicted correctly What a bubble actually is ::: an in-flight instruction with RegWrite=0, MemWrite=0 — flows through but changes nothing

See also: 5.2.11-Speculative-execution for what happens after a good prediction (running ahead), and the 5.2.08 Control hazards and pipeline flushes (Hinglish) walkthrough in Hinglish.