Superscalar execution: Exercises — Hardware deep dive

Before we start, here is the one formula that most problems lean on. We repeat it so no symbol is used before it is named.

Formula The IPC bottleneck formula

$IPC = min (W, min_{i} \frac{F _{i}}{p _{i}}, \frac{W \cdot ROB}{D \cdot L _{avg}})$ Reading each symbol in plain words:

$W$ = issue width — how many instructions the front-end can fetch/decode/rename per clock cycle. A hard ceiling.
$F_{i}$ = number of functional units of type $i$ (e.g. 3 integer ALUs → $F_{int} = 3$ ). A functional unit is a piece of hardware that actually does one kind of work.
$p_{i}$ = the fraction of instructions in the running program that need unit type $i$ . All the $p_{i}$ add up to $1$ .
$\frac{F _{i}}{p _{i}}$ = the throughput ceiling that unit type imposes. Think: "I can do $F_{i}$ of these per cycle, but only a fraction $p_{i}$ of my work is this type, so I could sustain $F_{i} / p_{i}$ total instructions per cycle before this unit chokes."
Edge case $p_{i} = 0$ : if a program uses none of unit type $i$ , that unit can never be a bottleneck, so we simply drop its term from the $min$ (formally $F_{i} /0 \to \infty$ , an infinitely high ceiling that can never be the smallest). Never write $F_{i} /0$ as a number.
$ROB$ = reorder buffer size — how many in-flight instructions the machine can track at once (its lookahead window).
$D$ = average dependency-chain length — how many instructions sit in a row where each waits on the previous one's result.
$L_{avg}$ = average instruction latency in cycles (how long one instruction takes from start to result). We always write the full subscript $L_{avg}$ — never a bare $L$ — so it is never confused with anything else.
The overall $min$ picks the tightest ceiling — the true bottleneck.

Level 1 — Recognition

Worked example L1.1 — Name the hazard

For each pair, name the dependency type (RAW / WAW / WAR):

(a) ADD R1, R2, R3   then   MUL R4, R1, R5
(b) ADD R1, R2, R3   then   SUB R1, R6, R7
(c) SUB R8, R1, R9   then   ADD R1, R6, R7

Also: which of these does register renaming eliminate?

Recall Solution L1.1

(a) RAW (Read After Write): the MUL reads R1 that ADD just wrote. This is a true data dependency — the value genuinely must flow. Renaming cannot remove it.
(b) WAW (Write After Write): both instructions write R1. A false (name-only) dependency. Renaming eliminates it by sending each write to a different physical register.
(c) WAR (Write After Read): the first reads R1, the second writes R1. A false (anti-)dependency. Renaming eliminates it so the writer doesn't clobber a value the reader still needs.
Renaming removes (b) and (c); (a) stays.

Recall Solution L1.2

"4-wide" = the front-end issue width $W = 4$ : at most 4 instructions are fetched/decoded/renamed per cycle.
"6 execution ports" = 6 places instructions can be sent to execute per cycle, i.e. the total execution back-end can accept up to 6/cycle (spread across the $F_{i}$ functional units).
The 4 is $W$ . Note the back-end (6) is wider than the front-end (4) here — a common design so the narrow front-end is never starved by the back-end.

Level 2 — Application

Recall Solution L2.1

Compute every ceiling, then take the min.

$W = 4$ .
Integer: $\frac{3}{0.4} = 7.5$
FP: $\frac{2}{0.2} = 10$
Memory: $\frac{2}{0.3} = 6.67$
Branch: $\frac{1}{0.1} = 10$ → tightest FU ceiling $= 6.67$ .
Dependency: $\frac{W \cdot ROB}{D \cdot L _{avg}} = \frac{4 \times 128}{3 \times 2} = \frac{512}{6} = 85.3$ . $IPC = min (4, 6.67, 85.3) = 4$ The front-end width is the bottleneck; the machine has plenty of units and lookahead.

Recall Solution L2.2

First, the FP edge case. This program has $p_{FP} = 0$ : no instruction ever uses an FP unit. From the formula's edge-case rule, $F_{FP} / p_{FP} = 2/0 \to \infty$ — an infinitely high ceiling that can never be the smallest — so we drop the FP term entirely and it plays no role below.

