Pipeline Conflicts (Hazards) and Remedies

Pipeline ideally gives 1 instruction per cycle, but dependencies cause hazards that stall/flush pipeline.

1. Structural Hazards (Resource Conflicts)

• Cause: Two stages need same hardware same cycle. e.g., single memory for IF and MEM stage; single ALU; register file with one write port but two instructions need write.
• Example: 4-stage pipeline with IF and MEM sharing memory -> IF of I4 conflicts with MEM of I1.
• Solutions:
  • Separate Instruction and Data caches (Harvard) / L1 split - simultaneous IF+MEM.
  • Multiple functional units, pipelined units, extra ports on register file.
  • Stall (bubble) - hardware interlock delays one instruction.

2. Data Hazards (Data Dependency)

• RAW - Read After Write (True): ADD R1,R2,R3 ; SUB R4,R1,R5 - second needs R1 before first writes. Classic.
  • Sub-types: distance 1,2 hazards in pipeline.
• WAR - Write After Read and WAW - Write After Write (false dependencies) - occur in OOO / superscalar pipelines due to register reuse.
• Effects: Wrong operand value if pipeline forwards unupdated register.
• Solutions:
  • Data Forwarding / Bypassing: Directly route ALU output to next instruction's ALU input via forwarding path (EX->EX, MEM->EX) - avoids stall for most RAW.
  • Stall / Pipeline Interlock + NOP injection: Compiler/hardware inserts bubble when forwarding insufficient (e.g., Load-Use hazard: LW R1,0(R2) ; ADD R3,R1,R4 - needs one stall because data available after MEM).
  • Register Renaming: Remove WAR/WAW by mapping to physical registers (Tomasulo).
  • Compiler Scheduling: Reorder independent instructions between dependent pair: LW R1; ... independent ... ; USE R1
  • Out-of-Order Execution + Scoreboarding: Execute independent instructions while dependent waits in reservation station.

3. Control Hazards (Branch Hazards)

• Cause: Pipeline doesn't know next PC after Branch/Jump until decode/execute stage. Fetches wrong path.
• Example: BEQ R1,R2, Label - 2-3 instructions after branch already fetched before condition resolved.
• Penalties: Flush 1-3 cycles (branch penalty) ~10-20% performance loss if ~15% branches.
• Solutions:
  • Stall + Flush: On branch detection, freeze IF/ID, flush wrong path once target known (simple, slow).
  • Branch Prediction: Predict taken/not-taken.
    • Static: Predict not-taken or compiler hint.
    • Dynamic: 1-bit / 2-bit saturating counter, Correlated (Gshare), BTB (Branch Target Buffer) to store target. Accuracy 90-95% -> penalty only on mispredict.
  • Delayed Branch (Branch Delay Slot): Architecturally fill slot after branch with useful independent instruction - used in MIPS.
  • Predicated Execution: Convert branch to conditional move CMOV -> no flush.
  • Speculative Execution: Execute predicted path speculatively with ROB, rollback on mispredict.
  • Loop Buffer / Branch Target Cache: Cache branch targets.

Summary Table

Hazard	Cause	Detection	Remedy	Cost
Structural	Resource sharing	Scheduler	Duplicate resources, split cache	Hardware cost
Data RAW	Register dependency	Comparator on RD vs RS	Forwarding + stall if load-use	1 bubble if not forwarded
Control	PC change	Branch logic	Predict, delayed branch, flush	1-3 cycles mispredict penalty

Overall techniques to keep pipeline busy: Forwarding (data), Prediction + Speculation (control), Superscalar OOO + Renaming.

Ideal CPI =1, actual CPI =1 + stall cycles per instruction. With forwarding+prediction CPI ~1.1-1.3 instead of ~1.6 without.