Load-use hazard and stalls: Exercises — Hardware deep dive

This page is a self-testing ladder. Each problem states its level so you know how much you are stretching. Every solution lives inside a collapsible [!recall]- box — read the problem, think, then unfold. After each level there is one [!mistake] box steel-manning the trap most people fall into there.

Parent: Load-use hazard and stalls. Prerequisites you may want open: Five-stage MIPS pipeline, Data hazards and forwarding, Hazard detection unit.

Look at the figure above: the red dot (data ready) sits at the far edge of cycle 4, while the coral arrow (data needed) points at the near edge of cycle 4. The arrow would have to travel left in time — impossible. That gap is the whole subject.

So "MEM/WB → EX" = take the load's result out of the MEM/WB latch and drop it onto an ALU input. "MEM/WB → MEM" = feed that same latched value into the store's data port in the MEM stage. Same idea, different destination. See Data hazards and forwarding.

Level 1 — Recognition

Goal: can you spot a hazard at a glance?

Worked example Exercise 1.1

For each pair, say YES (load-use stall needed) or NO.

(a) lw  $2, 0($1)
    add $4, $2, $3
 
(b) lw  $2, 0($1)
    add $4, $5, $3
 
(c) add $2, $1, $3
    add $4, $2, $3
 
(d) lw  $0, 0($1)
    add $4, $0, $3

Recall Solution 1.1

Apply the three stall conditions: (1) the earlier instr is a load, (2) its destination register is read by the next instr, (3) that register is not $0.

(a) YES. lw writes $2; add reads $2. All three conditions hold.
(b) NO. add reads $5 and $3, never $2. Condition 2 fails.
(c) NO. The first instruction is an add, not a load — an ALU→ALU dependency solved by forwarding alone. Condition 1 fails.
(d) NO. The load targets $0, which is hardwired to zero in MIPS; add reading $0 sees zero regardless. Condition 3 fails.

Recall Solution 1.2

Frozen: the PC and the IF/ID register. This re-fetches the same instruction and holds the dependent instruction in ID for one extra cycle.
Zeroed: the ID/EX control signals, turning the EX stage into a NOP (no write, no memory op) for the injected bubble.
Untouched: MEM and WB continue normally, so the load finishes on schedule. See Pipeline control signals.

Level 2 — Application

Goal: draw the correct pipeline diagram and count cycles.

Recall Solution 2.1

Cycle:  1    2    3    4    5    6    7
lw      IF   ID   EX   MEM  WB
add          IF   ID   **   EX   MEM  WB

** is the bubble. add's EX slides to cycle 5. The load's data (ready end of cycle 4, sitting in MEM/WB) is forwarded MEM/WB → EX into that cycle-5 EX. Reading the add row: EX = cycle 5, MEM = cycle 6, WB = cycle 7. So add reaches WB in cycle 7 (the cycle header now goes out to 7 to show it).

Recall Solution 2.2

No stall. A store consumes its store-data register late, in its MEM stage.

Cycle:  1    2    3    4    5
lw      IF   ID   EX   MEM  WB
sw           IF   ID   EX   MEM

lw finishes MEM at end of cycle 4. sw writes memory in its own MEM stage, cycle 5 — after the data exists. A MEM/WB → MEM forward delivers $2 in time. No bubble.

Recall Solution 2.3

No stall. The independent or sits between the load and the use.

Cycle:  1    2    3    4    5    6    7
lw      IF   ID   EX   MEM  WB
or           IF   ID   EX   MEM  WB
add               IF   ID   EX   MEM  WB

add's EX is now in cycle 5, and lw's data (ready end of cycle 4) forwards MEM/WB → EX cleanly. This is exactly what Compiler instruction scheduling exploits.

Level 3 — Analysis

Goal: reason about performance numbers.

Recall Solution 3.1

Stall frequency $= 0.25 \times 0.40 = 0.10$ of all instructions. $CPI = 1.0 + 0.10 \times 1 = 1.10$ Slowdown $= (1.10 - 1.0) /1.0 = 0.10 = 10%$ more cycles than ideal.

Recall Solution 3.2

First, the ideal (no-stall) cost. Why does a pipeline cost more than "1 cycle each"? The first instruction must march through all $5$ stages before it finishes — that's $5$ cycles to fill the pipeline. After it, each additional instruction finishes just $1$ cycle later, because they overlap and come out back-to-back. So for $n$ instructions in a $d$ -stage pipeline: $ideal cycles = d + (n - 1)$ Here $d = 5$ , $n = 3$ : $5 + (3 - 1) = 5 + 2 = 7$ cycles. (Check the rows: lw WB is cycle 5, then +1 per instruction.)

