Superscalar, Out-of-Order & Speculative Execution

Before superscalar, let us be precise about what we are improving upon. A classic scalar, in-order pipeline fetches one instruction per cycle, decodes it, reads its register operands, executes it in a functional unit, and writes the result back. Every stage takes (ideally) one cycle, so the pipeline achieves one instruction per cycle (IPC) at best.

The problem is dependencies. If instruction 2 needs a result computed by instruction 1, instruction 2 cannot enter the execute stage until instruction 1's result is available — even if instruction 3 and 4 are completely independent of both. The pipeline stalls: it inserts bubbles (do-nothing cycles) to wait. On a real workload, a load-use stall (load from memory followed immediately by a use of the loaded value) can burn 4–20 cycles, because main memory is hundreds of cycles away.

The fundamental problem is structural: the pipeline enforces program order even when the program's data dependencies do not require it. Superscalar and out-of-order execution are the solution to that structural problem.

# Illustrate stall with a data dependency
# (RISC-V assembly, classic in-order pipeline)

lw   a0, 0(a1)      # Load from memory — takes many cycles
add  a2, a0, a3     # STALL: a2 depends on a0, must wait for load
sub  a4, a5, a6     # Independent! Could run during the stall, but
mul  a7, t0, t1     # so could this — in-order pipeline cannot exploit it

A superscalar processor widens the pipeline's front end: instead of fetching and decoding one instruction per cycle, it fetches and decodes N instructions at once (N is called the issue width or fetch width). A modern Intel or AMD core is typically 4-wide to 6-wide; Apple's M-series cores are 8-wide.

The term 'superscalar' just means the hardware can issue more than one instruction per clock — it says nothing about whether those instructions are dispatched in order or out of order. Early superscalar designs (some RISC-IV, early SPARC) were in-order superscalar: they issued multiple instructions per cycle only when adjacent instructions in program order were independent. That is a limited win.

The real breakthrough is combining superscalar width with dynamic scheduling — letting the hardware reorder instructions to keep execution units busy. The two ideas are orthogonal but almost always paired in practice.

One important constraint: the fetch unit must predict the next fetch address on every cycle (because branches disrupt the sequential stream). This is why the branch predictor must work at fetch bandwidth: it is predicting multiple branches per cycle on a wide machine.

/* On a 4-wide superscalar OoO machine, this loop's body
   contains 4 independent multiply-accumulate operations.
   The CPU can issue all four in a single cycle if execution
   units are available — achieving 4x IPC over scalar. */
void dot4(float *a, float *b, float *c, int n) {
    for (int i = 0; i < n; i += 4) {
        c[0] += a[i+0] * b[i+0];   // independent
        c[1] += a[i+1] * b[i+1];   // independent
        c[2] += a[i+2] * b[i+2];   // independent
        c[3] += a[i+3] * b[i+3];   // independent
    }
}

Before the hardware can reorder instructions, it must understand which reorderings are safe. There are exactly three kinds of instruction-level dependency:

RAW (Read After Write) — True dependency. Instruction B reads a register that instruction A writes. B genuinely needs A's result. This cannot be eliminated; it is a real data-flow constraint.

WAR (Write After Read) — Anti-dependency. Instruction B writes a register that instruction A reads. A must finish reading before B overwrites the value. This looks like a dependency, but it is not a true data-flow dependency — it exists only because A and B happen to use the same architectural register name. If you gave B a different physical register to write into, the constraint vanishes.

WAW (Write After Write) — Output dependency. Both A and B write the same register. B must complete after A so B's value is the final one. Again, this is a name dependency, not a true data-flow dependency — it disappears if B writes to a different physical register.

This distinction is the key insight behind register renaming: WAR and WAW dependencies are artifacts of the ISA's limited register namespace. The ISA has 16 or 32 architectural registers; the physical machine has 100–300. By mapping architectural register names to a much larger pool of physical registers, the CPU eliminates false dependencies and exposes parallelism that the programmer (or compiler) was unable to express.

# WAR (anti-dependency) example — RISC-V
add  t0, a0, a1     # reads t0 (WAR target below)
mul  t0, a2, a3     # writes t0 — must wait for add to read t0
                    # but only because they share the name "t0"!
                    # If mul wrote p99 instead, no constraint exists.

