Worked examples — Pipelining — 5-stage pipeline, each stage

You have built the machinery in the parent note: the five stages IF, ID, EX, MEM, WB, the timing law $T_{\text{pipe}}=(k+n-1)t$, the speedup $S=\frac{nk}{k+n-1}$, and the fact that pipelines can stall when instructions depend on each other. This page does one thing: it drags those formulas through every kind of situation they can meet, so no exam problem surprises you.

Before any symbol appears, let us re-anchor the three numbers we will use constantly:

Because every example leans on the same two laws, let us restate them here on this page (they were derived in the parent) so you never have to leave to remember where they came from:

---

The scenario matrix

Every problem on this topic is one (or a blend) of these cells. We will hit all of them.

Cell	What makes it special	Where it bites
A. Large $n$	$n\gg k$	Speedup near its ceiling $k$
B. Small $n$	$n$ comparable to $k$	Fill cycles dominate, speedup poor
C. Degenerate $n=1$	a single instruction	Speedup $=1$: pipelining does nothing
D. Limiting $n\to \infty$	infinite stream	Speedup $\to k$ exactly
E. Unbalanced stages	stages have different delays	Clock set by the slowest stage, not the average
F. Register overhead	latch adds $t_{\text{reg}}$	Real clock period grows, speedup shrinks
G. Stalls / hazards	bubbles inserted	Effective cycles $>k+n-1$
H. Word problem	real throughput in instr/sec	Translate cycles ↔ seconds
I. Exam twist	"how many stages for a target speedup?"	Solve the formula backwards

Each worked example below is tagged with the cell(s) it covers.

---

Example 1 — Cell A (large $n$, the happy case)

Steps.

1. Non-pipelined time. Each instruction visits all $k$ boxes, so it takes $k\cdot t$; do that $n$ times in a row. $T_{\text{seq}}=nkt=500\cdot 5\cdot 2=5000\text{ ns}$ Why this step? This is the baseline we are trying to beat — no overlap at all.

2. Pipelined time. Fill the pipe with $k$ cycles, then one instruction leaves every cycle for the remaining $n-1$. $T_{\text{pipe}}=(k+n-1)t=(5+500-1)\cdot 2=504\cdot 2=1008\text{ ns}$ Why this step? The fill cost is paid once; after that it is one-per-tick.

3. Speedup = old time ÷ new time. $S=\frac{5000}{1008}\approx 4.96$ Why this step? Speedup answers "how many times faster", so it is a ratio of the two times.

Recall Verify (Example 1)

$S=\frac{nk}{k+n-1}=\frac{500\cdot 5}{504}=\frac{2500}{504}\approx 4.96$. Same as $5000/1008$. ✓ Close to the ceiling $5$, as Cell A predicts.

---

Example 2 — Cell B (small $n$, pipelining barely helps)

Steps.

1. Non-pipelined: $T_{\text{seq}}=3\cdot 5\cdot 2=30\text{ ns}$. Why this step? Baseline again.

2. Pipelined: $T_{\text{pipe}}=(5+3-1)\cdot 2=7\cdot 2=14\text{ ns}$. Why this step? Notice $7$ cycles for $3$ instructions — the $4$ fill cycles ($k-1=4$) are a huge fraction here.

3. Speedup: $S=\frac{30}{14}\approx 2.14$. Why this step? Ratio of times.

What the figure below shows (read it before moving on): three colored instruction rows (blue, orange, green) march diagonally down-right through the five labelled stage boxes IF→ID→EX→MEM→WB. Reading any vertical column tells you which stages are busy in that clock cycle. The gray slab along the bottom marks the first four cycles — the fill cycles ($k-1=4$) during which the pipe is not yet producing one finished instruction per tick. The red double arrow spans the full width and labels the total, $k+n-1=7$ cycles. Notice visually how wide the gray fill region is compared to the useful region when $n$ is only 3.

Recall Verify (Example 2)

$S=\frac{3\cdot 5}{5+3-1}=\frac{15}{7}\approx 2.14$. ✓ Much less than 5 — Cell B confirmed: fill cycles dominate.

---

Example 3 — Cell C (the degenerate single instruction)

Steps.

1. Non-pipelined time for one instruction: $T_{\text{seq}}=1\cdot k\cdot t=5t$. Why this step? One instruction, all five stages.

2. Pipelined time: $T_{\text{pipe}}=(k+1-1)t=kt=5t$. Why this step? Plug $n=1$ into $(k+n-1)$: the $n-1$ term vanishes. Nothing overlaps because there is nothing to overlap with.

3. Speedup: $S=\frac{5t}{5t}=1$. Why this step? Equal times ⇒ ratio $1$ ⇒ no gain.

Recall Verify (Example 3)

