Exercises — Hazard detection units

• (a) Control hazard — the pipeline fetched an instruction before it knew whether the branch is taken.
• (b) Data hazard (RAW: sub reads $1, which add writes). In the reference figure, this is exactly what the arrow labelled "EX/MEM → ALU" resolves without any stall.
• (c) Structural hazard — two instructions compete for one hardware resource (the memory port) in the same cycle.

Answer: 2. Combinational logic has no memory; given the inputs (the register fields already latched in the pipeline registers) it produces stall/flush outputs within the cycle, so the correct control decision is ready before the next clock edge commits any value.

The detection condition is $\text{MemRead}\wedge ((\text{RegisterRd}=\text{RegisterRs})\vee (\text{RegisterRd}=\text{RegisterRt})).$ Substituting: $\text{MemRead}=1$ (true). Then $\text{RegisterRd}=2$, $\text{RegisterRs}=5$ → $2=5$ false; $\text{RegisterRd}=2$, $\text{RegisterRt}=2$ → $2=2$ true. The OR is true, the AND is true. Result: STALL asserted. The RegisterRt clause fired. In the reference figure this is the cyan arrow (ID/EX → HDU) reading MemRead, triggering the white "STALL" arrow.

• PCWrite = 0 — freezes the PC, so no new instruction is fetched.
• IF/ID_Write = 0 — freezes the IF/ID register, so the dependent instruction stays in ID to retry.
• Control_Mux = 0 — as defined above, selects the all-zeros input into ID/EX, inserting a NOP bubble so the frozen instruction doesn't corrupt EX.

Register $0 is hardwired to zero — a "load into $0" produces no usable value and nobody truly depends on it. So the guard RegisterRd ≠ 0 is added. Here $\text{RegisterRd}=0$, so the guard is false, the whole condition is false, and no stall is asserted. Proceed normally.

With the stall, the schedule is (matching the parent note). Only these two instructions exist in the program, so from cycle 4 onward nothing new is fetched — the IF column is empty simply because the program has ended, not because of a stall:

Why does IF show add again in cycle 3 rather than going empty? During the stall the HDU sets PCWrite = 0, so the PC does not advance — it still holds the address of add. The IF stage has no memory of its own; every cycle it simply fetches whatever address the PC currently points at. With the PC frozen on add's address, IF re-fetches the same add in cycle 3. Meanwhile IF/ID_Write = 0 freezes the IF/ID register, so the copy of add already in ID is held for its retry. The re-fetched add is harmless: it lands in IF/ID again next cycle and simply overwrites the identical value. So a frozen PC produces a repeated fetch, not an empty slot.

