COA Notes
Interactive pipeline simulation exercises demonstrating hazards, stalls, and forwarding.
Introduction
Pipelining is one of those concepts that seems simple in theory but gets tricky in practice. The best way to truly understand pipeline hazards, stalls, and forwarding is to simulate them yourself — trace instructions through stages cycle by cycle, identify dependencies, and figure out where stalls must be inserted. This lab gives you that hands-on experience with progressively complex scenarios. By the end, you will be able to look at any instruction sequence and immediately spot hazards and calculate the actual execution time.
The 5-Stage Pipeline Model
We use the classic MIPS 5-stage pipeline:
- IF: Fetch instruction from I-cache
- ID: Decode instruction, read registers
- EX: ALU operation or address calculation
- MEM: Memory read/write (loads and stores)
- WB: Write result back to register file
Pipeline Register Notation
Data flows between stages through pipeline registers:
- IF/ID: Holds fetched instruction
- ID/EX: Holds decoded operands and control signals
- EX/MEM: Holds ALU result, branch target
- MEM/WB: Holds memory data or ALU result for writeback
Simulation 1: No Hazards (Ideal Pipeline)
Instruction Sequence
| I1 | ADD R1, R2, R3 |
| I2 | SUB R4, R5, R6 |
| I3 | AND R7, R8, R9 |
| I4 | OR R10, R11, R12 |
| I5 | XOR R13, R14, R15 |
Pipeline Timing Diagram
| Cycle | 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 |
Analysis: 5 instructions complete in 9 cycles. Without pipelining: 5 × 5 = 25 cycles. Speedup = 25/9 = 2.78× (approaching 5× as instruction count grows).
Simulation 2: Data Hazard (RAW Dependency)
Instruction Sequence
| I1 | ADD R1, R2, R3 (produces R1) |
| I2 | SUB R4, R1, R5 (needs R1 - RAW hazard!) |
| I3 | AND R6, R1, R7 (needs R1 - RAW hazard!) |
| I4 | OR R8, R9, R10 (independent) |
Without Forwarding (Stall Solution)
R1 is written in WB stage of I1 (cycle 5), but I2 needs it in ID stage (cycle 3). We must stall I2 until R1 is available:
| Cycle | 1 2 3 4 5 6 7 8 9 10 11 |
| I1 | IF ID EX MEM WB |
| I2 | IF -- -- ID EX MEM WB |
| I3 | IF ID EX MEM WB |
| I4 | IF ID EX MEM WB |
Two stall cycles (bubble) inserted for I2. Total: 11 cycles instead of 8.
With Full Forwarding
The ALU result from EX stage can be forwarded to the next instruction's EX stage:
| Cycle | 1 2 3 4 5 6 7 8 |
| I1 | IF ID EX MEM WB |
| I2 | IF ID EX MEM WB ← EX-EX forward (R1 from I1's EX) |
| I3 | IF ID EX MEM WB ← MEM-EX forward (R1 from I1's MEM) |
| I4 | IF ID EX MEM WB |
No stalls needed! Forwarding paths:
- I1 EX/MEM register → I2 EX stage input (EX-EX forwarding)
- I1 MEM/WB register → I3 EX stage input (MEM-EX forwarding)
Simulation 3: Load-Use Hazard (Unavoidable Stall)
Instruction Sequence
| I1 | LW R1, 0(R2) (loads R1 from memory) |
| I2 | ADD R3, R1, R4 (needs R1 immediately!) |
| I3 | SUB R5, R1, R6 |
The Problem
Even with forwarding, we have a problem. The LOAD instruction produces its result at the END of MEM stage (cycle 4). But the ADD needs it at the START of EX stage (cycle 3). We cannot forward backward in time!
| Cycle | 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 |
One stall cycle is unavoidable for load-use hazards even with full forwarding. This is why compilers try to schedule instructions to avoid load-use dependencies.
Compiler Solution: Instruction Reordering
Simulation 4: Control Hazard (Branch)
Instruction Sequence
| I1 | BEQ R1, R2, target (branch instruction) |
| I2 | ADD R3, R4, R5 (next sequential - might be wrong path) |
| I3 | SUB R6, R7, R8 (might be wrong path) |
| I7 | AND R9, R10, R11 (branch target) |
Branch Resolved in EX Stage (2-cycle penalty)
| Cycle | 1 2 3 4 5 6 7 8 9 |
| I1(BEQ) | IF ID EX MEM WB |
| I2 | IF ID XX XX (flushed - wrong path!) |
| I3 | IF XX XX (flushed - wrong path!) |
| I7 | IF ID EX MEM WB (correct target fetched) |
Two instructions fetched on wrong path are discarded (2-cycle branch penalty).
Branch Prediction: Predict Not Taken
If we predict NOT taken and are correct, no penalty:
If prediction is wrong (branch IS taken), flush and redirect.
Simulation 5: Multiple Hazards Combined
Instruction Sequence
| I1 | LW R1, 0(R10) |
| I2 | LW R2, 4(R10) |
| I3 | ADD R3, R1, R2 (depends on both loads!) |
| I4 | SW R3, 8(R10) (depends on ADD result) |
| I5 | BEQ R3, R0, skip (depends on ADD result + branch) |
Execution with Forwarding
| Cycle | 1 2 3 4 5 6 7 8 9 10 11 |
| 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 |
Analysis:
- I3 needs R2 from I2's LOAD → 1 stall (load-use hazard)
- I3 needs R1 from I1's LOAD → OK via MEM-EX forward (R1 available from I1's WB)
- I4 needs R3 from I3 → OK via EX-EX forward
- I5 needs R3 from I3 → OK via MEM-EX forward
Total: 11 cycles for 5 instructions (CPI = 11/5 = 2.2)
Performance Calculations
Formulas Applied
For the above simulation:
General Pipeline Performance with Stalls
Example: 30% loads with 50% causing stalls, 15% branches with 2-cycle penalty and 80% prediction:
Exercises for Self-Practice
Exercise 1: Trace this sequence (with forwarding)
Draw the pipeline diagram. How many stalls? Which forwarding paths are used?
Exercise 2: Identify all hazards
List each hazard (RAW/structural/control), identify if forwarding resolves it, and calculate total execution cycles.
Exercise 3: Reorder to eliminate stalls
Reorder these instructions (without changing program semantics) to eliminate all load-use stalls.
Key Takeaways
- Pipeline timing diagrams are the essential tool for understanding instruction-level parallelism
- RAW data hazards can usually be solved with forwarding — except load-use which always costs 1 stall
- Control hazards (branches) can cost 2-3 cycles per misprediction in a 5-stage pipeline
- Compiler instruction scheduling can eliminate many stalls by reordering independent instructions
- Real CPI is always greater than 1 due to hazards — the goal is to minimize the stall component
- Practice tracing pipeline diagrams by hand — this skill is directly tested in exams and builds intuition for how hardware actually works
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Pipeline Simulation.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Computer Organization & Architecture topic.
Search Terms
computer-organization, computer organization & architecture, computer, organization, practicals, and, simulations, pipeline
Related Computer Organization & Architecture Topics