Doing more per cycle: superscalar, static vs dynamic scheduling, the limits of ILP

One instruction per cycle is a ceiling, not a law

Every pipeline so far — the five-stage datapath of lesson 1, the multi-cycle pipelines of lesson 7 — obeys one silent rule: at most one instruction enters per clock and at most one leaves. Ideal CPI = 1; hazards push it above 1. Even a program of independent instructions is processed by the scalar pipeline "sequentially, one at a time" (p. 89).

Dynamic scheduling (lesson 7) attacks the stalls, not the rule. The notes' three instructions of p. 87, numbered from I0 as the papers do and in the papers' mnemonics (older papers write $F0; the 2026 paper and this notebook drop the dollar sign):

I0: FDIV F0, F2, F4       ; long: the divider takes many cycles
I1: FADD F10, F0, F8      ; RAW on F0: must wait for I0
I2: FSUB F12, F8, F14     ; independent of both

In order, I2 waits behind I1 and I1 waits for the divider. With dynamic scheduling the three are still issued in program order, but into reservation stations: I1 waits there for F0 while I2 executes, and each result reaches its consumers over the common data bus (lessons 11–13; the scoreboard, lessons 9–10). What does not change: one instruction is still issued per cycle, so the CPI can approach 1 but never go below it.

The simplest case is the dual-issue pipeline: up to two instructions fetched, decoded and issued per clock (Definition 2, p. 90). Fig. 1 redraws the notes' Figure 22 as a before / after pair: same stages, same clock, instructions travelling in pairs.

The notes' figure runs its clock at 2 ns: two instructions every 2 ns is one per nanosecond, 1000 MIPS from a 500 MHz clock — twice the scalar pipeline. Ideal IPC = 2, ideal CPI = 1/2 = 0.5. The general rule (p. 95), on which every "ideal CPI" quiz of the exam rests, is one line:

What a second issue slot costs

Figure 23 of the notes (p. 91) is Patterson and Hennessy's two-issue datapath, its additions drawn in orange but not explained; Fig. 2 names them. One packet per cycle — one ALU-or-branch instruction plus one load-or-store, p. 91 — needs five additions:

1. a wider fetch: two instructions, 64 bits, per cycle;
2. two decoders;
3. a register file with 4 read ports and 2 write ports — an ALU operation reads two registers and a store reads two more (base and data); an ALU operation and a load both write in the same cycle;
4. a second adder for the load's address;
5. hazard detection across the pair (p. 93): independent, compatible types.

Even this ideal 2-wide machine rarely reaches its width. Patterson and Hennessy's own five-instruction loop runs on it at IPC 1.25, not 2: the pairing rule and the load-use delay leave three of the eight slots empty, and only unrolling the loop four times lifts it to 1.75. That gap is what the notes mean by "it cannot be always reached" (p. 95) and what the exam measures as code efficiency (section 4).

Each costs area and power, and not alike: ports and decoders grow with w, the bypass network — each result compared with every source operand of the next packet — with w². The widget shows that growth, and the ideal CPI falling as 1/w while the achieved one goes flat.

Multiple issue multiplies the work in flight by the width: ideal CPI = 1/w, in flight = w × depth — a ceiling, because the slots still have to be filled with independent instructions.

Four steps from scalar to superscalar

The notes (pp. 92–94) describe the road from the scalar pipeline to the modern core as four steps, summed up in Table 10. Read it column by column first.

Issue is in order in every row; commit is in order in every row; only Execution changes, and the width. A processor becomes superscalar by widening issue and freeing execution — never by reordering issue or commit. Issue stays in order so that each instruction meets its predecessors on the way in; commit stays in order so that an exception finds the state a sequential execution would have left — precise, as in lesson 7; the reorder buffer of lesson 17 enforces it, and the notes assume it for step 2 ("a commit stage ensures in-order architectural updates", p. 92).