add reaches WB in cycle 7. One bubble was inserted (cycle 3's NOP). In cycle 5, lw's data is in MEM/WB and the forwarding unit feeds it into EX for add — this is the arrow labelled "MEM/WB → ALU" in the reference figure doing its job.

• (a) EX-hazard match with RegWrite → forward from EX/MEM (the arrow labelled "EX/MEM → ALU" in the reference figure). No stall.
• (b) No EX match, but MEM-hazard match with RegWrite → forward from MEM/WB (the arrow labelled "MEM/WB → ALU"). No stall.
• (c) Source of a load still in EX → data not ready → HDU stalls one cycle (the "STALL" arrow), then forwarding takes over.

Counting convention used on this page: the branch penalty is the number of wrong-path instructions that were fetched and must be discarded. The count depends on which stage first knows the branch outcome, because the pipeline keeps fetching one new instruction per cycle until then.

• Resolve in EX: the branch travels IF→ID→EX, and it only learns its outcome at the end of EX. By that point two younger instructions have been fetched (one during the branch's ID cycle, one during its EX cycle), both wrong → penalty = 2. (You will sometimes see "3" quoted — that convention also counts the cycle in which the correct target is finally fetched as lost, i.e. it measures lost cycles rather than discarded instructions. Same pipeline, different thing being counted. This page counts discarded instructions, so we use 2.)
• Resolve in ID: with a comparator and a target adder placed in ID, the outcome is known one stage earlier, so only one younger instruction (the PC+4 fetch during the branch's ID cycle) has been fetched → penalty = 1.

This is the "penalty 2→1" (or "3→1" under the lost-cycle convention) improvement the parent note describes. See 5.2.11-Branch-prediction for how prediction pushes this toward 0.

First the internal detection signal: $\text{Stall}=\text{MemRead}\wedge (\text{RegisterRd}\ne 0)\wedge ((\text{RegisterRd}=\text{RegisterRs})\vee (\text{RegisterRd}=\text{RegisterRt})).$ Then the HDU drives the full output interface from that one signal:

• $\text{PCWrite}=\neg \text{Stall}$ — so PCWrite = 0 exactly when Stall = 1 (freeze the PC).
• $\text{IF/ID\_Write}=\neg \text{Stall}$ — so IF/ID_Write = 0 exactly when Stall = 1 (hold the dependent instruction in ID).
• $\text{Control\_Mux}=\neg \text{Stall}$ — so Control_Mux = 0 exactly when Stall = 1 (inject the NOP bubble into ID/EX).

When Stall = 0 all three are 1 and the pipeline advances normally. This mirrors the Verilog sketch in the parent note, with the RegisterRd != 0 guard added and the two write-enables plus the bubble mux spelled out. It is purely combinational: no clocked storage, outputs valid within the cycle.

• I1→I2: I2 computes its address from $2, which I1 loads. When I1 is in EX (MemRead=1, RegisterRd=2) and I2 is in ID reading RegisterRs=2 → stall 1 cycle. Address computation cannot use un-arrived load data, and forwarding to the address ALU can't precede MEM.
• I2→I3: I3 reads $3 (loaded by I2) and $2. When I2 is in EX with MemRead=1, RegisterRd=3, and I3 is in ID reading $3 → stall 1 cycle. After the bubble, $3 forwards from MEM/WB; $2 (from I1, long done) forwards or reads normally.
• Total: 2 stalls (2 bubbles).

• Load-use stalls: $200\times \frac{1}{2}=100$ stall cycles.
• Branch flushes: $150\times 0.40=60$ flush cycles.
• Total penalty cycles $=100+60=160$.
• Total cycles $=1000(\text{base})+160=1160$.
• Effective CPI $=1160/1000=1.16$.

Interpretation: hazards added 16% overhead. Moving branch resolution earlier (or adding prediction) attacks the 60-cycle branch term; scheduling an independent instruction after each load attacks the 100-cycle stall term.

Move the independent sub between the load and its use:

lw   $2, 0($1)    ; I1
sub  $6, $7, $8   ; I3 (independent - fills the delay slot)
add  $4, $2, $5   ; I2 ($2's data is now ready via forwarding)

When add reaches ID, the lw is already in MEM (not EX), so MemRead in ID/EX is 0 for the compare — no stall condition — and $2 forwards from MEM/WB (the arrow labelled "MEM/WB → ALU" in the reference figure). Stalls: 0. This is compiler scheduling: the same job the HDU would otherwise do with a bubble, done for free by reordering.

Load-use is the only data hazard that forces a stall ::: because a load's data doesn't exist until after MEM, so no earlier stage can forward it in time for the very next instruction. Stall vs flush ::: a stall holds a still-valid instruction to retry later while nothing is discarded; a flush cancels a wrong-path instruction that must never execute. Why the HDU sits in ID ::: registers are read in ID, so source dependencies are known before EX would use stale data. The three stall signals ::: PCWrite=0 freezes the PC, IF/ID_Write=0 holds the instruction in ID, Control_Mux=0 injects a NOP bubble into ID/EX. Why a frozen PC causes IF to re-fetch the same instruction ::: IF has no memory of its own and simply fetches whatever address the PC holds, so a frozen PC yields a repeated fetch rather than an empty slot.