Intuition What this page doesThe parent note built the machinery: the 5 stages , stalling, forwarding, and branch prediction. This page stress-tests every one of those tools against every case it can face — the closest producer, the farthest producer, a load, a zero-register write, two operands at once, a branch flush, a loop, and an exam trick. Guess each answer first, then check.
Before we start, we need two things: the timeline convention and the field notation used in every forwarding condition below.
Definition The cycle gridWe line up instructions in a table where columns are clock cycles and each row shows which stage an instruction occupies that cycle. Stages in order: IF (fetch) → ID (decode + read registers) → EX (ALU) → MEM (memory) → WB (write register file). A value is born at the end of EX (for ALU ops) or end of MEM (for loads), and is read at the start of EX by a consumer. Forwarding sends a value from a later stage's latch back to an earlier instruction's EX in the same or a later cycle — never earlier in absolute time.
Definition Pipeline-register fields (the forwarding notation)Between every pair of stages sits a pipeline register (a latch) that carries an instruction's data and control bits forward one cycle. We name a field as LATCH.field:
==EX/MEM== — the latch after EX (holds an ALU result that is 1 instruction ahead of whoever is in EX now).
==MEM/WB== — the latch after MEM (holds a result 2 instructions ahead).
==ID/EX== — the latch feeding EX — it carries the current instruction's source-register numbers.
.RegWrite — a 1-bit control flag: "this instruction will write a register.".rd — the destination register number this instruction writes..rs, .rt — the two source register numbers the current instruction reads.
So EX/MEM.rd = ID/EX.rs reads in English: "the register the instruction one-ahead-of-me will write is the same register I'm reading as my first operand." That match is exactly when we must forward.
Every case this topic can throw, and which example covers it.
#
Case class
Concrete trigger
Covered by
A
Producer 1 ahead (EX-hazard)add then dependent addEx 1
B
Producer 2 ahead (MEM-hazard)one gap instruction between
Ex 2
C
Double writer, newest-wins two producers write same reg
Ex 3
D
Load-use, unavoidable stall lw then immediate useEx 4
E
Degenerate: write to $zero rd = $0Ex 5
F
No hazard at all dependency ≥ 3 apart
Ex 6
G
Two operands, two latches at once rs from EX/MEM, rt from MEM/WBEx 7
H
Control hazard: branch flush mispredict, flush the grid
Ex 8
I
Word problem + limits: CPI m = 1 m = 0 Ex 9
J
2-bit predictor on a loop taken×N then not-taken
Ex 10
K
Exam twist: load-use hidden by scheduling compiler reorders
Ex 11
The figures ahead draw the cycle grid so you can see where a value is born and where it is needed.
Worked example Two back-to-back ALU opsadd $t0, $s1, $s2 (add: $t0 born end of EX)
sub $t3, $t0, $s4 (sub: needs $t0 at start of its EX)
Forecast: how many stalls? Where does the value come from?
Place them on the grid. add: IF₁ ID₂ EX₃ MEM₄ WB₅. sub: IF₂ ID₃ EX₄ MEM₅ WB₆.
Why this step? We must know the exact cycle each stage lands in before we can compare "born" vs "needed".Find born and needed cycles. $t0 is born at the end of cycle 3 so B = 3 sub needs it at the start of cycle 4 so N = 4 N − 1 = 3 Why this step? Feed these into the one stall rule.Apply the rule: max ( 0 , B − ( N − 1 )) = max ( 0 , 3 − 3 ) = 0 Why this step? B = 3 Check the EX-hazard forward condition: EX/MEM.RegWrite ∧ (EX/MEM.rd ≠ 0) ∧ (EX/MEM.rd = ID/EX.rs). In cycle 4, add sits in MEM so its result is in the EX/MEM latch , EX/MEM.rd = $t0 ≠ 0, and ID/EX.rs = $t0 (that's sub's source). Condition true → forward EX/MEM → ALU input A of sub.
Why this step? This is the hardware test that fires the mux — confirm the wire exists.
Read the figure: the shaded red cells are add's MEM (its EX/MEM latch) and sub's EX. The red arrow drops straight down from the latch into sub's EX in the same column (cycle 4) — that vertical, same-cycle arrow is a legal forward. 0 stalls.
Verify: max ( 0 , 3 − 3 ) = 0
Worked example One independent instruction sits betweenadd $t0, $s1, $s2 (add: $t0 born end of EX)
or $t5, $s6, $s7 (independent filler)
and $t3, $t0, $s4 (and: needs $t0)
Forecast: stalls? Which latch supplies $t0?
Grid. add: EX₃ MEM₄ WB₅. or: EX₄ MEM₅. and: IF₃ ID₄ EX₅ MEM₆ WB₇.
Why this step? and's EX is cycle 5; we need to know what stage add occupies then.Born vs needed. B = 3 add's EX). and needs it start of cycle 5, so N = 5 N − 1 = 4 max ( 0 , 3 − 4 ) = 0 Why this step? Even more slack than Case A — one whole spare cycle.Where is add in cycle 5? In WB — so $t0 sits in the MEM/WB latch , not EX/MEM. Apply the MEM-hazard forward: MEM/WB.RegWrite ∧ (MEM/WB.rd ≠ 0) ∧ (MEM/WB.rd = ID/EX.rs), and the EX-hazard is not also true. It holds.
Why this step? The correct latch depends on distance: 1 ahead → EX/MEM, 2 ahead → MEM/WB.Conclusion: 0 stalls, forwarded from MEM/WB.
Verify: max ( 0 , 3 − 4 ) = 0
Worked example Which value reaches the consumer?add $t0, $s1, $s2 (writes $t0, value = 10)
sub $t0, $s3, $s4 (ALSO writes $t0, value = 7)
or $t9, $t0, $s5 (reads $t0 -> must get 7, not 10)
Forecast: does the reader see 10 or 7? Which forward fires?
Grid. add: EX₃ MEM₄ WB₅. sub: EX₄ MEM₅ WB₆. or: IF₃ ID₄ EX₅.
Why this step? or's EX is cycle 5 — check what BOTH writers are doing then.In cycle 5: sub is in MEM (value 7 in EX/MEM ), add is in WB (value 10 in MEM/WB ). BOTH forward conditions match $t0!
Why this step? This is exactly the collision the parent's "newest wins" rule solves.Priority rule: the EX-hazard (closer, EX/MEM) wins over the MEM-hazard. Program order says the last write before me is sub = 7, and sub is the closer one → EX/MEM supplies 7 .
Why this step? Picking the newer value is what makes forwarding correct , not just fast.Conclusion: or reads 7 . 0 stalls.
Read the figure: two red arrows race into or's EX (cycle 5) — a solid one from sub's MEM (EX/MEM, value 7) and a dashed, greyed one from add's WB (MEM/WB, value 10). The solid arrow wins; the priority mux picks the closer latch. That's "newest wins" drawn as a picture.
Verify: last writer before or is sub (value 7). EX/MEM latch holds it in cyc 5. Answer = 7. ✓
lw then immediate consumer
lw $t0, 0($s0) (lw: $t0 born end of MEM)
add $t1, $t0, $s1 (add: needs $t0 at start of its EX)
Forecast: how many stalls, even with full forwarding?
Grid (no stall yet). lw: IF₁ ID₂ EX₃ MEM₄ WB₅. add: IF₂ ID₃ EX₄.
Why this step? We must see the timing clash before "fixing" it.Born vs needed. $t0 born at end of MEM → B = 4 add needs it at start of cycle 4 → N = 4 N − 1 = 3 Why this step? Now the stall rule does the work — no ad-hoc reasoning.Apply the rule: max ( 0 , B − ( N − 1 )) = max ( 0 , 4 − 3 ) = 1 one cycle past the deadline (cycle 3), and forwarding cannot send data backward in time → 1 bubble .
Why this step? This is the whole load-use story in a single arithmetic line.Insert the bubble: hold add in ID one extra cycle so its EX slides to cycle 5. Now N = 5 B = 4 ≤ 4 lw is in WB in cycle 5, forward MEM/WB → add's EX.
Why this step? The single stall pushes the deadline out to meet the birth.
Read the figure: add's row shows a red -- (bubble) cell in cycle 4; its EX shifts right to cycle 5. The red arrow now goes from lw's WB down into add's EX — legal because it points down-and-into-the-same-cycle, not backward. Exactly 1 stall — the load-use hazard .
Verify: max ( 0 , 4 − 3 ) = 1
$0 trap
add $zero, $s1, $s2 (writes $0 -- but $0 is hardwired to 0)
or $t3, $zero, $s4 (reads $0)
Forecast: should the hardware forward here? What value should or see?
Recall the rule detail: every forward condition includes (rd ≠ 0).
Why this step? Register $0 in MIPS is a constant 0; nothing can actually change it.Evaluate: EX/MEM.rd = $0, so (EX/MEM.rd ≠ 0) is false → forwarding is suppressed .
Why this step? If we forwarded add's numeric result (say s 1 + s 2 = 30 or, or would wrongly read 30 instead of 0.Conclusion: no forward; or reads $0 from the register file = 0 . 0 stalls (no real dependency existed).
Verify: $0 is constant 0, so the correct read is 0; the (rd ≠ 0) guard blocks the bad forward. Result = 0. ✓
Worked example Enough distance = freeadd $t0, $s1, $s2
or $t5, $s6, $s7
and $t8, $s3, $s4
xor $t9, $t0, $s5 (reads $t0, 3 instructions later)
Forecast: stalls? forwarding needed?
Grid. add: WB₅. xor: ID₅ EX₆.
Why this step? Locate add's WB and xor's ID/EX.Born vs needed. B = 3 add's EX). xor needs it start of cycle 6, N = 6 max ( 0 , 3 − 5 ) = 0 Why this step? Confirms no stall by the rule.Do we even forward? xor's ID is cycle 5, add's WB is cycle 5. Classic MIPS writes in the first half of WB and reads in the second half of the same cycle, so xor's normal register read gets the fresh $t0. No forward, no wire.
Why this step? Once WB has completed before the read, the register file itself delivers the value.
Verify: distance 3 ⇒ max ( 0 , 3 − 5 ) = 0
rs and rt want different latches at once
add $t0, $s1, $s2 (produces $t0)
sub $t1, $s3, $s4 (produces $t1)
and $t9, $t0, $t1 (rs = $t0, rt = $t1 -- BOTH are hazards)
Forecast: where does each operand of and come from — same latch or two different ones?
Grid. add: EX₃ MEM₄ WB₅. sub: EX₄ MEM₅ WB₆. and: IF₃ ID₄ EX₅.
Why this step? and's EX is cycle 5; check where each producer sits then.Operand rs = $t0 (from add): in cycle 5, add is in WB , so $t0 is in the MEM/WB latch (2 ahead). MEM-hazard forward feeds ALU input A .
Why this step? add is the farther producer → longer wire.Operand rt = $t1 (from sub): in cycle 5, sub is in MEM , so $t1 is in the EX/MEM latch (1 ahead). EX-hazard forward feeds ALU input B .
Why this step? sub is the closer producer → shorter wire.Conclusion: the two forwarding muxes fire independently — input A from MEM/WB, input B from EX/MEM, in the same cycle , 0 stalls. The "newest wins" priority is per operand , and here each operand has exactly one matching producer, so there's no conflict.
Why this step? This is the key edge case: a single instruction can pull its two operands from two different latches at once.
Read the figure: two red arrows land on and's EX (cycle 5) from different rows and different latch columns — one long arrow from add's WB (labelled "to input A"), one short arrow from sub's MEM (labelled "to input B"). Different sources, one destination, same cycle.
Verify: add born B = 3 sub born B = 4 N = 5 max ( 0 , 3 − 4 ) = 0 max ( 0 , 4 − 4 ) = 0
Worked example Branch resolves in EX, wrong-path instructions must dieAssume branches resolve at the end of EX and we predict not-taken (keep fetching the fall-through). The branch turns out taken , so the 2 fall-through instructions already fetched are wrong.
beq $t0, $t1, TARGET (branch; resolves end of EX)
or $t2, $s0, $s1 (fall-through -- WRONG path, must flush)
and $t3, $s2, $s3 (fall-through -- WRONG path, must flush)
TARGET: xor $t4, ... (correct target, fetched after resolve)
Forecast: how many instructions get flushed, and what's the penalty p
Grid the branch. beq: IF₁ ID₂ EX₃. It resolves at the end of cycle 3 .
Why this step? The resolve cycle decides how many wrong instructions slipped in behind it.Grid the wrong-path fetches. or: IF₂ ID₃ (…). and: IF₃ (…). By the end of cycle 3, both or and and have entered the pipe on the not-taken assumption.
Why this step? Everything fetched between the branch's IF and its resolve is speculative.Flush them. At end of cycle 3 the hardware learns "taken", so in cycle 4 it squashes or and and (turns them into bubbles by clearing their control bits) and fetches xor from TARGET.
Why this step? Wrong-path instructions must not write registers or memory — squashing zeroes their effect.Count the penalty. Two fetched-then-killed instructions ⇒ penalty p = 2 cycles for this branch (2 empty slots before the correct xor gets going).
Why this step? This p
Read the figure: or and and rows have their post-cycle-3 cells shaded red and struck through ("FLUSH"), and a red arrow jumps from beq's EX (cycle 3) to a fresh IF of xor in cycle 4 — the pipeline redirects to the real target. The two red bubbles ARE the branch penalty.
Verify: wrong instructions fetched before resolve = 2 (or, and) ⇒ p = 2
Worked example Sizing a branch predictor for a real workloadA program: 25% of instructions are branches (b = 0.25 p = 4 m = 1 m = 0.08 m = 0
Forecast: which regime gives the biggest CPI? By how much does the good predictor beat always-flush?
Recall the model: CPI = 1 + b ⋅ m ⋅ p Amdahl's Law and CPI analysis ).
Why this step? Each branch pays p m b Always-flush (worst limit), m = 1 CPI = 1 + 0.25 ⋅ 1 ⋅ 4 = 1 + 1.0 = 2.0 Why this step? m = 1 Good predictor, m = 0.08 CPI = 1 + 0.25 ⋅ 0.08 ⋅ 4 = 1 + 0.08 = 1.08 Why this step? Plug the realistic miss rate; this is the number you'd quote.Oracle (best limit), m = 0 CPI = 1 + 0 = 1.0 Why this step? m = 0 Speedup of good over always-flush: 2.0/1.08 ≈ 1.85 × Why this step? CPI is inversely proportional to throughput, so the ratio is the speedup.
Read the figure: three bars; the red one (always-flush, CPI = 2.0) towers over the two black bars, and the dashed line at CPI = 1.0 marks the ideal floor the oracle bar sits on.
Verify: 1 + 0.25 ⋅ 1 ⋅ 4 = 2.0 1 + 0.25 ⋅ 0.08 ⋅ 4 = 1.08 1 + 0 = 1.0 2.0/1.08 = 1.8518 …
Worked example Trace the counter through a loopA loop branch is Taken 4 times (iterations 1–4, staying in the loop) then Not-Taken once (iteration 5, exiting). The 2-bit counter starts at 10 (weak-Taken). States: 00 sNT → 01 wNT → 10 wT → 11 sT; predict Taken if top bit = 1. Taken → increment (max 11), Not-taken → decrement (min 00).
Forecast: how many mispredictions across these 5 branch outcomes?
Outcome 1 = Taken. State 10 → predict T ✓ correct; increment → 11.
Why this step? Each branch: predict from current top bit, compare to actual, then update.Outcome 2 = Taken. State 11 → predict T ✓; increment saturates → 11.
Why this step? Saturation means 11 + T stays 11, building confidence.Outcome 3 = Taken. 11 → T ✓ → 11.Outcome 4 = Taken. 11 → T ✓ → 11.Outcome 5 = Not-Taken (loop exit). State 11 → predict T ✗ wrong ; decrement → 10.
Why this step? The single exit costs exactly one miss — and hysteresis means the counter only drops to 10, still predicting Taken for the next loop entry.Count: 4 correct, 1 misprediction .
Read the figure: five cells left-to-right show the counter state before each branch; only the last cell (the loop-exit) is shaded red and labelled MISS, while the four Taken outcomes stay black and correct. One red cell = one miss.
Verify: predictions [T,T,T,T,T] vs actuals [T,T,T,T,NT] ⇒ exactly 1 mismatch. A 1-bit predictor would also miss the exit, then flip to NT and miss the next entry too — 2 misses per trip. The 2-bit's hysteresis saves that second miss. ✓
Worked example Reorder to reclaim the bubbleOriginal code, running on a fully-forwarded pipeline:
lw $t0, 0($s0)
add $t1, $t0, $s1 (load-use -> 1 stall, Case D)
or $t5, $s6, $s7 (totally independent)
sub $t8, $s3, $s4 (totally independent)
Forecast: can a compiler remove the stall without changing the result?
Baseline cost: the lw → add pair forces 1 stall (proved in Case D). Total ≈ 4 instr + 1 bubble.
Why this step? Establish what we're trying to beat.Find an independent instruction to slot right after lw. or uses only $s6,$s7 — independent of $t0. Move it up:
lw $t0, 0($s0)
or $t5, $s6, $s7 (fills the load-delay slot)
add $t1, $t0, $s1 ($t0 now ready via MEM/WB forward)
sub $t8, $s3, $s4
Why this step? The independent or occupies the cycle the bubble would have wasted — real work instead of a NOP.Re-check the load-use timing. Now add is 2 instructions behind lw. lw born B = 4 add's EX is now cycle 5, so N = 5 N − 1 = 4 max ( 0 , 4 − 4 ) = 0 0 stalls , forwarded from MEM/WB. This is exactly Case B's geometry reached by reordering.
Why this step? The extra distance moved the deadline from cycle 3 to cycle 4, and B = 4 Correctness: reordering only moved an instruction that shares no register with the others, so the final register values are unchanged.
Why this step? Scheduling is legal only when it preserves data dependencies.
Verify: after moving or, gap is 1 instruction ⇒ B = 4 N = 5 max ( 0 , 4 − 4 ) = 0
Recall Self-test (reveal after guessing)Producer 1 ahead needs which latch? ::: EX/MEM (EX-hazard forward).
Producer 2 ahead needs which latch? ::: MEM/WB (MEM-hazard forward).
What does EX/MEM.rd = ID/EX.rs mean in English? ::: "The register the instruction one-ahead-of-me will write equals the one I'm reading as operand 1" — forward it.
Two writers to same reg — who wins? ::: The closer one (EX/MEM), i.e. newest write.
State the stall rule. ::: stalls = max ( 0 , B − ( N − 1 )) B N lw→use cost a stall even with forwarding? ::: B = 4 > N − 1 = 3 rs from MEM/WB and rt from EX/MEM in the same cycle (Case G).
Branch penalty for a not-taken predictor when the branch is taken and resolves in EX? ::: 2 flushed instructions ⇒ p = 2 CPI = 1 + b ⋅ m ⋅ p
Every hazard question reduces to two cycle numbers: B orn (B N eeded (N = max ( 0 , B − ( N − 1 )) B ≤ N − 1
See also: Pipelining basics — 5-stage MIPS · Datapath and control signals · Out-of-order execution and Tomasulo · Caches and memory hierarchy · Amdahl's Law and CPI analysis · Compiler instruction scheduling