# RAW (true dependency) — cannot be eliminated
add  t1, a0, a1     # writes t1
sub  t2, t1, a2     # reads t1 — genuinely needs add's result

Register renaming is the mechanism that eliminates WAR and WAW dependencies at hardware decode time. The idea: maintain a physical register file (PRF) with many more entries (e.g., 256) than the ISA's architectural registers (e.g., 16 for x86-64 integer). Keep a rename table (also called a Register Alias Table, or RAT) that maps each architectural register to the physical register currently holding its 'live' value.

When the decoder processes a destination register write (e.g., mov rax, rbx + rcx), it:

1. Allocates a fresh physical register from a free list.
2. Updates the RAT: architectural register rax now maps to the new physical register p47.
3. Saves the old RAT entry for rax (it was p23) in the instruction's ROB entry, so it can be freed when this instruction eventually retires.
4. Translates source registers (rbx, rcx) by reading their current RAT entries to find their physical registers.

Now consider the WAR example from before: two instructions both writing t0. After renaming, the first write goes to p45 and the second to p47. They are now completely independent physical destinations — the second no longer needs to wait for the first to complete. The ISA's sequential semantics are still maintained because the RAT always reflects the 'most recently written' mapping, and the ROB restores old mappings on rollback.

This is one of the most elegant pieces of hardware engineering ever invented. It was first described by Robert Tomasulo for the IBM System/360 Model 91 in 1967 — a machine designed to run floating-point scientific code faster.

/*
 Conceptual rename table state (architectural → physical)
 Before: rax→p10, rbx→p11, rcx→p12

 Instruction 1: add rax, rbx, rcx
   src rax reads p10, src rbx reads p11
   Allocate p20 for dest rax
   RAT update: rax→p20  (old entry p10 remembered in ROB)

 Instruction 2: add rax, rax, 1   (WAW with inst 1 — same dest)
   src rax reads p20 (inst 1's output — RAW dep on inst 1)
   Allocate p21 for dest rax
   RAT update: rax→p21

 Instruction 3: mov rdx, rax      (reads rax — WAR would block,
   src rax reads p21              but renaming already handled it)
   dest rdx: allocate p22, RAT: rdx→p22

 Result: inst 1 and inst 2 are still serialized by the RAW dep
 (inst 2 reads p20, which inst 1 produces), but inst 3 is free
 to proceed as soon as inst 2's result in p21 is ready.
*/

After renaming, instructions are placed into reservation stations (RS) — a distributed buffer that sits in front of each execution unit (or group of units). A reservation station entry holds:

• The renamed opcode
• The renamed source operands or tags (physical register numbers) for operands not yet ready
• A ready bit for each source

Each cycle, the RS wakes up instructions whose all source operands have become ready. When an execution unit finishes and broadcasts its result on a common data bus (CDB), all RS entries watching for that physical register tag catch the value and mark themselves ready. An instruction is issued (dispatched to an execution unit) as soon as it is the oldest ready instruction in the RS, or — on many real designs — simply as soon as any ready instruction exists and a suitable execution unit is free.

This is the Tomasulo algorithm: distributed, data-driven, dynamic scheduling. The key properties:

• Instructions can issue out of program order as long as their operands are ready.
• Multiple instructions can be in-flight simultaneously across different execution units.
• The RS effectively 'looks ahead' into the instruction stream to find independent work.

Modern CPUs have unified or distributed scheduler queues (the term 'reservation station' is sometimes used interchangeably with 'scheduler'). Intel's P6 microarchitecture (Pentium Pro, 1995) popularised the design for x86. Modern cores have 80–200 scheduler entries, allowing a very deep lookahead window.

/* Imagine three RS entries after renaming:

   Entry A: ADD p20 <- p10(ready=1) + p11(ready=1)   → can issue NOW
   Entry B: MUL p21 <- p20(ready=0) + p12(ready=1)   → waiting for A
   Entry C: SUB p22 <- p13(ready=1) - p14(ready=1)   → can issue NOW

   Cycle 1: Issue A to ALU0, issue C to ALU1 (two-wide issue)
   Cycle 2: A completes, broadcasts p20 on CDB.
            Entry B sees p20 ready, wakes up.
            Issue B to multiplier.
   Cycle 3: C and B complete.

   Effective execution: 3 instructions in 3 cycles,
   but only 2 cycles of latency on the critical path (A→B),
   and C runs in parallel — no stall at all.
*/