One fragment, four rows. The machine: one unit of each kind, all pipelined; FDIV 8 cycles, FADD and FMUL 3, LD 2, ADDUI 1; a result is written the cycle after execution ends and committed the cycle after that; different units may write in the same cycle; at most w commits per cycle. "In-order execution" means that the starts are in program order — a short operation may still finish before a longer one that started earlier, as in the multi-cycle pipeline of lesson 7; the in-order commit puts the results back in order.

I0: FDIV  F0, F2, F4        ; 8 cycles
I1: FADD  F6, F0, F8        ; RAW on F0 (I0)
I2: LD    F10, 0(R1)        ; 2 cycles, independent
I3: FMUL  F12, F10, F14     ; RAW on F10 (I2)
I4: ADDUI R1, R1, 8         ; writes the R1 that I2 reads (WAR)
I5: FADD  F16, F8, F14      ; independent

Step 1 — single issue, in-order execution. I0 issues in cycle 1, starts in 2, writes F0 in 10. I1 needs F0 and cannot issue before 10 — nor can anything behind it: I2, dependent on nobody, waits until 11. Last commit: cycle 21. "Hazards (data, structural, control) cause pipeline stalls that affect all subsequent instructions" (p. 92).

Step 2 — single issue, out-of-order execution. I1 issues in cycle 2 into a reservation station and waits; I2 issues in 3, starts in 4, writes in 6; I3 to I5 follow. Every result exists by cycle 14, but commit is in order, one per cycle: I1 at 15, I2 to I5 at 16 to 19. "Throughput is still constrained by the single-issue limit" (p. 92).

Step 3 — dual issue, in-order execution. Two independent instructions on different units issue together: I1 and I2 in cycle 10, I3 and I4 in 13, I5 in 14 — 19 again, because an in-order packet stalls as a unit: I2 waited with I1. "Dependent instructions must wait, even if others could proceed" (p. 93).

Step 4 — dual issue, out-of-order execution. I0 and I1 issue in cycle 1, I2 and I3 in 2, I4 and I5 in 3; the independent work is written by cycle 9, the chain at 14, and two commits per cycle end at 17. In the layout of the exam's Tomasulo tables, with a commit column:

Against step 1: step 2 saves two cycles, step 3 two, step 4 four. Each middle step removes one restriction — the order of execution or the width of issue — and the superscalar removes both. And no machine on the ladder, however wide, finishes before cycle 15: issue, start, eight cycles of divide, three of add and one commit for the chain FDIV → FADD. A true dependence is what no width can touch; section 5 names that fact.

Issue and commit are in order in every design; only execution is freed, and only the width grows. Step 2 and step 3 each remove one restriction of the scalar pipeline; the superscalar removes both.

The superscalar recipe and its six parts

The notes reserve the word for step 4 — multiple issue plus dynamic scheduling; some textbooks also call step 3 an in-order superscalar, but on the exam follow the notes. Four key characteristics (pp. 95–96): an issue width, "the maximum number of instructions a processor can fetch, decode, issue, and begin executing in a single clock cycle", which "cannot be always reached (hazards, etc.)"; dynamic scheduling, the hardware analysing dependences in real time; out-of-order execution, as soon as operands and resources are ready; in-order commit, so that the architectural state follows program order and exceptions stay precise. A superscalar is not several pipelines side by side: one front end issues up to w instructions per cycle into one shared pool of units, and they still form one program.

The architecture "must include" six components (p. 96). Fig. 3 places each in the path of an instruction; the list says what each buys, because the exam asks for benefits.

• Multiple functional units — ALUs, FP units, load/store units: somewhere to put a wide issue.
• Register renaming — more physical names than architectural registers; it "eliminates WAR and WAW hazards".
• Reservation stations / issue queues — where instructions wait for operands or units, so issue continues past a stalled one.
• Reorder buffer — holds results "until they are safe to commit": in-order commit, precise exceptions.
• Common data bus — broadcasts each result with its tag to every waiting instruction in one cycle.
• Instruction window — the "sliding window of in-flight instructions from which the scheduler selects those ready to issue".

