Pipelining Fundamentals: Speedup, Throughput, and Hazards

Pipelining is a technique in computer architecture that divides instruction execution into a sequence of stages so that multiple instructions overlap in time. The key performance ideas are latency (time for one instruction to complete) and throughput (rate at which instructions complete). Pipelining works best when stage delays are balanced and hazards are minimized.

A pipeline of $N$ stages has a pipeline fill period and a pipeline drain period: the first instruction completes after roughly $N$ cycles (one per stage), and afterward the pipeline can ideally complete one instruction per cycle (or per fixed interval), yielding high throughput. In ideal conditions (no hazards and full utilization), speedup improves because overlap increases the amount of useful work done per unit time.

To reason about performance, we typically use:

• Stage latency (must fit the clock period)
• CPI (higher CPI indicates stalls/hazards)
• Throughput
• Speedup

Pipeline hazards are situations that prevent the next instruction from advancing to the next stage on time. These hazards reduce throughput by forcing stalls or squashing/restarting work. The classic hazard categories are structural hazards, data hazards, and control hazards.

Mermaid overview of an ideal pipeline overlap:

Note: Precise formula forms (e.g., using CPI, cycle counts, or ideal speedup equations) depend on whether you assume fixed pipeline stage timing and whether you model start-up/steady-state behavior. The concepts of fill/drain, throughput, and hazards remain consistent.

Ideal throughput and speedup intuition

In a simple pipeline where each stage completes in one cycle and the CPU can issue a new instruction every cycle, the pipeline ideally achieves:

• After the pipeline is full: completes 1 instruction per cycle (throughput maximized).
• Overall completion time: depends on how many instructions you execute due to the initial fill and final drain effects.

We can characterize performance by separating startup from steady state:

• Pipeline fill takes about $N-1$ extra cycles before the first cycle where every stage is busy.
• After that, each additional instruction arrives with a new cycle’s worth of overlap.

This leads to the commonly taught qualitative model:

• With pipelining, the first instruction experiences latency similar to the whole non-pipelined execution.
• Subsequent instructions benefit from overlap, increasing throughput dramatically.

Pipeline speedup increases as:

• the number of pipeline stages $N$ grows (more opportunity for overlap),
• the workload has enough instructions to amortize fill/drain,
• hazards are rare so the pipeline runs close to full utilization.

Speedup vs throughput: even if speedup (for a finite program) looks limited by fill/drain, throughput (steady-state rate) can still be close to ideal once the pipeline is fully utilized.

Pipeline hazards: what they are and why they matter

A hazard occurs when an instruction cannot proceed to the next pipeline stage as planned.

In practice, hazards create two main effects:

1. Stalls / bubbles: inserted cycles where useful work cannot proceed.
2. Squashes / flushes: wrong-path instructions are cancelled when control flow is resolved.

Hazard categories

1. Structural hazards
   Example: two instructions require the same memory port in a cycle.

2. Data hazards
   Example dependency patterns:

   • RAW (Read After Write): a consumer needs a value produced by an earlier instruction that hasn’t written it back yet.
   • Mitigations include stalling until data is ready and forwarding/bypassing to supply results directly from intermediate pipeline stages.

3. Control hazards
   Example: the pipeline fetches instructions based on a prediction, but later determines the branch outcome was different. Mitigations include:

   • stalling until the branch condition is known,
   • branch prediction (speculate),
   • pipeline flushing when the speculation is wrong.

Speedup and throughput: connecting the ideas

To link everything quantitatively, a standard approach is to express performance using CPI and relate execution time to cycle counts.

A common framing:

• Execution time is proportional to $\\text{(cycles)} = \\text{CPI} \\times \\text{instruction count}$.
• Pipelining aims to reduce CPI toward its ideal value (often near 1 in an ideal pipeline), but hazards increase CPI by adding stalls/flush overhead.

So:

• Throughput increases when CPI decreases.
• Speedup comes from reduced total cycles compared with a non-pipelined design.

Pipeline hazards are the principal reason real CPI exceeds the ideal, turning theoretical speedup into smaller realized speedup.