$W = 4$ .
Integer: $\frac{3}{0.3} = 10$
FP: $p_{FP} = 0 \Rightarrow$ term dropped (never the bottleneck).
Memory: $\frac{2}{0.6} = 3.33$ ← tightest
Branch: $\frac{1}{0.1} = 10$
Dependency: $\frac{W \cdot ROB}{D \cdot L _{avg}} = \frac{4 \times 128}{3 \times 2} = 85.3$ . $IPC = min (4, FU = 3.33 min (10, 3.33, 10), 85.3) = 3.33$ Bottleneck: memory ports. Only 2 load/store units, but 60% of work needs them.

Look at the figure: each colored bar is one ceiling. The shortest bar wins — that is what $min$ means visually. In L2.1 the width bar is shortest; in L2.2 the memory bar drops below the width bar and becomes the limiter. Note L2.2 has no FP bar at all — a dropped $p_{i} = 0$ term simply does not appear.

Level 3 — Analysis

Recall Solution L3.1

$W = 4$ .
FU ceilings unchanged (same 40/20/30/10 mix): $min (\frac{3}{0.4}, \frac{2}{0.2}, \frac{2}{0.3}, \frac{1}{0.1}) = min (7.5, 10, 6.67, 10) = 6.67$ (memory).
Dependency: $\frac{W \cdot ROB}{D \cdot L _{avg}} = \frac{4 \times 8}{4 \times 3} = \frac{32}{12} = 2.67$ . $IPC = min (4, 6.67, 2.67) = 2.67$ Now the dependency term dominates. Physically: the ROB (lookahead window) is so small the machine can't see far enough ahead to find independent work while long chains stall. The functional units sit idle waiting — plenty of execution muscle, no independent instructions to feed it.

Recall Solution L3.2

Current bottleneck (from L2.2) is memory: $F_{mem} / p_{mem} = 2/0.6 = 3.33$ . FP term is dropped ( $p_{FP} = 0$ ). We now show all three terms of the $min$ for each fix.

Fix A ( $W = 6$ ): only $W$ changes. FU ceilings are $min (\frac{3}{0.3}, \frac{2}{0.6}, \frac{1}{0.1}) = min (10, 3.33, 10) = 3.33$ . Dependency becomes $\frac{6 \times 128}{3 \times 2} = \frac{768}{6} = 128$ . So $IPC_{A} = min (6, 3.33, 128) = 3.33.$ Memory is still the smallest — widening the front-end and enlarging the window both raise their terms, but neither touches the memory ceiling. IPC stays 3.33; the silicon is wasted.
Fix B (3rd L/S unit): memory ceiling becomes $\frac{3}{0.6} = 5.0$ . FU ceilings $min (\frac{3}{0.3}, \frac{3}{0.6}, \frac{1}{0.1}) = min (10, 5.0, 10) = 5.0$ . Width $= 4$ , dependency $= \frac{4 \times 128}{3 \times 2} = 85.3$ . So $IPC_{B} = min (4, 5.0, 85.3) = 4 .$

Fix B works, raising IPC from 3.33 to 4 (now width-limited: the $4$ is the smallest of the three). Attack the actual bottleneck, not the biggest-sounding knob.

Level 4 — Synthesis

Recall Solution L4.1

Target: every ceiling $\geq 4$ , with $min = 4$ so width is the (cheapest) binding term. FP is absent ( $p_{FP} = 0$ , term dropped).

Width: need $W \geq 4$ . Choose $W = 4$ (smallest that admits IPC 4).
Memory ( $p = 0.5$ ): need $\frac{F _{mem}}{0.5} \geq 4 \Rightarrow F_{mem} \geq 2$ . Choose 2.
Integer ( $p = 0.3$ ): need $\frac{F _{int}}{0.3} \geq 4 \Rightarrow F_{int} \geq 1.2$ . Choose 2 (must be integer count, $1$ gives $1/0.3 = 3.33 < 4$ ).
Branch ( $p = 0.2$ ): need $\frac{F _{br}}{0.2} \geq 4 \Rightarrow F_{br} \geq 0.8$ . Choose 1. Check all terms: $min (W 4, m i n (4, 6.67, 5) = 4 min (2/0.5, 2/0.3, 1/0.2), dep ≫ 4) = 4$ . ✔ Minimal design: $W = 4$ , 2 mem, 2 int, 1 branch. Note integer needed 2 (not 1) purely because you can't buy a fractional unit.

