Worked examples — Pipeline throughput and CPI

This page is the drill ground for the parent topic. Before we compute anything, let us list every kind of question the topic can throw at you. Then we solve one example per cell, so you never meet a scenario you haven't already seen.

---

The scenario matrix

Every exam question about pipeline performance lands in one of these cells. Our job is to hit them all.

#	Cell (case class)	What makes it tricky	Hit by
A	Ideal fill-up — exact cycles for $n$ instructions	the "$+(k-1)$" fill cost, small $n$	Ex 1
B	Limiting value $n\to \infty$	why CPI collapses to $1$	Ex 1
C	Clock period from unbalanced stages	pick the max, add register overhead	Ex 2
D	Speedup vs single-cycle	sum-of-stages ÷ pipe period	Ex 2
E	CPI with data + control hazards	combine two stall sources	Ex 3
F	Forwarding removes stalls	before/after CPI difference	Ex 4
G	Branch prediction improvement	accuracy → mispredict rate flip	Ex 5
H	Degenerate: 1-stage / perfectly balanced	edge where pipelining does nothing	Ex 6
I	Zero-hazard vs all-hazard extremes	CPI floor and a worst case	Ex 6
J	Superscalar: CPI < 1	IPC > 1, real-world word problem	Ex 7
K	Exam twist: which processor is faster?	GHz alone is a trap	Ex 8

Prerequisite links if a cell needs backup: 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.

---

Example 1 — Cells A & B: exact cycles and the limit

Forecast: guess now — does CPI fall or rise as $n$ grows? Toward what number?

Look at the figure: each row is one instruction sliding right by one stage per cycle. The staircase takes $k$ cycles just to reach the WB corner for the first instruction; after that, one finishes every single cycle.

Step 1 — Count the fill. The first instruction needs all $k=5$ cycles to travel IF→ID→EX→MEM→WB. Why this step? Nothing can finish before the pipe is full — this is the unavoidable start-up cost.

Step 2 — Count the steady state. After the first finishes, the remaining $n-1$ instructions finish one per cycle. $\text{Total cycles}=k+(n-1)=5+(n-1)=n+4$ Why? Each later instruction is one cycle behind the one ahead — the assembly-line rhythm.

Step 3 — Divide to get CPI. $\text{CPI}=\frac{n+4}{n}$

$n$	Total cycles	CPI
1	5	5.000
5	9	1.800
100	104	1.040
$10^6$	1000004	1.000004

Step 4 — The limit. As $n\to \infty$, the constant $4$ becomes negligible next to $n$: ${\lim }_{n\to \infty }\frac{n+4}{n}=1.$ Why a limit here? CPI is a per-instruction average; the fixed fill cost gets shared over ever more instructions, so its per-instruction share vanishes.

Verify: For $n=5$: $\frac{9}{5}=1.8$ ✓. Single instruction gives CPI $=5$ (equals latency — pipelining gives you nothing for one instruction, exactly as expected).

---

Example 2 — Cells C & D: clock period and speedup

Forecast: which stage sets the clock, and will speedup reach the ideal $5\times$?

Step 1 — Pick the slowest stage. All stages tick on the same clock edge, so the clock can only be as fast as the slowest one allows. $\max (80,70,100,90,60)=100\text{ps (EX)}.$ Why max, not average? A worker who is slow holds up the whole line even if others are fast.

Step 2 — Add register overhead. $T_{pipe}=100+30=130\text{ps}.$ Why? Each stage's result must be latched into the pipeline register before the next edge.

Step 3 — Single-cycle period = sum of all stages. With no overlap one instruction walks through every stage in one long cycle: $T_{single}=80+70+100+90+60=400\text{ps}.$

Step 4 — Speedup. $\text{Speedup}=\frac{T_{single}}{T_{pipe}}=\frac{400}{130}\approx \mathrm{3.08.}$ Why below $5$? The stage imbalance (EX hogs the clock) plus the $30$ ps overhead steal the ideal $5\times$.

Verify: $130\times 3.08\approx 400$ ✓. Ideal (balanced, no overhead) would be $400/80=5$ — our $3.08$ correctly sits below it.

---

Example 3 — Cell E: CPI with both hazard types

Forecast: will CPI land nearer $1.1$ or $1.4$?

Step 1 — Branch stalls per instruction. Only mispredicted branches cost cycles: $0.25\times 0.10\times 3=\mathrm{0.075.}$ Why the triple product? Fraction that are branches × fraction of those that mispredict × cycles each wastes.

Step 2 — Data-hazard stalls per instruction. $0.15\times 2=\mathrm{0.30.}$

Step 3 — Add to the ideal floor of 1. $\text{CPI}=1+0.075+0.30=\mathrm{1.375.}$

Step 4 — Throughput. $\frac{2\times 10^9}{1.375}\approx 1.4545\times 10^9\text{instr/s}.$ Why divide by CPI? Each instruction now eats $1.375$ cycles, so fewer finish per second.

Verify: $1.4545\times 10^9\times 1.375\approx 2\times 10^9$ ✓ (back to the raw cycle rate). Ideal throughput would be $2\times 10^9$; we get $1/1.375=72.7\%$ of it.

---

Example 4 — Cell F: forwarding erases stalls

Forecast: how much CPI does forwarding buy back?

