Exercises — Structural hazards

$\text{CPI}=1+fs$ (read before Level 5)

• $f=0$ or $s=0$ → $\text{CPI}=1$: no real hazard, ideal pipeline.
• $f=1,s=1$ → $\text{CPI}=2$: every instruction stalls once, throughput halved.
• What if $f\cdot s>1$? Totally allowed — it just means the average instruction eats more than one bubble (e.g. $f=1,s=4$ gives $\text{CPI}=5$). CPI can grow up to the pipeline depth (full serialisation); it never goes below $1$ because $f,s\ge 0$.
• Negative stalls are impossible: $f\ge 0$ and $s\ge 0$ by definition (you cannot un-stall), so $\text{CPI}\ge 1$ always. If a formula ever hands you $\text{CPI}<1$ you made a sign error.

Read the chart column by column (each column is one clock cycle). A structural hazard is two stages needing the same physical unit in the same column — that is exactly the pair of red boxes in Figure 1.

• Cycle 4: I1 is in MEM (touching memory for data) and I4 is in IF (touching memory to fetch its instruction).
• The single memory port can serve only one of them.

Answer: The hazard is in cycle 4; the conflict is between I1's MEM stage and I4's IF stage, both demanding the single memory port.

• (a) Data hazard — it is about information/order (a value produced then consumed), not a shared box of hardware.
• (b) Structural hazard — two stages want the same physical adder in one cycle.
• (c) Control hazard — the decision of what to fetch next is not resolved.

Rule of thumb: if you can fix it by buying another copy of a hardware unit, it was structural.

Use the boxed model from the top of this page, ${\text{CPI}}_{\text{actual}}={\text{CPI}}_{\text{ideal}}+fs$. Every symbol first:

• $f=f_{\text{mem}}=0.30$ is the fraction of instructions that trigger the hazard.
• $s=1$ cycle is the stall penalty per hazard.

$\text{Stalls per instruction}=f\times s=0.30\times 1=0.30$ ${\text{CPI}}_{\text{actual}}={\text{CPI}}_{\text{ideal}}+fs=1.0+0.30=1.30$

Now use the "$\text{Performance}\propto 1/\text{CPI}$ at equal clock" result derived at the top. Same machine, same clock, so the speed ratio of the hazarded pipeline to the ideal one is: $\frac{{\text{Perf}}_{\text{hazard}}}{{\text{Perf}}_{\text{ideal}}}=\frac{{\text{CPI}}_{\text{ideal}}}{{\text{CPI}}_{\text{actual}}}=\frac{1.0}{1.30}\approx 0.769$

Answer: ${\text{CPI}}_{\text{actual}}=1.30$; performance lost $=1-0.769=0.231\approx 23\%$ slower.

In the boxed model, eliminating the memory hazard sets its $f$ to $0$, so that term vanishes. Only the ALU term remains: ${\text{CPI}}_{\text{actual}}=1.0+f_{\text{alu}}\times 1=1.0+0.05=1.05$

Compare with the old $1.30$. Again same clock, so we use $\text{Perf}\propto 1/\text{CPI}$; the speedup of the new design over the old is the ratio of their CPIs: $\frac{{\text{Perf}}_{\text{new}}}{{\text{Perf}}_{\text{old}}}=\frac{{\text{CPI}}_{\text{old}}}{{\text{CPI}}_{\text{new}}}=\frac{1.30}{1.05}\approx 1.238$

Answer: ${\text{CPI}}_{\text{actual}}=1.05$; the redesign makes the machine about 24% faster. Yes, it helped.

Why the "8" of ideal issue. In a pipeline, a new instruction enters IF every clock and, with no hazards, exactly one instruction finishes every clock. So issuing 8 instructions ideally takes 8 issue slots — one cycle each. That is where the bare $8$ comes from (it is the ideal-issue count, before any bubbles; start-up fill is excluded as the problem states).

What causes each stall: when a load reaches MEM (a red box in Figure 2), the instruction entering IF that same cycle must wait. The first load (L1) reaches MEM in cycle 4 while L4 wants IF — so L4 stalls. Every subsequent load likewise pushes one stall onto the instruction behind it.

Counting inside the window: Loads L1…L8 each want to generate one MEM/IF collision with a follower. The last load L8 has no follower inside these 8 — its induced stall would land on an instruction outside the window — so it contributes no stall here. That leaves collisions from L1…L7 → 7 stall cycles.

$\text{cycles}=\underset{\text{ideal issue}}{\underbrace{8}}+\underset{\text{stalls}}{\underbrace{7}}=15,\text{CPI}=\frac{15}{8}=1.875$

Answer: 7 stall cycles inside the window; $\text{CPI}=15/8=1.875$.

Sanity check with the model: in the steady state (infinite stream) every load stalls, so $f=1.0,s=1$ gives $\text{CPI}\to 1+1.0\times 1=2.0$. Our windowed $1.875$ is just below $2.0$ because L8's stall spilled out of the window — exactly what we expect. ✓

Loads at I1, I3, I5, I7 → 4 loads, each induces 1 stall on the instruction behind it (I2, I4, I6, I8 respectively — all inside the window). So 4 stall cycles.

$\text{cycles}=8+4=12,\text{CPI}=\frac{12}{8}=1.5$

Cross-check with the boxed model, $f=4/8=0.5$, $s=1$: $\text{CPI}=1+0.5\times 1=1.5✓$

Answer: 4 stalls; $\text{CPI}=1.5$.

