Neural Sync Active
Pipelining — Datapath, Hazards, and Forwarding
Registry Synced
Pipelining — Datapath, Hazards, and Forwarding
763 words
4 min read
Reading compass
Now · 🎯 Learning Objectives
Pipelining — Datapath, Hazards, and Forwarding
🎯 Learning Objectives
- Explain the 5-stage MIPS pipeline
- Identify and resolve data hazards via forwarding
- Handle control hazards with branch prediction
- Calculate pipeline performance (CPI, speedup)
1. 5-Stage MIPS Pipeline
| Stage | Name | What Happens |
|---|---|---|
| IF | Instruction Fetch | Fetch instruction from memory |
| ID | Instruction Decode | Read registers, decode instruction |
| EX | Execute | ALU operation, address calculation |
| MEM | Memory Access | Load/store data memory |
| WB | Write Back | Write result to register |
(Diagram)
2. Pipeline Performance
Ideal speedup: 5× (for 5-stage pipeline).
Actual CPI: > 1 due to hazards.
Amdahl's Law: Speedup = 1 / ((1 - f) + f/n) where f = fraction parallelizable, n = stages.
3. Data Hazards
3.1 Read After Write (RAW)
assemblyadd $t0, $t1, $t2 # WB writes $t0 sub $t3, $t0, $t4 # ID reads $t0 (before add writes!)
Without forwarding:
| Cycle | IF | ID | EX | MEM | WB |
|---|---|---|---|---|---|
| 1 | add | — | — | — | — |
| 2 | sub | add | — | — | — |
| 3 | _ | sub | add | — | — |
| 4 | _ | _ | sub | add | — |
| 5 | _ | _ | _ | sub | add |
| 6 | _ | _ | _ | _ | sub |
Problem: Sub reads t0incycle3,butaddwritest0 in cycle 5 → sub gets old value.
3.2 Forwarding (Bypassing)
Forward result from EX/MEM or MEM/WB pipeline register back to EX input.
| Cycle | IF | ID | EX | MEM | WB |
|---|---|---|---|---|---|
| 1 | add | — | — | — | — |
| 2 | sub | add | — | — | — |
| 3 | nop? | sub | add ← forward here! | — | — |
| Wait — with forwarding: sub's EX in cycle 3 gets add's result from MEM (cycle 4) or EX output (cycle 3). |
Actually: add's result is available at end of EX (cycle 3). Sub's EX is in cycle 3. Forward the result directly: sub gets $t0 from add's EX output without waiting for WB.
3.3 Load-Use Hazard (1 Stall)
assemblylw $t0, 0($s1) # MEM reads memory in cycle 4 add $t3, $t0, $t4 # EX needs $t0 in cycle 3 → must stall 1 cycle
Solution: Insert one bubble (stall), then forward from MEM to EX.
4. Control Hazards
4.1 Branch Hazard
assemblybeq $t0, $t1, target # Branch outcome known in EX (cycle 3) add $t3, $t4, $t5 # Fetched but might be wrong!
4.2 Branch Prediction
| Strategy | Accuracy | Cost |
|---|---|---|
| Always not taken | ~60% | 0 stall (if correct), 1 stall (if wrong) |
| Always taken | ~70% | 0/1 stall |
| 2-bit saturating counter | ~90% | 0/1 stall |
| Global history | ~95% | 1-2 stalls |
| Tournament | ~97% | 1-2 stalls |
5. Pipeline Performance Calculation
Example: 20% loads (1 stall each), 15% branches (1 stall each), 10% no forwarding needed
CPI_ideal = 1.0, Stalls = 0.20 × 1 + 0.15 × 1 = 0.35
CPI_actual = 1.0 + 0.35 = 1.35
Speedup over non-pipelined (CPI=5): 5/1.35 = 3.7× (vs ideal 5×)
6. Common Pitfalls
Pitfall: Load-Use Hazard Detection
The mistake: Forgetting that the LOAD instruction's result is only available after MEM stage.
Correct approach: A load-use hazard requires a 1-cycle stall (insert bubble) because the loaded value is available at the end of MEM, not EX.
7. Key Concepts Reference
| Hazard Type | Cause | Resolution |
|---|---|---|
| RAW (data) | Instruction reads register before previous writes | Forwarding + stalling |
| WAW (data) | Out-of-order write (rare in 5-stage) | In-order pipeline avoids |
| WAR (data) | Read before write (not in 5-stage) | Not possible with in-order |
| Control | Branch changes PC | Branch prediction |
8. 📝 Practice Questions
Q1: Identify hazards: lw t0,0(s1); add t1,t0, t2;subt3, t1,t0Answer:
- lw→add: load-use hazard on $t0 (1 stall + forward)
- add→sub: RAW hazard on $t1 (forward from EX/MEM)
- lw→sub: RAW hazard on $t0 (forward from MEM/WB) Total: 1 stall + 2 forwarding paths. Q2: Calculate CPI if 25% loads (1 stall), 20% branches (2 stalls without prediction), others 1 cycle.
Answer: CPI = 1 + 0.25×1 + 0.20×2 = 1 + 0.25 + 0.40 = 1.65. Speedup over non-pipelined (ideal CPI=5 if 5 stages but we'd use CPI=5 for 5-stage unpipelined): 5/1.65 = 3.03×. Q3: Why can't all data hazards be solved by forwarding alone?Answer: Load-use hazards require A stall because the data from lw is available only after MEM (end of cycle 4), but the dependent instruction needs it in EX (start of cycle 3). Forwarding cannot go backward in time — we must stall one cycle to align the data availability with the consuming stage. For ALU-ALU RAW hazards (add followed by sub), forwarding works without stalls because result is available at end of EX, which is when the next instruction's EX begins. Q4: A branch that's taken 90% of the time. What's accuracy of "always taken" predictor?Answer: 90% accuracy (matches the taken frequency). "Always not taken" would be 10% accurate. A 2-bit saturating counter would reach ~95%+ because it learns the pattern quickly.
9. 🔗 Cross-References
- Week 6 - Processor Design: Datapath stages
- Week 8 - ISA: Instruction types
- BSCS4022 (OS): Context switching Join Discord PreviousISANextCache Memory