Classic 5-stage pipeline (IF - ID - EX - MEM - WB): Worked examples

This deep dive drills the timing formulas of the Classic 5-stage pipeline until no case can surprise you. We build every symbol from zero, then walk one worked example per scenario cell.

Building the symbols from zero

Before any arithmetic, here is every letter we will use. A symbol you have not met yet is never allowed.

The scenario matrix

Every timing question this topic can throw is one of these cells. The worked examples below each carry a [Cell X] tag so you can see the coverage is total.

Cell	Scenario class	The twist it tests
A	Large $N$ , balanced stages	Speedup → $k$ (the ideal limit)
B	Small $N$	Fill cost dominates; speedup far below $k$
C	$N = 1$ (degenerate)	Pure latency; pipelining loses here
D	Unbalanced stage delays	One slow stage wastes the others' slots
E	Deeper pipeline, same work	Latch overhead $d$ eats the gain (diminishing returns)
F	Limiting case $N \to \infty$	Prove the cap is exactly $k$
G	Real-world word problem	Translate English → the three equations
H	Exam twist: superpipeline vs. cost	When more stages hurt

Worked examples

Cell A — large stream, balanced stages

Worked example Example 1 — the near-ideal speedup

[Cell A] A balanced 5-stage pipeline. Each stage has logic delay $t_{i} = 2$ ns and latch overhead $d$ is negligible here, so $T_{c l k} = 2$ ns. Run $N = 1000$ instructions, no stalls. Compare to a single-cycle machine whose one giant cycle does all five stages' logic plus its single latch: $5 \times 2 + d \approx 10$ ns (with $d \approx 0$ ).

Forecast: guess the speedup — is it closer to 4, 5, or 6?

Cycles $= k + (N - 1) = 5 + 999 = 1004$ . Why this step? $k = 5$ ticks fill the pipe (first result appears at cycle 5), then the remaining $999$ instructions each finish on the next tick — one per cycle.
Pipelined time $= 1004 \times 2 = 2008$ ns. Why? each cycle lasts exactly $T_{c l k} = 2$ ns.
Single-cycle time $= N \times (5 t_{i} + d) = 1000 \times (10 + 0) = 10000$ ns. Why? the non-pipelined machine does all five stages' logic in one sweep (10 ns) plus one latch $d$ ; here $d$ is taken $\approx 0$ , so $10$ ns per instruction. (This is the same " $\sum t_{i} + d$ " rule Example 3 uses — here $d$ is just negligibly small.)
Speedup $= 10000/2008 \approx 4.98 \times$ . Why? large $N$ makes the 4-cycle fill cost negligible, so we approach the ideal $k = 5$ .

Verify: the formula limit $\frac{N k}{k + N - 1} = \frac{5000}{1004} = 4.98$ ✓ — matches, and it sits just under 5 as expected.

Cell B — a short stream

Worked example Example 2 — when the pipe is barely filled

[Cell B] Same balanced 5-stage pipeline ( $T_{c l k} = 2$ ns, single-cycle $\approx 10$ ns per instruction as in Example 1), but only $N = 3$ instructions.

Forecast: with only 3 instructions, do we still get near $5 \times$ ?

Cycles $= k + (N - 1) = 5 + (3 - 1) = 7$ . Why? the pipeline spends most of its life half-empty — only cycles 5, 6, 7 produce a result.
Pipelined time $= 7 \times 2 = 14$ ns. Why? each of the 7 cycles lasts $T_{c l k} = 2$ ns.
Single-cycle time $= N \times 10 = 3 \times 10 = 30$ ns. Why? three instructions, each one $\approx 10$ ns sweep (same single-cycle cost as Example 1).
Speedup $= 30/14 = \frac{15}{7} \approx 2.14 \times$ . Why so low? the 4-cycle fill overhead is a huge fraction of just 7 cycles. Fill cost has NOT been amortised.

Verify: cross-check with the formula $\frac{N k}{k + N - 1} = \frac{15}{7} = 2.142 \dots$ ✓; between $1$ and $k = 5$ ✓.

Cell C — the degenerate single instruction

Worked example Example 3 — one instruction only (

$N = 1$ ) [Cell C] Run a single instruction. Balanced stages, $t_{i} = 2$ ns each, latch $d = 0.2$ ns, so $T_{c l k} = 2.2$ ns. Compare pipelined latency to a single-cycle machine.

Forecast: does the pipeline win, tie, or lose for one instruction?

