Pipeline throughput and CPI: Exercises — Hardware deep dive

This page is a ladder. Each rung is harder than the last. Do a problem before opening its solution — the collapsible callout hides the answer until you click it. Everything here builds on Pipeline throughput and CPI; if a symbol feels unfamiliar, that parent note defined it, and this page uses it.

Before we start, let us re-anchor the four symbols we will lean on the hardest, so nothing is used unearned.

So the master clock-period rule we will invoke again and again is: $T_{p i p e} = max (t_{1}, t_{2}, \dots, t_{k}) + t_{r e g} .$

Figure 1 (below) is the mental model for the whole page. Read its legend first:

Level 1 — Recognition

Goal: read a definition and plug one number in.

Recall Solution L1.1

WHAT we do: find the slowest stage, then add register overhead. WHY: every stage clocks on the same edge, so the tick must be long enough for the worst stage to finish and for its output register to latch. $max (90, 60, 110, 100, 70) = 110 ps (EX is the bottleneck)$ $T_{p i p e} = 110 + 20 = 130 ps$

Recall Solution L1.2

WHAT: throughput $= 1/ (CPI \times T)$ . WHY: with $CPI = 1$ , one instruction exits every tick, and a tick lasts $T$ seconds. $Throughput = \frac{1}{1 \times 130 \times 1 0 ^{- 12}} = 7.69 \times 1 0^{9} instr/s \approx 7.69 billion/s$

Recall Solution L1.3

WHAT: CPI = total cycles $\div$ instructions. WHY: CPI is a per-instruction average, so we divide the whole bill by the count. $CPI = \frac{520}{400} = 1.30$

Level 2 — Application

Goal: chain two or three formulas together.

Recall Solution L2.1

WHAT: speedup = (time per instruction, single) $\div$ (time per instruction, pipe). WHY: ideal CPI is $1$ for both the per-instruction comparison at steady state, so the ratio is just the ratio of clock periods. $T_{s in g l e} = 90 + 60 + 110 + 100 + 70 = 430 ps$ $Speedup = \frac{430}{130} = 3.31 \times$ Not $5 \times$ — because EX is a bottleneck (unbalanced stages) and we pay $t_{r e g}$ every tick.

Recall Solution L2.2

WHAT: add each stall source's expected cost onto the ideal CPI of 1. WHY: expected stalls = (fraction of instructions affected) $\times$ (penalty each). Independent sources add. $Branch stalls = 0.20 \times 0.10 \times 4 = 0.08$ $Data stalls = 0.30 \times 1 = 0.30$ $CPI = 1 + 0.08 + 0.30 = 1.38$

Recall Solution L2.3

WHAT: throughput = clock rate / CPI. WHY: clock rate is ticks per second; dividing by cycles-per-instruction converts ticks into finished instructions. $Throughput = \frac{2.5 \times 1 0 ^{9}}{1.38} = 1.812 \times 1 0^{9} \approx 1.81 billion instr/s$

Level 3 — Analysis

Goal: compare designs, reason about "which is better and why."

Figure 2 shows exactly what the "split the bottleneck" move does to the clock: the tall EX bar is sawn in half, and the ceiling (dashed red line = the clock period) drops to whatever the next tallest bar reaches.

Recall Solution L3.1

(a) New clock period. WHAT: re-run $max (stage delays) + t_{r e g}$ with EX now two 55-ps stages. WHY: the clock is always set by the single worst stage; once EX (110) is gone, the new worst stage is MEM at 100 ps (look at the new red ceiling in Figure 2). $T_{n e w} = max (90, 60, 55, 55, 100, 70) + 20 = 100 + 20 = 120 ps$ Old $T = 110 + 20 = 130$ ps. (b) New CPI. WHAT: add the extra stall the deeper pipe introduces onto the old CPI of 1.20. WHY: CPI $= 1 + stalls/instr$ ; the old 0.20 data-hazard stalls remain, and the longer forwarding distance adds 0.05 more, so the stall term grows from 0.20 to 0.25. $CPI_{n e w} = 1.20 + 0.05 = 1.25$ (c) Throughput ratio. WHAT: form the ratio of the two throughputs, each $= 1/ (CPI \times T)$ . WHY compare $1/ (CPI \times T)$ and not CPI alone: the time per instruction is $CPI \times T$ — both factors changed here (CPI rose, $T$ fell), so judging by CPI alone would falsely say the new design is worse. Only the product captures real speed. $\frac{new}{old} = \frac{1/ ( 1.25 \times 120 )}{1/ ( 1.20 \times 130 )} = \frac{1.20 \times 130}{1.25 \times 120} = \frac{156}{150} = 1.04 \times$ Verdict: a measly 4% gain. WHY so small? Splitting EX only moved the bottleneck to MEM — the clock barely dropped (130→120), and the extra stall ate part of that. This is the law of diminishing returns from deepening pipelines. Contrast with 5.3.02-Superscalar-architecture, which attacks CPI itself rather than $T$ .

