Deep pipelining trade-offs: Exercises — Hardware deep dive

This page is a self-test ladder. Each problem states its difficulty level (L1 → L5). Try it with the Solution callout collapsed, then open it to check every step. All numbers are machine-verified.

Before we start, let us make sure every symbol used below is already earned — nothing here appears without a plain-words meaning first.

Definition The symbols this page uses

$k$ = number of pipeline stages (how many slices we cut instruction work into). More slices = shorter slice = faster clock. $k$ is a positive integer, $k \geq 1$ — you cannot build "half a stage." We will often solve a continuous formula first and then round to a whole number, because the maths gives real numbers but hardware only accepts integers.
$T_{0}$ = total combinational logic delay if we did NOT pipeline at all (one giant slice), measured in nanoseconds (ns).
$τ = T_{0} / k$ = logic delay of one stage after cutting $T_{0}$ into $k$ equal pieces.
$t_{reg}$ = pipeline-register overhead per stage: the fixed time cost of the latch between stages (setup + clock-to-Q + skew). It does not shrink when you add stages.
$T_{cycle} = τ + t_{reg}$ = clock period, the time one tick takes. Set by the slowest stage.
$f = 1/ T_{cycle}$ = clock frequency (ticks per second). If $T_{cycle}$ is in ns, then $f = 1000/ T_{cycle}$ in MHz.
CPI = cycles per instruction = average clock ticks each instruction consumes. Ideal pipeline = 1; hazards push it above 1.
Throughput = useful work per second $= f / CPI$ . This is the number that actually matters.

See Deep pipelining trade-offs for the full derivations these problems drill.

Level 1 — Recognition

Problem 1.1

State, in one sentence each, what $k$ , $τ$ , $t_{reg}$ , and $T_{cycle}$ mean, and write the formula linking them.

Recall Solution 1.1

$k$ = number of pipeline stages (a positive integer, $k \geq 1$ ).
$τ = T_{0} / k$ = combinational logic delay of one stage.
$t_{reg}$ = fixed per-stage pipeline-register overhead (does not shrink with $k$ ).
$T_{cycle}$ = clock period = time of one tick.
Link: $T_{cycle} = τ + t_{reg} = \frac{T _{0}}{k} + t_{reg} .$ What this says: as we add stages, the first term shrinks but the second never does.

Problem 1.2

A pipeline has $T_{0} = 12$ ns of logic split into $k = 6$ stages, with $t_{reg} = 0.3$ ns. Find $τ$ , $T_{cycle}$ , and $f$ (in MHz).

Recall Solution 1.2

$τ = 12/6 = 2$ ns.
$T_{cycle} = 2 + 0.3 = 2.3$ ns.
$f = 1000/2.3 \approx 434.8$ MHz. Why 1000? 1 ns $= 1 0^{- 9}$ s, so $1/ T_{cycle} [ns] = 1 0^{9} / T_{cycle}$ Hz $= 1000/ T_{cycle}$ MHz.

Problem 1.3

True or false: "Adding more pipeline stages always lowers $T_{cycle}$ ." Explain using the formula.

Recall Solution 1.3

False (in practice), true only in the idealised logic-only model. In the pure model $T_{cycle} = T_{0} / k + t_{reg}$ , raising $k$ shrinks $T_{0} / k$ , so $T_{cycle}$ keeps falling — but only asymptotically toward $t_{reg}$ , never below it. In reality logic is not infinitely divisible (atomic stages), so past some depth the slowest stage stops shrinking and $T_{cycle}$ flattens. So the honest answer is: it never increases $T_{cycle}$ in the ideal model, but the benefit vanishes.

Level 2 — Application

Problem 2.1

Unpipelined logic $T_{0} = 10$ ns, register overhead $t_{reg} = 0.2$ ns, perfect balance. Compute the ideal speedup $\frac{T _{0}}{T _{cycle}}$ for $k = 5$ , $k = 10$ , and $k = 20$ stages. Round to two decimals.

Recall Solution 2.1

Why this formula? Unpipelined, one instruction takes the whole $T_{0}$ to finish. A full $k$ -stage pipeline, once its stages are all busy, retires one instruction every clock tick — i.e. one every $T_{cycle}$ . So the time per instruction drops from $T_{0}$ to $T_{cycle}$ , and speedup is the ratio of those two per-instruction times: $Speedup = \frac{T _{0}}{T _{cycle}} = \frac{T _{0}}{T _{0} / k + t _{reg}} .$ That is why $T_{0}$ sits on top and one cycle sits on the bottom — we are comparing "seconds per instruction, before vs after."

