Superscalar Execution

A scalar pipeline advances at most one instruction through each pipeline stage per cycle: at best, one instruction completes per cycle in steady state (a throughput of Instructions Per Cycle, IPC, equal to 1). A superscalar pipeline widens every stage — fetch, decode, issue, execute, and often writeback — so that a bundle of $w$ instructions can move through together, where $w$ is the issue width (also called superscalar degree). An issue width of 4 means the machine can, in the best case, fetch four instructions, decode four instructions, and dispatch four instructions to execution units in one cycle, giving a theoretical peak IPC of 4. Two structural ingredients make this possible. First, replicated resources: multiple ALUs, multiple load/store ports, multiple decoders, and wide fetch/decode datapaths, so that $w$ instructions physically have somewhere to go simultaneously. Second, and far more subtle, parallel dependence checking: hardware logic that examines all $\binom{w}{2}$ pairs of instructions in the current bundle (plus in-flight instructions from prior bundles) and determines which subset can legally issue together this cycle. Instructions with an unresolved hazard against an earlier instruction in program order must wait, and in a simple in-order superscalar design, if instruction $i$ in the bundle stalls, every instruction after it in program order stalls too — even if instruction $i{+}1$ has no hazard at all. This is the crucial asymmetry that separates in-order superscalar from the out-of-order designs that came later. The three hazard types inherited from pipelining reappear here, but now checked across a group instead of just against the immediately preceding stage:

• RAW (read-after-write / true dependence): instruction $j$ reads a register that instruction $i$ (earlier in program order, possibly in the same bundle) writes. $j$ cannot issue until $i$'s result is available (or forwarded).
• WAW (write-after-write): two instructions in the bundle write the same destination register; the later one in program order must be the one whose write is architecturally visible last.
• WAR (write-after-read): a later instruction writes a register an earlier instruction still needs to read; in-order pipelines with a single register-read stage rarely hit this in-bundle, but it matters once instructions are reordered, foreshadowing Out-of-Order Execution.
• Structural hazards also multiply: if the bundle contains three loads but the machine has only two load/store units, one load must be held back regardless of data dependences.

The superscalar front end must do three things every cycle: fetch a bundle, decode it, and determine an issue mask — which instructions in the bundle (and which carried-over instructions from a prior stalled bundle) actually proceed to execution this cycle. The algorithm below models a canonical in-order superscalar issue stage with width $w$. ``` // Superscalar in-order issue, width w // pending[]: instructions already fetched/decoded, waiting to issue, // in strict program order (oldest first) // scoreboard: tracks which registers have results "not yet ready" // (i.e., produced by an in-flight, uncompleted instruction) function ISSUE_CYCLE(pending, scoreboard, functional_units): issued = [] blocked = false // once true, stop issuing (in-order) used_units = {} // structural resources claimed this cycle for k = 0 to w - 1: if blocked or pending is empty: break instr = pending[0] // oldest remaining instruction // 1. Structural hazard check unit = REQUIRED_UNIT(instr) if used_units.count(unit) >= AVAILABLE(unit): blocked = true break // 2. RAW hazard check against scoreboard (in-flight results) // and against instructions already issued THIS cycle for src in SOURCE_REGS(instr): if scoreboard[src].not_ready: blocked = true for prior in issued: if DEST_REG(prior) == src: blocked = true // same-cycle producer, not forwarded yet if blocked: break // 3. WAW hazard check: if a same-cycle earlier instruction in the // bundle writes the same destination, order must be preserved; // with in-order issue this is automatic since we issue oldest-first // and only the last write commits architecturally. // Passed all checks: commit to issuing this instruction issued.append(instr) used_units[unit] += 1 mark scoreboard[DEST_REG(instr)] as "not_ready" (result pending) pending.pop_front() return issued // 0 to w instructions issued this cycle ``` Three points about this pseudocode deserve emphasis because they are exactly where correctness lives: 1. Program order is preserved by construction. The loop always considers `pending[0]`, the oldest not-yet-issued instruction, first. The moment any instruction fails a check, `blocked` is set and the loop breaks — no younger instruction is allowed to "jump ahead," which is precisely the in-order-issue guarantee. 2. Same-cycle producers are not treated as forwarded for free. A same-cycle RAW dependence (instruction 2 in the bundle needs the result of instruction 1, also in the bundle) blocks issue unless the microarchitecture has an explicit same-cycle bypass path; the pseudocode is conservative and correct by default, and a real design that adds intra-bundle forwarding must justify it with an explicit bypass network. 3. Structural hazards are checked before data hazards, but the order doesn't matter for correctness — both are AND-ed together; what matters is that both are checked for every candidate instruction before it is allowed into `issued`.

Hardware complexity of dependence checking. For a bundle of width $w$, every instruction's source registers must be compared against every other instruction's destination register to detect RAW hazards, and every destination must be compared against every other destination for WAW hazards. This requires $O(w^2)$ comparators in the checking network (each comparator being a small equality circuit on register-number bits). Because comparator delay and wiring fan-out grow with $w$, the critical path through the issue logic — and hence achievable clock frequency — degrades roughly quadratically as width increases, which is why practical issue widths have historically topped out around 4–8 rather than growing to 32 or 64. This $O(w^2)$ scaling is the single most important complexity fact about superscalar hardware: doubling issue width more than doubles dependence-checking hardware, for a throughput gain that (as argued below) is typically much less than double.