Recall Solution L3.2

Before forwarding: $CPI_{b e f or e} = 1 + 0.35 \times 2 = 1.70$ After forwarding: only the load-use subset stalls, at 1 cycle. $load-use fraction = 0.35 \times 0.20 = 0.07$ $CPI_{a f t er} = 1 + 0.07 \times 1 = 1.07$ Improvement: $1.70 - 1.07 = 0.63$ cycles/instr saved. See 5.2.07-Forwarding-and-bypassing for the bypass wires that make the 0-cycle path physical, and 5.2.03-Data-hazards for why load-use can't be fully forwarded (the data isn't ready until MEM).

Level 4 — Synthesis

Goal: combine several moving parts and design toward a target.

Recall Solution L4.1

(a) Max CPI. WHAT: invert throughput = clock/CPI to solve CPI = clock/throughput. WHY: throughput is set by how many finished instructions each second's worth of ticks yields; pinning the target and the clock leaves CPI as the only unknown. $CPI_{ma x} = \frac{3.0 \times 1 0 ^{9}}{3.0 \times 1 0 ^{9}} = 1.00$ That is impossible with any stalls — an ideal pipeline already sits at CPI 1 and these hazards push above it. So the target as stated cannot be met by prediction alone; let's see how close and what's needed. (b) Solve for mispredict rate $m$ . WHAT: write CPI as $1 + branch stalls (m) + data stalls$ , set it equal to the required 1.00, and solve for $m$ . WHY: only $m$ is adjustable; forcing the equation to the target tells us exactly what $m$ the target demands. $1 + branch 0.25 \cdot m \cdot 3 + data 0.30 \cdot 2 = 1.00$ $0.75 m + 0.60 = 0.00 \Rightarrow m = - 0.80$ A negative mispredict rate is impossible. Conclusion: the 0.60 data-stall term alone already forces CPI $\geq 1.60$ , so 3 Ginstr/s is unreachable at this clock. The design must attack data stalls (forwarding) — not branches. Re-doing with full forwarding (data stalls → 0): $1 + 0.25 \cdot m \cdot 3 = 1.00 \Rightarrow m = 0,$ i.e. even then you need perfect prediction. Realistically the clock must rise. This is exactly the kind of dead-end that pushes designers toward 5.3.02-Superscalar-architecture (CPI below 1).

Recall Solution L4.2

WHAT: for each choice, subtract that stall term from the current CPI, then compare throughputs. WHY: eliminating a stall category removes exactly its contribution from the CPI sum; with the clock fixed, throughput $\propto 1/ CPI$ , so the throughput ratio is simply $CPI_{o l d} / CPI_{n e w}$ . Option A — kill branch stalls: new CPI $= 1.50 - 0.20 = 1.30$ . Option B — kill data stalls: new CPI $= 1.50 - 0.30 = 1.20$ . Throughput ratio vs current (clock fixed) $= CPI_{o l d} / CPI_{n e w}$ : $A: \frac{1.50}{1.30} = 1.154, B: \frac{1.50}{1.20} = 1.250$ Kill data stalls (Option B): a $25%$ throughput gain vs $15.4%$ . WHY: the bigger stall term (0.30) is the bigger lever — you speed up what dominates. That is Amdahl's Law in disguise.

Level 5 — Mastery

Goal: reason about limits, degenerate cases, and where the simple model breaks.

Before the problems, we make the fill-and-drain picture explicit, because every Level-5 answer leans on it.

Figure 3 shows this literally: the number of red exit-boxes per column starts at 0 (pipe filling), rises to 1 (full), and the count of busy boxes tapers back down as the last instructions drain out.

Recall Solution L5.1

