Pipeline hazards — structural, data (RAW - WAR - WAW), control: Visual walkthrough

This page goes term-by-term deeper than the parent hazards note. If a word feels unfamiliar, we build it here.

Step 1 — What "one clock cycle per instruction" even means

WHAT. Before any hazard, we imagine the perfect pipeline. A pipeline (see Instruction Pipelining basics) is an assembly line with 5 workstations: IF, ID, EX, MEM, WB. Once the line is full, one finished instruction rolls off the end every clock tick.

WHY. A clock cycle is one tick of the CPU's heartbeat — the fixed slice of time in which each workstation does exactly one small job. If a new instruction finishes every tick, then on average we spend 1 cycle per instruction. We give that average a name.

PICTURE. The grid below shows the filled line: five instructions, each shifted one tick right, and the green band where one instruction leaves per column — that steady drip is the meaning of $CPI = 1$ .

Figure — Pipeline hazards — structural, data (RAW - WAR - WAW), control

Step 2 — A bubble: the atom of "extra cost"

WHAT. When an instruction is not allowed to move forward this tick, we insert a bubble — a do-nothing gap that shoves everything behind it one cycle later.

WHY. A bubble is literally one wasted clock cycle. Everything expensive about hazards is measured in bubbles. So if we can count bubbles, we can compute CPI. That is the whole plan.

PICTURE. Same line as Step 1, but one instruction is held for a cycle. Watch the green "one per column" drip skip a beat — that skipped beat is exactly one extra cycle added to the whole program's length.

Step 3 — Why branches make bubbles at all

WHAT. A branch is an instruction that may change which instruction comes next (an if, a loop jump). The problem: IF must grab the next instruction immediately, but the branch doesn't decide its answer until a later stage (say EX).

WHY. The fetch unit can't wait — it fetches something right after the branch. If the branch later says "actually, go somewhere else," those already-fetched instructions are wrong and must be thrown away (flushed), leaving bubbles behind. (Guessing the answer early is branch prediction.)

PICTURE. The branch sits in the line; the two instructions fetched behind it are painted pink ("wrong path") and crossed out. The number of crossed-out slots before the correct instruction enters is $p$ .

Step 4 — Not every instruction is a branch: the fraction $b$

WHAT. In real code, only some instructions are branches. Let $b$ be the fraction of all instructions that are branches.

WHY. A bubble-causing event can only come from a branch. So before we multiply by any penalty, we must first shrink our attention to just the branch-shaped slice of the program. That slice's size is $b$ .

PICTURE. A long strip of 10 instruction-boxes; the branches are highlighted blue. Count them: 2 of 10 blue ⇒ $b = 0.2$ . Only the blue boxes can ever cost us.

Step 5 — Not every branch is mispredicted: the rate $m$

WHAT. Of the branches (the blue slice), only some are guessed wrong. Let $m$ be the fraction of branches that mispredict.

WHY. A correctly predicted branch costs zero bubbles — the fetched instructions were the right ones, nothing is flushed. Only the wrong guesses pay the penalty $p$ . So we must narrow the blue slice down again to the fraction $m$ that misfired.

PICTURE. Zoom into the two blue branches from Step 4. Split each into "guessed right" (blue, free) and "guessed wrong" (pink, costs $p$ ). Only the pink survivors reach the multiplication.

Step 6 — Multiply the funnel: assembling $b \cdot m \cdot p$

WHAT. We now chain the three filters into the average bubbles per instruction, $s_{ctrl}$ .

WHY. Read it as a funnel, left to right, per single instruction picked at random:

probability it is a branch $= b$ ,
times probability that branch is mispredicted $= m$ ,
times cost when that happens $= p$ cycles.

Multiplying an event's probability by its cost gives the average (expected) cost — that is exactly what "average bubbles per instruction" means.

PICTURE. A funnel: 100 instructions enter the top → $b$ narrows to the branches → $m$ narrows to the mispredicts → each survivor drops $p$ bubbles into the bucket. The bucket's total ÷ 100 is $b m p$ .

Plug into Step 2's $CPI = 1 + s$ (taking $s = s_{ctrl}$ ):

Step 7 — Sanity: the edge and degenerate cases

WHAT. A formula you can't stress-test is a formula you don't understand. We push each knob to its extreme.

WHY. If the equation stays sensible at the corners, we trust its middle.

Case	Set to	$CPI = 1 + bm p$	Reading
No branches	$b = 0$	$1$	Nothing to mispredict ⇒ perfect.
Perfect predictor	$m = 0$	$1$	Every guess right ⇒ no flush.
Zero-cost resolve	$p = 0$	$1$	Branch decided instantly ⇒ no bubbles.
Worst case	$b = m = 1, p = 3$	$4$	Every instruction a mispredicted branch: 1 useful + 3 wasted cycles each.

PICTURE. Three mini-lines: one with $b = 0$ (all straight, no pink), one with $m = 0$ (branches present but no crosses), one with everything maxed (crosses everywhere). All match the table.

Step 8 — From CPI to speedup

WHAT. Turn "cycles per instruction" into "how much faster than a slow single-cycle machine."

WHY. A single-cycle CPU does one instruction in one long tick equal to all $k$ stages back-to-back — so $k$ "stage-times" per instruction. The pipeline does one instruction per $CPI$ cycles, where each cycle is one stage-time. The ratio of times is the speedup.

PICTURE. Two time-bars for the same 4 instructions: a long single-cycle bar (each block = $k$ stage-times) above a short pipelined bar (staggered stages). The length ratio, annotated, is $k / (1 + s)$ .

The one-picture summary

One frame carries the whole derivation: the instruction river (Step 4 blue branches), the misprediction sliver (Step 5 pink), the crossed-out penalty slots (Step 3 give $p$ ), all funneling (Step 6) into $s_{ctrl} = bm p$ , which sits inside $CPI = 1 + s$ (Step 2) and finally divides into the speedup $k / (1 + s)$ (Step 8).

Recall Feynman retelling — say it back in plain words

A perfect assembly line spits out one instruction per tick — that's the "1". ::: Real code trips on branches. Only some instructions are branches (fraction $b$ ). Of those, only some are guessed wrong (fraction $m$ ). Each wrong guess throws away $p$ already-fetched instructions. Multiply the chances by the cost — $b \times m \times p$ — and that's the average wasted ticks per instruction. Add it to the ideal 1 to get $CPI = 1 + bm p$ . Finally, a slow single-cycle CPU needs $k$ stage-times per instruction while ours needs $CPI$ , so we go $k / (1 + s)$ times faster — the number sinks below $k$ by exactly the bubbles we couldn't avoid.

Recall Quick self-checks

What does each factor in $b \cdot m \cdot p$ represent? ::: $b$ = fraction that are branches, $m$ = fraction of branches mispredicted, $p$ = cycles wasted per mispredict. Why isn't the cost just $b \cdot p$ ? ::: Correctly predicted branches cost nothing; the $m$ factor removes them. With $b = 0.2, m = 0.1, p = 3$ , what is CPI? ::: $1.06$ . With $k = 5$ and that CPI, what is the speedup? ::: $\approx 4.72$ . What happens to CPI if $m = 0$ ? ::: It returns to the ideal $1$ (a perfect predictor erases the penalty).