$S=\frac{1\cdot 5}{5+1-1}=\frac{5}{5}=1$. ✓

---

Example 4 — Cell D (the limiting value $n\to \infty$)

Steps.

1. Write the general speedup and divide top and bottom by $n$. $S=\frac{nk}{k+n-1}=\frac{k}{\frac{k-1}{n}+1}$ Why this step? Dividing by $n$ isolates how each term behaves as $n$ grows — the tool for "what happens in the limit."

2. Let $n\to \infty$. The term $\frac{k-1}{n}\to 0$. $S\to \frac{k}{0+1}=k=5$ Why this step? This is the limit: the value the sequence hugs but never quite touches.

3. Confirm it never reaches $k$ for finite $n$: since $\frac{k-1}{n}>0$ always, the denominator is $>1$, so $S<5$ strictly. Why this step? Answers the "approaches but never equals" part.

What the figure below shows (read it before moving on): a blue curve of $S$ against the number of instructions $n$. It rises steeply for small $n$, then bends over and flattens. The dashed red horizontal line at height $5$ is the ceiling $S=k$; the blue curve creeps toward it but never touches it. The green dot at $n=1$ sits at height $1$ (the degenerate case of Example 3), and the gray annotation points to where the curve "flattens toward 5". The visual message: extra instructions give big gains at first, then almost none.

Recall Verify (Example 4)

At $n=1000$: $S=\frac{5000}{1004}\approx 4.9801$ — under 5, and closer than at $n=500$. ✓ The limit is $k=5$.

---

Example 5 — Cell E + F (unbalanced stages and register overhead)

We will need one total time and one per-cycle time here, so to avoid clashing with $T_{\text{seq}}$ (the total non-pipelined time), we name the single-cycle clock period $t_{\text{single}}$.

Steps.

1. Non-pipelined (single-cycle) period = whole instruction = sum of stages. $t_{\text{single}}=3+5+4+2=14\text{ ns}$ Why this step? With no latches, one clock does the entire journey; see Single-cycle vs Multi-cycle Datapath. This is a per-instruction period, not the total $T_{\text{seq}}$.

2. Pipelined clock = slowest stage + register overhead. Not the average — the whole pipe waddles at the pace of its slowest member. $t_{\text{clk}}=\max (3,5,4,2)+t_{\text{reg}}=5+1=6\text{ ns}$ Why this step? Every stage must fully finish inside one tick; the worst stage sets the tick.

3. Times. Non-pipelined total: $T_{\text{seq}}=n\cdot t_{\text{single}}=100\cdot 14=1400\text{ ns}$. Pipelined: $T_{\text{pipe}}=(k+n-1)t_{\text{clk}}=(4+100-1)\cdot 6=103\cdot 6=618\text{ ns}$. Why this step? Now $t$ is $t_{\text{clk}}=6$, not an idealised balanced value.

4. Speedup: $S=\frac{1400}{618}\approx 2.27$. Why this step? Ratio — far below the ceiling $4$ because the pipe is unbalanced and pays register overhead.

Recall Verify (Example 5)

$t_{\text{clk}}=6$; $T_{\text{pipe}}=103\cdot 6=618$; $T_{\text{seq}}=1400$; $S=1400/618\approx 2.265$. ✓

What the figure below shows (read it before moving on): four vertical bars, one per stage, with heights equal to the stage delays $3,5,4,2$ ns (each labelled). The tallest bar (orange, 5 ns) is the bottleneck. A red slab of height $t_{\text{reg}}=1$ ns sits on top of that tallest bar, and a dashed red line runs across the whole plot at height $t_{\text{clk}}=6$ ns — the clock period. Visually, the short bars (like the 2 ns one) leave empty space below the dashed line: that empty space is idle time, hardware sitting still because the whole pipe waits for the 5 ns stage.

---

Example 6 — Cell G (a stall / hazard adds bubbles)

Steps.

1. Ideal pipelined cycles (no stalls): $k+n-1=5+20-1=24$ cycles. Why this step? Start from the perfect world, then add penalties.

2. Add the stall bubbles. Each stall injects 1 extra cycle; 4 stalls ⇒ $+4$ cycles. $\text{cycles}=24+4=28$ Why this step? A bubble is a wasted tick where the pipe advances a "do-nothing" so the dependency resolves.

3. Times. $T_{\text{pipe}}=28\cdot 1=28\text{ ns}$. Non-pipelined: $T_{\text{seq}}=nkt=20\cdot 5\cdot 1=100\text{ ns}$. Why this step? Convert cycles to time with $t=1$ ns.

4. Effective speedup: $S=\frac{100}{28}\approx 3.57$. Why this step? Ratio. Compare to the stall-free value $100/24\approx 4.17$ — the hazards cost about $0.6\times$ of speedup.

Recall Verify (Example 6)

