Visual walkthrough — Pipelining — 5-stage pipeline, each stage

---

Step 1 — What "doing an instruction" even means

WHAT. An instruction is not one lump of work. It is a sequence of small jobs done in order. In the classic RISC design there are 5 such jobs, called stages:

• IF — fetch the instruction from memory
• ID — decode it and read the registers it needs
• EX — do the arithmetic in the ALU
• MEM — touch data memory (only loads/stores)
• WB — write the answer back into a register

WHY start here. Every later idea depends on one fact: these 5 jobs use different hardware (fetch unit, decoder, ALU, memory, register file). Different hardware means they could run at the same time on different instructions — that is the seed of the whole trick.

PICTURE. One instruction shown as 5 coloured boxes in a row. Read left→right in time. Each box takes the same slice of time $t$; the whole instruction takes 5 of them.

---

Step 2 — The slow way: one instruction fully, THEN the next

WHAT. Run instruction 1 through all 5 boxes. Only when it completely finishes do we start instruction 2. This is the non-pipelined (sequential) machine.

WHY. This is our baseline — the thing we want to beat. To know if pipelining helps, we need the "before" time.

PICTURE. Look at the figure: instruction 2's row of boxes starts only after instruction 1's last box ends. Notice the huge empty space — while instruction 1 is in EX, the fetch unit sits idle. That wasted whiteness is exactly what pipelining will fill.

One instruction alone: $T_{\text{instr}}=\underset{\text{number of stages}}{\underbrace{k}}\cdot \underset{\text{time per stage}}{\underbrace{t}}$

Every symbol: $k$ counts the boxes, $t$ is the width of one box, and their product is the total row length.

For $n$ instructions done back-to-back, we just stack $n$ full rows: $T_{\text{seq}}=\underset{\text{how many instructions}}{\underbrace{n}}\cdot \underset{\text{time for one}}{\underbrace{k\cdot t}}$

---

Step 3 — The trick: slide each instruction one box to the right

WHAT. Don't wait. The instant instruction 1 leaves the IF box, push instruction 2 into IF. Each new instruction starts exactly one stage-time after the previous one.

WHY this works. Because the 5 stages use different hardware (Step 1). When instruction 1 is in EX, the fetch unit is free — so instruction 2 can be in IF at the same time. Nobody fights over hardware; everybody's busy.

PICTURE. The famous staircase / diagonal diagram. Each row is one instruction; each row is shifted one box right from the row above. Read any vertical slice (one clock cycle) and you see up to 5 different instructions, each in a different stage — all working at once.

---

Step 4 — Counting cycles: fill the pipe, then one per cycle

WHAT. Count how many stage-times the whole staircase takes. Split it into two parts.

WHY split it. Because the staircase has two personalities:

1. A warm-up where the pipe is filling and no instruction has finished yet.
2. A steady state where a finished instruction pops out every single cycle.

PICTURE. The figure shades the warm-up region (first instruction climbing all 5 stages) in one colour, and the steady-state finishers in another. The very first instruction needs the full $k$ cycles to reach WB. After it finishes, each remaining instruction is only one cycle behind the one before it.

$T_{\text{pipe}}=\underset{\text{fill: 1st instr reaches WB}}{\underbrace{k\cdot t}}+\underset{\text{the other }n-1\text{ finish, 1 per cycle}}{\underbrace{(n-1)\cdot t}}$

Term by term:

• $k\cdot t$ — the first instruction climbs all $k$ stages: the warm-up cost you pay once.
• $(n-1)$ — every other instruction (all but the first) adds just one cycle, because it finishes one cycle after its neighbour.
• $t$ — each of those extra cycles is one stage-time wide.

Combine: $T_{\text{pipe}}=(k+n-1)t$

---

Step 5 — The speedup ratio

WHAT. Divide "before" by "after". Speedup $S$ = how many times faster the pipelined machine is.

WHY a ratio. A raw time in seconds means nothing without a comparison. Dividing cancels the $t$ (they share the same stage time) and leaves a pure number — the honest "×faster".

