Superscalar — multiple execution units: Exercises

Before we start, one shared picture of the tools we will reuse. Every formula below is earned in the parent note; here we only apply and stress-test it.

Here $N_{inst}$ = number of instructions actually run, $CPI$ = average Cycles Per Instruction, $T_{cycle}$ = one clock tick in seconds, $IPC$ = Instructions Per Cycle (the reciprocal), $N$ = issue width = how many instructions the machine can launch into execution units in one cycle, and $p$ = the parallel fraction just defined above.

Figure — Superscalar — multiple execution units

How to read Figure 1. The top block is a scalar core: a single horizontal lane (one execution unit), so at most one orange arrow — one instruction — moves through per clock cycle, i.e. IPC $\leq 1$ . The bottom three stacked blocks are a superscalar core of width $N = 3$ : three parallel lanes (three execution units), so up to three orange arrows advance in the same cycle, i.e. IPC $\leq 3$ . Reading left-to-right is the passage of one clock cycle; reading top-to-bottom is the extra lanes width buys you.

Level 1 — Recognition

Exercise 1.1 (L1)

A CPU can dispatch at most 4 instructions to its execution units every clock cycle. What is this number called, and what does it place a ceiling on?

Recall Solution 1.1

WHAT we did: matched a description to a defined term. The number 4 is the issue width $N$ . It is the hard ceiling on IPC: since you cannot finish more instructions than you start, $IPC \leq N = 4$ . WHY: every instruction that retires must first have been issued into some unit, so the launch rate bounds the completion rate.

Exercise 1.2 (L1)

A processor measures $CPI = 0.5$ . Is this machine scalar or superscalar? Give its IPC.

Recall Solution 1.2

WHAT we did: converted CPI to IPC with the reciprocal link. $IPC = \frac{1}{CPI} = \frac{1}{0.5} = 2$ . A scalar pipeline caps IPC at 1 (CPI $\geq 1$ ). Here IPC $= 2 > 1$ , so it must be superscalar — it is completing two instructions per cycle on average. WHY CPI $< 1$ is valid: CPI is cycles per instruction averaged over instructions. If two instructions finish in the same single cycle, that cycle is "shared" by two instructions, so each is charged only half a cycle — an average of $0.5$ . Only a single-issue machine is forced to spend a whole cycle per instruction; parallel launch lets the average dip below 1.

Level 2 — Application

Exercise 2.1 (L2)

A program runs $N_{inst} = 6, 000$ instructions on a CPU with $CPI = 1.5$ and a clock period $T_{cycle} = 0.4 ns$ . Find the runtime $T$ in microseconds.

Recall Solution 2.1

Plug straight into the runtime equation: $T = N_{inst} \times CPI \times T_{cycle} = 6000 \times 1.5 \times 0.4 ns$ $T = 6000 \times 0.6 ns = 3600 ns = 3.6 μ s$ WHY this order: $6000 \times 1.5 = 9000$ cycles total, then $9000 \times 0.4 ns$ converts cycles into time. Units cancel: (instructions) $\times$ (cycles/instruction) $\times$ (ns/cycle) = ns.

Exercise 2.2 (L2)

Half of a workload is perfectly parallel and half is a strict dependency chain, so $p = 0.5$ . The core is $N = 4$ wide. What effective IPC do you sustain?

Recall Solution 2.2

Use the parallel-ceiling formula: $IPC_{eff} = \frac{1}{( 1 - p ) + \frac{p}{N}} = \frac{1}{0.5 + \frac{0.5}{4}} = \frac{1}{0.5 + 0.125} = \frac{1}{0.625} = 1.6$ WHY the answer is so far below 4: the serial half pays full price ( $0.5$ ) and cannot be sped up at all. Even with infinite lanes the parallel half shrinks to 0, giving a hard cap of $1/0.5 = 2$ . So width 4 gets you $1.6$ , not $4$ .

Exercise 2.3 (L2)

Sanity-check the parallel-ceiling formula at its four extremes. Evaluate $IPC_{eff}$ for (a) $p = 1$ , any $N$ ; (b) $p = 0$ , any $N$ ; (c) $N = 1$ , any $p$ ; (d) $p = 0.5$ , $N \to \infty$ .

Recall Solution 2.3

Substitute each edge into $IPC_{eff} = \frac{1}{( 1 - p ) + p / N}$ and read the picture.

