Structural hazards: Visual walkthrough — Hardware deep dive

Prerequisites we will lean on but re-explain as needed: Pipelining Fundamentals, Pipeline Stalls.

Step 1 — Draw the grid: what "a pipeline" actually is

WHAT. Before any formula, we need a picture of time. We chop time into equal slices called clock cycles — think of them as identical ticks of a metronome. We line them up left-to-right. We stack instructions top-to-bottom. Each instruction moves through five stages, one stage per cycle:

IF — Instruction Fetch: go to memory, grab the instruction.
ID — Instruction Decode: figure out what it says, read registers.
EX — Execute: do the arithmetic in the ALU.
MEM — Memory access: read or write data in memory (only loads/stores really use this).
WB — Write Back: store the result into a register.

WHY these five and not some other count. Five is the classic textbook split because each stage uses a different piece of hardware, so ideally all five can be busy at once — like five workers on an assembly line. That "all busy at once" is the whole point of pipelining, and it is exactly what a hazard will break.

PICTURE. Look at the diagonal staircase: each instruction starts one cycle after the one above it. In any single vertical column (one cycle) you see five different instructions, each in a different stage.

Step 2 — The perfect case: why ideal CPI is exactly 1

WHAT. Watch the staircase for a long program. Instruction 1 finishes at cycle 5. Instruction 2 finishes at cycle 6. Instruction 3 at cycle 7. After the first four cycles of "fill-up," one instruction pops out the right edge every single cycle.

WHY this gives CPI $= 1$ . If $N$ instructions finish and (for large $N$ ) each takes one net cycle once the pipe is full, then total cycles $\approx N$ , so

$CPI_{ideal} = \frac{total cycles}{instructions} = \frac{N}{N} = 1.0$

$CPI_{ideal}$ — the best we could ever do.
$\frac{total cycles}{instructions}$ — the definition of average cost: how many ticks per finished job.
$= 1.0$ — one finished instruction per tick. This is the number every hazard is trying to spoil.

PICTURE. The green arrows mark completions leaving the right edge — one per column, perfectly regular.

Recall

In a full, hazard-free pipeline, how many instructions finish per clock cycle? ::: Exactly one — that is why ideal CPI $= 1.0$ .

Step 3 — The collision: two stages reaching for ONE memory

WHAT. Now suppose the machine has a single unified memory — one door into memory, used both for fetching instructions (the IF stage) and for reading/writing data (the MEM stage). Overlay the staircase again and stare at cycle 4:

Instruction 1 is in MEM — it wants to touch memory for data.
Instruction 4 is in IF — it wants to touch memory for its instruction.

Two hands reach for one door in the same cycle.

WHY this is a structural hazard and not something else. Nothing is wrong with the instructions themselves — they don't depend on each other's data (that would be a data hazard) and no branch is deciding the future (that would be a control hazard). The problem is purely not enough hardware: one memory port, two customers, same cycle. That is the definition of a structural hazard.

PICTURE. The red burst sits at the crossing of I1's MEM cell and I4's IF cell — both point at the single grey memory box.

Step 4 — The fix: insert a bubble (a stall)

WHAT. Only one of the two can use memory. We let the older instruction (I1, in MEM) win, and we freeze the younger one (I4) for one cycle. That frozen empty slot is a bubble.

WHY a bubble works. By delaying I4's fetch by one cycle, I1 finishes its memory access first; the door is then free and I4 fetches cleanly. Nothing is skipped, nothing is corrupted — we simply waited. The cost is one cycle in which no new instruction entered the pipe.

PICTURE. The plum-coloured bubble cell shows the wasted cycle; every instruction behind I4 slides one column to the right (the whole tail shifts).

Step 5 — Counting: turn "how often" into a number $p$

WHAT. To get a formula we must ask: how often does this collision happen? The MEM stage is only actually used by loads and stores (instructions that touch data memory). Suppose a fraction $f_{mem}$ of all instructions are loads/stores. Each such instruction, when it reaches MEM, collides with whatever is being fetched — one collision, one bubble.

WHY a fraction and not a count. We are averaging over a whole program, so we work with probabilities. Let

$p = f_{mem}$

$p$ — the probability (chance, between 0 and 1) that a given instruction triggers a stall.
$f_{mem}$ — the fraction of instructions that are memory operations, e.g. $0.30$ means 3 in 10.

PICTURE. A bar of 10 instruction-tokens: the coloured 3 are memory ops (each causes a bubble), the pale 7 sail through untouched.

Step 6 — Counting: how many cycles each collision costs, $s$

