Skip to content
Tutorials Center
My learning

Topics

Lesson 64 of 67 ยท Practice and Interview

Pipeline Speedup, CPI and Exam-Style Calculations

Master pipeline arithmetic: speedup with unequal stages, throughput, CPI with load-use, branch and structural stalls, and pipeline depth trade-offs, with worked problems and Python checks.

Exams and interviews love pipeline questions because a handful of formulas cover most of them. The trick is to recognize which formula a problem wants and to avoid the usual slips: forgetting the latch delay, counting fill time wrongly, or mixing cycles with nanoseconds.

This lesson gives you a compact formula sheet and six worked problems, each checked with Python. It assumes you know pipelining, pipeline hazards and the performance equation. More mixed practice is in Practice: CPU, Pipeline, Cache and Virtual Memory.

The formula sheet

Let k be the number of stages, n the number of instructions, tp the pipelined clock period, and tn the time per instruction without pipelining.

Quantity Formula
Clock period of a pipeline tp = (slowest stage delay) + (latch delay)
Time for n instructions (no stalls) (k + n - 1) x tp
Time without pipelining n x tn where tn is the sum of stage delays
Speedup (n x tn) / ((k + n - 1) x tp)
Ideal speedup, equal stages, n large approaches k
Throughput 1 / tp (after the pipeline fills)
CPI with stalls 1 + (stall cycles per instruction)
Stall cycles per instruction sum of (frequency of event) x (penalty in cycles)
Execution time instruction count x CPI x clock period

Three reminders. First, the fill time is k - 1 cycles, so the first instruction finishes after k cycles and each later one one cycle after the previous. Second, latency of one instruction is k x tp, which is longer than without a pipeline, so pipelining improves only throughput. Third, when a problem gives stage delays that differ, the slowest stage sets the clock for all stages.

Problem 1: unequal stages

A 4-stage pipeline has stage delays 60, 50, 90 and 80 ns, and each pipeline register adds 10 ns. How long do 1,000 instructions take, and what is the speedup over the unpipelined design?

The clock is 90 + 10 = 100 ns. The pipelined time is (4 + 999) x 100 = 100,300 ns. The unpipelined time per instruction is 60 + 50 + 90 + 80 = 280 ns, so 1,000 instructions take 280,000 ns. Speedup is 280,000 / 100,300 = 2.79, well below the ideal 4, because the stages are unbalanced and the latches add delay.

Problem 2: equal stages and the fill penalty

A 6-stage pipeline with equal stages runs 200 instructions. Ignoring latch delay, the speedup is (n x k) / (k + n - 1) = 1200 / 205 = 5.85. With only 10 instructions it would be 60 / 15 = 4.0, which shows why short programs benefit less.

Problem 3: stalls from several sources

On a 5-stage pipeline, 30% of instructions are loads, and half of those are followed by an instruction that uses the loaded value (one bubble even with forwarding). 15% of instructions are branches, 70% of them taken, and a taken branch costs 3 cycles. What is the CPI, and the speedup over a non-pipelined machine with CPI 5 and the same clock?

Load-use stalls: 0.30 x 0.50 x 1 = 0.15. Branch stalls: 0.15 x 0.70 x 3 = 0.315. CPI = 1 + 0.15 + 0.315 = 1.465. Speedup = 5 / 1.465 = 3.41.

Problem 4: a structural hazard

A pipeline shares one memory port between instruction fetch and data access, so every load or store (35% of instructions) stalls the fetch of a later instruction by one cycle. CPI = 1 + 0.35 x 1 = 1.35. A split instruction/data cache removes the stall, so it is 1.35 / 1 = 1.35 times faster when the clock does not change.

Problem 5: pipeline depth versus CPI

A 5-stage design has a 0.9 ns clock and CPI 1.3. A deeper 10-stage design has a 0.5 ns clock but its longer penalties give CPI 2.4. Which one executes an instruction faster on average?

Time per instruction is CPI x clock. Shallow: 1.3 x 0.9 = 1.17 ns. Deep: 2.4 x 0.5 = 1.20 ns. The shallow pipeline wins by a small margin. Raising the clock rate alone does not guarantee speed: if CPI grows faster than the clock shrinks, performance drops. This is one reason clock speeds stopped climbing.

Problem 6: branch prediction accuracy

20% of instructions are branches, the predictor is correct 90% of the time and a misprediction costs 15 cycles. CPI = 1 + 0.20 x 0.10 x 15 = 1.30. Raising accuracy to 97% gives 1 + 0.2 x 0.03 x 15 = 1.09, a speedup of about 1.19.

Python Check all six problems

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common traps

  • Forgetting latch delay. The pipelined clock is slowest stage plus register delay, not just the slowest stage.
  • Using k instead of k + n - 1 cycles. The first instruction needs the whole pipeline; only the following ones complete one per cycle.
  • Adding frequencies without multiplying by penalty. Every stall source is frequency x penalty.
  • Comparing CPI alone. If clocks differ, compare CPI x period.
  • Counting stalls twice. A branch delay and a load-use delay are separate sources, but one bubble can serve both only if the instructions overlap in the way the question describes.

When a problem is long, write down each given number with its unit first, then pick the formula. Most mistakes come from choosing the wrong quantity, not from arithmetic.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A pipeline has stage delays of 40, 70, 50 and 60 ns with 5 ns of latch delay. What is its clock period?

    The slowest stage (70 ns) plus the latch delay (5 ns) sets the clock.
  2. 2. How many cycles does a 5-stage pipeline need to finish 50 instructions with no stalls?

    k + n - 1 = 5 + 50 - 1 = 54 cycles.
  3. 3. 25% of instructions are branches, 40% are taken, and each taken branch costs 2 cycles. What is the CPI?

    Stalls = 0.25 x 0.40 x 2 = 0.20, so CPI = 1.20.
  4. 4. Does pipelining reduce the latency of a single instruction?

    One instruction still passes through every stage, and latch delay adds to its time; the gain comes from overlapping many instructions.
  5. 5. A design has CPI 1.5 at 1.0 ns and another has CPI 2.0 at 0.7 ns. Which is faster per instruction?

    Time per instruction is CPI times the clock period: 1.5 ns versus 1.4 ns.

Summary

  • The clock of a pipeline is its slowest stage plus register delay; n instructions take k + n - 1 cycles.
  • Speedup compares total times, and approaches the number of stages only for balanced, stall-free pipelines and large n.
  • Each stall source adds frequency x penalty cycles to the base CPI of 1.
  • Compare designs by CPI x clock period, not by either number alone.
  • Pipelining improves throughput, not the latency of a single instruction.

Continue with Practice: CPU, Pipeline, Cache and Virtual Memory.