Exercises — Pipelining — 5-stage pipeline, each stage

Mnemonic: "I Do Everything My Way."

Count from I3's start. I3 enters IF in cycle 3 (each new instruction starts one cycle later). So:

• Cycle 3 → IF
• Cycle 4 → ID

The rule: instruction $i$ is in stage $s$ during cycle $c=i+s-1$ (with $i$, $s$ starting at 1). For $i=3$, $c=4$: $s=c-i+1=4-3+1=2=$ ID. ✔

A pipeline register (latch) — the IF/ID, ID/EX, EX/MEM, MEM/WB registers. Without it, the output of stage $i$ for the current instruction would be overwritten on the next cycle by the next instruction entering stage $i$. The register holds each instruction's own intermediate state as it travels down the pipe.

WHY these formulas: non-pipelined runs each instruction fully (all $k$ stages) before the next, so times just add. Pipelined overlaps them, so we pay $k$ cycles to fill, then 1 cycle each for the remaining $n-1$.

(a) $T_{\text{seq}}=nkt=8\cdot 5\cdot 2=80\text{ns}$ (b) $T_{\text{pipe}}=(k+n-1)t=(5+8-1)\cdot 2=12\cdot 2=24\text{ns}$ (c) $S=\frac{T_{\text{seq}}}{T_{\text{pipe}}}=\frac{80}{24}\approx 3.33$

Set $\frac{nk}{k+n-1}\ge 4$ with $k=5$: $\frac{5n}{n+4}\ge 4\Rightarrow 5n\ge 4n+16\Rightarrow n\ge 16.$ So you need at least $\mathbf{n}=16$ instructions. Check: $S=\frac{5\cdot 16}{16+4}=\frac{80}{20}=4.0$ exactly. ✔

WHY the max: every stage shares one common clock; the clock cannot tick faster than the slowest stage can finish, or that stage's work would be cut off. $t_{\text{clk}}=\max (2,3,2,4,1)+t_{\text{reg}}=4+0.5=4.5\text{ns}$ Once full, one instruction completes per cycle, so $\text{Throughput}=\frac{1}{t_{\text{clk}}}=\frac{1}{4.5\times 10^{-9}\text{s}}\approx 2.22\times 10^8\text{instr/s}.$

Total work per instruction is the same ($10$ ns) in both — B just slices it thinner. $T_A=(5+100-1)\cdot 2=104\cdot 2=208\text{ns}$ $T_B=(10+100-1)\cdot 1=109\cdot 1=109\text{ns}$ B wins: $208-109=99\text{ns}$ faster, a ratio of $208/109\approx 1.91\times$. WHY: deeper pipe → shorter cycle → more overlap. The extra fill cycles ($10$ vs $5$) are tiny against $n=100$. (In real hardware register overhead and hazards eventually cap this — see Superscalar and Out-of-Order Execution.)

Set $T_A=T_B$: $(5+n-1)\cdot 2=(10+n-1)\cdot 1$ $2(n+4)=n+9\Rightarrow 2n+8=n+9\Rightarrow n=1.$ They tie only at $\mathbf{n}=1$ (a single instruction). Verify by plugging $n=1$ back in: $T_A=(5+1-1)\cdot 2=10\text{ns}$ and $T_B=(10+1-1)\cdot 1=10\text{ns}$. Both $10$ ns. ✔ Interpretation: for a single instruction both pipelines just do the full $10$ ns of work with no overlap to exploit — latency is identical. For every $n>1$, the deeper pipe B is strictly faster. Pipelining only pays off across streams.

Before: $t_{\text{clk}}=\max (5,5,5,5,9)=9\text{ns}$, throughput $=1/9$ instr/ns. After: the hot stage becomes two $4.5$ ns stages; now $t_{\text{clk}}=\max (5,5,5,5,4.5,4.5)=5\text{ns}$, throughput $=1/5$ instr/ns. Improvement factor $=\frac{1/5}{1/9}=\frac{9}{5}=1.8\times$. WHY: the slowest stage alone dictates the clock. Splitting the bottleneck lets a different stage (the 5 ns ones) become the new limiter. This is the whole art of stage balancing.