Cycle:  1    2    3    4    5    6    7    8
lw      IF   ID   EX   MEM  WB
add          IF   ID   **   EX   MEM  WB
sub               IF   ID   **   EX   MEM  WB

One bubble pushes everything by one cycle → sub finishes in cycle 8. Ratio $= 8/7 \approx 1.14$ . Note sub needs no extra stall: by the time it reaches EX, add's result forwards normally EX/MEM → EX.

Recall Solution 3.3

Stalls per iteration $= 2$ . Instructions per iteration $= 6$ . $CPI = 1.0 + \frac{2 stalls}{6 instructions} = 1.0 + 0.3333 \dots = 1.333$ A big hint that this loop is a prime candidate for Compiler instruction scheduling reordering.

Level 4 — Synthesis

Goal: rebuild code and hardware conditions yourself.

Recall Solution 4.1

Move an independent instruction into the load's delay slot (right after lw). or uses only $7,$8 — independent of $2. So:

lw   $2, 0($1)
or   $6, $7, $8      ; independent — fills the slot
add  $4, $2, $5      ; now sees $2 forwarded MEM/WB to EX, no stall
and  $9, $10, $11

Results unchanged (no instruction wrote a register another now reads out of order), and the stall is gone. This is exactly the Compiler instruction scheduling technique.

Recall Solution 4.2

Symbol key first: $\land$ means AND (both true), $\lor$ means OR (at least one true), $\neq =$ means not equal. $stall = ID/EX.MemRead \land (ID/EX.Rt = IF/ID.Rs \lor ID/EX.Rt = IF/ID.Rt) \land (ID/EX.Rt \neq = 0)$

ID/EX.MemRead $= 1$ : a load is currently in EX (only loads read memory into a register).
ID/EX.Rt: the destination register of that load (for lw, the target is the Rt field).
IF/ID.Rs / IF/ID.Rt: the two source registers of the instruction now in ID (the potential dependent).
$\neq = 0$ : exclude the hardwired $0, which never carries a real dependency.

Recall Solution 4.3

Without forwarding, add must read $2 from the register file in its ID stage, and the register file is written by lw in WB (cycle 5). With a same-cycle-write-then-read register file, add's ID must land in cycle 5.

Cycle:  1    2    3    4    5    6
lw      IF   ID   EX   MEM  WB
add          IF   **   **   ID   EX  ...

That is 2 bubbles. Forwarding (MEM/WB → EX) is what shrinks it to the single unavoidable bubble.

Level 5 — Mastery

Goal: combine everything, including cache latency and back-to-back loads.

Recall Solution 5.1

Two separate load-use hazards chain together.

lw $3 uses $2 in its EX (address computation) → 1 stall after the first load.
add uses $3 in its EX → 1 stall after the second load.

Cycle:  1    2    3    4    5    6    7    8    9
lw $2   IF   ID   EX   MEM  WB
lw $3        IF   ID   **   EX   MEM  WB
add               IF   ID   **   **   EX   MEM  WB

Row-by-row, matched to the header:

lw $2: IF1 ID2 EX3 MEM4 WB5.
lw $3: IF2 ID3, one bubble ** in cycle 4, then EX5 MEM6 WB7.
add: IF3 ID4, then two bubbles ** in cycles 5 and 6 (it must wait for lw $3's data), then EX7 MEM8 WB9. add writes back in cycle 9. 2 stall cycles total (one per load-use hazard).

Recall Solution 5.2

Break the penalty into two independent contributions (per all instructions):

Load-use stalls: $0.30 \times 0.50 \times 1 = 0.15$ .
Cache-miss penalty: $0.30 \times 0.05 \times 10 = 0.15$ . $CPI = 1.0 + 0.15 + 0.15 = 1.30$ The miss penalty comes from Memory hierarchy and cache and is a separate effect from the pipeline stall — they simply add.

Recall Solution 5.3

$CPI_{A} = 1.0 + 0.20 \times 1 = 1.20$ .
$CPI_{B} = 1.0 + 0.20 \times 2 = 1.40$ .
Ratio $= 1.40/1.20 = 1.1 \overline{6} \approx 1.17$ . Machine A is faster: it takes about 17% fewer cycles than Machine B on this program. Forwarding earns back exactly one bubble per load-use hazard, and that single saved bubble is the entire gap between the two machines.

Recall Rapid self-check (cloze)

A load produces data at the ::: end of the MEM stage. A dependent ALU instruction needs it at the ::: start of its EX stage. The minimum unavoidable bubbles for a load-use hazard with forwarding is ::: one. Without forwarding, the load-use gap grows to ::: two bubbles. Condition that excludes false hazards on the zero register: ::: ID/EX.Rt ≠ 0.