Benefits (p. 96): high ILP; dynamic parallelism — "no need for compiler to expose ILP, hardware finds it at runtime"; latency hiding of misses and FP divides; generality, "even without manual tuning". Challenges (pp. 96–97): complex hardware; issue-logic scalability — "the complexity of deciding which N instructions to issue out of M in-flight grows quickly", every broadcast tag being compared with every waiting operand every cycle; branch and memory dependences; diminishing returns — "after 3-4 issue width, real programs rarely expose enough parallelism to fully utilize the issue bandwidth" (p. 97; p. 102 says 4–6 for the hardware's own limit).

The exam question this section answers

Question 1 of the 22 June 2026 paper (8 points): "Explain the main concepts and benefits of each one of the following techniques used by modern superscalar processors (Tomasulo-style)" — eight techniques, five lines each. The discipline is concept, benefit, cost: the table is the compressed form, the exam section writes it out. Reservation stations, the reorder buffer and SMT have their own lessons (11, 17, 29).

Three true sentences from the 2025 midterm

The midterm of 5 May 2025, as the notes transcribe it (pp. 540–541), ends with three true-or-false statements to motivate: doubling the number of issues reduces the CPI; out-of-order execution can be generated by data cache misses; dynamic branch predictors improve the CPI. All three are true, and the motivation earns the points — the first only for the ideal CPI, the second because the scheduler, not the miss, is the mechanism. They are the fourth exam question below, with the motivations; the third one rests on the notes' formula (p. 541):

Superscalar = multiple issue + dynamic scheduling + out-of-order execution + in-order commit, built from units, renaming, stations, a reorder buffer, a common data bus and a window — and the exam wants the benefit of each.

Compiler or hardware: static vs dynamic scheduling

Who finds the parallelism? Table 11 (p. 98) answers in two rows, and everything else follows from them.

A VLIW (Very Long Instruction Word) processor is "a statically scheduled, multiple issue processor architecture in which the compiler selects and packs multiple independent operations into a single, wide instruction word that is executed in parallel by the processor" (p. 98) — a memory, a floating-point and an integer operation per word, the three columns of the exam's VLIW table. The compiler detects the ILP, schedules around the hazards (it knows every latency) and fills the empty slots "with NOPs when no instruction fits" (p. 98); the hardware checks nothing.

The formula sheet measures the left panel in one number:

In Fig. 4, 10/21 = 47.6 % of the slots do work; lesson 20 computes it for the exam's schedules, where every VLIW exercise asks it. The right panel is the superscalar's answer: "the compiler generates sequential code (as usual, no additional effort)" (p. 99); the hardware chooses every cycle from whatever is ready.

The balance sheet (pp. 98–99) follows from who decides. The VLIW gains simple hardware — "no need for out-of-order logic, dependency checks at runtime, or renaming hardware" — predictable timing, and energy efficiency, the decision being made once at compile time instead of every cycle in silicon. It loses three ways: performance depends on the compiler and on the visible ILP; binary compatibility — the schedule encodes one machine's units and latencies, so the next machine needs a recompilation, and it "cannot adapt to unpredictable latencies at runtime"; and wasted slots — NOPs that still cost fetch bandwidth and code size. The superscalar reverses every line — adapts, stays portable, finds hidden ILP — and pays in area, power, scheduling logic that "becomes a bottleneck at wider issue widths" and timing that is hard to verify (Table 12).

"Moderate" on the dynamic side is a real middle: a scheduling compiler still helps a superscalar (fewer stalls inside the window), but nothing breaks without it, whereas on a VLIW the compiler's schedule is the only thing that keeps the results right.

Hence the domains (p. 100): VLIW "for predictable workloads, embedded systems, or domain specific processors, where simplicity and determinism matter"; superscalar for general-purpose computing, where run-time variability makes "hardware-managed scheduling more effective". Lessons 19–21 open the static side: bundles, list scheduling, software pipelining.

Static: the compiler packs independent operations into wide words and pays in NOPs and portability. Dynamic: the hardware picks from a window every cycle and pays in silicon and power.

Why ILP hit a wall — and the way out

Pipelining, multiple issue, dynamic scheduling and renaming "have pushed ILP to impressive levels" (p. 101) — and then it stops. Five limits, each already met in a widget:

1. Limited parallelism in programs. Much code is sequential in logic, and the hardware exploits only what it sees: the instruction window, "the set of instructions that the processor can see and analyze" at a given time — a few dozen to a few hundred, bounded by area, power and timing, "a practical limit". Behind it stands a theoretical one, Amdahl's law.
2. Dependency constraints. True dependences "cannot be bypassed or parallelized because the value doesn't exist yet": a chain executes one link at a time — the FDIV → FADD chain of the stepper.
3. Control dependences and branches. Even with prediction and speculation, "mispeculation causes flushes and wasted cycles", growing with depth × width — the dial's second wall.
4. Memory latency and aliasing. Misses are long and unpredictable, and dependences through memory are hard to resolve at run time, addresses being known only after execution — the third wall.
5. Hardware complexity and power. The logic for dependence checking, wakeup-select, renaming and window scaling "grows rapidly"; "superscalar processors beyond 4-6 issue width become infeasible to scale" (p. 102) — the quadratic bar.

Amdahl's law, derived and corrected

The notes put limit 1 in numbers: "if 10% of our program is serial (f = 0.1), then the best speedup we can ever get is 1/0.1 = 10", even with "unlimited issue width, perfect branch prediction, and ideal memory". Lesson 3 met the law for one enhancement; here the enhancement is everything the machine can overlap and the serial part is the dependent chain.

1. Call the original execution time 1. A fraction \(f\) of it is serial and cannot be sped up; the rest, \(1 - f\), can be run \(p\) times faster (more issue slots, more units — any overlap).

2. The serial part still takes \(f\). The parallel part now takes \((1-f)/p\):

   \[ T_{new} = f + \frac{1-f}{p} . \]

3. Speedup is old time over new time:

   \[ \mathrm{Speedup}(p) = \frac{1}{\,f + \dfrac{1-f}{p}\,} . \]

4. Let \(p\) grow without bound; the parallel term vanishes and the serial one stays:

   \[ \mathrm{Speedup}_{max} = \frac{1}{f} \quad (p \to \infty) . \]

The example formula sheet writes the same law with the enhanced fraction \(F\) and its speedup \(S\):

Same formula, \(F = 1 - f\) and \(S = p\). The exam trap is the reading: check whether the fraction you are given is the serial or the enhanced one before substituting. With \(f = 0.1\): \(p = 2\) gives 1.82, \(p = 4\) gives 3.08, \(p = 8\) gives 4.71, and no \(p\) reaches 10.

Where the slots went

Now the opening puzzle. A 512-entry window sees sixty-four times more than Tomasulo's eight instructions, but it sees the same programs: dependence chains executed one link at a time (limit 2, Amdahl's serial part); a branch every few instructions, each misprediction discarding depth × width slots (limit 3); loads that miss, stores whose addresses arrive late (limit 4). Two or three of the six slots fill on an average cycle, and widening window or issue adds comparators to a wakeup-select network that grows with window × width (limit 5). The slots went into the structure of the programs. The notes' "alternative forms of parallelism" (p. 102) are the rest of this course:

• Thread-level parallelism — multithreading. Several threads on one core or many; threads are independent by construction, so nothing has to be tracked between them: a stalled thread is replaced by a ready one, and an SMT core issues from several in the same cycle. Lesson 29.
• Data-level parallelism — SIMD and vectors. One instruction on many data elements; the parallelism is known in advance, so the window problem disappears. Lessons 30–32.
• Heterogeneous computing — accelerators. GPUs, TPUs, NPUs, FPGAs take the parallel, compute-intensive parts off the CPU. Lesson 32.

Five walls — window, true dependences, branches, memory, wakeup-select hardware — cap the sustained IPC at two or three; Amdahl says 1/f is the most any width can give; the way past is threads, data parallelism and accelerators.