Pipelining & Hazards

Pipelining — The Assembly Line of CPUs

Analogy: A car factory with 5 workstations. Without pipelining, car 2 can only start after car 1 is 100% complete. With pipelining, as soon as car 1 moves from station 1 to station 2, car 2 enters station 1. All stations work simultaneously!

Classic 5-Stage MIPS Pipeline

    Stage        │ What happens
─────────────────┼──────────────────────────────────────────
IF  (Fetch)      │ Fetch instruction from memory, PC = PC+4
ID  (Decode)     │ Decode instruction, read registers
EX  (Execute)    │ ALU operation or address calculation
MEM (Memory)     │ Read/write data memory
WB  (Writeback)  │ Write result back to register

Pipeline in action (5 instructions):

Time:    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

All 5 stages busy from time 5 onward — throughput = 1 instruction/cycle!

Pipeline Performance

Non-pipelined: n instructions × k cycles each = n×k cycles total

Pipelined:     (n + k - 1) × T_clock
  (k-1 cycles to fill the pipeline, then 1 instruction per cycle)

Speedup = (n×k) / (n+k-1)  ≈  k  for large n

Example: 1000 instructions, 5-stage pipeline
  Non-pipelined: 1000 × 5 = 5000 cycles
  Pipelined:     1000 + 4 = 1004 cycles
  Speedup ≈ 5×

Ideal CPI = 1
With stalls: CPI = 1 + average_stalls_per_instruction

Pipeline Hazards — Things That Break the Flow

1. Structural Hazard

Two instructions need the SAME hardware at the same time.

Example: If only ONE memory (not separate I-cache and D-cache):
  I1 in MEM stage (reading data from memory)
  I4 in IF stage  (fetching instruction from memory)
  → Both need memory simultaneously!

Solution: Harvard architecture — SEPARATE instruction memory (I-cache) and
          data memory (D-cache). Modern CPUs all do this.

2. Data Hazard — RAW (Read After Write)

Most common hazard. Instruction needs a value that a previous instruction has not yet written.

ADD R1, R2, R3    ; writes R1 in WB stage (cycle 5)
SUB R4, R1, R5    ; reads R1 in ID stage (cycle 3) ← WRONG R1!

Timeline:
         IF  ID  EX  MEM WB
ADD R1:  1   2   3   4   5    ← R1 ready at WB (cycle 5)
SUB R4:  2   3   4   5   6    ← R1 read at ID (cycle 3) ← uses STALE R1!

Solution 1: Stalling (inserting bubbles)

ADD R1:  IF  ID  EX  MEM WB
NOP:         IF  ID  EX  MEM WB   ← wait 2 cycles
NOP:             IF  ID  EX  MEM WB
SUB R4:              IF  ID  EX  MEM WB ← now gets correct R1

Solution 2: Forwarding (Bypassing) — preferred!

Forward the result from EX/MEM output DIRECTLY to the next instruction's EX input:

ADD R1:  IF  ID  EX → forward R1 here!
SUB R4:      IF  ID  EX ← receives forwarded R1

No stall needed! Hardware adds extra data paths.

Load-Use Hazard — The One That Even Forwarding Cannot Fix:

LW  R1, 0(R2)   ; R1 available only after MEM stage
ADD R3, R1, R4  ; needs R1 at EX stage — 1 cycle TOO EARLY!

LW:   IF  ID  EX  MEM  WB
ADD:      IF  ID  --- EX   MEM  WB  ← 1 stall unavoidable!
              ↑
         1 bubble inserted

3. Control Hazard (Branch Hazard)

We do not know where to fetch the next instruction until the branch is resolved.

BEQ R1, R2, TARGET   ; is branch taken or not?
ADD R3, ...          ; fetched, but may be wrong if branch taken!

5-stage pipeline: branch resolved at end of ID stage → 1-cycle penalty
Some pipelines: branch at EX → 2-cycle penalty

Solutions:

1. Always predict NOT TAKEN: continue fetching sequentially
   On wrong prediction: flush the fetched instructions

2. Branch Prediction (dynamic):
   1-bit predictor: remember last outcome
   2-bit saturating counter:
     00 (strongly not-taken) → 01 → 11 (strongly taken) → 10
     More stable — one wrong prediction does not immediately flip prediction

3. Delayed Branching:
   Always execute the N instructions after branch (delay slots)
   Fill delay slots with useful work (instructions that run regardless of branch)
   MIPS uses 1 delay slot

Speedup With Hazards

CPI = 1 + stall_cycles_per_instruction

Stall sources:
  Data hazard stalls: fraction_RAW × stalls_per_RAW
  Control hazard stalls: branch_fraction × branch_penalty
  Load-use stalls: load_use_fraction × 1

Example:
  30% loads, 20% branches (1-cycle penalty), 10% load-use
  CPI = 1 + 0.10×1 + 0.20×1 = 1.3
  Speedup vs non-pipelined 5-stage = 5/1.3 ≈ 3.8×

Quick Check

Q1. 5-stage pipeline. Following sequence: LW R1, 0(R2); ADD R3, R1, R4. How many stall cycles? Answer: 1 stall cycle — Load-Use hazard. The loaded value is ready after MEM stage, but ADD needs it at EX, which is one cycle too early even with forwarding.

Q2. What is the difference between structural and data hazards? Answer: Structural hazard = resource conflict (two instructions want the same hardware). Data hazard = data dependency (one instruction needs the output of a previous instruction that has not finished yet).

Q3. Why does the 2-bit saturating counter predict better than 1-bit? Answer: One wrong prediction does not immediately flip the prediction. The counter must be wrong TWICE consecutively to change prediction. This handles occasional anomalies (like branch not taken once) without changing a stable prediction.

Key Points