$k = 5$ : $T_{cycle} = 2 + 0.2 = 2.2$ ; speedup $= 10/2.2 = 4.55 \times$ .
$k = 10$ : $T_{cycle} = 1 + 0.2 = 1.2$ ; speedup $= 10/1.2 = 8.33 \times$ .
$k = 20$ : $T_{cycle} = 0.5 + 0.2 = 0.7$ ; speedup $= 10/0.7 = 14.29 \times$ . What it looks like — read Figure s01: the blue curve is this speedup versus $k$ . The three coloured dots mark our answers (orange $k = 5$ , green $k = 10$ , gray $k = 20$ ). Notice the gap between the green and gray dots is not double the gap between orange and green — the curve is bending toward the dashed red ceiling. That bend IS diminishing returns, made visible.

Problem 2.2

Using the $k = 5 \to k = 20$ result above, quantify the "diminishing returns": we made the pipeline $4 \times$ deeper — by what factor did ideal speedup actually grow?

Recall Solution 2.2

Deeper by $20/5 = 4 \times$ . Speedup grew by $14.29/4.55 = 3.14 \times$ . So $4 \times$ the hardware depth buys only $3.14 \times$ the speed. The missing $0.86 \times$ is eaten by $t_{reg}$ , which is now $0.2/0.7 = 28.6%$ of every cycle (vs $0.2/2.2 = 9.1%$ at $k = 5$ ). On the figure: this is exactly the vertical distance from the gray dot down to where a straight $4 \times$ line from the orange dot would have landed — the shortfall is the red ceiling pulling the curve flat.

Problem 2.3

A design has $T_{0} = 15$ ns and $t_{reg} = 0.5$ ns. What is the maximum possible clock frequency (the asymptotic limit as $k \to \infty$ ), in MHz?

Recall Solution 2.3

As $k \to \infty$ , $T_{0} / k \to 0$ , so $T_{cycle} \to t_{reg} = 0.5$ ns. $f_{m a x} = 1000/0.5 = 2000 MHz = 2 GHz .$ Why there is a ceiling: you can never make a cycle shorter than the register handoff itself. This is the wall deep pipelining runs into. (This limit is a mathematical $k \to \infty$ ; real $k$ is a finite integer, so you only ever approach 2 GHz.)

Level 3 — Analysis

Problem 3.1

Branches occur every 5 instructions; prediction accuracy is 90%; misprediction penalty is $k - 1$ cycles. Compute the effective CPI for a 5-stage and a 20-stage pipeline (ignore data hazards).

Recall Solution 3.1

Fraction of instructions that are branches $= 1/5 = 0.2$ . Mispredicted fraction $= 0.2 \times (1 - 0.90) = 0.2 \times 0.10 = 0.02$ per instruction. Stall CPI $= 0.02 \times (k - 1)$ .

5-stage: $0.02 \times 4 = 0.08$ ⇒ CPI $= 1.08$ .
20-stage: $0.02 \times 19 = 0.38$ ⇒ CPI $= 1.38$ . What it looks like: each mispredict flushes the whole pipeline; a longer pipe throws away more in-flight work. See Branch Prediction and Pipeline Hazards.

Problem 3.2

The 20-stage pipeline runs its clock $4 \times$ faster than the 5-stage one. Using the CPIs from 3.1, find the effective speedup (throughput ratio). Did the $4 \times$ frequency pay off?

Recall Solution 3.2

Throughput $\propto f / CPI$ . $Speedup = \frac{f _{20}}{f _{5}} \cdot \frac{CPI _{5}}{CPI _{20}} = 4 \times \frac{1.08}{1.38} = 4 \times 0.7826 = 3.13 \times .$ Verdict: the $4 \times$ clock delivers only $3.13 \times$ throughput. The CPI grew from 1.08 to 1.38 ( $1.28 \times$ worse), erasing about a quarter of the frequency win. See Superscalar Architectures for the complementary lever (raising IPC instead of $f$ ).

Problem 3.3

At what branch prediction accuracy $p$ would the 20-stage pipeline's control-stall CPI equal the 5-stage pipeline's control-stall CPI from 3.1 (which was 0.08)? Keep branch frequency $0.2$ and penalty $19$ .

Recall Solution 3.3

