Pipelining — Stages, Speedup, Throughput and Hazards (Structural, Data, Control) with Solved Numericals

Washing clothes: wash (30 min), dry (40 min), fold (20 min). Doing 4 loads one after another takes 6 hours. But you can start washing load 2 while load 1 dries — that's pipelining, and it's how every modern CPU executes several instructions at once.

1. The 5-stage pipeline

Each instruction still takes 5 cycles (latency unchanged), but once the pipeline is full, one instruction completes every cycle (throughput up to 5×).

2. The speedup formula

With k stages, n instructions, and each stage taking time t:

• Non-pipelined: n × k × t
• Pipelined: (k + n − 1) × t — k cycles for the first instruction, then one more per instruction
• Speedup = n·k / (k + n − 1) → approaches k as n grows

def speedup(k, n):
    return n * k / (k + n - 1)

for n in [1, 5, 100, 10_000]:
    print(f"k=5, n={n:6}: cycles pipelined = {5 + n - 1:6}, speedup = {speedup(5, n):.3f}")

k=5, n=     1: cycles pipelined =      5, speedup = 1.000
k=5, n=     5: cycles pipelined =      9, speedup = 2.778
k=5, n=   100: cycles pipelined =    104, speedup = 4.808
k=5, n= 10000: cycles pipelined =  10004, speedup = 4.998

3. Unequal stages and latch delay

Real stages don't take equal time. The clock must fit the slowest stage plus the pipeline register (latch) delay.

Example. Stage delays 150, 120, 160, 140, 130 ps; latch delay 10 ps; 1000 instructions.

stages = [150, 120, 160, 140, 130]
latch = 10
n = 1000

non_pipelined = n * sum(stages)
cycle = max(stages) + latch
pipelined = (len(stages) + n - 1) * cycle

print("clock cycle =", cycle, "ps")
print("non-pipelined:", non_pipelined, "ps | pipelined:", pipelined, "ps")
print(f"speedup = {non_pipelined / pipelined:.2f} (ideal would be {len(stages)})")

clock cycle = 170 ps
non-pipelined: 700000 ps | pipelined: 170680 ps
speedup = 4.10 (ideal would be 5)

Speedup is well below 5 because the stages are unbalanced and latches add delay — which is why designers try to balance stages.

4. Hazards: why pipelines stall

A hazard prevents the next instruction from running in its slot. Three kinds:

Structural hazard — fighting over hardware

Two instructions need the same unit in the same cycle — e.g. one memory for both instruction fetch and data access. Fix: duplicate resources (separate instruction and data caches — the Harvard idea from lesson 1).

Data hazard — waiting for a result

ADD R1, R2, R3     ; R1 = R2 + R3      (result written in WB, cycle 5)
SUB R4, R1, R5     ; needs R1 in ID/EX (cycle 3/4) — not ready yet!

Types: RAW (read after write — the real one in simple pipelines), WAR and WAW (matter in out-of-order CPUs).

Fixes:

• Stall (insert bubbles) until the value is written.
• Forwarding / bypassing — send the ALU result straight from the EX/MEM pipeline register to the next instruction's EX input. Removes most stalls.
• Load-use hazard: a value loaded from memory isn't available until after MEM, so even with forwarding the next instruction stalls 1 cycle. Compilers reorder instructions to fill that slot.

Control hazard — branches

After a branch, which instruction comes next isn't known until the branch is resolved (EX stage in our pipeline). Fixes:

• Stall until resolved (branch penalty).
• Branch prediction — guess (e.g. "loops usually repeat"), fetch along the guess, and flush if wrong. Modern predictors are right well over 90% of the time.
• Delayed branch — the instruction after the branch always executes (older RISC designs).

5. Effective CPI with stalls

Speedup = pipeline depth / (1 + stall cycles per instruction) (ideal CPI 1).

def effective_cpi(branch_freq, mispredict_rate, penalty, load_use_freq=0.0, load_stall=1):
    return 1 + branch_freq * mispredict_rate * penalty + load_use_freq * load_stall

no_pred = effective_cpi(0.20, 1.0, 2)                 # stall on every branch
predictor = effective_cpi(0.20, 0.10, 2)              # 90% accurate predictor
with_loads = effective_cpi(0.20, 0.10, 2, 0.15, 1)    # plus 15% load-use stalls

for name, cpi in [("always stall", no_pred), ("90% predictor", predictor), ("predictor + load-use", with_loads)]:
    print(f"{name:22} CPI = {cpi:.2f}  speedup over non-pipelined 5-stage = {5 / cpi:.2f}")

always stall           CPI = 1.40  speedup over non-pipelined 5-stage = 3.57
90% predictor          CPI = 1.04  speedup over non-pipelined 5-stage = 4.81
predictor + load-use   CPI = 1.19  speedup over non-pipelined 5-stage = 4.20

6. Beyond the basic pipeline

• Superscalar — multiple pipelines; issue 2–8 instructions per cycle.
• Out-of-order execution — run later independent instructions while earlier ones wait.
• Deeper pipelines allow higher clocks but bigger branch penalties.
• Multicore — several complete CPUs on one chip (parallelism at the thread level).

Common mistakes

• Using n·k cycles for the pipelined case (it's k + n − 1).
• Forgetting latch delay or using the average stage delay instead of the maximum.
• Assuming forwarding removes the load-use stall (it leaves 1 cycle).
• Saying pipelining reduces the latency of one instruction (it improves throughput).

Quick recap

• 5 stages: IF, ID, EX, MEM, WB; pipelining raises throughput, not single-instruction latency.
• Pipelined time = (k + n − 1) × cycle; speedup = nk/(k+n−1) → k.
• Cycle = slowest stage + latch delay.
• Hazards: structural (duplicate resources), data (stall, forwarding; load-use costs 1), control (stall, prediction, delayed branch).
• CPI = 1 + stall cycles per instruction.