Control hazards and pipeline flushes: Visual walkthrough

Before any symbol appears, we agree on the picture everything sits on: the pipeline diagram.

Step 1 — Draw the pipeline as a conveyor belt

WHAT. We lay the five stations left-to-right and let one instruction advance one station per cycle. If a new instruction enters IF every cycle, five instructions are "in flight" at once, each in a different station.

WHY. The whole hazard problem only exists because several instructions overlap in time. You cannot see the cost of a wrong guess until you can see multiple instructions coexisting. So the belt is the stage on which the drama plays out.

PICTURE. The belt below shows one instruction sliding right, one station per tick. Notice the red PC feeding IF — that arrow is the thing a branch will later hijack.

This belt is the same one from pipelining fundamentals; if IF/ID/EX/MEM/WB feel shaky, revisit that first.

Step 2 — Watch IF commit to the next address before EX knows the answer

WHAT. Every cycle, IF fetches whatever the PC points to, then blindly bumps the PC by 4. It does this immediately, at the end of IF — it cannot wait, because next cycle IF must feed a fresh instruction or the belt starves.

WHY. This is the seed of the whole problem. A branch (see branch instructions) might want the PC to jump somewhere far away — but that decision happens later, in EX. IF has already moved on. The fetch is a bet placed before the result is known.

PICTURE. The red arrow is the PC. It advances $100 \to 104 \to 108$ on its own, cycle after cycle, with no idea a branch is sitting in the belt behind it.

Here each symbol, term-by-term:

$address IF will fetch PC_{next} = address just fetched PC_{now} + bytes per instruction 4$

Step 3 — Pin down when the branch actually answers "taken?"

WHAT. A branch like BEQ R1, R2, 200 ("go to 200 if R1 equals R2") must subtract $R 1 - R 2$ to test equality. That subtraction lives in the ALU, which lives in EX. So the answer arrives at EX — no sooner.

WHY. We need the exact cycle of the answer because the number of wasted instructions is literally how many the belt swallowed while waiting. Earlier resolution → fewer wasted; later → more. This is the pivot of the whole derivation.

PICTURE. Follow the branch (red) as it crawls IF → ID → EX. The green "✓ decided" flag lights up only when it reaches EX.

Let $t$ be the cycle the branch sits in IF. Then:

$branch in EX at cycle IF \to ID \to EX, two hops t + 2$

Step 4 — Count who slipped in behind it

WHAT. While the branch travels IF (cycle $t$ ) → ID (cycle $t + 1$ ) → EX (cycle $t + 2$ ), IF did not sit idle. It fetched the fall-through instructions at PC+4 (during cycle $t + 1$ ) and PC+8 (during cycle $t + 2$ ).

WHY. Those two instructions are the wrong-path candidates. They only make sense if the branch was not taken. We fetched them on the default "straight ahead" bet from Step 2 — before Step 3's answer was in.

PICTURE. Snapshot at cycle $t + 2$ : the branch is in EX (red), and directly behind it sit two instructions the belt already accepted — PC+4 in ID, PC+8 in IF. Those two are what a taken branch will condemn.

$wrong-path instructions in flight = cycle branch resolves (t + 2) - cycle branch fetched t = 2$

$(t + 2)$ — the cycle the answer arrives.
$t$ — the cycle the gate opened and fetching-past-the-branch began.
Their difference is the count of extra fetches, i.e. the branch penalty.

This is the parent's headline formula, now seen:

$Penalty = (resolve stage index) - (fetch stage index) = EX - IF = 2.$

Step 5 — The flush: turn the two intruders into bubbles

WHAT. At cycle $t + 2$ , EX declares taken. Hardware does two things at once: (1) sets PC = target so cycle $t + 3$ fetches the correct instruction (OR@200), and (2) reaches back into the IF/ID and ID/EX pipeline registers holding the two wrong-path instructions and kills their control signals, converting them to bubbles.

WHY not just delete them? The belt is clocked — every station must hand something to the next station each tick, or downstream logic desynchronises. You cannot pull a link out of a moving chain. So instead you neuter the link: it keeps moving but does nothing. (This is the same bubble machinery used for data-hazard stalls, repurposed.)

PICTURE. Same snapshot as Step 4, but now the two red intruders are crossed out and relabelled BUBBLE; the red PC arrow snaps from 108 to the target 200.

Step 6 — Edge case: branch not taken costs zero

WHAT. Suppose at cycle $t + 2$ EX says not taken. Then PC+4 and PC+8 were the right instructions all along. Nothing is flushed. Penalty = 0.

WHY. Our default fetch (Step 2) was a bet on "straight ahead." When the branch agrees with that bet, the bet paid off — the belt is already full of correct work. This is exactly why predict-not-taken (parent note) is free on not-taken branches.

PICTURE. Two belts side by side: taken (top, two red bubbles) vs not-taken (bottom, everything black and alive). Only mismatched guesses cost cycles.

$Penalty = flush count 2 \times fraction that betray the guess P (taken)$

So the average cost depends on how often the guess is wrong — which is the whole reason branch prediction and speculation exist.

Step 7 — Edge case: resolve one stage earlier, pay one less

WHAT. Add dedicated comparators in ID so equality is known one stage sooner. Now the branch resolves at cycle $t + 1$ .

WHY show this? To prove the "2" is not magic — it is resolve − fetch. Move resolution up by one stage and the arithmetic drops the penalty by exactly one.

PICTURE. The Step 4 count-line redrawn with the "decided" flag moved left onto ID. Only one instruction (PC+4) has slipped in behind.

$Penalty_{ID resolve} = (t + 1) - t = 1.$

Same formula, smaller gap. The count of wasted instructions equals the distance between where we guess and where we know.

The one-picture summary

One diagram, the whole story: the branch (red) resolves in EX at $t + 2$ ; the two instructions fetched at $t + 1$ and $t + 2$ become bubbles; the PC snaps to the target; the gap $(t + 2) - t = 2$ is the penalty. Slide the resolve point left → the gap shrinks.

Recall Feynman retelling — say it back in plain words

A pipeline is a conveyor belt where an instruction takes five ticks (IF, ID, EX, MEM, WB) to cross. Every tick, the fetch station must grab some instruction, so by default it grabs the next one in line and bumps the address by 4 — a bet that we're going straight. A branch, though, doesn't know whether to go straight or jump until it reaches the EX station, two ticks after it was fetched. In those two ticks the belt already sucked in two "straight ahead" instructions. If the branch says "jump!", those two are wrong-path garbage. We can't yank them off a moving belt, so we zero their controls — turn them into harmless bubbles — and point the address at the real target. Cost: two wasted ticks. The number two isn't special; it's just (the stage that decides) minus (the stage that fetches). Decide one stage earlier and you waste one fewer. Guess correctly (branch not taken) and you waste none.

Recall

Why exactly 2 wasted instructions for EX-resolved branches? ::: EX is two stages after IF, so the belt fetches 2 fall-through instructions before the branch's answer arrives: $(t + 2) - t = 2$ . What is a bubble and why not just delete the wrong instructions? ::: A no-op with all control signals zeroed; the clocked belt must hand something forward each tick, so we neuter rather than remove. Is the branch instruction itself ever flushed? ::: No — it is correct and must finish (update PC, reach WB). Only the instructions fetched after it are flushed. What is the penalty on a not-taken branch under predict-not-taken? ::: Zero — the fall-through instructions were the correct path. How does resolving in ID instead of EX change the penalty? ::: $(t + 1) - t = 1$ ; one fewer wrong instruction is fetched.