Instructions issue and execute out-of-order, but the visible state of the program (registers, memory) must match what a sequential execution would have produced. The reorder buffer (ROB) is the mechanism that enforces this.

The ROB is a circular buffer. Every decoded instruction gets a ROB entry, allocated in program order. The entry tracks:

• The instruction's physical destination register
• A 'complete' bit (set when execution finishes)
• For stores: the address and data
• The old architectural-to-physical mapping (for rollback)

Instructions execute out of order and set their 'complete' bit when done. But they can only retire (commit their results to architectural state and free their ROB entry) from the head of the ROB, in program order. If the head instruction has not finished, retirement stalls — even if twenty later instructions are already done.

This 'in-order retirement' guarantee is crucial for two reasons:

1. Precise exceptions: if a page fault or divide-by-zero occurs, all instructions before the faulting one have already retired (their effects are permanent), and all instructions after it have not yet retired (their effects are discarded). The architectural state is exactly at the faulting instruction's boundary — this is what 'precise' means.
2. Speculation rollback: if a branch was mispredicted, the ROB is flushed from the mispredicted entry to the tail, the rename table is restored using the saved entries, and fetch restarts at the correct target. All speculative work is discarded cleanly.

The ROB size directly determines the instruction window — how far ahead the CPU can look to find independent work. Modern cores have ROBs of 300–600 entries.

/* ROB snapshot (program order, head→tail):

   ROB[0]: ADD p20<-p10+p11  complete=1  ← HEAD, ready to retire
   ROB[1]: MUL p21<-p20+p12  complete=0  ← executing
   ROB[2]: SUB p22<-p13-p14  complete=1  ← done but cannot retire
   ROB[3]: BEQ branch         complete=0  ← speculative boundary
   ROB[4]: LD  p23<-[addr]   complete=0  ← speculative

   This cycle: retire ROB[0] → free p10's old mapping,
               write rax→p20 into arch state.
   ROB[1] not done → retirement stops.
   ROB[2] is done but MUST wait behind ROB[1].

   If BEQ turns out mispredicted:
   → Flush ROB[3], ROB[4]
   → Restore RAT to state at ROB[3]
   → Restart fetch at correct target
   → ROB[0],[1],[2] results are kept (already retired or still valid)
*/

A conditional branch has two possible outcomes: taken or not-taken. The CPU does not know which until it evaluates the branch condition — which may be several cycles into execution. If the CPU simply stalls and waits, it wastes the entire issue width for those cycles. On a 6-wide machine with a 20-stage pipeline, a stall on every branch would be catastrophic.

The solution is speculative execution: the CPU guesses the branch outcome using a branch predictor, continues fetching and executing instructions along the predicted path, and only confirms or corrects when the branch finally resolves.

Modern branch predictors are extraordinarily accurate — typically 95–99% on real workloads. They use multiple correlated tables of 2-bit saturating counters, global branch history, perceptron predictors, and sophisticated TAGE (TAgged GEometric history length) predictors. The hardware invests enormous die area and power in prediction because the cost of being right (near-zero stall) far outweighs the cost of being wrong (pipeline flush, ~15–25 cycles).

Speculation extends beyond branches:

• Memory speculation: the CPU may predict that a load does not conflict with an earlier unresolved store, execute the load early, and check afterward.
• Value prediction: experimental in some research CPUs, the CPU guesses the value a computation will produce.
• Return address prediction: a return-address stack (RAS) predicts where ret will jump.

The critical invariant: speculative results are never committed to architectural state until the speculation is confirmed. They live in the ROB and physical register file, invisible to the rest of the system — at least, that was the assumption before Spectre.

// Branch predictor behaviour is observable in C
// A sorted array is more branch-predictor friendly
#include <stdlib.h>
#include <time.h>
#include <stdio.h>

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int main(void) {
    int data[32768];
    for (int i = 0; i < 32768; i++) data[i] = rand() % 256;

    // Unsorted: branch in sum loop is nearly random → ~50% mispredict
    long sum_unsorted = 0;
    for (int i = 0; i < 32768; i++)
        if (data[i] >= 128) sum_unsorted += data[i];

    qsort(data, 32768, sizeof(int), cmp);

    // Sorted: branch flips exactly once → ~0% mispredict after that
    long sum_sorted = 0;
    for (int i = 0; i < 32768; i++)
        if (data[i] >= 128) sum_sorted += data[i];

    // On a modern OoO CPU, sorted version is ~3-6x faster
    // purely due to branch prediction, not data access patterns
    printf("%ld %ld\n", sum_unsorted, sum_sorted);
}

