Pipelining — 5-stage pipeline, each stage: Question bank

The symbols this page uses (define before you argue)

Before any trap, pin down every letter so no reveal ever surprises you.

Definition The five symbols

$k$ = the number of stages in the pipeline (IF, ID, EX, MEM, WB → so $k = 5$ here). One instruction must visit all $k$ of them.
$n$ = the number of instructions we are running through the pipe, one after another.
$t$ = the clock period: the time for one clock tick, i.e. the time one stage gets to do its work. Every stage advances once per tick.
$t_{reg}$ = pipeline-register overhead: the tiny extra time each latch between two stages needs (to safely capture and hold a value) before the next stage may use it.
$t_{clk}$ = the actual clock period a real pipeline must use. It is just $t$ made concrete: $t_{clk} = max (stage delays) + t_{reg}$ — the slowest stage plus the latch overhead. When stages are balanced and overhead is ignored, $t_{clk} = t$ .
$S$ = the speedup: how many times faster the pipelined machine finishes the same $n$ instructions than the non-pipelined one, i.e. $S = \frac{time without pipelining}{time with pipelining}$ .

Below, the figure turns these letters into a picture so you can see fill, steady state, and drain.

Figure — Pipelining — 5-stage pipeline, each stage

Formula Deriving the timing from the picture (WHAT, WHY, WHAT IT LOOKS LIKE)

Non-pipelined. Each instruction occupies all hardware for its whole life, so it takes $k$ ticks; $n$ of them run strictly one-after-another (no overlap): $T_{seq} = n k t$ Pipelined. Read the figure left to right. The first instruction still needs its full $k$ ticks to reach WB — that's the diagonal fill ramp (top-left triangle). But every instruction behind it is already climbing the pipe one stage behind, so once the first exits, a new instruction completes on every following tick. Instructions $2, 3, \dots, n$ therefore add just one tick each: $T_{pipe} = fill: 1st instr k t + one per tick after (n - 1) t = (k + n - 1) t$ Speedup is the ratio of those two times — that is the definition of $S$ , now made explicit: $S = \frac{T _{seq}}{T _{pipe}} = \frac{n k t}{( k + n - 1 ) t} = \frac{n k}{k + n - 1}$ The $t$ cancels because both machines tick at $t$ per stage — speedup is about overlap, not tick length. As $n \to \infty$ the " $- 1 + k$ " shrinks against $n$ and $S \to k$ .

True or false — justify

A stage is one of the $k$ steps (IF, ID, EX, MEM, WB) an instruction passes through; latency is the time from an instruction entering the pipe to it finishing; throughput is how many instructions complete per unit time. Keep those three apart and most traps disappear.

Pipelining makes each individual instruction run faster.

False. A single instruction still visits all

k

stages, so its latency is unchanged (often slightly worse from register overhead). Only throughput — completions per second — improves.

A 5-stage pipeline always delivers exactly 5× speedup.

False.

S = \frac{nk}{k + n - 1}

only approaches

k

n \to \infty

, and only with balanced stages and zero stalls. Real speedup is lower — see Pipeline Hazards (Data, Control, Structural).

If all stages are perfectly balanced and there are no hazards, throughput is one instruction per cycle.

True. After the pipe fills, a completed instruction exits every cycle, giving throughput

1/ t

where

t

is the clock period — the ideal steady state.

Adding more pipeline stages always increases performance.

False. Deeper pipelines shrink the clock period but add more register overhead

t_{reg}

per stage and worsen hazard penalties (branch misprediction flushes cost more stages). There is a sweet spot beyond which it hurts.

Pipeline registers are wasted hardware you could remove to save area.

False. Without latches the result of stage

i

would be clobbered when the next instruction enters stage

i

next cycle. They hold each instruction's per-stage state as it moves down the pipe.

The clock period of a pipeline equals the total instruction time divided by the number of stages.

False. It equals the slowest single stage delay plus register overhead,

t_{clk} = max (stage delays) + t_{reg}

— the max, not the average.

Doubling the number of instructions doubles the speedup.

False. Speedup is bounded above by

k

; as

n

grows,

S

climbs toward

k

but flattens. Doubling

n

from huge to huger barely moves it.

In steady state, all

k

stages are busy on

k

different instructions at once.

True. That overlap is the entire point —

k

instructions are "in flight," each in a different stage, so no hardware sits idle.

Spot the error

Each item states a piece of reasoning with a hidden flaw. Find it before revealing.

"Latency improves because the program finishes sooner, so each instruction is quicker."

The program finishes sooner because instructions overlap, not because any one sped up. Program time ↓ while per-instruction latency stays

\approx k

cycles — those are different quantities.

"Speedup for

n = 2

k = 5

is 5 because there are 5 stages."

Only

n = 2

instructions can't hide the 4 fill cycles. Actual

S = \frac{2 \cdot 5}{5 + 2 - 1} = \frac{10}{6} \approx 1.67

. Max speedup is a limit reached only for large

n

"We set the clock to the average stage delay so faster stages compensate for slower ones."

