Superscalar — multiple execution units: Worked examples

This page is a workout. The parent note built the machinery: issue width $N$ and IPC (Instructions Per Cycle). One more symbol appears in the effective-IPC formula, so we define it before we ever write it down:

Here we hit every kind of case you could be asked, one worked example per case, so no exam scenario surprises you. Before the numbers, one reminder in plain words:

The scenario matrix

Every superscalar timing/throughput problem lands in one of these cells. We will fill all of them with a worked example.

#	Case class	What is special	Example
A	Fully independent code	best case, IPC hits the ceiling $N$	Ex 1
B	Pure dependency chain	worst case, IPC collapses to 1	Ex 2
C	Mixed / partial parallelism	realistic middle, use the $p$ formula	Ex 3
D	Multi-cycle latency op	a result isn't ready next cycle	Ex 4
E	Structural hazard	only ONE unit of a needed type	Ex 5
F	False dependency (WAR and WAW)	fixed by register renaming	Ex 6
G	Limiting behaviour	$N \to \infty$ , $p \to 1$ , $p \to 0$	Ex 7
H	Real-world word problem	translate a spec into IPC & time	Ex 8
I	Exam-style twist	in-order vs out-of-order same code	Ex 9

Convention for all examples unless stated: 2-wide machine, two identical integer ALUs, each op has latency 1 (result ready at the end of the cycle it issues, usable the next cycle), in-order issue. We change one knob per example.

Case A — fully independent (IPC hits the ceiling)

Worked example Ex 1

I1: r1 = r2 + r3
I2: r4 = r5 + r6
I3: r7 = r8 + r9
I4: r10 = r11 + r12

No instruction reads a register another writes. 2-wide, 2 ALUs. How many cycles? What IPC?

Forecast: guess the cycle count before reading on. Four independent adds, two lanes…

Check dependencies. Every destination register (r1, r4, r7, r10) is distinct from every source. Why this step? Independence is the only thing that lets two ops share a cycle — no RAW hazard means the second lane is legal to use.
Pack the lanes. Cycle 1: issue I1, I2. Cycle 2: issue I3, I4. Why? With 2 ALUs and no dependency, we fill both lanes each tick — nothing forces a stall.
Count. $2$ cycles for $4$ instructions. Why this step? IPC is defined as instructions ÷ cycles, so to get the number we simply total each and divide.

$IPC = \frac{4 instructions}{2 cycles} = 2 = N$

Verify: A scalar (1-wide) machine takes 4 cycles → IPC 1. Speedup $= 2/1 = 2 \times$ , the peak for a 2-wide core. Ceiling $IPC_{m a x} = N = 2$ respected ( $2 \leq 2$ ✓).

The figure below draws the schedule as a grid: columns are cycles, rows are the two ALU lanes. Look at how both boxes in each column are filled (blue on ALU 1, green on ALU 2) — that "no white gaps" pattern is exactly what IPC = N looks like.

Figure — Superscalar — multiple execution units

Case B — pure dependency chain (IPC collapses to 1)

Worked example Ex 2

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

Same 2-wide machine. Cycles? IPC? Does the second ALU help?

Forecast: each op eats the previous one's output. Guess whether width matters here.

Trace the chain. I2 needs r1 (made by I1), I3 needs r4 (made by I2), I4 needs r6. Each result is ready only at the end of its cycle. Why this step? A RAW hazard forbids issuing the consumer until the producer's value exists.
Schedule. C1: I1. C2: I2. C3: I3. C4: I4. The second ALU sits idle every cycle. Why? There is never a second independent instruction to hand it.
Count. $4$ cycles for $4$ instructions. Why this step? Same reason as Ex 1 — total instructions ÷ total cycles gives IPC, and here that ratio exposes the collapse.

$IPC = \frac{4}{4} = 1$

Verify: This is $p = 0$ (nothing parallelizable) in $IPC_{eff} = \frac{1}{( 1 - 0 ) + 0/2} = 1$ . Matches. Width bought us nothing — the parent note's "dependency chains are the enemy," proven.

Contrast this figure with the previous one: the red boxes march diagonally, one per cycle on ALU 1, while the whole ALU 2 row is dashed and empty ("idle"). The yellow arrows show each result feeding the next instruction — that arrow chain is why the second lane never fills.

Case C — mixed / partial parallelism (the realistic middle)

Forecast: $N = 4$ is the ceiling. Guess whether we get close.

Find $p$ . $p$ = fraction that parallelizes (defined at the top of this page). Here $6$ of $8$ are independent, parallel work. Why this step? The formula needs the split between "shareable" and "chained" work. $p = \frac{6}{8} = 0.75, 1 - p = 0.25$
Plug into the formula. Why? It's Amdahl's Law for ILP — the serial part sets a hard floor.
$= \frac{1}{0.4375} \approx 2.2857 $$$