Pipelined cycles $= k + (N - 1) = 5 + 0 = 5$ . Why? the lone instruction must still crawl through all 5 stages; there is no later instruction to overlap with.
Pipelined latency $= 5 \times 2.2 = 11.0$ ns. Why? five clock ticks, each padded by latch overhead $d$ — the pipe latches five times.
Single-cycle latency $= 5 \times t_{i} + d = 10 + 0.2 = 10.2$ ns. Why? one combinational sweep of all the logic, latched once — the same $\sum t_{i} + d$ rule as Examples 1–2, now with $d$ visible.
Result: pipelining is slower here: $11.0 > 10.2$ ns. Why? pipelining pays latch overhead $d$ five times ( $5 d = 1.0$ ns) instead of once — see Single-cycle vs Multicycle Datapath.

Verify: $11.0 - 10.2 = 0.8$ ns extra $= 4 d = 4 \times 0.2$ ✓ (four extra latches beyond the single one). This is the concrete proof of the parent note's "latency slightly worsens" claim.

Cell D — unbalanced stages

Worked example Example 4 — one slow stage poisons the clock

[Cell D] Stage delays: IF = 200, ID = 100, EX = 150, MEM = 200, WB = 100 (ps). Latch $d = 20$ ps. Find $T_{c l k}$ , and the realistic speedup for large $N$ .

Forecast: total logic is $750$ ps split into 5 — will speedup be near 5?

$max_{i} (t_{i}) = 200$ ps (IF and MEM tie for slowest). Why max? all stages share one clock; the clock must be long enough for the slowest logic to settle, or that stage's result is wrong. Look at the tallest bars in the figure.
$T_{c l k} = 200 + 20 = 220$ ps. Why $+ d$ ? every stage must also latch its result into its pipeline register.
Single-cycle machine needs $750 + 20 = 770$ ps per instruction (all logic in one sweep, latched once). Why $750$ ? $200 + 100 + 150 + 200 + 100$ = the full combinational chain, plus its single $d = 20$ .
Large- $N$ speedup $= 770/220 \approx 3.5 \times$ , not $5 \times$ . Why the shortfall? WB uses only 100 of its 220 ps slot — the grey wasted area in the figure. Imbalance wastes clock time in the fast stages.

Verify: $770/220 = 3.5$ exactly ✓. Wasted time in WB $= 220 - 20 - 100 = 100$ ps ✓ (matches the grey gap).

Cell E — deeper pipe, same total work

Worked example Example 5 — diminishing returns from more stages

[Cell E] Context switch: we now work in picoseconds with a total combinational workload of $\sum_{i} t_{i} = 750$ ps (the same 750 ps chain as Example 4, not the 2 ns/stage balanced case of Examples 1–3). We compare two ways to slice that same 750 ps: into $k = 5$ balanced stages, and into $k = 10$ balanced stages. Latch $d = 20$ ps.

Forecast: doubling stages to 10 — do we double the throughput?

5-stage (balanced) $T_{c l k}$ $= 750/5 + 20 = 150 + 20 = 170$ ps. Why? splitting 750 ps into 5 equal stages gives $150$ ps of logic each, plus one latch $d$ .
10-stage $T_{c l k}$ $= 750/10 + 20 = 75 + 20 = 95$ ps. Why? each stage now holds only $75$ ps of logic, but still pays the full $20$ ps latch.
Throughput ratio $= 170/95 \approx 1.79 \times$ , not $2 \times$ . Why not double? the latch $d = 20$ ps is now a huge $21%$ of each tiny 95 ps period. Overhead does not shrink when stages do — see Clocking & Latch Overhead.

Verify: $170/95 = 1.789 \dots$ ✓ — strictly less than the naive $2 \times$ you'd hope for.

Cell F — the limit, proven

Worked example Example 6 — why speedup caps at exactly

$k$ [Cell F] Prove $N \to \infty lim \frac{N k}{k + N - 1} = k$ .

Forecast: as $N$ grows huge, the speedup climbs toward some ceiling — what is it, exactly?

Divide top and bottom by $N$ : $\frac{N k}{k + N - 1} = \frac{k}{\frac{k - 1}{N} + 1}$ . Why divide by $N$ ? it isolates the parts that vanish as $N$ grows. The constant $k - 1$ (the fill cost) becomes a fraction $\frac{k - 1}{N}$ .
As $N \to \infty$ , $\frac{k - 1}{N} \to 0$ . Why? a fixed number divided by an ever-growing one shrinks to nothing — the fill cost is amortised over infinitely many instructions.
So the expression $\to \frac{k}{0 + 1} = k$ . Why $k$ ? with the fill negligible, you have exactly $k$ instructions overlapped in flight — a $k$ -fold throughput gain. The curve in the figure hugs the dashed line $y = k$ .

