Pipeline throughput and CPI: Visual walkthrough — Hardware deep dive

This page takes the parent result — Pipeline throughput and CPI — and rebuilds it from absolutely nothing. No formula appears before you have seen it as a picture. By the end you will be able to draw the whole story on a napkin.

We are answering one question the whole way down:

Step 1 — What is a "stage"? Draw the assembly line

WHAT. A processor doing one instruction has to do several small jobs in order: fetch the instruction, decode it, do the arithmetic, touch memory, write the answer back. We chop that work into boxes called stages. The classic count is $k = 5$ stages named IF, ID, EX, MEM, WB.

WHY boxes? Because if each box has its own hardware, then while box 2 works on instruction #1, box 1 can already start instruction #2. Nobody sits idle. That overlap is the entire point — and we cannot reason about cycles until we can see the boxes.

PICTURE. Five labelled boxes in a row, an instruction entering the left and the finished result leaving the right.

Step 2 — Why the clock ticks at the speed of the SLOWEST box

WHAT. Every box hands its result to the next box on the same shared heartbeat — the clock. One tick = one clock cycle. We now find how long one tick must last.

WHY the maximum, not the average? All boxes step forward together, on the same edge. If the clock ticks before the slowest box has finished, that box passes on garbage. So the tick must wait for the slowest box. Picture a marching band: everyone steps on the same beat, so the beat must be slow enough for the slowest marcher.

PICTURE. The five stage delays drawn as bars of different heights; a horizontal dashed line sits on top of the tallest bar — that height is the clock period.

Why does a tool called $max$ enter here and not, say, an average? Because we need the worst box to be safe, and only the worst one matters. $max$ is exactly the operation "give me the largest of these" — the right question is "who is slowest?", and $max$ answers it.

Step 3 — Watch the pipeline FILL: the first instructions are slow

WHAT. Send in instruction $I_{1}$ . On tick 1 it is in box IF. On tick 2 it moves to ID and $I_{2}$ enters IF. And so on. We watch the diagonal wave sweep across.

WHY watch this? Because at the very start the pipeline is half-empty — not every box is busy. Those early ticks are the "fill-up" cost, and we must count them honestly before claiming "one instruction per tick".

PICTURE. The standard pipeline space-time chart: rows = instructions, columns = clock cycles, each cell coloured by which stage it is in. The staircase shows the fill.

Read the chart: $I_{1}$ finishes (leaves WB) at the end of cycle 5 — it needed all $k = 5$ ticks. But $I_{2}$ finishes one tick later, at cycle 6. $I_{3}$ at cycle 7. After the staircase is built, one instruction pops out every single tick.

Step 4 — Count the total ticks for $n$ instructions

WHAT. Add up the ticks needed to run $n$ instructions through a $k$ -stage pipeline.

WHY. Total cycles ÷ instructions is CPI, by definition. So if we can count total cycles, we are done.

PICTURE. The same chart split into two coloured zones: the teal fill triangle (first instruction climbing through $k$ stages) and the orange steady zone (one completion per tick thereafter).

Count from the picture:

$Total Cycles = ticks for I_{1} to cross all boxes k + one extra tick for each of the other n - 1 (n - 1)$

$k$ — the fill cost, paid once, no matter how many instructions.
$(n - 1)$ — after the pipe is full, every remaining instruction adds exactly one tick.

Step 5 — Divide, then let $n$ grow: CPI marches to 1

WHAT. Turn "total cycles" into "cycles per instruction" by dividing by $n$ .

WHY divide? Because CPI is defined as total cycles over instructions. This step literally is the definition applied to Step 4's count.

$CPI_{ideal} = \frac{Total Cycles}{n} = \frac{k + ( n - 1 )}{n} = 1 + \frac{k - 1}{n}$

$1$ — the steady-state cost: one tick per instruction once full.
$\frac{k - 1}{n}$ — the fill cost spread thin over all $n$ instructions.

WHY does a limit enter here? We ask "what happens to the fill penalty for a long program?" The penalty $\frac{k - 1}{n}$ shrinks as $n$ grows — that shrinking-toward-a-value is exactly what a limit describes. The right tool for "where does this settle for huge $n$ ?" is the limit $n \to \infty$ .

