Hazard mitigation — stalling, forwarding - bypassing, branch prediction: Visual walkthrough

This is the deep, picture-first version of the 5-stage pipeline hazard story from the parent note Hazard mitigation. We build the whole thing from zero.

Step 1 — What is a "stage" and what is a "cycle"?

WHAT. An instruction does not finish in one instant. It walks through 5 rooms, one room per clock tick (one cycle). The rooms, in order:

IF — Instruction Fetch: grab the instruction from memory.
ID — Instruction Decode: figure out what it is and read the registers it needs.
EX — Execute: the calculator (ALU) does the arithmetic.
MEM — Memory: touch data memory (only loads/stores use this room meaningfully).
WB — Write Back: store the result into the register file so future instructions can see it.

WHY these two words matter. The whole hazard argument is about timing: at which cycle is a value born, and at which cycle is it needed? So we must first pin down that a value read happens in ID, and a value produced by the calculator is finished at the end of EX.

PICTURE. One instruction, five rooms, five ticks. Watch the token move right by one room each cycle.

Figure — Hazard mitigation — stalling, forwarding - bypassing, branch prediction

Step 2 — Overlap: five instructions in flight at once

WHAT. Pipelining means: as soon as instruction 1 leaves IF for ID, instruction 2 enters IF. Slide every instruction one room to the right, one tick later. Draw them stacked and you get a diagonal staircase.

WHY. This staircase is the entire point of a pipeline: five rooms are busy at once, so we finish one instruction every cycle after the pipe fills. That dream throughput is 1 instruction per cycle — the number we compare everything against in CPI analysis.

PICTURE. The staircase. Notice the key fact we will exploit: at any single cycle (a vertical slice), different instructions sit in different rooms.

Recall Why does a vertical slice matter?

A vertical slice is "one moment in time." ::: Because each instruction is in a different room at that moment, we can ask: is the value one instruction needs physically sitting in a room near it right now?

Step 3 — The dependency that starts the trouble

WHAT. Two instructions where the second reads what the first writes:

sub $t0, $s1, $s2   ; writes $t0
add $t1, $t0, $s3   ; reads  $t0

This is a RAW hazard (Read-After-Write): add reads $t0, which sub must first produce.

WHY it's a problem on the staircase. Line up their timelines. add wants to read $t0 in its ID (Step 1 told us reads happen in ID). But at that cycle, sub has not reached WB yet — the official copy of $t0 in the register file is still the old value.

PICTURE. The red arrow shows the "need" (add's ID) landing earlier than the "official supply" (sub's WB). If we did nothing, add reads stale garbage.

Definition The two clocks — measured to

half-cycle precision A single stage has a start edge and an end edge. To compare "born" vs "needed" honestly we must record which edge. We do this by adding a half:

Let $C_{avail}$ = the moment the value is finished. A value latched at the end of stage-cycle $k$ we write as $C_{avail} = k + \frac{1}{2}$ .
Let $C_{need}$ = the moment the consumer must have it. A value needed at the start of stage-cycle $k$ we write as $C_{need} = k - \frac{1}{2}$ . $stall cycles = ⌈ max (0, C_{avail} - C_{need}) ⌉$
the $\pm \frac{1}{2}$ — encodes end-of-stage vs start-of-stage so that "same cycle number" no longer hides a real ordering.
$max (0, \cdot)$ — you never stall a negative number of cycles; if born before needed, the gap is $\leq 0$ and the stall is $0$ .
$⌈ \cdot ⌉$ (ceiling, "round up") — you can only stall a whole number of cycles, so any positive fraction of a cycle costs a full bubble.

Step 4 — The rescue: the value already exists in a latch

WHAT. Between every two rooms sits a small holding-box called a pipeline latch (EX/MEM, MEM/WB, …). When sub finishes EX, its answer $t0 is latched into EX/MEM at the end of EX — long before WB.

WHY this is the key insight. We do not need to wait for the register file. The number physically exists in the EX/MEM latch. Look at the staircase for our pair:

When add is in EX (needs $t0 at the start of that cycle),
sub is one room ahead in MEM, so $t0 is sitting right there in the EX/MEM latch.

So we add a wire + a multiplexer (mux) that routes the latch value straight into the ALU input. That wire is forwarding (bypassing).

PICTURE. Green arrow: value leaves sub's EX/MEM latch and jumps down and right into add's ALU. It travels forward in time (same cycle or later) — physically possible.

Let's confirm the arithmetic with the half-cycle clocks. sub produces $t0 at the end of EX = end of cycle 3, so $C_{avail} = 3 + \frac{1}{2} = 3.5$ . add needs it at the start of EX = start of cycle 4, so $C_{need} = 4 - \frac{1}{2} = 3.5$ . $C_{avail} = 3.5, C_{need} = 3.5 \Rightarrow stall = ⌈ max (0, 3.5 - 3.5)⌉ = ⌈ 0 ⌉ = 0.$

$3.5 - 3.5 = 0$ — born and wanted at the same instant (the end-of-EX edge feeds the start-of-EX edge). The wire spans zero time.
$⌈ max (0, 0)⌉ = 0$ — no bubbles. The forward covers it exactly.

Step 5 — The load: same picture, one room later

WHAT. A load lw does not finish in EX. In EX it only computes the address; the actual data comes back from memory at the end of MEM (recall the precondition: MEM finishes inside its one cycle).

lw  $t0, 0($s0)   ; $t0 born at end of MEM
add $t1, $t0, $s3 ; needs $t0 at start of EX

