COMPUTER ORGANIZATION & ARCHITECTURE / 7. PIPELINING
Pipelining — Instruction-Level Parallelism
Overlapping instruction execution — from 1 to 5 instructions per cycle
EXPLANATION
Pipelining is the single most important performance technique in CPU design. Instead of completing one instruction before starting the next, you overlap multiple instructions like an assembly line. The 5-stage RISC pipeline (classic): - IF — Instruction Fetch: read instruction from memory at PC - ID — Instruction Decode: decode opcode, read registers, extend immediates - EX — Execute: ALU performs operation, compute branch/memory address - MEM — Memory Access: read or write data memory (load/store only) - WB — Write Back: write result to register file Without pipelining: each instruction takes 5 cycles. 1000 instructions = 5000 cycles. With pipelining: after filling the pipeline, one instruction completes every cycle. 1000 instructions ≈ 1004 cycles (5 cycle fill + 999 cycles). Throughput = 5× better. Pipeline Hazards — three types of problems: 1. Structural Hazard: two instructions need the same hardware resource in the same cycle. Example: only one memory port, but IF and MEM both need memory. Solution: separate instruction cache and data cache (Harvard architecture). Modern CPUs do this. 2. Data Hazard: instruction needs result from previous instruction not yet written back. Example: ADD R1, R2, R3 then SUB R4, R1, R5 — R1 isn't written until WB, but SUB needs it in ID. Types: • RAW (Read After Write): most common, also called "true dependency" • WAR (Write After Read): happens in out-of-order execution • WAW (Write After Write): also out-of-order Solutions: • Stalling (bubbles): insert NOPs, waste cycles. Simple but slow. • Forwarding (bypassing): route result from EX/MEM stage output directly back to EX input. Eliminates most RAW stalls without wasting cycles. Used in all real CPUs. • Out-of-order execution: reorder instructions to avoid hazards. Complex but powerful. 3. Control Hazard: branch instructions — we don't know next PC until EX stage. Problem: we've already fetched 2 more instructions into the pipeline. Wrong instructions! Solutions: • Flush: discard the 2 wrongly-fetched instructions (2 cycle penalty). • Branch prediction: guess which way the branch goes, speculatively execute. Modern CPUs predict with ~95%+ accuracy. Misprediction penalty: 15-20 cycles (emptying the deep pipeline). • Branch Delay Slot (MIPS): always execute the instruction after the branch (programmer fills it or assembler inserts NOP). Exposes pipeline to software. Branch Prediction — how CPUs guess: - Static prediction: always predict taken, or always not taken - 1-bit predictor: remember last outcome - 2-bit saturating counter: bimodal predictor — needs 2 misses to change prediction - Tournament predictor: choose between local and global predictors - Modern: neural branch predictors with 95%+ accuracy
DIAGRAM
WITHOUT PIPELINING (5 cycles per instruction):
Cycle: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Instr1: IF ID EX MM WB
Instr2: IF ID EX MM WB
Instr3: IF ID EX MM WB
3 instructions = 15 cycles
WITH PIPELINING (1 instruction per cycle after fill):
Cycle: 1 2 3 4 5 6 7 8 9
Instr1: IF ID EX MM WB
Instr2: IF ID EX MM WB
Instr3: IF ID EX MM WB
Instr4: IF ID EX MM WB
Instr5: IF ID EX MM WB
5 instructions = 9 cycles (vs 25 without)
DATA HAZARD + FORWARDING:
ADD R1, R2, R3 IF ID EX→─┐ MM WB
SUB R4, R1, R5 IF ID ↑EX MM WB
└─ forwarded result (no stall!)
BRANCH MISPREDICTION (15-cycle penalty on modern CPUs):
BEQ R1, R2, target IF ID EX ← branch resolved here
wrong_instr1: IF ID ← FLUSHED (wasted)
wrong_instr2: IF ← FLUSHED (wasted)
correct_instr: IF ID EX MM WBCODE