Recall Solution L4.2

Physical registers available for renaming in-flight writers $= 192 - 32 = 160$ .
Each in-flight writer needs one. Fraction of in-flight instructions that write $= 0.70$ .
So the ROB can hold $N$ entries where $0.70 \times N \leq 160 \Rightarrow N \leq \frac{160}{0.70} = 228.6$ .
Largest usable ROB $= 228$ entries. Interpretation: if the ROB were built bigger than 228, the physical register file would run dry first — the two structures must be sized together (see Register Renaming and Reorder Buffer).

Level 5 — Mastery

Recall Solution L5.1

Design X: ceilings — $W = 6$ ; mem $2/0.5 = 4$ ; int $3/0.3 = 10$ ; branch $1/0.2 = 5$ ; dep $≫ 6$ . $IPC_{X} = min (6, 4, 10, 5, ≫ 6) = 4$ (memory-limited). Design Y: ceilings — $W = 4$ ; mem $3/0.5 = 6$ ; int $2/0.3 = 6.67$ ; branch $1/0.2 = 5$ ; dep $≫ 4$ . $IPC_{Y} = min (4, 6, 6.67, 5, ≫ 4) = 4$ (width-limited). Same IPC = 4 on this workload!

Ship for power: Design Y. It reaches IPC 4 with a narrower front-end ( $W = 4$ ). Front-end width is one of the most power-hungry parts of a core (wide fetch, wide decode, wide rename, more wakeup logic). Y burns less to hit the same throughput here — the sensible pick under a power budget.
When X wins — the alternate workload. Take a compute-heavy mix of 15% memory / 65% integer / 20% branch (still 0% FP). Recompute both designs on it:
- Design X ( $W = 6$ , 2 mem, 3 int, 1 branch): mem $\frac{2}{0.15} = 13.33$ ; int $\frac{3}{0.65} = 4.62$ ; branch $\frac{1}{0.2} = 5$ ; dep $≫ 6$ . So $IPC_{X} = min (6, 13.33, 4.62, 5, ≫ 6) = 4.62$ (integer-limited).
- Design Y ( $W = 4$ , 3 mem, 2 int, 1 branch): mem $\frac{3}{0.15} = 20$ ; int $\frac{2}{0.65} = 3.08$ ; branch $\frac{1}{0.2} = 5$ ; dep $≫ 4$ . So $IPC_{Y} = min (4, 20, 3.08, 5, ≫ 4) = 3.08$ (integer-limited).
- Now X wins, $4.62$ vs $3.08$ . With little memory traffic and lots of integer work, X's extra ALU (3 vs 2) and its wider front-end ( $6$ vs $4$ ) both pay off, while Y's 2 ALUs choke on the 65% integer stream. The moral: no design is "best" — the winner depends on the program's mix.

The figure below turns the first (50/30/20) comparison into bars. Read it as follows: for each design, the shortest bar is the ceiling that binds. Design X's memory bar (4) is its shortest — X is memory-limited. Design Y's width bar (4) is its shortest — Y is width-limited. The dashed line at IPC 4 shows both land on the same height by different routes, which is the whole point of the exercise.

Recall Solution L5.2

Work in "instructions per branch" as the natural chunk.

Fraction of instructions that are branches $= 0.20$ , so on average there is 1 branch every $1/0.20 = 5$ instructions.
Misprediction rate $= 1 - 0.92 = 0.08$ . So a mispredict happens every $5/0.08 = 62.5$ instructions on average.
Cycles for those 62.5 instructions: useful cycles $= 62.5/4 = 15.625$ (running at IPC 4), plus one penalty $= 14$ cycles.
Effective IPC $= \frac{62.5}{15.625 + 14} = \frac{62.5}{29.625} = 2.11$ . Lesson: an 8% miss rate nearly halves real throughput on a deep-pipeline wide machine — which is exactly why branch prediction accuracy is worth so much silicon. Compare this dynamic-scheduling cost with the compiler-scheduled VLIW Architecture approach, and note that Tomasulo's Algorithm provides the out-of-order engine that keeps IPC near $W$ between mispredicts.