A fast stage cannot "finish early and help." Every stage must complete within one period, so the clock

t_{clk}

is governed by the slowest stage; the fast ones just wait.

"Since IF and WB both touch memory-like structures, one register file port is enough — no structural conflict."

IF fetches from instruction memory while WB writes the register file, and ID reads the register file simultaneously. Sharing a single port causes a structural hazard (see Pipeline Hazards (Data, Control, Structural)). Split ports / caches exist precisely to avoid this.

"With forwarding installed, we get the full 5× speedup on any program."

Forwarding and Bypassing removes most data-hazard stalls, but load-use hazards still cost a bubble and control hazards from branches still cause flushes. Speedup improves but stays below

k

"Non-pipelined CPI is 5 and pipelined CPI is 1, so the speedup is exactly 5 always."

Ideal pipelined CPI is 1 only in steady state with no stalls. Fill cycles, hazards, and branch penalties push effective CPI above 1 — see Clock Frequency and CPI.

"A single-cycle CPU has no pipeline registers, so it must have lower latency per instruction."

A single-cycle instruction's latency is one long clock (

\approx k \cdot t

) with no register overhead, so its latency can be comparable or lower — but its throughput is far worse. Compare via Single-cycle vs Multi-cycle Datapath.

Why questions

Why is the maximum speedup equal to the number of stages, not something larger?

In the best case the pipe completes exactly one instruction per cycle (throughput

1/ t

) versus

1/ (k t)

non-pipelined — a

k \times

ratio. You can't finish faster than one-per-cycle without going superscalar (Superscalar and Out-of-Order Execution).

Why do we bother balancing stage delays if the whole instruction time is fixed?

Because the clock period

t_{clk}

is set by the slowest stage. One bloated stage stretches every cycle for every instruction, so balancing minimizes the max stage delay and thus the period.

Why does a small

n

give disappointing speedup even with a perfect pipeline?

The first instruction still needs

k

cycles to fill the pipe. Those

k - 1

warm-up cycles are a fixed cost amortized over

n

; when

n

is small they dominate

T_{pipe} = (k + n - 1) t

Why can pipelining make per-instruction latency slightly worse than non-pipelined?

Each stage boundary inserts a pipeline register with setup/propagation delay

t_{reg}

. Summed across

k

boundaries, that overhead adds to the instruction's total journey time.

Why does branch prediction matter for keeping the pipeline full?

A branch's outcome isn't known until a later stage, but IF must keep fetching now. Guessing wrong means discarding wrongly-fetched instructions (a flush). Good Branch Prediction keeps the fetch stream correct and the pipe fed.

Why doesn't Amdahl's Law contradict the

k \times

speedup claim?

Amdahl's Law limits overall program speedup when only part of the work is accelerated; the

k \times

figure is the ideal speedup of the pipelineable instruction stream itself, assuming no unpipelinable serial bottleneck.

Why is throughput the right metric to advertise a pipeline, not latency?

Pipelines are designed to overlap work, which raises completions-per-second without shortening any single job — exactly what throughput measures. Advertising latency would hide the real benefit.

Edge cases

n = 1

: what is the speedup?

S = \frac{1 \cdot k}{k + 1 - 1} = \frac{k}{k} = 1

. One lone instruction gets no overlap partner — pipelining gives zero benefit, and with register overhead it's marginally slower.

k = 1

(a "one-stage pipeline"): speedup?

S = \frac{n \cdot 1}{1 + n - 1} = 1

. With a single stage there is nothing to overlap; it's just the non-pipelined machine.

One stage is far slower than the rest (e.g. MEM =

4 t

, others

= t

): what happens to the clock?

The clock period stretches to that slowest stage (

t_{clk} \approx 4 t

). Throughput collapses toward one instruction per

4 t

— the bottleneck stage sets the pace regardless of how fast the others are.

Every instruction stalls one cycle (a bubble each): effect on steady-state throughput?

Effective CPI rises from 1 to 2, halving throughput. Stalls insert idle "bubble" cycles where no instruction completes even though the pipe is running.

n \to \infty

with balanced stages and no hazards: throughput and speedup?

Throughput

\to 1/ t

(one per cycle) and speedup

\to k

. The fill cycles become negligible and the ideal limit is reached.

A program is one huge unbreakable instruction (can't be split into stages): can pipelining help it?

No. Pipelining exploits overlap between the stages of consecutive instructions; a single indivisible unit offers no stages to overlap and no successor to feed in behind it.

Two consecutive instructions where the second needs the first's result immediately: does the pipe still complete one-per-cycle?

Not without help — that's a data hazard. Either a stall bubble is inserted (throughput dips) or Forwarding and Bypassing routes the result early to preserve the one-per-cycle rate.

Connections

Pipeline Hazards (Data, Control, Structural)
Forwarding and Bypassing
Branch Prediction
Single-cycle vs Multi-cycle Datapath
Clock Frequency and CPI
Amdahl's Law
Superscalar and Out-of-Order Execution