Memory operations are the most complex part of out-of-order execution. The CPU cannot simply reorder loads and stores freely — doing so would break the program's intended memory semantics (and on multiprocessor systems, break the memory consistency model that the OS and hardware jointly guarantee).

The hardware uses a load-store queue (LSQ) or separate load queue and store queue:

• Stores are not committed to the cache until they retire from the ROB. Until then, their address and value sit in the store queue. This is essential: a speculative store must not become visible to other cores.
• Loads can be executed speculatively, but the hardware must check whether a later-in-program-order store (which may execute after the load, out-of-order) was to the same address. If so, the load must use the store's value (store-to-load forwarding) rather than the stale cache value.
• If a load has already been executed and then a conflicting store is discovered, the load (and all its dependents) must be squashed and re-executed. This is a memory ordering violation.

For kernel programmers, the key consequence is that the hardware may reorder loads and stores in ways that are invisible to a single thread but visible to other threads/cores. This is the hardware memory model (x86 is TSO — Total Store Order — which is relatively strong; ARM and RISC-V are weaker). The kernel uses memory barriers (mb(), rmb(), wmb(), smp_mb()) to tell the CPU 'do not reorder memory operations across this point.' Without them, lock-free data structures and RCU would be broken.

// This is the classic memory ordering bug
// Without barriers, on a weakly-ordered CPU (ARM, RISC-V),
// thread 2 can see x==1 but flag==0 — impossible under sequential
// execution, but real under hardware reordering.

// Thread 1:
int x = 0, flag = 0;
void writer(void) {
    x = 1;              // store 1
    // smp_wmb() needed here in kernel code!
    flag = 1;           // store 2 — may become visible BEFORE store 1
}

// Thread 2:
void reader(void) {
    while (!flag);      // spin
    // smp_rmb() needed here!
    assert(x == 1);     // may FAIL without barrier — store 2 seen,
                        // store 1 not yet visible
}

Spectre (2018, Kocher et al.) and Meltdown (2018, Lipp et al.) are two of the most significant hardware security vulnerabilities ever discovered. Both exploit speculative execution. Understanding them requires everything in this module.

Meltdown exploits the fact that on pre-patch x86 CPUs, the out-of-order engine would speculatively execute a load from a kernel-mapped address even when running in user mode, before the permission check raised the page-fault exception. The speculative load put kernel data into a cache line. Even though the load's result was never committed to architectural state (the page fault rolled it back), the cache state change was not rolled back — it was a microarchitectural side-effect. An attacker could then measure cache timing to reconstruct the loaded value. The fix: KPTI (Kernel Page Table Isolation) — map the kernel out of the user-mode page table entirely, so there is nothing to speculatively load.

Spectre is subtler and harder to fix. It tricks the branch predictor into mispredicting a branch in the victim's address space (which could be another process, or the kernel), causing the victim to speculatively execute its own code with the attacker-controlled index. The speculative execution loads victim data into the cache. The attacker then reads the cache timing. Spectre exploits the fact that the branch predictor's state is shared across privilege levels (or processes). Mitigations include retpoline (replace indirect branches with a construct that prevents speculative execution through them), IBRS/IBPB (flush branch predictor on privilege transitions), and many others — all at significant performance cost.

For kernel developers: the mitigations are built into the Linux kernel's entry/exit paths, interrupt handlers, and syscall paths. Understanding them requires knowing exactly what the speculative execution engine can do and why cache state is the covert channel.

// Simplified Spectre variant 1 concept (do NOT use — educational only)
// The attacker trains the branch predictor to predict 'taken'
// even when the bounds check should fail.

// Victim code (kernel or library):
void victim_fn(size_t x) {
    if (x < array1_size) {          // bounds check
        // Speculatively executed even when x >= array1_size
        // because branch predictor was trained to expect 'taken'
        uint8_t val = array1[x];    // out-of-bounds speculative load
        // val leaks via cache timing on array2:
        (void)array2[val * 512];    // cache line loaded — observable!
    }
    // Page fault or misprediction recovery: architectural state
    // rolled back. But the cache line in array2 is still warm.
}
// Attacker measures which cache line of array2 is warm → recovers val
// val could be kernel memory the attacker should never see.