Step 1 — CPI without forwarding. ${\text{CPI}}_{no}=1+0.30\times 2=\mathrm{1.60.}$

Step 2 — CPI with forwarding. Stalls drop to $0$: ${\text{CPI}}_{fwd}=1+0.30\times 0=\mathrm{1.00.}$ Why zero? The EX result is handed straight to the next EX input, so nobody waits for writeback.

Step 3 — Cycles saved per instruction. $1.60-1.00=\mathrm{0.60.}$

Verify: speedup $=1.60/1.00=1.60\times$ — forwarding here recovers the entire hazard penalty, exactly matching the parent note's claim. ✓

---

Example 5 — Cell G: better branch prediction

Forecast: how many CPI points does going $50\%\to 90\%$ accurate save?

Step 1 — Convert accuracy to mispredict rate. Mispredict $=1-\text{accuracy}$: so $0.50$ and $0.10$. Why the flip? Penalties come from the branches we get wrong, not right.

Step 2 — CPI at 50% accuracy. $1+0.20\times 0.50\times 3=1+0.30=\mathrm{1.30.}$

Step 3 — CPI at 90% accuracy. $1+0.20\times 0.10\times 3=1+0.06=\mathrm{1.06.}$

Step 4 — Improvement. $1.30-1.06=0.24\text{CPI saved}.$

Verify: throughput ratio $=1.30/1.06\approx 1.226$ → a $\sim 22.6\%$ throughput gain. ✓

---

Example 6 — Cells H & I: degenerate and extreme inputs

Forecast: for (a), is there any speedup at all?

Step 1 — (a) $k=1$. Total cycles $=k+(n-1)=1+(n-1)=n$, so CPI $=1$ but there is no overlap — this is the single-cycle machine. Why the degenerate result? With one stage there is nothing to pipeline; speedup over single-cycle $=1\times$.

Step 2 — (b) balanced, no overhead. $T_{single}=4\times 100=400,T_{pipe}=100+0=100,\text{Speedup}=\frac{400}{100}=4=k.$ Why exactly $k$? Perfect balance and zero overhead is the ideal limit — speedup reaches the stage count.

Step 3 — (c) zero-hazard floor. ${\text{CPI}}_{min}=1+0=1.$ CPI can never dip below $1$ for a scalar pipeline (one finish per cycle max) — that changes only in Example 7.

Step 4 — (d) all-hazard worst case. $\text{CPI}=1+1.00\times 2=3.$ Why $1.00$? "Every" instruction hazards → hazard rate $=1$. This is the ceiling for a $2$-cycle-stall world.

Verify: (a) speedup $400/400=1$ if that single stage summed the same $400$ ps — pipelining nothing changes nothing ✓. (b) $4=k$ ✓. (d) $3=1+2$ ✓.

---

Example 7 — Cell J: superscalar, CPI below 1 (real-world)

Forecast: can a single instruction really take a quarter of a cycle?

Step 1 — IPC is the reciprocal of CPI. $\text{IPC}=\frac{1}{\text{CPI}}=\frac{1}{0.25}=4\text{instructions/cycle}.$ Why reciprocal? CPI is cycles-per-instruction; flip it to get instructions-per-cycle.

Step 2 — Throughput. $4.0\times 10^9\text{cycles/s}\times 4\text{instr/cycle}=16\times 10^9\text{instr/s}.$

Step 3 — Why CPI < 1? No single instruction is faster — the core simply issues 4–6 instructions in the same cycle using multiple execution units. Averaged, each instruction shares a cycle, so the per-instruction cycle count drops below $1$.

Verify: $16\times 10^9/4\times 10^9=4$ IPC ✓; and $1/4=0.25$ CPI ✓.

---

Example 8 — Cell K: the exam trap "which is faster?"

Forecast: the flashy $5$ GHz chip — winner or bait?

Step 1 — Performance $=$ clock rate ÷ CPI. $P:\frac{5.0\times 10^9}{4.0}=1.25\times 10^9\text{instr/s}.$ $Q:\frac{3.0\times 10^9}{1.0}=3.0\times 10^9\text{instr/s}.$ Why divide by CPI? Raw GHz counts cycles; only dividing by cycles-per-instruction turns it into work done.

Step 2 — Compare. $Q$ delivers $3.0\times 10^9$ vs $P$'s $1.25\times 10^9$ — Q is faster.

Step 3 — By how much. $\frac{3.0\times 10^9}{1.25\times 10^9}=2.4\times .$

Verify: time for $N$ instructions on P $=N\times 4.0/(5\times 10^9)=8\times 10^{-10}N$ s; on Q $=N\times 1.0/(3\times 10^9)\approx 3.33\times 10^{-10}N$ s. Ratio $=8/3.33\approx 2.4$ ✓ — the "slower-clocked" chip wins by $2.4\times$. This is the iron law in one punch.

---

Recall Self-test

CPI in the limit of many instructions for an ideal k-stage pipe ::: 1 Pipeline clock period formula ::: $\max (t_i)+t_{reg}$ Why superscalar can give CPI < 1 ::: it issues multiple instructions per cycle (IPC > 1) Faster: 5 GHz CPI=4 or 3 GHz CPI=1 ::: the 3 GHz one (performance = rate ÷ CPI) Cycles saved per instruction by forwarding when 30% hazard, 2-cycle stall ::: 0.60