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

(a) Structural — two instructions demand the same hardware (one memory port) at once. (b) Data hazard (RAW) — add reads $t0 that lw will write; specifically the load-use flavour. (c) Control hazard — the next PC is unknown until the branch resolves. Why: structural = hardware clash, data = value-not-ready, control = which-PC-unknown. Match the cause, not the symptom.

Registers are read in ID. Results are written back in WB. Why it matters: the gap between "read in ID" and "written in WB" is exactly the window where a RAW hazard can bite — the reader can arrive before the writer finishes.

False. The load's value is born at the end of MEM (cycle 4 for the load), but the consumer needs it at the start of EX (cycle 3 of the pipeline timeline) — one cycle earlier in absolute time. Forwarding moves data forward in time only, so it cannot help. At least 1 stall remains.

1 bubble. lw's value exists only at the end of MEM (cycle 4). add must be in EX no earlier than cycle 4, so it holds in ID for one extra cycle. Then the MEM/WB value is forwarded into add's EX. See the figure — this is a legal forward (rightward in time), unlike the illegal one from cycle 4 → cycle 3.

0 bubbles.

At cycle 4, add is in EX and sub is in MEM, so $t0 sits in the EX/MEM latch. Forward EX/MEM → ALU input A. An ALU producer's value is ready one cycle earlier than a load's, so no stall is needed.

Formula: $\text{CPI}=1+b\cdot m\cdot p$. (a) $\text{CPI}=1+0.20\cdot 1\cdot 3=1.6$. (b) $\text{CPI}=1+0.20\cdot 0.08\cdot 3=1+0.048=1.048$. Why: each branch pays $p$ only when mispredicted (probability $m$); branches are a fraction $b$ of all instructions, so multiply the probabilities and add to the ideal 1.

Rule: predict T if state ≥ 10. Taken → increment (cap 11); Not-taken → decrement (floor 00).

Mispredictions = 3 (the two warm-up misses, plus the single NT anomaly). Crucially, the lone NT at step 4 did not flip the long-run guess — the counter only dropped from 11 to 10, still "predict T". That is the hysteresis 2 bits buys you.

1-bit: predict whatever happened last time.

1-bit mispredictions = 3. Here they tie on this short trace, but note the pattern of failure: the 1-bit predictor mispredicts twice around the single NT (step 4 exit and step 5 re-entry), whereas the 2-bit predictor only paid for the exit and immediately recovered on step 5. On a longer loop the 2-bit predictor wins because it costs ~1 miss per loop-exit instead of ~2.

Per 100-outcome loop:

• 2-bit: the counter sits at 11 (strong-T). The single NT on exit is a miss and drops it to 10; the very next T is still predicted correctly (top bit still 1) and pushes back to 11. So 1 miss per 100 → $m=0.01=1\%$.
• 1-bit: the exit NT is a miss (predicted T), and it flips the predictor to "NT"; the next iteration's first T is then also a miss (predicted NT), flipping it back. So 2 misses per 100 → $m=0.02=2\%$. Why the 2-bit halves it: the hysteresis absorbs the single anomaly without changing the long-run prediction — exactly the point of a second bit.

Build CPI as ideal + each independent penalty source (they don't overlap here):

• Load-use stalls: fraction of instructions that stall = $0.20\times 0.40=0.08$, each costs 1 cycle → $+0.08$.
• Branch mispredicts: $b\cdot m\cdot p=0.15\times 0.05\times 2=0.015$ → $+0.015$. $\text{CPI}=1+0.08+0.015=1.095$ Why add them: each hazard type independently injects bubbles; total stall-cycles-per-instruction is the sum of the per-source expected stalls. See Amdahl's Law and CPI analysis for the general additive-overhead model.

With load-use hidden, only branch penalty remains: ${\text{CPI}}_{\text{new}}=1+0.015=1.015$ Speedup $=\frac{{\text{CPI}}_{\text{old}}}{{\text{CPI}}_{\text{new}}}=\frac{1.095}{1.015}\approx 1.0788$ (≈ 7.9% faster). Why: removing $0.08$ stall-cycles/instr shrinks the divisor. Same clock, same instruction count, fewer wasted cycles → higher throughput.

Yes — that specific forward becomes unnecessary. The MEM-hazard case is a producer that reaches WB in the same cycle the consumer is in ID:

If WB writes in the first half of cycle 5 and ID reads in the second half of cycle 5, the register file already holds the new value when the consumer reads — no wire needed. This is the classic "write in first half, read in second half" trick. But the closer EX-hazard (1-ahead) still needs forwarding: there the producer is only in MEM (not WB) when the consumer is in EX, so the value isn't in the register file yet. Conclusion: split-cycle register access removes the 2-ahead forward but not the 1-ahead forward, and not the load-use stall.

A consumer needs its operand at the start of EX. List producers by when their result is born:

• ALU op (add,sub,…): result born end of EX. The immediately-following instruction is in EX exactly one cycle later, so the value (in EX/MEM) can be forwarded → no stall. ✓
• 2-ahead producer: reaches WB while consumer is in ID; split-cycle register access delivers it → no stall, no forward. ✓
• Load (lw): result born end of MEM — one cycle later than an ALU result. The immediately-following consumer would need it in EX before it exists. No forward can reach into the past → ≥1 stall is forced. ✗ Every producer either delivers in time (ALU, 2-ahead) or is a load. Therefore the load-use hazard is the unique unavoidable single-gap stall. ∎ Why this is the deep point: stalls aren't arbitrary — they are exactly the cases where "value born" is later in absolute time than "value needed." Everything else is a wiring problem, solvable by a mux.

Both replace "wait for the value to travel through the register file" with "deliver the value the moment it is computed, tagged so only the waiters that need it grab it." In-order forwarding is a fixed set of wires (EX/MEM and MEM/WB latches → ALU inputs) governed by the RegWrite/rd comparisons. Tomasulo generalizes this to a common data bus: any functional unit broadcasts its result with a tag, and every reservation station watching that tag latches the value simultaneously — forwarding to an arbitrary number of consumers, out of program order. Forwarding is Tomasulo with a hard-wired, 1-or-2-deep forwarding network; Tomasulo is forwarding scaled to a dynamic, associative broadcast. See also Caches and memory hierarchy for how memory-side latency reshapes when values are "born."

Load-use minimum bubbles with full forwarding? ::: 1 CPI overhead formula for branches? ::: $b\cdot m\cdot p$ Which forward does split-cycle register access eliminate? ::: the 2-instructions-ahead (MEM/WB → ID) one Steady-state loop-exit misprediction: 1-bit vs 2-bit? ::: 2 misses vs 1 miss per loop