Exercises — Data hazards and forwarding - bypassing

A RAW hazard requires $\text{Rd}(i)=\text{Rs}(j)\text{ or }\text{Rt}(j)$ and $\text{Rd}(i)\ne \text{R0}$.

• (a) Rd = R1, next reads R1. Hazard. ✅
• (b) Rd = R1, next reads R6, R5 — never R1. No hazard.
• (c) Destination is R0 (hardwired zero, writing it is a no-op). Reading R0 always gives 0, so no real hazard.
• (d) LW writes R1, next reads R1. Hazard — and a special one (a load-use hazard, more on that in L3).

• Sources are read in the ID stage.
• ALU results are written in the WB stage. This gap (read early, write late) is the entire reason hazards exist.

ADD writes R1 during its WB stage. SUB reads R1 during its ID stage. Line up the cycles: ADD occupies IF ID EX MEM WB in cycles 1–5. SUB naturally has ID in cycle 3. With the write-then-read register file, SUB may read in the same cycle WB happens (cycle 5) because the write completes first. So SUB's ID must be pushed to cycle 5. Its natural ID was cycle 3 → push to cycle 5 → 2 bubbles. ✅

$\text{stalls}=(\text{WB cycle of }i)-(\text{natural ID cycle of }j)=5-3=2$

ADD's ALU result exists at the end of its EX (cycle 3), sitting in the EX/MEM register in cycle 4. SUB needs it at the start of its EX (cycle 4). The forwarding wire delivers it exactly on time. 0 stalls. ✅ This is the whole payoff of forwarding for ALU→ALU dependencies.

Cycle-align: I1 EX in cycle 3, so I1 is in MEM (cycle 4) and WB (cycle 5). I3 EX is in cycle 5. In cycle 5, I1's result has moved into the MEM/WB register (it left EX/MEM two cycles ago). So SUB forwards from MEM/WB. 0 stalls — the independent OR conveniently filled the gap.

LW's data appears at the end of MEM (cycle 4). ADD needs it at the start of its EX (cycle 4). These overlap in time — you cannot forward a value backward in the same cycle before it exists. So insert 1 bubble: push ADD's EX to cycle 5. Now LW's data is in the MEM/WB register and forwards cleanly. 1 stall, forwarded from MEM/WB. ✅ This is the one hazard forwarding alone cannot fully hide — see 6.2.03-Compiler-optimization-techniques for how compilers reorder code to fill this slot.

Cycle-align: I2 EX in cycle 4 → its result is in EX/MEM in cycle 5. I1's older result is in MEM/WB in cycle 5. I3's EX is cycle 5. SUB must read the most recent R1, which is I2's. The forwarding unit uses the priority rule: EX/MEM forwarding overrides MEM/WB. So forward from EX/MEM (I2's value). Using MEM/WB would grab the stale I1 value — a subtle bug. ✅

Check the EX/MEM condition for input A (the Rs side): $\text{RegWrite}=1\wedge \text{Rd}=5\ne 0\wedge \text{Rd}=5=\text{Rs}=5$ → all true. So ALU input A is forwarded from EX/MEM. MEM/WB also matches, but priority gives EX/MEM. Input B: Rt = 9, matches neither Rd = 5 → input B reads normally from the register file.

Dependencies:

• I3 uses R2 (from I1) and R3 (from I2).
• I4 uses R4 (from I3).

Check each:

• I2→I3 (R3): I2 is a load, I3 is the immediately next instruction using it → classic load-use → 1 stall, then forward from MEM/WB.
• I1→I3 (R2): I1's data is available long before I3 needs it (I3 is 2 instructions later, plus the stall) → forwards with no extra stall.
• I3→I4 (R4): ALU result → store. The store needs R4 for its MEM stage; forwarding delivers it in time → 0 stalls.

Total = 1 stall cycle. ✅ Only the tight load-use pair (I2→I3) costs anything.

Move an independent instruction into the load-use gap. Here we can swap so both loads finish before the dependent ADD... but they already are adjacent. The trick is to separate the second load from its use:

LW  R2, 0(R1)    # I1
LW  R3, 4(R1)    # I2
ADD R4, R2, R3   # I3  -- still tight on R3

With only these four instructions there is no independent instruction to hoist, so the honest answer is: 1 stall is irreducible for this exact block. To reach 0, the compiler must find independent work from a larger window — e.g. moving a later address computation up:

LW  R2, 0(R1)
LW  R3, 4(R1)
ADD R7, R1, R1   # independent filler hoisted here
ADD R4, R2, R3   # R3 now ready via MEM/WB forward, 0 stalls
SW  R4, 8(R1)

0 stalls. ✅ This is exactly what instruction scheduling does.

CPI = total cycles ÷ instructions.

• Base cycles (ideal fill/drain) $=100+4=104$.
• Without forwarding: add $30\times 2=60$ stall cycles → $104+60=164$ cycles. $\text{CPI}=164/100=1.64$.
• With forwarding: stalls removed → $104$ cycles. $\text{CPI}=104/100=1.04$.
• Speedup $=164/104\approx 1.577$. ✅

Method carried over from 5.2.09-Pipeline-performance-analysis.

• I1→I2 (R1): load-use, I2 immediately follows → 1 stall, then MEM/WB forward.
• I2→I3 (R2): ALU→ALU adjacent → forward EX/MEM → 0 stalls.
• I3→I4 (R3): ALU→ALU adjacent → forward EX/MEM → 0 stalls.
• I1→I3 (R1) and I2→I4 (R2): two instructions apart → data ready, 0 stalls.

Total stalls = 1. Cycles = base fill/drain $(4+4=8)$ + 1 stall = 9 cycles. ✅

ADD R1, R2, R3   # I1
OR  R6, R7, R8   # I2  (independent)
SUB R4, R1, R5   # I3  needs R1

From Exercise 2.3, I3 gets R1 from MEM/WB (I1 is in WB when I3 is in EX). Remove that path and I3 can no longer be fed → it must stall 1 cycle until the register file itself provides R1 via write-then-read. So dropping MEM/WB forwarding trades area for a stall on any dependency exactly 2 instructions apart. ✅

ALU→ALU dependency, no forwarding, how many stalls ::: 2 Load-use dependency, with full forwarding, how many stalls ::: 1 When two writes target the same register, which path wins ::: EX/MEM (most recent) Which stage reads source registers ::: ID Which pipeline register feeds a same-cycle EX→next-EX forward ::: EX/MEM