$lim_{n \to \infty} (1 + \frac{k - 1}{n}) = 1 ⟹ CPI_{ideal} = 1$

PICTURE. A curve of CPI versus $n$ , starting high (small programs feel the fill), sliding down and hugging the dashed line $CPI = 1$ .

Step 6 — The degenerate case: what if $n = 1$ ?

WHAT. Run a single instruction, $n = 1$ .

WHY show it? A contract must cover every input, including the smallest. It also kills a famous misconception.

$CPI = \frac{k + ( 1 - 1 )}{1} = \frac{k}{1} = k$

One instruction costs $k$ ticks — the same $k$ boxes it must cross. Pipelining gave it zero help. This is the visual proof that pipelining does not make one instruction faster (its latency is unchanged); it only makes completions more frequent when many are in flight.

PICTURE. Left: a lone instruction crawling through 5 boxes over 5 ticks (latency $= k$ ). Right: a dense stream where one pops out every tick (throughput $= 1/ T_{p i p e}$ ). Same boxes, totally different feeling.

See also 5.1.05-CPU-performancemetrics for how latency and throughput sit inside the full performance equation.

Step 7 — Reality bites: hazards add ticks on top of the ideal

WHAT. Real streams hit hazards — moments where an instruction must wait. The pipeline inserts a bubble (a do-nothing NOP), which is a wasted tick. Each wasted tick adds to CPI.

WHY add, not multiply? Because a stall is literally extra cycles glued on to the ideal count. Extra cycles per instruction simply add to the baseline of 1.

$CPI_{actual} = ideal, Step 5 1 + wasted ticks, averaged Stalls per Instruction$

The stall term itself is a sum of independent troublemakers:

$Stalls/Instr = data hazards (f_{D} \cdot s_{D}) + branch mispredicts (f_{B} \cdot m_{B} \cdot p_{B})$

$f_{D}$ — fraction of instructions that hit a data hazard (5.2.03-Data-hazards).
$s_{D}$ — average bubbles each such hazard costs (cut by forwarding).
$f_{B}$ — fraction that are branches; $m_{B}$ — fraction of those that mispredict; $p_{B}$ — penalty ticks per mispredict (5.2.05-Control-hazards).

PICTURE. A bar starting at height 1 (ideal), with a teal segment for data stalls and an orange segment for branch stalls stacked on top — the total height is $CPI_{actual}$ .

The one-picture summary

Everything above, compressed: boxes → slowest box sets the tick → fill triangle → count $k + (n - 1)$ → divide → limit hits 1 → hazards stack extra ticks on top.

Recall Feynman retelling — say it back in plain words

Imagine a car factory with five stations. A single car still takes five station-times to be born — pipelining never rushed one car. But once the line is full, a finished car rolls out every single beat. To find the real cost per car, I count all the beats and divide by the number of cars: I paid five beats to fill the line once, plus one beat for every car after the first, so total beats $= k + (n - 1)$ . Divide by $n$ and the "fill the line once" cost gets spread thinner the more cars I make — for a huge batch it vanishes and each car costs one beat: CPI = 1. But the factory jams sometimes: a station waits on the previous one's result (data hazard) or the line guessed the wrong turn (branch mispredict), and each jam is a wasted beat glued onto that clean 1. So the honest number is $1$ plus all the average wasted beats — that's why real CPI sits a little above 1, and only a fancier multi-line factory (superscalar) can push it below.

Recall Quick self-check

Total cycles for $n$ instructions in a $k$ -stage pipe ::: $k + (n - 1)$ Why the clock period uses $max$ of the stage delays ::: all stages tick together, so the slowest one gates everyone CPI for a single instruction ( $n = 1$ ) ::: $k$ — pipelining gives one lonely instruction no help What each stall adds to CPI, and why we add it ::: wasted (bubble) cycles per instruction; they are extra ticks glued onto the ideal 1 The CPI when $f_{B} = 0.25, m_{B} = 0.10, p_{B} = 3, f_{D} = 0.15, s_{D} = 2$ ::: $1.375$

Parent: Pipeline throughput and CPI · Related: 5.2.03-Data-hazards · 5.2.05-Control-hazards · 5.2.07-Forwarding-and-bypassing · 5.3.02-Superscalar-architecture · 5.1.05-CPU-performancemetrics