(a) $p = 1$ (fully parallel): $\frac{1}{0 + 1/ N} = N$ . Every instruction shares the lanes → you hit the peak IPC $= N$ . This is the best case.
(b) $p = 0$ (one dependency chain): $\frac{1}{1 + 0} = 1$ , for any $N$ . Width is useless when nothing is independent — extra lanes stand idle (Worked Example 2 in the parent).
(c) $N = 1$ (scalar): $\frac{1}{( 1 - p ) + p} = \frac{1}{1} = 1$ , for any $p$ . With one lane there is nowhere to run parallel work, so IPC collapses to 1 regardless of how parallel the code is.
(d) $p = 0.5$ , $N \to \infty$ : $p / N \to 0$ , so $\frac{1}{0.5 + 0} = 2$ . Even with infinite lanes the serial half caps you at $1/ (1 - p) = 2$ . The serial fraction sets the hard ceiling. WHY this matters: these four corners are exactly Amdahl's Law. They tell you when to spend transistors on width (large $p$ ) and when not to bother (small $p$ ).

Level 3 — Analysis

Exercise 3.1 (L3)

Given this code on an in-order, 2-wide core (each op = 1 cycle latency, result available the next cycle), fill in the issue schedule and compute IPC:

I1: r1 = r2 + r3
I2: r4 = r1 + r5     (needs r1)
I3: r6 = r7 + r8     (independent)
I4: r9 = r4 + r6     (needs r4 and r6)

Recall Solution 3.1

Trace it cycle by cycle. In-order means we may not skip ahead past a stalled instruction, but we can pair the stalled one's independent neighbour if the neighbour is next in line.

Cycle	Issued	Why
1	I1 only	I2 needs r1 (not ready until end of C1). I3 is behind I2 in program order → in-order cannot let I3 jump over the stalled I2. So only I1 issues.
2	I2, I3	r1 now ready → I2 issues. I3 independent and next in line → pairs with I2. Both fit in 2 wide.
3	I4	needs r4 (from I2, ready end C2) and r6 (from I3, ready end C2) → both ready in C3.

Total = 3 cycles for 4 instructions, so $IPC = 4/3 \approx 1.33$ . WHAT the numbers say: the in-order rule cost us a cycle — I3 was ready in cycle 1 but had to wait behind I2.

Exercise 3.2 (L3)

Same code as 3.1, but now the core is out-of-order, 2-wide. What is the new schedule and IPC? What single feature bought the improvement?

Recall Solution 3.2

Out-of-order may let a ready instruction overtake a stalled one.

Cycle	Issued	Why
1	I1, I3	I1 ready; I3 independent and now allowed to jump ahead of the stalled I2. Fill both lanes.
2	I2, —	I2's r1 ready end of C1. I4 still needs r4 (produced by I2 this cycle) → not ready. Only I2 issues.
3	I4	r4 (from I2, C2) and r6 (from I3, C1) both ready.

Total = 3 cycles, IPC $= 4/3 \approx 1.33$ — same as in-order here, because I4's chain (I1→I2→I4) is the real bottleneck. The reorder only moved I3 earlier; it did not shorten the critical dependency chain. Feature responsible: Out-of-Order Execution scheduling, made safe by the Reorder Buffer (ROB) which retires in program order.

Level 4 — Synthesis

Exercise 4.1 (L4)

This code has a false dependency. On a 2-wide core show (a) the naive in-order IPC and (b) the IPC after Register Renaming, and explain the mechanism.

I1: r1 = r2 + r3
I2: r1 = r4 + r5     (writes r1 again; values independent of I1)
I3: r6 = r1 + r7     (needs the r1 from I2)

Recall Solution 4.1

(a) Naive: a hardware that trusts register names sees I1 and I2 both writing r1 — a WAW hazard — and serializes them for safety. Schedule:

Cycle	Issued
1	I1
2	I2
3	I3 (needs I2's r1)

3 cycles for 3 instructions → IPC $= 3/3 = 1$ . No parallelism gained.

(b) With renaming: rename I2's destination to a fresh physical register, say p7, and I1's to p3. Now I1 (→p3) and I2 (→p7) have no naming clash and their inputs are all ready → they issue together in cycle 1. I3 reads I2's value (p7), ready in cycle 2.

Cycle	Issued
1	I1, I2
2	I3

2 cycles for 3 instructions → IPC $= 3/2 = 1.5$ . Mechanism: the WAW conflict was a naming artifact, not real data flow; mapping the two writes of r1 to different physical registers dissolves it. See Data Hazards (RAW WAR WAW).

How to read Figure 2. The top pair of teal boxes is the before case: I1 and I2 both name their destination r1, so the hardware sees a name clash (the orange arrow marks the forced serialization) and runs them one after the other. The bottom pair of plum boxes is the after case: renaming sends I1 to physical register p3 and I2 to p7, so there is no shared name — the double-headed orange arrow shows they now issue side by side in the same cycle, lifting IPC to 2.

Exercise 4.2 (L4)

A 4-wide OoO core sustains IPC $= 2.0$ at clock $T_{cycle} = 0.5 ns$ . A competing 2-wide core sustains IPC $= 1.5$ but at a faster clock $T_{cycle} = 0.3 ns$ . For a program of $N_{inst} = 1, 000, 000$ instructions, which finishes first?

Recall Solution 4.2

WHY IPC lands in the denominator: start from the runtime equation $T = N_{inst} \times CPI \times T_{cycle}$ and substitute $CPI = 1/ IPC$ (the reciprocal link). That gives $T = N_{inst} \times \frac{1}{IPC} \times T_{cycle} = \frac{N _{inst} T _{cycle}}{IPC}$ Unit-check: (instructions) $\times$ (ns/cycle) $\div$ (instructions/cycle) = ns. IPC sits below the bar because more instructions per cycle means less total time — throughput is inversely related to runtime.

Wide core: $T_{A} = \frac{1 0 ^{6} \times 0.5 ns}{2.0} = \frac{500000}{2} ns = 250000 ns = 250 μ s$ .

Fast core: $T_{B} = \frac{1 0 ^{6} \times 0.3 ns}{1.5} = \frac{300000}{1.5} ns = 200000 ns = 200 μ s$ .

The 2-wide core wins (200 µs < 250 µs). Higher IPC alone is not victory — the product of IPC and clock speed decides. This is the whole reason superscalar (width) and deep pipelining (frequency) are orthogonal levers you trade off.

Level 5 — Mastery

Exercise 5.1 (L5)

A 3-wide superscalar has only one load/store unit (a structural limit) but three ALUs. In this loop body, 2 of every 5 instructions are loads and the rest are independent ALU ops. Loads cannot be issued together (one L/S port). What is the best sustainable IPC per 5-instruction group, and which hazard type caps it?

Recall Solution 5.1

Label the group: L L A A A (2 loads, 3 ALU ops), all data-independent. The ALUs can take up to 3 ops/cycle; the single L/S port takes at most 1 load/cycle.

Loads: 2 loads ÷ 1 port = needs 2 cycles minimum (one load per cycle).
ALU ops: 3 ops fit in one cycle across 3 ALUs.

Best packing:

Cycle	Issued
1	L1, A1, A2 (1 load + 2 ALU, fits 3-wide, 1 L/S port)
2	L2, A3 (second load + last ALU)

5 instructions in 2 cycles → IPC $= 5/2 = 2.5$ . The cap comes from the structural hazard (single load/store port), not from data dependencies (there are none here). Even though we are 3-wide with no data hazards, the port serializes the two loads. WHY it never reaches 3: issue width 3 promises 3/cycle, but a shared functional unit with one port throttles a whole instruction class.

Exercise 5.2 (L5)

A branch is mispredicted every 100 instructions. Each misprediction flushes the pipeline and wastes an average of 8 issue slots' worth of work on a 4-wide core (recall: an issue slot is one launch opportunity in one cycle on one lane, so a 4-wide core has 4 slots per cycle). Each wasted slot is one launch opportunity that produced nothing useful. Ignoring all other stalls, and assuming the machine otherwise sustains its peak of IPC $= 4$ , estimate the effective IPC.

Recall Solution 5.2

Set up per 100 real instructions. At peak, 100 useful instructions would take $100/4 = 25$ cycles. But each misprediction wastes 8 slots; at 4 slots/cycle that is $8/4 = 2$ extra cycles per misprediction. One misprediction per 100 instructions adds 2 cycles.

Total cycles $= 25 + 2 = 27$ for 100 useful instructions. $IPC_{eff} = \frac{100}{27} \approx 3.70$ Interpretation: even a fairly good 1-in-100 misprediction rate shaves peak IPC from 4.0 to ≈3.70 — a ~7.4% loss. This is why Branch Prediction accuracy is life-or-death for wide machines: the wider $N$ , the more slots each flush discards. See also VLIW, where the compiler (not hardware) must pack slots and mispredicts hurt even more.

Recall One-line self-check for the whole ladder

Peak IPC is set by == the issue width $N$ ; real IPC is dragged below it by data, structural, and control hazards (D-S-C), and total runtime still hinges on IPC times clock frequency ==, not IPC alone.