Baseline CPI — because the three hazards never hit the same instruction, their per-instruction stall contributions $f_i{s}_i$ just add on top of the ideal (this is the boxed model with several terms): $\text{CPI}=1+{\sum }_i{f}_i{s}_i=1+(0.30\cdot 1+0.05\cdot 1+0.02\cdot 1)=1+0.37=1.37$

Why "benefit = $fs$". Removing a hazard deletes exactly its term $f_i{s}_i$ from the CPI sum — so the CPI you save by fixing hazard $i$ is precisely $f_i{s}_i$. That is the benefit of the fix. Here every $s_i=1$, so benefit $=f_i$.

Why "benefit per area" is the right metric. With a hard area budget you want the most CPI removed per area unit spent — the classic bang-for-buck ratio $\frac{\text{CPI removed}}{\text{area}}$. Rank the fixes by it:

Budget = 5. The memory fix (area 10) is unaffordable outright. Within 5 units you can take ALU (1) + write port (4) = 5 units exactly:

• CPI removed $=0.05+0.02=0.07$ → new $\text{CPI}=1.37-0.07=1.30$.

Alternative: ALU alone (1 unit) removes 0.05 → $\text{CPI}=1.32$, leaving 4 units unused. Taking both ALU + write port spends the whole budget and reaches $\text{CPI}=1.30$, the best achievable within 5 units.

Answer: Buy the ALU adder + register write port (total area 5), reaching $\text{CPI}=1.30$. The memory fix, though it removes the biggest single stall, doesn't fit the budget.

A: ${\text{CPI}}_A=1.0$. B: ${\text{CPI}}_B=1+f\cdot 1=1+f$. Same clock, so (from the top-of-page result) equal performance means equal CPI: $1+f_{\text{eq}}=1.0\Rightarrow f_{\text{eq}}=0.$

Interpretation: with a nonzero hazard frequency, B is always slower than the hazard-free Harvard machine. B only ties A when $f_{\text{eq}}=0$ — i.e. never in practice. So the choice is purely performance (A) vs area/power (B): B is justified only when the 10 extra area units and power matter more than the guaranteed $\approx 23\%$ slowdown (at $f=0.30$).

Answer: $f_{\text{eq}}=0$; B can never match A on speed, so pick B strictly for area/power reasons.

Demand per cycle for two 2-source, 1-destination instructions issued together:

• Reads needed: each op reads 2 source registers, two ops → $2\times 2=4$ register reads in one cycle.
• Writes needed: each op writes 1 destination, two ops → $2\times 1=2$ register writes when both reach WB together.

(a) Read-port hazard? The file has 3 read ports but the cycle demands 4. $4>3$, so yes, there is a read-port structural hazard — the file physically cannot deliver 4 source operands at once, so one instruction must stall (or issue must be narrowed to one op that cycle).

(b) Write-port hazard? The file has 1 write port but two destinations want to commit in the same WB cycle. $2>1$, so yes, there is a write-port structural hazard — the two writes must be serialised, stalling one.

(c) Minimum ports to never stall for dual 2-source/1-dest issue: enough read ports for all sources ($2\times 2=4$) and enough write ports for all destinations ($2\times 1=2$). So the register file needs 4 read ports and 2 write ports (in general, $2n$ read and $n$ write ports for $n$-wide issue of 2-source/1-dest ops).

Answer: (a) yes — need 4 reads, have 3; (b) yes — need 2 writes, have 1; (c) 4 read ports, 2 write ports. This is exactly why wider Superscalar Processors pay steeply — port count scales with issue width, and each extra port adds area and power.

• (a) $f=0\Rightarrow \text{CPI}=1$: no hazards ever, ideal pipeline, one instruction finishes per cycle. This is the Harvard/split-cache dream.
• (b) $f=1,s=1\Rightarrow \text{CPI}=2$: every instruction stalls exactly one cycle. The diagram is a bubble after every instruction — throughput halved (matches Ex 3.1's steady-state limit of 2.0 ✓).
• (c) $s=0\Rightarrow \text{CPI}=1$: a "hazard" that costs zero cycles is no hazard at all — the resource conflict was resolved for free (e.g. a cheap duplicated unit). Frequency $f$ becomes irrelevant.
• (d) $f=1,s=4$ on a 5-stage pipe $\Rightarrow \text{CPI}=5$: every instruction waits 4 cycles, so instruction $k+1$ only starts after instruction $k$ has fully drained. That is serial execution — pipelining's overlap has been completely destroyed. CPI equals the pipeline depth, the worst case. Note $f\cdot s=4>1$ here, which is perfectly valid: the average instruction eats more than one bubble.

Answer: (a) ideal, CPI 1; (b) CPI 2, one bubble per instruction; (c) not a real hazard, CPI 1; (d) CPI 5 = fully serialised, no pipeline benefit remains.

Structural hazard is defined by sharing a … ::: physical hardware resource in the same cycle. Formula for CPI with hazards ::: $\text{CPI}=1+fs$. Why is performance $\propto 1/\text{CPI}$ ::: time per instruction $=\text{CPI}\times$ cycle time; performance is its reciprocal, so at equal clock bigger CPI = slower. Ex 2.1 answer ::: CPI = 1.30, about 23% slower. Ex 3.2 answer ::: CPI = 1.5. Ex 4.1 best-within-budget CPI ::: 1.30 (ALU + write-port fixes). Dual 2-source/1-dest issue needs how many ports ::: 4 read, 2 write. Limiting CPI when $f=1,s=4$ on 5 stages ::: 5 (fully serial).