Everything discussed so far is invisible in normal program output — but the CPU hardware exposes it through performance monitoring counters (PMC / PMU). These are hardware registers that count microarchitectural events: cycles, retired instructions, branch mispredictions, ROB stalls, cache misses, execution port utilisation, and hundreds more.

On Linux, perf is the tool that accesses these counters. It uses the perf_event_open(2) syscall (implemented in kernel/events/core.c). This is also why understanding the kernel matters for performance work: the PMU driver is in the kernel, and reading counters from user space goes through the kernel.

Key metrics to understand:

• IPC (Instructions Per Cycle): perf stat gives instructions and cycles; IPC = instructions/cycles. A modern OoO core can sustain IPC > 4 on compute-bound code.
• Branch miss rate: branch-misses / branches — should be < 1% for well-predicted code.
• Cache miss rate: cache-misses / cache-references — a few percent is normal; tens of percent signals a memory-bound workload.
• Stalled cycles: stalled-cycles-frontend (fetch/decode bottleneck) vs stalled-cycles-backend (execution unit or memory bottleneck).

On x86, Intel's Top-Down Microarchitecture Analysis (TMA) methodology formalises a hierarchical breakdown of where cycles are lost: Frontend Bound, Backend Bound (further split into Memory Bound and Core Bound), Bad Speculation, and Retiring. This is the professional way to diagnose performance problems on OoO hardware.

# Profile a program with perf stat
# -e selects specific hardware events
perf stat -e cycles,instructions,branch-misses,branches,\   
          cache-misses,cache-references                     \
          ./your_program

# Sample for hotspots (requires kernel with PMU support,
# and /proc/sys/kernel/perf_event_paranoid <= 1)
perf record -g ./your_program
perf report

# Annotate with instruction-level counts
perf annotate your_function

# TMA-style top-down analysis (Intel VTune or toplev.py)
# toplev.py is a Python tool by Andi Kleen:
# python3 toplev.py -l2 -- ./your_program

The execution units inside a modern CPU are not a single resource — they are a set of ports, each capable of dispatching certain instruction types. On Intel's Golden Cove (Alder Lake P-core), for example, there are 12 execution ports. Integer ALU operations can go to ports 0, 1, 5, 6; loads go to ports 2, 3; stores go to ports 4, 7, 8, 9; and so on.

This distinction between latency and throughput is fundamental:

• Latency: how many cycles until the result of this instruction is available to a dependent instruction. An integer add has latency 1; an integer multiply has latency 3; an FP multiply might be 4–5; a cache-hit load is 4–5; a cache miss can be 50–300.
• Throughput (or reciprocal throughput): how many cycles the CPU must wait before it can issue another identical instruction (assuming no dependency). An integer multiply might have throughput 1 even though its latency is 3, because the multiplier is pipelined.

For a chain of dependent instructions (a = f(a) repeated), the bottleneck is latency. For a set of independent instructions (SIMD reduction unrolled), the bottleneck is throughput (port bandwidth). Real code is a mix, and the OoO engine tries to fill the throughput slots with independent instructions while waiting for the latency of the critical path.

This is why loop unrolling helps: it exposes more independent instructions to the scheduler, allowing the throughput of fast execution units to be fully exploited even when the loop-carried dependency has non-trivial latency.

// Critical path analysis example
// Version A: chain of dependent adds — bottlenecked by latency
void chain(long *a, int n) {
    long x = 0;
    for (int i = 0; i < n; i++)
        x = x + a[i];   // each iteration depends on previous x
    // critical path latency = n * 1 cycle (ADD latency)
}

// Version B: 4-way unrolled reduction — exposes parallelism
void unrolled(long *a, int n) {
    long x0=0, x1=0, x2=0, x3=0;
    for (int i = 0; i < n; i += 4) {
        x0 += a[i+0];   // chain 0 — independent of chains 1,2,3
        x1 += a[i+1];   // chain 1
        x2 += a[i+2];   // chain 2
        x3 += a[i+3];   // chain 3
    }
    // critical path latency = (n/4) * 1 cycle  — 4x faster
    // (limited by memory bandwidth, not ADD latency)
}