PICTURE. Two bars: the tall sequential bar $T_{\text{seq}}$ and the short pipelined bar $T_{\text{pipe}}$. Their length ratio is $S$.

$S=\frac{T_{\text{seq}}}{T_{\text{pipe}}}=\frac{nkt}{(k+n-1)t}=\frac{nk}{k+n-1}$

The $t$ on top and bottom cancel — speedup does not depend on how long a stage takes, only on the counts $n$ and $k$.

---

Step 6 — The limit: WHY the cap is exactly $k$

WHAT. Ask: what happens to $S$ when $n$ becomes enormous (a long program)?

WHY the limit tool. We want the best possible speedup. "Best" is the direction $n$ grows without bound, so we take a limit — the mathematical way to ask "what value does this creep toward?"

PICTURE. A curve of $S$ against $n$ for $k=5$: it rises fast, then flattens, hugging a horizontal dashed line at $S=5$ but never crossing it. That ceiling is the number of stages.

Divide top and bottom by $n$ to see the limit clearly: $S=\frac{nk}{k+n-1}=\frac{k}{\frac{k-1}{n}+1}$

As $n\to \infty$, the term $\frac{k-1}{n}\to 0$ (a fixed number over a growing one), so: $S⟶\frac{k}{0+1}=k$

Meaning: for a long stream you finish 1 instruction per cycle ($1/t$) instead of 1 per $k$ cycles ($1/(kt)$) — exactly a $k\times$ win. The $k-1$ fill cycles were paid once and vanish against millions of instructions.

---

Step 7 — The degenerate cases (never hit an unshown scenario)

WHAT. Check the extremes so no reader is surprised.

PICTURE. Three mini-panels: tiny $n$, $n=1$, and unbalanced stages.

Case $n=1$ (a single instruction). $S=\frac{1\cdot k}{k+1-1}=\frac{k}{k}=1$ No speedup at all — with one instruction there is nothing to overlap. The pipeline's whole idea is overlap, and one lonely instruction has no neighbour to overlap with.

Case small $n=2$, $k=5$. $S=\frac{2\cdot 5}{5+2-1}=\frac{10}{6}\approx 1.67$ Far below 5. The 4 fill cycles dominate when only 2 instructions run. Pipelines win on long streams, not short bursts.

Case unbalanced stages. If one stage is slower than the others, the clock must wait for the slowest one, so the true cycle time is: $t_{\text{clk}}=\max (\text{stage delays})+t_{\text{reg}}$ Here $t_{\text{reg}}$ = the extra time each pipeline register adds. One fat stage sets the pace for everybody — this is why real speedup is below $k$, and why designers work hard to balance the stages. (Hazards and stalls, covered in Pipeline Hazards (Data, Control, Structural), cut it further.)

---

The one-picture summary

This single figure stacks the whole story: the tall sequential bar, the compact pipelined staircase beneath it labelled with its fill and steady-state regions, and the speedup ratio pointing at the $S\to k$ ceiling.

Recall Feynman retelling — explain the whole walkthrough to a friend

An instruction is 5 little jobs done in a row (fetch, decode, do-the-math, touch-memory, write-back), each using different hardware. The slow machine finishes one instruction completely before starting the next, so most hardware sits idle — wasted. The pipeline slides each new instruction in one step behind the last, so all 5 pieces of hardware stay busy on 5 different instructions at once. Counting time: the first instruction still needs all 5 steps to fill the pipe (that's $k$ cycles), but after that a finished instruction drops out every cycle — so the other $n-1$ instructions add only one cycle each. Total $=(k+n-1)$ cycles. Divide the old time $nk$ by the new time $(k+n-1)$ and the speedup is $\frac{nk}{k+n-1}$. For a huge program the $k-1$ startup cycles are a rounding error, and you approach a clean $k\times$ — but never more, and much less if one stage is fat or instructions get in each other's way.

---

Connections

• Pipeline Hazards (Data, Control, Structural)
• Forwarding and Bypassing
• Branch Prediction
• Single-cycle vs Multi-cycle Datapath
• Clock Frequency and CPI
• Amdahl's Law
• Superscalar and Out-of-Order Execution