Pipelining

What Pipelining Is

Pipelining overlaps the execution of multiple instructions by dividing the datapath into stages, each completing in one clock cycle. Like an assembly line: a new instruction enters the pipeline every cycle (ideally).

Throughput gain: an n-stage pipeline can process up to n instructions simultaneously, approaching n× speedup (ignoring hazards and fill/drain time).

Classic 5-Stage RISC Pipeline

Pipeline Diagram (no hazards)

Cycle:       1    2    3    4    5    6    7    8    9
I1:         IF   ID   EX  MEM   WB
I2:              IF   ID   EX  MEM   WB
I3:                   IF   ID   EX  MEM   WB
I4:                        IF   ID   EX  MEM   WB
I5:                             IF   ID   EX  MEM   WB

At cycle 5 all five stages are busy simultaneously.

Pipeline Hazards

Structural Hazard

Two instructions need the same hardware resource at the same time.

• Classic example: single memory for instructions and data (unified cache) — IF and MEM conflict.
• Solution: separate I-cache and D-cache (Harvard-style split at L1).

Data Hazard (RAW — Read After Write)

An instruction reads a register that a previous instruction has not yet written.

ADD r1, r2, r3    # writes r1 in WB (cycle 5)
SUB r4, r1, r5    # reads r1 in ID (cycle 3) — stale!

Solutions:

Forwarding paths that cover most RAW hazards:

• EX/MEM → EX input (1-cycle lag)
• MEM/WB → EX input (2-cycle lag)
• MEM/WB → MEM input (load-use with intermediate instruction)

Load-Use hazard — unavoidable 1-cycle stall even with forwarding:

LW  r1, 0(r2)     # r1 not ready until end of MEM
ADD r3, r1, r4    # needs r1 at start of EX → 1 stall

Cycle:       1    2    3    4    5    6    7
LW:         IF   ID   EX  MEM   WB
ADD:             IF   ID  stall  EX  MEM   WB

Control Hazard (Branch)

The pipeline doesn't know the next PC until the branch resolves.

Without prediction (stall until branch resolves at EX): - 1–3 wasted cycles per branch depending on when branch is resolved

Branch resolution stage and penalty:

Solutions:

Branch Prediction Detail

1-Bit Predictor (last outcome, per branch)

On taken: state ← 1. On not-taken: state ← 0.

Bimodal Predictor (2-bit saturating counter)

States: Strongly Not Taken (00) ↔ Weakly Not Taken (01) ↔ Weakly Taken (10) ↔ Strongly Taken (11)
Predict Taken if state ≥ 2.

A single mispredict no longer flips the prediction — tolerates one anomalous outcome.

Two-Level / Correlating Predictor

Uses a global history register (GHR) of the last k branch outcomes, indexing a table of 2-bit counters. Correlation: if (aa) if (bb) — knowing aa's outcome predicts bb's.

TAGE (Tagged Geometric History Lengths)

Modern CPUs (Intel, AMD). Multiple tables with geometrically increasing history lengths; tags distinguish conflicting entries. Achieves ~96–99% accuracy.

Pipeline CPI Formula

CPI = Ideal CPI + Stall cycles per instruction

Stall sources:

Example: - Ideal CPI = 1, branch freq = 15%, miss rate = 10%, penalty = 15 cycles - Stalls = 0.15 × 0.10 × 15 = 0.225 cycles/instr - Effective CPI = 1 + 0.225 = 1.225

Deeper Pipelines

Modern high-performance CPUs use 14–22+ stages to allow higher clock frequencies. Each stage does less work → shorter critical path → higher fmax. Trade-off: branch misprediction penalty grows proportionally.

Superscalar Pipelines

Issue multiple instructions per cycle (issue width = n):

• In-order superscalar: issue 2–4 instructions/cycle, all must be hazard-free
• Out-of-order (OOO): dynamic scheduling; instructions execute as operands are ready, not in program order; results committed in order via Reorder Buffer (ROB)

VLIW (Very Long Instruction Word)

Compiler statically schedules multiple operations into one wide instruction word. Used in DSPs, Intel Itanium (IA-64). Relies entirely on compiler to find ILP; no OOO hardware needed but binary compatibility suffers when execution units change.