Pipeline timing latency and throughput
Goals and assumptions
Compute pipeline clock period, fill/drain cost, finite-workload speedup and steady-state throughput. Prerequisites: CPU time/CPI lesson and datapath lesson. Hazards are introduced only as a specified stall count; their causes are taught next.
Unless changed, the pipeline is scalar, in order, initially empty, with k stages and one cycle per stage. It can admit at most one instruction each cycle. Instructions traverse all stages, resources do not conflict, and there are no data/control stalls. Stage delays d_i are combinational delays; pipeline-register overhead h includes clock-to-Q, setup and any clock allowance specified by the problem. This h is paid in the clock-period bound once per stage traversal, not k times in one cycle.
1. Period: the slowest stage sets the pace
The pipeline period is τ=max(d_i)+h. Faster stages wait until the next clock edge; their spare time does not automatically transfer to a slower stage. First-instruction latency is kτ. With no stalls, after filling, one result completes each τ, giving throughput 1/τ. Latency and throughput are different: an individual instruction may take longer while a long instruction stream finishes sooner.
Worked example: four stage delays 100, 160, 120 and 140 ps with h=20 ps give τ=180 ps. A single instruction takes 4×180=720 ps. Ideal steady throughput is one instruction/180 ps≈5.556 billion instructions/s. A separately specified unpipelined design using the serial sum, with no additional overhead, takes 520 ps per instruction; thus its individual instruction is faster than the pipeline's 720 ps latency.
2. Derive n+k−1 rather than guessing
The first instruction finishes at the end of cycle k. Instruction 2 finishes at k+1; instruction n at k+n−1. Hence T_pipe=(n+k−1)τ for n≥1. The k−1 extra cycles include the boundary effect of filling/draining; do not add another k−1 after already using this formula. This is a finite isolated batch, not a continuous pipeline measured only after warm-up.
Worked example: n=10 in the four-stage example needs 13 cycles, or 2340 ps. The unpipelined comparator takes 10×520=5200 ps. Speedup=5200/2340≈2.222. For n=1 speedup=520/720<1. As n grows, speedup approaches 520/180≈2.889, not four. Unbalanced stages and register overhead prevent the ideal stage-count limit.
For equal stage delays d, zero overhead and a serial unpipelined time kd, speedup is nk/(n+k−1), tending to k only for a long stream. State the comparator: if its overhead differs, use its actual given time rather than silently kτ.
3. Stalls, CPI and useful completions
If a problem supplies S additional non-overlapping lost cycles for the whole batch, total cycles=n+k−1+S. An inserted bubble does no useful instruction work. Do not count it as a completed program instruction. Effective finite-batch CPI is (n+k−1+S)/n. In a long stream where boundary cost is negligible, CPI≈1+S/n. These equations assume stall accounting has already handled any overlapping causes.
Worked example: a five-stage pipeline runs 40 useful instructions with 6 added stall cycles, period 2 ns. Total cycles=40+4+6=50; time=100 ns; finite CPI=1.25. The steady-state estimate 1+6/40=1.15 omits four boundary cycles and should not be presented as this batch's exact CPI.
4. Deeper is not automatically faster
Consider delays [100,160,120,140] ps and h=20 ps again. Split the 160 ps stage into two 80 ps stages, preserving dependencies. The new maximum is 140 ps, new τ=160 ps, and depth k=5. For n=10, time=14×160=2240 ps, a modest improvement over 2340 ps. For n=1, latency becomes 800 ps, worse than 720 ps. Splitting the 100 ps stage instead leaves the bottleneck 160 ps unchanged: τ remains 180 ps while k increases, worsening finite-batch time. Real designs may also change h and branch penalties.
Common mistakes and a solve-first checklist
Write k, n, stage delays, h, and exactly which extra cycles are counted. Compute period before multiplying cycles. Compare useful work against the stated nonpipelined baseline. Do not equate pipeline depth with speedup, first-result latency with completion interval, or program instruction count with instruction-plus-bubble count. No superscalar or out-of-order claim is implied by this scalar model.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Stage delays are 80,120,100 ps; register overhead is 10 ps. Pipeline period?
A. 110 ps B. 120 ps C. 130 ps D. 330 ps
Answer: C
A: An average does not cover the slowest stage.
B: Register overhead is missing.
C: max(80,120,100)+10=130 ps.
D: The pipeline does not traverse all stages combinationally in one cycle.
P02. An initially empty five-stage scalar pipeline completes 12 instructions without stalls in how many cycles?
A. 12 B. 16 C. 17 D. 60
Answer: B
A: This omits four boundary cycles.
B: 12+5−1=16.
C: Adding all five rather than four extra cycles is an off-by-one error.
D: 60 is non-overlapped five-cycle execution.
P03. A four-stage ideal scalar pipeline has period 3 ns. First-instruction latency and steady completion interval are:
A. 3 ns, 3 ns B. 12 ns, 12 ns C. 12 ns, 3 ns D. 3 ns, 12 ns
Answer: C
A: The first instruction traverses four stages.
B: 12 ns is latency, not steady interval.
C: Latency=4×3=12 ns; one completion every 3 ns after filling.
D: These quantities are reversed.
P04. A five-stage pipeline processes 20 useful instructions with 3 additional non-overlapping stall cycles. Exact batch CPI?
A. 1.15 B. 1.20 C. 1.35 D. 1.40
Answer: C
A: This ignores fill/drain boundary cost.
B: This includes boundary cost but ignores stalls.
C: Cycles=20+4+3=27; CPI=27/20=1.35.
D: This incorrectly adds five boundary cycles instead of four.
P05. A comparator takes 600 ps/instruction. A three-stage pipeline has period 250 ps. For 8 instructions without stalls, speedup is:
A. 3 B. 2.4 C. 1.92 D. 0.8
Answer: C
A: Stage count is not finite-workload speedup.
B: 2.4 is the long-stream limit, not the eight-instruction result.
C: Old=4800 ps; new=(8+2)×250=2500 ps; ratio=1.92.
D: The correct time ratio is 4800/2500.
P06. A stage that is not the bottleneck is split into two; overhead and the bottleneck delay are unchanged. With no stalls, what happens to a fixed finite batch?
A. It always halves execution time B. Period stays the same and total cycles increase by one C. Period doubles D. Total cycles decrease by one
Answer: B
A: The bottleneck still determines period.
B: Depth grows by one, so n+k−1 grows by one; period is unchanged.
C: Maximum stage delay and overhead are unchanged.
D: Adding a stage adds a boundary cycle.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire COA syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in