WHAT. We saw in Step 4 that fixing one collision cost exactly one wasted cycle. Call the cost per collision the stall penalty $s$ . For the single-memory hazard, $s = 1$ .

WHY name it separately. Other structural hazards might cost more than one cycle (a slow shared multiplier might block two or three cycles). By keeping $s$ as its own symbol, the same formula covers every structural hazard — we just plug in the right penalty.

PICTURE. A magnifying glass on one collision showing exactly one plum bubble cell = $s = 1$ ; a side sketch shows what $s = 2$ would look like (two bubbles) for a heavier resource.

Step 7 — Assemble the result: effective CPI

WHAT. Every instruction costs the ideal 1 cycle plus its average share of bubbles. Add them:

$CPI_{actual} = = 1.0 CPI_{ideal} + wasted cycles p \times s = 1 + p s$

$CPI_{ideal} = 1.0$ — the perfect one-per-cycle base from Step 2.
$p s$ — the average bubble tax from Step 6.
their sum — the real average cost per instruction once hazards are counted.

Plug in the memory example, $p = f_{mem} = 0.30$ , $s = 1$ :

$CPI_{actual} = 1 + 0.30 \times 1 = 1.30$

WHY it's a plain sum. Bubbles are extra cycles glued onto the ideal schedule — they neither remove nor overlap useful work, so we simply add them on. No hidden multiplication, no fancy correction.

PICTURE. A stacked bar: a tall $1.0$ block of useful work topped by a short $0.30$ plum block of stall — total height $1.30$ .

Step 8 — Turn CPI into lost speed, and cover the edge cases

WHAT. Speed is inversely proportional to CPI (higher cost per instruction = slower). Comparing perfect against actual:

$Relative speed = \frac{CPI _{ideal}}{CPI _{actual}} = \frac{1.0}{1.30} \approx 0.77$

So the machine runs at $\approx 77%$ of its ideal rate — a $\approx 23%$ slowdown.

numerator $CPI_{ideal}$ — cycles the perfect machine needs.
denominator $CPI_{actual}$ — cycles the real machine needs.
ratio $< 1$ — the real machine is slower; $1 - 0.77 = 0.23$ is the fraction of speed lost.

Now the edge cases — the reader must never meet a scenario we skipped:

$p = 0$ (no memory ops, or separate I/D caches): $CPI = 1 + 0 = 1.0$ . No collision ever — this is the Harvard-style split-cache cure. The hazard vanishes, not just shrinks.
$p = 1$ (every instruction hits the resource): $CPI = 1 + s$ . Worst case; with $s = 1$ the pipe is half-wasted.
$s = 0$ (hardware fixed by adding a port/adder): $CPI = 1 + p \times 0 = 1.0$ regardless of $p$ . Throwing hardware at it drives the penalty to zero — Solution 1 from the parent note.
Non-memory hazards (bigger $s$ ): a shared 3-cycle multiplier used by 20% of instructions gives $CPI = 1 + 0.20 \times 3 = 1.60$ — same formula, new numbers. This is why keeping $s$ symbolic mattered.

PICTURE. A curve of $CPI = 1 + p s$ versus $p$ for $s = 1, 2, 3$ , with the three edge points ( $p = 0$ , $p = 1$ , $s = 0$ ) circled.

The one-picture summary

Everything above, compressed: the staircase collides at the single memory (Step 3), we insert a bubble (Step 4), we count its chance $p$ and cost $s$ (Steps 5–6), and add the tax onto the ideal 1 to get $CPI = 1 + p s$ (Step 7), which converts to lost speed (Step 8).

Recall Feynman retelling — say it back in plain words

Picture five workers on an assembly line, each doing one job, so one product finishes every tick — that's "cost 1." But two of the workers share a single tool (the memory door). Whenever an instruction needs that shared tool at the wrong moment, one worker must freeze for a tick — a "bubble" — and no product comes out that tick. If 3 out of every 10 instructions cause such a freeze (that's $p = 0.3$ ), and each freeze wastes exactly 1 tick ( $s = 1$ ), then on average every instruction carries an extra $0.3$ ticks of dead time. Add that to the base 1 and you get $1.3$ ticks per instruction — the machine runs at $1/1.3 \approx 77%$ of full speed. Give the workers a second tool (split caches, an extra port) and the freeze cost $s$ drops to 0, so the tax disappears and we're back to a perfect 1. That single line, $CPI = 1 + p s$ , is the whole story — see also how it stacks with the tax from Data Hazards and Control Hazards in a real machine, and why Superscalar Processors chasing high Instruction-Level Parallelism must add lots of ports to keep $s$ near zero.