Set $0.2 \times (1 - p) \times 19 = 0.08$ . $1 - p = \frac{0.08}{0.2 \times 19} = \frac{0.08}{3.8} = 0.02105.$ $p = 1 - 0.02105 = 0.97895 \approx 97.9%.$ Meaning: to keep the 20-stage pipe's control stalls as low as the 5-stage pipe's, prediction must climb from 90% to ~97.9%. This is exactly why deep pipelines demand excellent branch prediction — the accuracy requirement rises with depth.

Level 4 — Synthesis

Problem 4.1

Dynamic power is $P = C V^{2} f$ . A deeper pipeline raises $f$ by $1.5 \times$ . If voltage $V$ is held constant and capacitance $C$ is held constant, by what factor does dynamic power rise? Then, if the designer drops $V$ by 10% (to $0.9 V$ ) to compensate, what is the net power factor?

Recall Solution 4.1

Constant $V$ : $P \propto f$ , so power rises by $1.5 \times$ . With $V \to 0.9 V$ : power scales as $V^{2} f$ , so factor $= (0.9)^{2} \times 1.5 = 0.81 \times 1.5 = 1.215 \times$ . Interpretation: even after a 10% voltage cut, power still climbs 21.5%. Voltage reduction (the lever behind Dynamic Voltage and Frequency Scaling (DVFS)) softens but does not erase the power cost of going faster, because power depends on $V$ squared but on $f$ only linearly.

Problem 4.2 — Pentium 4 Prescott reconstruction

Northwood (20 stages) vs Prescott (31 stages): Prescott raised frequency by $1.5 \times$ but its CPI also rose by $1.5 \times$ . (a) Compute the net performance factor. (b) If power rose by $1.5 \times$ as well, compute performance-per-watt relative to Northwood.

Recall Solution 4.2

(a) Performance $\propto f / CPI$ : $\frac{1.5 f}{1.5 CPI} = 1.0 \times .$ No net gain — the frequency win was exactly cancelled by the CPI loss. This is the "deep-pipeline wall." (b) Performance-per-watt $= \frac{performance}{power} = \frac{1.0}{1.5} = 0.667 \times$ . Verdict: same speed, $1.5 \times$ the power ⇒ efficiency dropped to two-thirds. This is why Intel abandoned the deep-pipeline path for the Core microarchitecture. See Pentium 4 vs Core Microarchitecture.

Problem 4.3

Combine two effects. Take $T_{0} = 10$ ns, $t_{reg} = 0.2$ ns. Define throughput index $Θ (k) = \frac{f ( k )}{CPI ( k )}$ where $f (k) = 1000/ (10/ k + 0.2)$ MHz and $CPI (k) = 1 + 0.02 (k - 1)$ (from the branch model of 3.1). Compute $Θ$ for $k = 5, 10, 15, 20$ and identify which $k$ maximises throughput.

Recall Solution 4.3

Why this index? $f$ tells you ticks-per-second, $CPI$ tells you ticks-per-instruction, so $f / CPI$ = instructions-per-second — the actual useful-work rate. Dividing cancels the "cycle" unit and leaves work-per-time, which is precisely what we want to maximise. We evaluate it only at whole-number $k$ because stages are integers. Compute each (frequency in MHz, CPI dimensionless, $Θ$ in MHz-per-instruction-cycle):

$k = 5$ : $f = 1000/2.2 = 454.55$ , CPI $= 1.08$ , $Θ = 420.9$ .
$k = 10$ : $f = 1000/1.2 = 833.33$ , CPI $= 1.18$ , $Θ = 706.2$ .
$k = 15$ : $f = 1000/0.8667 = 1153.85$ , CPI $= 1.28$ , $Θ = 901.4$ .
$k = 20$ : $f = 1000/0.7 = 1428.57$ , CPI $= 1.38$ , $Θ = 1035.2$ . Result: within this range $Θ$ still rises with $k$ (peaks at $k = 20$ ) — because 90% prediction keeps CPI growth mild. The peak moves to smaller $k$ once you add data hazards and worse prediction. The lesson: the optimal depth depends entirely on how steeply CPI climbs. Read Figure s02: the blue curve is this very $Θ (k)$ with no atomic floor — it keeps climbing across our whole range, which is why the naive model never tells you to stop.

Level 5 — Mastery

Problem 5.1 — Derive the true optimum with imbalance

Suppose logic cannot be split below an atomic floor: the slowest stage is $τ_{m i n} = max (T_{0} / k, a)$ where $a = 0.6$ ns is an unsplittable operation (e.g. a cache access, see Instruction Pipelining Basics). With $T_{0} = 10$ ns and $t_{reg} = 0.2$ ns, find the smallest $k$ beyond which adding stages gives zero frequency benefit.