(a) Exact CPI. WHAT: divide total cycles by the instruction count. WHY: CPI is by definition total-cycles-per-instruction; we just carry the exact fill-and-drain count instead of approximating. $CPI (n) = \frac{total cycles}{instructions} = \frac{k + n - 1}{n} = 1 + \frac{k - 1}{n} .$ The term $\frac{k - 1}{n}$ is the fill-and-drain tax: the $k - 1$ "wasted" edge cycles, amortised over all $n$ instructions. Big pipe (large $k$ ) or short program (small $n$ ) → big tax. (b) Values for $k = 5$ (so $k - 1 = 4$ ). $n = 1 : 1 + \frac{4}{1} = 5.00, n = 5 : 1 + \frac{4}{5} = 1.80,$ $n = 100 : 1 + \frac{4}{100} = 1.04, n \to \infty : 1 + \frac{4}{n} \to 1.$ (c) Within 5% of 1. WHAT: demand the tax term $\leq 0.05$ and solve for $n$ . WHY: "within 5%" means CPI $\leq 1.05$ , i.e. the extra $\frac{k - 1}{n}$ must not exceed $0.05$ . $\frac{k - 1}{n} \leq 0.05 \Rightarrow n \geq \frac{4}{0.05} = 80 \Rightarrow n \geq 80 .$ (d) The two edge cases, physically.

$n = 1$ (single instruction, $n < k$ ): the pipe never fills. That one instruction walks through all 5 stages alone; the other 4 stages sit idle every cycle. CPI $= 5 = k$ — you get zero pipelining benefit, exactly the same as a single-cycle machine's latency. This is the degenerate "short program" limit: a program shorter than the pipe depth pays close to full latency per instruction.
$n = k = 5$ : the pipe just barely fills on the very last instruction's entry, then immediately begins to drain. CPI $= 1.80$ — still 80% above ideal, because half the run is spent filling/draining. Only when $n ≫ k$ does the steady-state "one exit per tick" dominate and CPI settle toward 1.

Recall Solution L5.2

First, the symbol we need — IPC. IPC (Instructions Per Cycle) is the average number of instructions that finish per clock tick — it is the plain reciprocal of CPI: $IPC = 1/ CPI$ , and equivalently $CPI = 1/ IPC$ . Where CPI counts "ticks per instruction," IPC counts "instructions per tick." A scalar pipeline tops out at IPC $= 1$ ; a superscalar can exceed it. (a) Here the sustained IPC is given directly as 2.8 (instructions finished per tick). So $CPI = \frac{1}{IPC} = \frac{1}{2.8} = 0.357.$ (b) $Throughput = \frac{clock}{CPI} = \frac{4.0 \times 1 0 ^{9}}{0.357} = 1.12 \times 1 0^{10} = 11.2 billion instr/s$ (Equivalently $4.0 \times 1 0^{9} \times 2.8$ .) (c) A scalar pipeline finishes at most one instruction per tick (CPI $\geq 1$ ). A superscalar finishes several per tick, so CPI can drop below 1 — see 5.3.02-Superscalar-architecture.

Recall Solution L5.3

(a) Clock period. WHAT: apply $max (delays) + t_{r e g}$ . WHY: the zero-delay stage contributes 0 to the $max$ , so it is invisible to the clock — the tick is set by the 100-ps stages. $T_{p i p e} = max (100, 0, 100, 100, 100) + 15 = 100 + 15 = 115 ps$ (b) Compare the two designs. WHAT: check both factors of time-per-instruction ( $CPI \times T$ ) after removing the stage. WHY: removing a stage could change either $T$ or CPI; here the worst stage is unchanged so $T$ stays 115 ps, while CPI falls by 0.02 (one fewer register to forward across). $T_{4} = 115 ps (unchanged), CPI_{4} = 1.30 - 0.02 = 1.28$ Since $T$ is identical and CPI dropped, time per instruction $CPI \times T$ falls from $1.30 \times 115 = 149.5$ to $1.28 \times 115 = 147.2$ (ps). The 4-stage version is strictly faster. Lesson: a stage that neither raises the $max$ nor shortens some other stage is pure overhead — delete it.

Recall Self-check clozes

The pipeline clock period equals == $max$ of stage delays $+ t_{r e g}$ , not the sum. Actual CPI equals $1 +$ stalls per instruction for a scalar pipeline. Throughput equals clock rate $\div$ CPI. CPI below 1 requires superscalar (multiple-issue)== execution. Total cycles to run $n$ instructions in a $k$ -stage pipe ::: $k + (n - 1)$ . Fill-and-drain tax per instruction for $n$ instructions in a $k$ -stage pipe ::: $\frac{k - 1}{n}$ extra cycles. A program with $n = 1$ instruction on a $k$ -stage pipe has CPI ::: exactly $k$ (no overlap, pipe never fills).