WHY this breaks forwarding. Redo the half-cycle clocks. lw's $t0 is born at the end of MEM = end of cycle 4, so $C_{avail} = 4 + \frac{1}{2} = 4.5$ . add needs it at the start of EX = start of cycle 4, so $C_{need} = 4 - \frac{1}{2} = 3.5$ .

PICTURE. The would-be forwarding arrow now has to point backward in time (from $4.5$ to $3.5$ ). You cannot send data into the past. The arrow is drawn dashed-red to scream "impossible."

$C_{avail} = 4.5, C_{need} = 3.5 \Rightarrow stall = ⌈ max (0, 4.5 - 3.5)⌉ = ⌈ 1 ⌉ = 1.$

$4.5 - 3.5 = 1$ — the half-cycle bookkeeping now exposes the full one-cycle gap that the naive "cycle-number only" formula hid (it wrongly computed $4 - 4 = 0$ ).
$⌈ 1 ⌉ = 1$ — exactly one bubble. This is the load-use hazard.

This is the whole point of the $\pm \frac{1}{2}$ fix: without it, $C_{avail} = C_{need} = 4$ looked like "0 stall," contradicting the picture. With end-vs-start edges made explicit, the formula and the picture finally agree.

Step 6 — Inserting the bubble (what the stall does mechanically)

WHAT. To stall for one cycle the hardware, in that one cycle, does three things:

Freeze the PC — do not fetch a new instruction.
Freeze the IF/ID latch — the decoded add stays put in ID.
Inject a bubble into ID/EX — zero all its control signals so the EX room does nothing harmful that cycle.

WHY. Freezing (1) and (2) hold add in place for one extra tick; the bubble (3) fills the EX room so nothing downstream misbehaves. After that one tick, lw has reached the MEM/WB boundary and its $t0 can now be forwarded into add's (now delayed) EX.

PICTURE. The stalled timeline. Grey box = bubble. After the shift, a legal forward arrow (green, pointing forward) delivers $t0.

cyc	1	2	3	4	5	6
`lw`	IF	ID	EX	MEM	WB
`add`	IF	ID	bubble	EX	MEM	WB

Now add's EX sits in cycle 5, lw's MEM/WB holds $t0 at the start of cycle 5 → the forward points forward-in-time again. ✅ Re-checking with the clocks after the delay: $C_{need} = 5 - \frac{1}{2} = 4.5 = C_{avail}$ , so $⌈ max (0, 0)⌉ = 0$ residual stalls. The single bubble was exactly enough.

Step 7 — All the cases, so you never get surprised

WHAT. Every producer/consumer distance, resolved:

Producer	Distance to consumer	Value born	Consumer needs	Fix
ALU	1 instruction ahead	end EX	start EX (next cyc)	forward `EX/MEM`, 0 stall
ALU	2 instructions ahead	end EX	start EX (2 cyc later)	forward `MEM/WB`, 0 stall
ALU	3+ ahead	end EX	later	already in reg file, no forward needed
`lw`	1 ahead (immediate use)	end MEM	start EX	1 stall, then forward
`lw`	2 ahead	end MEM	start EX (2 cyc later)	forward `MEM/WB`, 0 stall
any	writes `$0` / `RegWrite=0`	—	—	never forward (the zero register / no write)

WHY the last two rows matter (degenerate cases).

lw 2-ahead has one free instruction between producer and consumer. Clocks: born end MEM $= 4 + \frac{1}{2} = 4.5$ ; needed start EX two cycles later $= 5 - \frac{1}{2} = 4.5$ . So $⌈ max (0, 4.5 - 4.5)⌉ = 0$ — the gap closes for free.
Register $0 is hard-wired to zero and instructions with RegWrite=0 write nothing. Forwarding to/from them would inject a phantom value. So every forwarding condition includes rd ≠ 0 and RegWrite = 1 — the guards from the parent note's formulas.

PICTURE. Two mini-timelines side by side: the load-2-ahead case (no stall) and the $0-guard case (forward suppressed).

The one-picture summary

Everything compressed: one timeline, the green forward arrows that are legal (forward in time), the dashed-red arrow that is illegal (backward in time) and therefore forces the single load-use bubble.

Recall Feynman retelling — say it like a story

An instruction walks through five rooms, one room per clock tick, and we start a new one every tick so five are moving at once — a staircase. A value a calculator makes is done the moment it leaves the EX room, and it gets stashed in a little holding-box (a latch) right away. So if a later instruction wants that number, we don't wait for it to be filed in the register file — we run a wire straight from the latch into the calculator. That's forwarding, and it saves the day as long as the number is born before or at the same instant we hand it over — you can always pass something forward in time. To be honest about "same instant" we tag every event with a half: born at end of a cycle is $k + \frac{1}{2}$ , needed at start is $k - \frac{1}{2}$ . For an ALU op those two halves line up perfectly (both $3.5$ ), so the wire spans zero time — free. But a load fetches its number from memory, which finishes one room later, at $4.5$ , while the next instruction needs it at $3.5$ . That's a full cycle backward — impossible. So we freeze the pipeline for exactly one tick (a bubble), which slides the "need" to $4.5$ and now the wire is forward again. One room of delay, one tick of stall — always exactly one. (All of this assumes memory answers in a single cycle; a cache miss is a separate, bigger stall.) Which distance costs a stall? ::: Only load → immediately-next instruction: the value is born one room too late. Why does forwarding fail there but work for ALU ops? ::: ALU result: born $3.5$ , needed $3.5$ → span 0, free. Load: born $4.5$ , needed $3.5$ → span $1$ backward, impossible → 1 stall. What breaks if memory is not single-cycle? ::: The load's data arrives even later than end-of-MEM, so the stall grows — handled by the memory hierarchy, not by forwarding.