Verify: at $N = 100$ , $k = 5$ : $\frac{500}{104} = 4.808$ ; at $N = 10000$ : $\frac{50000}{10004} = 4.9975$ — climbing toward 5 ✓.

Cell G — real-world word problem

Worked example Example 7 — the video encoder

[Cell G] A CPU pipeline runs at $2 GHz$ (so $T_{c l k} = 0.5$ ns) with $k = 5$ stages and no stalls. A video codec loop executes $8, 000, 000$ instructions per frame. How long does one frame take, and how far is throughput from ideal?

Forecast: with 8 million instructions, will speedup be essentially 5?

$T_{c l k} = 1/ (2 \times 1 0^{9} Hz) = 0.5$ ns. Why? period is the reciprocal of frequency; $2$ GHz means two billion ticks per second.
Cycles $= k + (N - 1) = 5 + 7, 999, 999 = 8, 000, 004$ . Why? the 4-extra fill cycles are utterly dwarfed by 8 million.
Frame time $= 8, 000, 004 \times 0.5 ns = 4, 000, 002 ns \approx 4.0$ ms. Why ns→ms? $4, 000, 002$ ns $= 4.000002 \times 1 0^{6}$ ns $= 4.0$ ms ( $1$ ms $= 1 0^{6}$ ns).
Speedup $= \frac{N k}{k + N - 1} = \frac{40 , 000 , 000}{8 , 000 , 004} \approx 4.9999975 \times$ . Why so near 5? enormous $N$ → fill cost invisible (Cell A taken to the extreme).

Verify: frame time $8000004 \times 0.5 = 4000002$ ns ✓; speedup $\approx 4.99999$ ✓ — throughput is $99.99995%$ of ideal.

Cell H — exam twist: when more stages hurt

Worked example Example 8 — the superpipeline trap

[Cell H] Same $750$ ps of logic. A vendor proposes $k = 30$ stages of $25$ ps each, latch $d = 20$ ps. Compare its clock period to the 5-stage balanced design ( $T_{c l k} = 170$ ps from Example 5) and comment.

Forecast: 30 stages — surely a much faster clock?

30-stage $T_{c l k}$ $= 25 + 20 = 45$ ps. Why? only $25$ ps of logic now sits per stage, but the $20$ ps latch is unavoidable.
Latch fraction $= 20/45 \approx 44.4%$ of every cycle is pure overhead. Why alarming? nearly half the clock does no useful computation — it just re-latches. Compare Example 5's $21%$ .
Throughput vs 5-stage $= 170/45 \approx 3.78 \times$ faster clock. Why not a clean win? this ignores that deeper pipes suffer far worse hazard penalties (longer branch mispredict flush) — see Pipeline Hazards (structural, data, control) and Branch Prediction — so real speedup shrinks below this raw clock ratio.
Judgement: raw throughput rises, but efficiency-per-transistor collapses and real speedup with stalls can fall. The parent note's "speedup saturates and can even fall" is exactly this cell.

Verify: $170/45 = 3.777 \dots$ ✓; overhead fraction $20/45 = 0.4444 \dots$ ✓.

Recall Coverage self-check

Ex 1 → A · Ex 2 → B · Ex 3 → C · Ex 4 → D · Ex 5 → E · Ex 6 → F · Ex 7 → G · Ex 8 → H. Every matrix cell has a worked example.

Active recall

For a k-stage pipeline running N instructions with no stalls, how many cycles?

k + (N - 1)

— k to fill, then one completes per cycle.

Why does a single instruction (N=1) run slower pipelined?

It still traverses all k stages, and pays latch overhead d once per stage (k·d) instead of once total.

In Example 4, why is speedup 3.5× and not 5×?

Stages are unbalanced; the clock is set by the slowest (200 ps + 20), wasting slots in faster stages like WB.

Why doesn't doubling the number of stages double throughput?

Latch overhead d is fixed per stage; as stages shrink, d becomes a larger fraction of

T_{c l k}

What is the large-N speedup limit and why?

k× — the fill cost (k−1) becomes negligible relative to N, leaving k overlapped instructions.

Which formula must you use for small N instead of the k-limit?

Speedup = \frac{N k}{k + N - 1}

How many times does a single-cycle machine latch per instruction, versus a k-stage pipeline?

Single-cycle latches once (one d); the pipeline latches k times (k·d).