Exercises — Pipeline hazards — structural, data (RAW - WAR - WAW), control

RAW data hazard (I2 reads R1 which I1 must write first). It is the special load-use case. Plain forwarding cannot fully remove it: a load's value is only ready at the end of MEM (cycle 4), but the dependent ADD wants it in EX (also cycle 4). There is no earlier stage to forward from, so you need one bubble, then forward. See Forwarding and bypassing.

Structural hazard (resource conflict, not a value conflict). By-design cure: split the memory into a separate I-cache and D-cache (Harvard style) so IF and MEM never fight.

• RAW = Read After Write = true dependence (real data flow).
• WAR = Write After Read = anti-dependence (a name hazard).
• WAW = Write After Write = output dependence (a name hazard). Only RAW is a true dependence; WAR/WAW come from reusing register names and vanish with Register renaming.

Use $\text{CPI}=1+b\cdot m\cdot p$. Why this form? Only branches ($b$) can stall; only mispredicted ones ($m$) actually do; each costs $p$. $\text{CPI}=1+0.25\times 0.2\times 4=1+0.2=1.2.$

Use $\text{Speedup}=\frac{k}{1+s}$. Why: single-cycle spends $k$ stage-times per instruction; the pipeline spends $1+s$ cycles. $\text{Speedup}=\frac{5}{1+0.5}=\frac{5}{1.5}=3.\overline{3}\approx 3.33\times .$

$\text{CPI}=1+0.25\times 0.05\times 4=1+0.05=1.05.$ The branch stall term fell from $0.2$ to $0.05$ — see Branch prediction (static vs dynamic) for why dynamic prediction earns this.

With no prediction help, IF keeps fetching the fall-through instructions in c2 and c3 while the branch is in ID and EX. When the branch resolves taken in EX (c3), the 2 instructions fetched behind it (in IF at c2, c3) are wrong and get flushed. So $p=2$ cycles. Correctly predicted (not-taken and it is not-taken): $p=0$. The penalty only bites on the outcome the predictor missed.

Add each stall contribution to the ideal CPI of 1.

• Data: $s_{\text{data}}=0.15\times 1=0.15$.
• Control: $s_{\text{ctrl}}=b\cdot m\cdot p=0.2\times 0.1\times 3=0.06$.
• Structural: $s_{\text{struct}}=0$. $\text{CPI}=1+0.15+0.06+0=1.21.$

$s=0.21$, so $\text{Speedup}=\frac{5}{1.21}\approx 4.13\times$.

Eliminate load-use (e.g. compiler scheduling): remove $0.15$ → CPI $=1.06$. Halve $m$ to $0.05$: control term $=0.2\times 0.05\times 3=0.03$ → CPI $=1.18$. The load-use fix drops CPI to 1.06 vs 1.18 — removing load-use stalls helps far more here, because $0.15\gg 0.06$. Attack the biggest stall term first (this is Amdahl's Law thinking).

WAW (Write After Write / output dependence). The architectural R1 must end up holding I2's (later, in program order) value, but if MUL's WB lands after ADD's, R1 is left with the stale MUL result. Why the simple pipeline is immune: all instructions write in the same stage (WB) and flow in order, so writes retire in program order automatically. WAW only becomes real when write timing can be reordered (variable-latency EX or out-of-order retire). See Out-of-order execution and Tomasulo. Fix: Register renaming — give each write a fresh physical register, so I1 and I2 no longer share the name R1. WAW and WAR are name dependences; renaming dissolves them. Only RAW (true data flow) survives.

A WAR hazard needs a later instruction $j$ to write a register before an earlier instruction $i$ reads it. In our pipeline, reads happen in ID (early) and writes happen in WB (late), and instructions enter in program order. So $i$ (earlier) reaches its ID before $j$ (later) reaches its WB. The read always precedes the write — WAR is structurally impossible here. It only appears once writes can happen early or instructions issue out of order.

Compute CPI for each (control stalls only):

• 5-stage: ${\text{CPI}}_5=1+0.2\times 0.1\times 3=1.06$.
• 10-stage: ${\text{CPI}}_{10}=1+0.2\times 0.1\times 7=1.14$.

Performance $\propto f/\text{CPI}$. Let 5-stage frequency $=1$, so 10-stage $=2$. $\frac{{\text{Perf}}_{10}}{{\text{Perf}}_5}=\frac{2/1.14}{1/1.06}=\frac{2\times 1.06}{1.14}=\frac{2.12}{1.14}\approx 1.86\times .$ Yes, ~1.86× faster — the doubled frequency wins even though CPI rose slightly. But note the deeper pipeline only delivered $1.86\times$, not the naive $2\times$: the bigger branch penalty ate part of the frequency gain. That gap is exactly why deep pipelines demand excellent branch prediction. (See the CPI and performance equation.)

RAW is the only true dependence; WAR and WAW are name dependences. The one RAW forwarding cannot fully remove ::: the load-use hazard (needs 1 bubble first). Formula linking branches to CPI ::: $\text{CPI}=1+b\cdot m\cdot p$. Why WAR/WAW never happen in the plain in-order pipeline ::: reads are in ID (early), writes in WB (late), and instructions flow in program order. Fix that dissolves WAR and WAW ::: register renaming.