Throughput bound. Let the dependence height of a straight-line code region be the length of the longest chain of true (RAW) dependences within it — this is exactly the notion introduced when discussing Instruction-Level Parallelism and Dependences. If a region of $n$ instructions has dependence height $h$, then no schedule — no matter how wide the issue width — can execute it in fewer than $h$ cycles, because a dependence chain of length $h$ is a serial critical path. Superscalar width $w$ can shrink the number of cycles from $n$ (scalar) toward $\max(h, \lceil n/w \rceil)$ at best, but never below $h$. This gives the honest complexity/performance statement:

so IPC is bounded by

The ratio $n/h$ is exactly the available instruction-level parallelism of the code. If a program has only 2-wide ILP on average, building a 6-wide superscalar machine wastes four issue slots per cycle on average — this is the concrete reason issue width alone does not guarantee proportional speedup, and it is the standard "Amdahl's-law-for-ILP" argument.

Correctness argument (in-order issue preserves sequential semantics). The claim to prove: the in-order superscalar issue algorithm produces results identical to running the same instructions one at a time in program order. The invariant maintained by `ISSUE_CYCLE` is: > At the start of every cycle, for every register $r$, if some issued-but-not-yet-completed instruction will write $r$, the scoreboard marks $r$ as not-ready, and no instruction reads a not-ready register in the same or an earlier cycle than its producer commits. This invariant is established by the RAW check (source registers are tested against the scoreboard and against same-cycle producers before an instruction is allowed into `issued`) and preserved because every newly issued instruction immediately marks its destination not-ready before the next candidate in the bundle is examined. WAW ordering is preserved automatically because instructions are only ever issued in increasing program-order index (`pending[0]` first, never skipped over), so if two instructions in flight write the same register, the one issued later in program order also completes its write later relative to program order — assuming a single, in-order writeback/commit stage, which real in-order superscalar pipelines provide. Combined, these guarantee that the final architectural state after all instructions retire is identical to sequential execution: the algorithm is a valid, hazard-safe parallelization of a sequential instruction stream, not merely a fast one.

Tradeoffs, stated honestly. In-order superscalar issue is simple to verify and cheap relative to out-of-order designs, but it pays for that simplicity with bundle-wide stalls: a single hazard anywhere in the bundle blocks everything behind it that cycle, even independent, ready-to-go instructions (visible in the worked example below). This wasted issue-slot problem is precisely what motivates dynamic instruction reordering, covered under Out-of-Order Execution.

Consider this five-instruction sequence issued on a 3-wide in-order superscalar machine, with a one-cycle execute latency for ALU ops and a two-cycle latency for loads (result not ready until the end of the cycle after the load executes): ``` I1: ADD r1, r2, r3 ; r1 = r2 + r3 I2: LD r4, 0(r5) ; r4 = MEM[r5] (2-cycle latency) I3: ADD r6, r7, r8 ; r6 = r7 + r8 (independent of I1, I2) I4: SUB r9, r1, r6 ; needs r1 (I1) and r6 (I3) -> RAW I5: ADD r10, r4, r1 ; needs r4 (I2, 2-cyc) and r1 (I1) -> RAW ``` Trace, assuming full same-cycle forwarding is not available (a same-cycle producer cannot feed a same-cycle consumer, matching the conservative pseudocode above), and one load/store unit:

Corrected cycle-by-cycle result: I1, I2, I3 issue in cycle 1 (3 instructions). I4's operands (r1 from I1, r6 from I3) are both ready at the start of cycle 2, so I4 issues alone in cycle 2 — but I5 cannot join it, because I5 needs r4 from the load I2, which has 2-cycle latency and is not ready until cycle 3. Because issue is in-order, I5 must wait even though lanes 1 and 2 are completely idle in cycle 2. In cycle 3, I5 finally issues. Total: 5 instructions in 3 cycles → IPC = 1.67, well under the peak width of 3, purely because of one RAW hazard on a load result and the in-order rule that idle lanes cannot be filled by instructions that come later in program order. This is exactly the throughput bound derived above: the dependence chain I2 → I5 has height 2 (in cycles, given the load latency), while $n/w = 5/3 \approx 1.67$ cycles-per-group if perfectly packed — the load latency, not width, is the binding constraint here.

Superscalar execution grew out of a lineage of research into pipelining and instruction-level parallelism at IBM, CDC, and several university groups exploring how to exceed one-instruction-per-cycle throughput without changing the instruction set architecture visible to software.

Every mainstream general-purpose processor today — Arm Cortex and Apple Silicon cores in phones and laptops, AMD Zen and Intel Core in desktops and servers, IBM POWER and RISC-V high-performance implementations — is superscalar, typically issuing between 4 and 10 instructions per cycle in its front end. Compilers exploit this by scheduling independent instructions adjacent to each other (instruction scheduling, software pipelining) specifically to keep multiple issue lanes busy, directly leveraging the ILP-and-dependence reasoning from Instruction-Level Parallelism and Dependences. Superscalar issue logic is also the direct ancestor of the dispatch stage in Out-of-Order Execution machines, where the dependence-checking problem becomes even harder because instructions may issue in an order different from how they were fetched. It further sets the stage for Simultaneous Multithreading, where a superscalar machine's spare issue slots — the very slots wasted by hazard stalls in the worked example above — are filled with instructions from an entirely different thread, squeezing out throughput that single-thread ILP alone cannot supply. GPUs and DSPs use related but distinct multi-issue and VLIW ideas, where the compiler rather than hardware guarantees independence, trading dependence-checking hardware for compiler complexity — a design point directly informed by the $O(w^2)$ hardware cost argument above.

Ask the tutor: How does adding out-of-order issue change the dependence-checking hardware compared to in-order superscalar issue?