Now hand-schedule to confirm. Why? The formula is an idealized estimate; scheduling the actual instructions tells us the real integer cycle count. Our lane-assignment policy is fixed and simple: each cycle, scan instructions in program order and place onto the lowest-numbered free lane every instruction whose operands are already available; skip any whose operands aren't ready yet. Applying that policy tick by tick:

Cycle	Lane assignment (by the policy above)
C1	Lane 1← $J_{1}$ , Lane 2← $J_{2}$ , Lane 3← $J_{3}$ , Lane 4← $J_{4}$ — all four are ready and independent, so the first four fill lanes 1–4.
C2	Lane 1← $J_{5}$ , Lane 2← $J_{6}$ , Lane 3← $K_{1}$ , Lane 4←idle — $J_{5}, J_{6}$ ready → lanes 1–2; $K_{1}$ has no unmet operand → lane 3; nothing left to place → lane 4 idle.
C3	Lane 1← $K_{2}$ , lanes 2–4 idle — $K_{2}$ 's operand $K_{1}$ became ready end of C2, so it takes lane 1; no other instruction remains.

That is $8$ instructions in $3$ cycles: $IPC_{hand} = \frac{8}{3} \approx 2.667$

The figure draws this exact schedule: four columns are lanes, three stacked bands are cycles. Watch the fully packed C1 row, the single idle lane in C2, and the lonely $K_{2}$ in C3 — the emptying staircase is the serial chain draining the parallelism.

Verify: The formula's $2.29$ and the hand-schedule's $2.667$ bracket the realistic range (both between 2 and 3, both far below the ceiling $N = 4$ ) — exactly the parent's "real IPC ≈ 1.5–2.5 on a 4-wide core." The hand-schedule is a touch higher because it packed the independent work maximally; the formula is conservative. Both confirm: the 2-long serial chain, not the width, is what stops us reaching 4. ✓

Case D — a multi-cycle latency op

Now we change one knob: latency > 1. Here the multiplier is pipelined (see the definition callout above): it takes 3 cycles to produce a result, but it accepts a new multiply every cycle and does not block the port for the consumer's independent neighbours. (Case E will show the opposite, blocking, situation.)

Worked example Ex 4

I1: r1 = r2 * r3     (multiply, latency 3, pipelined unit)
I2: r4 = r1 + r5     (needs r1)
I3: r6 = r7 + r8     (independent)
I4: r9 = r10 + r11   (independent)

2-wide, one pipelined multiplier + one ALU. When can each issue? Total cycles? IPC?

Forecast: I2 is stuck behind a slow multiply — but I3, I4 are free. Guess the schedule.

Latency accounting. I1 issues in C1; a 3-cycle latency means r1 is ready at the end of C3, usable in C4. Why this step? Latency is how many cycles pass before a result exists — the consumer's earliest issue is producer-issue + latency.
Fill the wait with independent work. Why? Because the multiplier is pipelined, its 3-cycle latency does not tie up the ALU — we can slot the independent adds alongside. C1: I1 (mul) + I3 (add). C2: I4 (add). C3: nothing ready (I2 still waiting on r1). C4: I2 (add), now r1 exists.
Count. Instructions retire by C4 → $4$ instructions in $4$ cycles. Why this step? We total instructions and the cycle at which the last one is placed, then divide, because IPC is exactly that ratio.

$IPC = \frac{4}{4} = 1.0$

The figure lays the four cycles across, with a multiply lane on top and an ALU lane below. The yellow multiply spans its 3-cycle latency shadow, and you can see the independent adds I3, I4 tucked into that shadow while I2 waits at the far right.

Verify: In-order without renaming/OoO would stall I2 and everything after it at C2, wasting lanes — you'd still finish by C4 here because I3/I4 got hoisted. The multiply latency (not the ALU count) set the critical path: $1 + 3 = 4$ cycles. Units check: cycles, dimensionless IPC ✓.

Case E — structural hazard (only one of a unit, blocking)

Worked example Ex 5

I1: r1 = r2 * r3    (multiply)
I2: r4 = r5 * r6    (multiply)

2-wide machine but only ONE multiplier, and here it is blocking (occupied one issue slot per multiply). Both are independent. Cycles? IPC?

Forecast: independent code — but is width enough?

Spot the structural clash. Why this step? Independence removes data hazards, but both instructions demand the same physical resource — the single multiplier. That's a structural hazard, the parent's obstacle #2.
Serialize on the scarce unit. C1: I1 uses the multiplier. C2: I2 uses it. Why? One multiplier can start one multiply per cycle; there is no second lane of that type.
Count. $2$ cycles for $2$ instructions. Why this step? Instructions ÷ cycles is the definition of IPC, so we tally both to read off the throughput.