WHY add stalls to the formula: each bubble is a wasted cycle where no new instruction completes, so it just adds cycles onto the ideal count. $T_{\text{pipe}}=(k+n-1+\text{stalls})t=(5+20-1+4)\cdot 2=28\cdot 2=56\text{ns}$ Non-pipelined: $T_{\text{seq}}=20\cdot 5\cdot 2=200\text{ns}$. $S=\frac{200}{56}\approx 3.57.$ Compare to the ideal (no stalls) $S=\frac{20\cdot 5}{24}=\frac{100}{24}\approx 4.17$. The 4 stalls cost us about $0.6$ of speedup.

WHY CPI: for large $n$ the fill cycles vanish, so ideal CPI $=1$ (one instruction finishes per cycle). Each stalling instruction adds its stall cycles to the average. $\text{CPI}=1+f\cdot (\text{stalls per such instr})=1+0.2\cdot 1=1.2.$ Throughput $\propto 1/\text{CPI}$, so the pipeline runs at $\frac{1}{1.2}\approx 0.83$ of the ideal — about a 17% loss. This is exactly what Forwarding and Bypassing and Branch Prediction fight to recover.

WHY each term: every hazard just adds its expected extra cycles per instruction on top of the base CPI of 1. We weight each penalty by how often it actually fires.

Control-hazard cost per instruction: $\underset{\text{branch}}{\underbrace{0.20}}\times \underset{\text{taken}}{\underbrace{0.60}}\times \underset{\text{flush cycles}}{\underbrace{2}}=0.24\text{ cycles/instr}.$ A not-taken branch causes no flush here (fetched instructions were correct), so only taken branches are counted — that is why the $0.60$ appears.

Structural-hazard cost per instruction: $\underset{\text{load}}{\underbrace{0.10}}\times \underset{\text{stall cycle}}{\underbrace{1}}=0.10\text{ cycles/instr}.$ The IF and MEM stages both want the single memory port on a load cycle; one must wait.

Effective CPI: $\text{CPI}=1+0.24+0.10=1.34.$ Throughput ratio $=\frac{1}{1.34}\approx 0.746$ — about a 25% loss versus the ideal pipeline. Control hazards ($0.24$) dominate here; that is precisely why deep pipes invest so heavily in Branch Prediction, and why adding a second memory port (a Harvard split of instruction/data memory) removes the structural term entirely.

WHY Amdahl: speedup applies only to the part you accelerate; the untouched part becomes the new bottleneck. $S_{\text{overall}}=\frac{1}{(1-P)+\frac{P}{S_{\text{part}}}}=\frac{1}{0.2+\frac{0.8}{5}}=\frac{1}{0.2+0.16}=\frac{1}{0.36}\approx 2.78.$ Even a perfect $5\times$ engine yields only $\approx 2.78\times$ overall, because the $20\%$ I/O sets a ceiling of $1/0.2=5\times$ that you can never exceed no matter how deep the pipe.

WHY the $12/k$ term: if the total useful work ($12$ ns) is split into $k$ equal stages, each stage holds $12/k$ ns of that work — that is the "real" computation time in one stage. WHY the $+0.5$ term: every stage ends in a pipeline register (latch) that must physically settle before the next cycle. That latch costs $t_{\text{reg}}=0.5$ ns per stage regardless of how thin the stage is. So the clock must fit useful work + one latch: $t_{\text{clk}}(k)=12/k+0.5$. WHY $\Theta =1/t_{\text{clk}}$: once the pipe is full, exactly one instruction finishes every clock period $t_{\text{clk}}$, so instructions-per-nanosecond is just the reciprocal of the period. $t_{\text{clk}}(k)=\frac{12}{k}+0.5,\Theta (k)=\frac{1}{\frac{12}{k}+0.5}\text{(instr/ns)}.$ Evaluate:

Throughput keeps rising to $k=12$: deeper is better here, because $t_{\text{reg}}$ ($0.5$ ns) is still small next to the useful work per stage. But notice the diminishing returns: doubling $k$ from 6→12 only raised $\Theta$ by $0.667/0.400\approx 1.67\times$, not $2\times$. As $k\to \infty$, $t_{\text{clk}}\to 0.5$ ns (pure overhead) and $\Theta$ caps at $2$ instr/ns — the overhead sets a hard ceiling. Real CPUs also stop deepening because deeper pipes suffer bigger branch mispredict penalties.

(a) $n=1$: $S=\frac{1\cdot k}{k+1-1}=\frac{k}{k}=1$. One instruction can't overlap with anything — no benefit. $T_{\text{pipe}}=kt=$ full latency, same as non-pipelined. (b) $k=1$: $S=\frac{n\cdot 1}{1+n-1}=\frac{n}{n}=1$. A "1-stage pipeline" is the non-pipelined machine — nothing to overlap. (c) $n\to \infty$: divide top and bottom by $n$: $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$, so $S\to \frac{k}{1}=\mathbf{k}$. WHY: the $k-1$ fill cycles become a vanishing fraction of a huge instruction stream, so you effectively finish 1 instr/cycle versus $1/k$ instr/cycle non-pipelined — the maximum, equal to the stage count. (d) $k\to \infty$, $n$ fixed: divide top and bottom by $k$: $S=\frac{nk}{k+n-1}=\frac{n}{1+\frac{n-1}{k}}$. As $k\to \infty$ the term $\frac{n-1}{k}\to 0$, so $S\to \frac{n}{1}=\mathbf{n}$. WHY: with absurdly many stages the fill cost is dwarfed, but you can never overlap more instructions than you actually have — so speedup is capped by $n$, the instruction count, not by $k$. (This assumes ideal balanced stages and ignores $t_{\text{reg}}$, which in reality kills very large $k$.)

Symmetry insight: in the two limits the speedup is bounded by whichever of "stages" ($k$) or "instructions" ($n$) runs out first — you cannot overlap beyond the scarcer resource.

Stalls: branches $=0.10\cdot 30=3$. Mispredicted $=0.50\cdot 3=1.5$ (use $1.5$ as an expected value). Each costs $19$ cycles → stall cycles $=1.5\cdot 19=28.5$. Pipelined cycles $=(k+n-1)+\text{stalls}=(20+30-1)+28.5=49+28.5=77.5$ cycles. Non-pipelined = $nk=30\cdot 20=600$ cycles (each instruction $k$ cycles of work, one at a time). Both use the same short cycle time $t$, so compare cycle counts: $S=\frac{600}{77.5}\approx 7.7.$ Judgement: the $20\times$ claim is fantasy for this workload. Two killers: (1) only $n=30$ instructions, so the $19$ fill cycles are a big fraction; (2) deep pipes make each mispredict brutally expensive ($19$ cycles). The vendor's number assumes infinite $n$ and zero hazards. Lesson: advertised max speedup $=k$ is a ceiling you rarely approach — real gains depend on stream length and hazard rate. See Branch Prediction and Superscalar and Out-of-Order Execution for how modern CPUs claw some of this back.

$n$ limit? $S=\frac{nk}{k+n-1}$, which approaches $k$ (the stage count) as $n\to \infty$.

The slowest (max) stage delay plus the pipeline-register overhead $t_{\text{reg}}$. Splitting any other stage doesn't help.

With $n=1$ there is nothing to overlap; $S=k/k=1$ and its latency is still the full $k$ stages.

Control hazards (branch flushes): a mispredict throws away all the instructions fetched behind the branch, and a deeper pipe means more wasted instructions per flush — hence heavy investment in branch prediction.