Recall Solution 5.1

Frequency stops improving once $T_{0} / k$ falls to the atomic floor $a$ , i.e. once $T_{0} / k \leq a$ : $k \geq \frac{T _{0}}{a} = \frac{10}{0.6} = 16.67.$ Integer-stage step: $16.67$ is not a legal stage count — $k$ must be a whole number. We round up to the next integer, $k = 17$ , because that is the first integer at which $T_{0} / k = 10/17 = 0.588 \leq 0.6$ actually holds (at $k = 16$ , $10/16 = 0.625 > 0.6$ , so the floor is not yet reached). For $k \geq 17$ , the slowest stage is stuck at $0.6$ ns, so $T_{cycle} = 0.6 + 0.2 = 0.8$ ns and $f$ freezes at $1000/0.8 = 1250$ MHz no matter how many more stages you add — but CPI keeps rising with $k$ . So past $k = 17$ , deeper is strictly worse. This is stage imbalance turning "harmless" into "harmful."

Problem 5.2 — Full throughput optimisation

Use $T_{cycle} (k) = max (10/ k, 0.6) + 0.2$ and $CPI (k) = 1 + 0.02 (k - 1)$ . Compute the throughput index $Θ (k) = f (k) / CPI (k)$ at $k = 15, 17, 20, 25$ and state the true optimal depth.

Recall Solution 5.2

Why the $max$ appears now: the clock is set by the slowest stage, and no stage can be faster than the atomic floor $a = 0.6$ ns. So the logic part of the cycle is $max (10/ k, 0.6)$ : it follows $10/ k$ while that is above $0.6$ , then clamps at $0.6$ . Evaluate only at integer $k$ :

$k = 15$ : $10/15 = 0.667 > 0.6$ , floor not yet active, so $T_{cycle} = 0.667 + 0.2 = 0.867$ ns, $f = 1000/0.867 = 1153.85$ MHz; CPI $= 1 + 0.02 (14) = 1.28$ ; $Θ = 1153.85/1.28 = 901.4$ .
$k = 17$ : $10/17 = 0.588 < 0.6$ , floor now active, so $T_{cycle} = 0.6 + 0.2 = 0.8$ ns, $f = 1000/0.8 = 1250$ MHz; CPI $= 1 + 0.02 (16) = 1.32$ ; $Θ = 1250/1.32 = 946.97$ .
$k = 20$ : floor active, $f = 1250$ MHz (frozen); CPI $= 1 + 0.02 (19) = 1.38$ ; $Θ = 1250/1.38 = 905.80$ .
$k = 25$ : floor active, $f = 1250$ MHz (frozen); CPI $= 1 + 0.02 (24) = 1.48$ ; $Θ = 1250/1.48 = 844.59$ . True optimal depth $k^{*} = 17$ . Reading down the list, $Θ$ climbs $901.4 \to 946.97$ as we reach the floor, then falls $946.97 \to 905.80 \to 844.59$ once frequency is frozen but CPI keeps rising. The maximum sits exactly at $k = 17$ — the first integer where the atomic floor caps the clock. Beyond it, you pay more registers and more hazard stalls for zero extra frequency, so throughput can only drop. This is the honest sweet spot: push depth up to the floor, then stop.

Problem 5.3 — Design judgement

A rival team proposes doubling depth from 17 to 34 stages, promising "double the frequency." Given the model in 5.2, write a two-line rebuttal with numbers.

Recall Solution 5.3

Rebuttal: Frequency does not double — the slowest atomic stage is already at the $0.6$ ns floor, so $f$ stays pinned at $1250$ MHz from $k = 17$ onward; doubling to 34 changes $f$ by $0%$ . Meanwhile CPI rises from $1.32$ to $1 + 0.02 (33) = 1.66$ , so throughput falls from $Θ = 947$ to $1250/1.66 = 753$ — a 20% loss — plus roughly double the register power. Doubling depth here is all cost, no benefit.

Recall Self-check summary (cloze)

The clock period is $T_{cycle} =$ ::: $τ + t_{reg} = T_{0} / k + t_{reg}$ The quantity that actually measures performance is ::: throughput $= f / CPI$ As $k \to \infty$ in the ideal model, $f$ is bounded by ::: $1/ t_{reg}$ Branch misprediction penalty in a $k$ -stage pipe is ::: $k - 1$ cycles The true depth limit appears when $T_{0} / k$ hits the ::: atomic (unsplittable) stage floor $a$ , i.e. $k = ⌈ T_{0} / a ⌉$