$IPC = \frac{2}{2} = 1.0$

The figure shows two lanes but the adder lane greyed out ("no multiply here") so both multiplies are forced onto the single multiplier lane in consecutive cycles — the visual reason width alone couldn't help.

Verify: Had there been two multipliers, both issue in C1 → IPC 2. So the limiter here is port/unit count, not data flow. Fix in real hardware: add multiple execution ports (parent's "multiple ports dissolve structural hazards"). ✓

Case F — false dependencies (WAR and WAW) killed by renaming

Two kinds of false dependency exist — both are naming artifacts, not real data flow, and both vanish under register renaming. We show both.

Worked example Ex 6a — WAW (write-after-write)

I1: r1 = r2 + r3
I2: r1 = r4 + r5    (writes r1 again — WAW with I1)
I3: r6 = r1 + r7    (reads r1 — must get I2's value)

Both writes target r1, but the values are independent. 2-wide. Cycles before and after register renaming?

Forecast: does writing the same name force serialization? Guess yes, then see.

Naive (no renaming). I1 and I2 both write r1; hardware fears a WAW conflict and serializes to preserve which write is "last": C1 I1, C2 I2, C3 I3. That's 3 cycles, IPC $= 3/3 = 1$ . Why this step? Without renaming, the register name is the only handle, so the machine can't tell the two r1s apart.
Rename. Map I1's r1 → physical p1, I2's r1 → physical p7. Why? The WAW is a naming artifact — different physical registers make the conflict vanish.
Re-schedule and count. I1 and I2 are now genuinely independent → issue together in C1. I3 must read the latest r1 = p7 (from I2), ready end of C1, so I3 issues C2. Total $2$ cycles. Why this step? We divide 3 instructions by the new 2-cycle span because that ratio is IPC.

$IPC_{renamed} = \frac{3}{2} = 1.5$

The figure stacks two mini-schedules: before (three red boxes marching diagonally) versus after (I1+I2 packed in C1, I3 in C2) — the physical-register relabelling r1→p1, r1→p7 shown in the boxes makes the fix concrete.

Worked example Ex 6b — WAR (write-after-read)

I1: r3 = r1 + r2    (reads r1)
I2: r1 = r4 + r5    (writes r1 — WAR with I1: I2 must not clobber r1 before I1 reads it)

2-wide. Can these run together? What does renaming do?

Forecast: I2 overwrites the very r1 that I1 is reading — is that a real conflict?

Name the hazard. This is a WAR: a later write (I2 → r1) that must not destroy the value an earlier read (I1 reads r1) still needs. Why this step? If I2 issued first and wrote r1, I1 would read the wrong value — but that's purely about the shared name r1.
Naive in-order. In program order I1 reads first, then I2 writes — safe, but a naive machine still refuses to reorder or overlap them for fear of the WAR, serializing to 2 cycles.
Rename and count. I2 writes physical p9 instead of reusing r1's physical register. Why? Now I1's read of old-r1 and I2's write of p9 touch different physical registers — no ordering constraint at all. They issue together in C1. Total $1$ cycle; $2$ instructions ÷ $1$ cycle gives IPC.

$IPC_{renamed} = \frac{2}{1} = 2$

Verify (both): WAW dropped 3 cycles → 2 (IPC 1 → 1.5); WAR dropped 2 cycles → 1 (IPC 1 → 2). Both improvements come only from renaming false dependencies, and in both cases the real data values read/written are unchanged — correctness preserved. This covers both false-dependency kinds promised in the matrix. ✓

Case G — limiting behaviour (the three extremes)

Forecast: guess which extreme still refuses to exceed some fixed number.

(a) Perfectly parallel, $p = 1$ . Why? Tests the ceiling. $IPC_{eff} = \frac{1}{( 1 - 1 ) + 1/ N} = \frac{1}{1/ N} = N$ Hits the ceiling exactly — matches Case A.
(b) Fully serial, $p = 0$ . Why? Tests the floor. $IPC_{eff} = \frac{1}{( 1 - 0 ) + 0/ N} = \frac{1}{1} = 1$ No width helps — matches Case B.
(c) Half parallel, infinite width $N \to \infty$ . Why? Shows the hard ceiling Amdahl imposes even with unlimited units. As $N \to \infty$ , $p / N \to 0$ : $lim_{N \to \infty} IPC_{eff} = \frac{1}{( 1 - 0.5 ) + 0} = \frac{1}{0.5} = 2$

Verify: With $p = 0.5$ , throwing infinite execution units at the problem still caps IPC at 2 — the serial half is the wall. This is the deep lesson: the serial fraction, not the unit count, sets the ultimate limit. ✓

The figure plots effective IPC (vertical) against issue width $N$ (horizontal) as four rising curves, one per $p$ . Watch the green $p = 1$ line climb forever (IPC = N), while the yellow $p = 0.5$ curve flattens toward a dotted ceiling at 2 and the red $p = 0$ line stays pinned at the floor 1 — the curves visually flattening is Amdahl's wall.

Case H — real-world word problem

Forecast: 2 billion instructions, ~2.5 per cycle, 4 billion cycles/sec — order of magnitude?

Cycles needed. Why this step? Time flows through cycles; convert instructions → cycles via IPC. $cycles = \frac{N _{inst}}{IPC} = \frac{2 \times 1 0 ^{9}}{2.5} = 8 \times 1 0^{8}$
Seconds per cycle. Why? We need real time, not a cycle count. The clock period is just the reciprocal of the frequency: $T_{cycle} = \frac{1}{4 \times 1 0 ^{9} Hz} = 0.25 ns$ (We keep this single form — $0.25$ ns — throughout, no second notation.)
Multiply. Why? Time = cycles × time-per-cycle (the parent's $T = N_{inst} T_{cycle} / IPC$ ). With $0.25 ns = 0.25 \times 1 0^{- 9} s$ : $T = (8 \times 1 0^{8}) \times (0.25 \times 1 0^{- 9} s) = 0.2 s$

Verify: Direct plug-in: $T = \frac{2 \times 1 0 ^{9} \times 0.25 \times 1 0 ^{- 9}}{2.5} = \frac{0.5}{2.5} = 0.2$ s. Units: (instr)(s/cycle)/(instr/cycle) = s ✓. So the program finishes in 0.2 seconds.

Case I — exam-style twist: in-order vs out-of-order, same code

Worked example Ex 9

I1: r1 = MEM[r2]     (load, latency 2 — result ready in C3)
I2: r3 = r1 + r4     (needs r1)
I3: r5 = r6 + r7     (independent)
I4: r8 = r9 + r10    (independent)

2-wide, 1 load unit + 1 ALU. Compare total cycles for in-order vs out-of-order issue.

Forecast: the load stalls its consumer; guess whether OoO rescues the independent ops.

In-order. Why this step? In-order forbids a younger instruction from issuing before an older stalled one. C1: I1 (load) issues; I2 needs r1 (ready C3) so it blocks, and I3, I4 behind it are stuck too. C2: stall. C3: r1 ready; issue I2 + I3 (both now legal). C4: I4. → 4 cycles, IPC $= 4/4 = 1$ .
Out-of-order. Why? OoO lets ready instructions overtake the stalled I2. C1: I1 (load) + I3 (add, independent). C2: I4 (add). C3: I2 (now r1 ready). → 3 cycles, IPC $= 4/3 \approx 1.333$ .
Compare and count. Why this step? Dividing the same 4 instructions by each schedule's cycle count (IPC = instructions ÷ cycles) is what makes the two policies directly comparable.

$IPC_{in-order} = 1.0, IPC_{OoO} = \frac{4}{3} \approx 1.333$

The figure puts the two schedules side by side: the in-order grid shows a wasted stall column in C2, while the OoO grid shows I3, I4 hoisted forward to fill it — the removed white gap is the speedup.

Verify: OoO never violates correctness — instructions execute out of order but retire in order via the Reorder Buffer, so the architectural state ends identical. Speedup $= (4/3) /1 = 1. \overline{3} \times$ . This is the classic exam contrast between in-order and OoO on identical code. ✓

Recall Self-test: match example → matrix cell

IPC = N happened in which example? ::: Ex 1 (Case A, fully independent). Which example proved width buys nothing? ::: Ex 2 (Case B, pure dependency chain, IPC = 1). Where did renaming fix a WAW, and where a WAR? ::: WAW in Ex 6a (IPC 1→1.5), WAR in Ex 6b (IPC 1→2). With $p = 0.5$ and infinite units, what is the IPC ceiling? ::: 2 (Ex 7, Case G limit). How long did the 2-billion-instruction program take? ::: 0.2 seconds (Ex 8, Case H). OoO vs in-order on the load example gave which two IPCs? ::: 1.0 in-order, 4/3 ≈ 1.333 OoO (Ex 9).

Prerequisites worth revisiting: Instruction-Level Parallelism (ILP), Data Hazards (RAW WAR WAW), Register Renaming, Out-of-Order Execution, Reorder Buffer (ROB), and the throughput ceiling logic in Amdahl's Law.