Stall-free cycles $=24$, with 4 stalls $=28$; $S=100/28\approx 3.571$; ideal-with-no-stall $S=100/24\approx 4.167$. ✓ Bubbles bite.

---

Example 7 — Cell H (word problem: instructions per second)

Before the numbers, one new word we will lean on:

Steps.

1. Ideal throughput = one instruction per cycle. With $t=0.5\text{ ns}$, that is $\frac{1\text{ instr}}{0.5\text{ ns}}=2\times 10^9\text{ instr/s}=2000\text{ MIPS}.$ Why this step? Throughput is 1 instr per tick in the ideal pipe; convert ticks to seconds.

2. Account for stalls via CPI. Each instruction costs $1$ cycle plus $\frac{1}{10}$ of a bubble cycle on average, so the effective $\text{CPI}=1+\frac{1}{10}=1.1\text{ cycles/instruction}.$ Why this step? CPI is exactly the tool for folding stalls into an average cost per instruction; ideal CPI is 1, stalls push it up.

3. Sustained throughput = one instruction per (CPI × clock period). $\frac{1}{\text{CPI}\cdot t}=\frac{1}{1.1\cdot 0.5\text{ ns}}=\frac{1}{0.55\text{ ns}}\approx 1.818\times 10^9\text{ instr/s}\approx 1818\text{ MIPS}.$ Why this step? More cycles per instruction ⇒ fewer instructions per second.

4. Compare: $\frac{1818}{2000}\approx 0.909$ — you keep about $90.9\%$ of ideal, losing $\approx 9.1\%$. Forecast confirmed. Why this step? Sanity check that the loss matches the $\frac{1}{11}\approx 9.1\%$ overhead of adding 0.1 cycle onto 1.1.

Recall Verify (Example 7)

Effective CPI $=1.1$; throughput $=1/(1.1\cdot 0.5\text{ns})\approx 1.818\times 10^9$ instr/s; fraction of ideal $=1/1.1\approx 0.909$. ✓

---

Example 8 — Cell I (exam twist: solve the formula backwards)

Steps.

1. For $n\to \infty$, Example 4 showed $S\to k$. So to get $S\ge 8$ ideally, you need $k\ge 8.$ Why this step? In the limit the ceiling is the stage count — invert it directly.

2. Reality check — why not $k=1000$? First define the two clock models so we can reconcile them:

   • In Example 5 the stages were given individually and were unbalanced, so the clock was set by the single worst stage: $t_{\text{clk}}=\max (\text{stage delay})+t_{\text{reg}}$.
   • Here we imagine instead taking one fixed lump of logic — call its total delay $W$ (the "combinational work" of the whole instruction, in ns) — and slicing it evenly into $k$ equal stages. Even slicing means each stage's delay is $W/k$, so the clock becomes $t_{\text{clk}}=\frac{W}{k}+t_{\text{reg}}.$ These are the same rule ($\max$ stage $+t_{\text{reg}}$); the second is just the ideal special case where every stage is equal to $W/k$, so the max equals $W/k$. Use the $\max$ form when stage delays are given; use the $W/k$ form when you are free to slice a total delay $W$ into $k$ balanced pieces. Why this step? We must express $t_{\text{clk}}$ in terms of $k$ to see what happens as $k$ grows.

3. Now watch $t_{\text{clk}}=\frac{W}{k}+t_{\text{reg}}$ as $k$ grows. The useful term $W/k$ shrinks toward $0$, but $t_{\text{reg}}$ is fixed. So the clock cannot fall below $t_{\text{reg}}$ no matter how many stages you add — beyond some $k$ the register overhead dominates and extra stages barely raise real speedup, while hazards/branch penalties grow with depth (see Branch Prediction and Superscalar and Out-of-Order Execution). Why this step? Answers the twist: the ideal $k=8$ is necessary, but deeper is not freely better.

4. Practical answer: the smallest $k\ge 8$ that keeps stages balanced, here $k=8$. Why this step? $k=8$ meets the target; $k=7$ gives a limiting speedup of only $7<8$.

Recall Verify (Example 8)

Ideal limit $S=k$, so $k\ge 8$ ⇒ smallest integer $k=8$; check $k=8$ gives limiting $S=8$. ✓ And $k=7$ gives only $7<8$. ✓

---

Coverage check

Recall Which example covered which matrix cell?

A → Ex 1 · B → Ex 2 · C → Ex 3 · D → Ex 4 · E,F → Ex 5 · G → Ex 6 · H → Ex 7 · I → Ex 8. Every cell hit.

Related depth: for why stalls happen and how forwarding removes some, jump to Pipeline Hazards (Data, Control, Structural) and Forwarding and Bypassing; for the fundamental limit on any speedup from a partial improvement, Amdahl's Law.