Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 67 ยท CPU Design

Superscalar, Out-of-Order and Speculative Execution

Learn how modern CPUs issue several instructions per cycle, rename registers, reorder work, speculate past branches, and why Spectre exists. With demos.

A perfect five-stage pipeline finishes at most one instruction per cycle, so its CPI cannot drop below 1. Real programs are full of independent work, though: the instruction that adds two registers rarely needs to wait for an unrelated load. Modern cores exploit this instruction-level parallelism (ILP) with three ideas that stack on top of each other: issue several instructions per cycle, let them run in whatever order their data is ready, and keep going past branches before the branch is resolved.

This lesson explains each idea, shows a small scheduler that compares in-order and out-of-order execution, and finishes with the security lesson that came out of speculation. It builds on pipelining, hazards and branch prediction.

Superscalar: more than one instruction per cycle

A superscalar processor has several execution units and can fetch, decode and issue W instructions in the same cycle, where W is the issue width. Typical desktop and phone cores today are 4 to 8 wide. With W = 4, the ideal CPI is 0.25, which is the same as saying the IPC (instructions per cycle) can reach 4.

The catch is that hardware has to find independent instructions. Three kinds of dependences limit it:

Dependence Name Example Real or false?
Read after write (RAW) true dependence add r2, r1, r3 needs the r1 produced by an earlier load Real: the data truly flows
Write after read (WAR) anti-dependence an earlier instruction still needs the old r1, a later one overwrites it False: only the name is shared
Write after write (WAW) output dependence two instructions write r1; the later must win False: only the name is shared

True dependences cannot be removed. False ones exist only because the instruction set has few registers (16 or 32), so compilers reuse names. Hardware can remove them, which is the job of register renaming.

A simple superscalar design is in-order: it issues in program order, and when one instruction must wait, everything behind it waits too.

Out-of-order execution

An out-of-order (OoO) core fetches and decodes in program order, but places instructions into a pool (often called the issue queue or reservation stations). Each instruction waits there until its operands are ready, then is sent to a free execution unit, no matter where it sits in the program. A slow instruction, such as a load that misses the cache, no longer blocks independent work behind it.

flowchart LR
  F["Fetch and decode<br/>(in order)"] --> R["Rename"]
  R --> Q["Issue queue<br/>(wait for operands)"]
  Q --> E["Execution units<br/>(any order)"]
  E --> B["Reorder buffer<br/>(restore order)"]
  B --> C["Commit<br/>(in order)"]

Instructions enter and leave in program order; the middle runs in dataflow order.

The following simulator schedules the same seven instructions four ways. The load takes 4 cycles (imagine a cache miss), mul takes 3, the rest take 1. An instruction can issue when its sources are available; the model counts cycles until the last result is ready.

Python In-order versus out-of-order scheduling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The totals are 12, 10, 6 and 5 cycles. Widening the in-order core to 2 only saves 2 cycles, because the mul and everything after it is stuck behind the load and its dependent add. Letting instructions go out of order is a much bigger win: mul and sub run at cycles 0 and 1 while the load is still in flight. Look at the last two runs: add r1, r8, r8 reuses the register name r1 that the load is still writing. Without renaming it must wait until cycle 4, delaying the xor. With renaming it issues at cycle 2.

Register renaming

The instruction set exposes, say, 16 architectural registers. The core has many more physical registers (100 to 600 in recent designs). At rename time every instruction that writes a register is given a fresh physical register, and a table remembers which physical register currently holds each architectural name. Later readers look up the table, so they read the right version. Two writes to r1 now go to two different places, and WAR and WAW dependences vanish.

Python Renaming removes false dependences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the output the first r1 becomes p2 and the second becomes p7. The sub no longer touches the register that add r4, ... reads, so it can run before, after or alongside it. Only the true dependences remain: add r4 reads p2, and the final add reads p7 (the newest r1) and p4.

The reorder buffer: out of order inside, in order outside

If instructions complete in random order, what happens when one of them faults, or when an interrupt arrives? The program must look as though it ran one instruction at a time, in order. The reorder buffer (ROB) guarantees this. Every instruction gets a ROB slot in program order at rename time. Results are written into the slot when execution finishes, and the oldest instruction commits (becomes architecturally visible) only when it reaches the head of the buffer and is complete. Younger instructions that finished early wait their turn.

Python A reorder buffer retires in program order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Instructions i4 and i2 finished at cycles 3 and 4 but retire at cycles 11 and 10, after the older ones. The size of the ROB (200 to 500 entries on current big cores) bounds how far ahead the core can look, which is why a long cache miss can still stall everything once the ROB fills.

Speculative execution

Branch prediction supplies the missing piece. When the front end meets a branch it cannot resolve yet, it speculates: it predicts the direction, and keeps fetching and executing along the predicted path. The results of speculative instructions sit in the ROB and are not committed. When the branch resolves:

  • Correct guess: nothing special happens, the instructions simply commit. Every cycle of the branch delay has been hidden.
  • Wrong guess: the core flushes every younger instruction from the ROB and the queues, restores the rename table to its state at the branch, and restarts fetch from the correct address. Architectural state is never wrong, but time is lost, as quantified in Branch Prediction.

Memory loads speculate too: a core may run a load before older stores whose addresses are not known yet, and undo it if the guess about aliasing turns out wrong.

flowchart TD
  B["Branch fetched<br/>(condition not ready)"] --> G["Predict: taken"]
  G --> S["Execute younger instructions<br/>(results held in ROB)"]
  S --> R{"Branch resolves"}
  R -->|prediction right| K["Commit the instructions"]
  R -->|prediction wrong| X["Flush them, restore state,<br/>fetch the other path"]

Speculative results become real only when the branch resolves correctly.

The catch: speculation leaves traces

Squashing a wrong-path instruction undoes its effect on registers and memory, but not everything it touched. A speculative load pulls a cache line into the cache, and the cache is not rolled back. That is invisible to the program's results, yet it changes timing: reading that address later is fast, other addresses are slow.

In 2018, researchers publicized a family of attacks, Spectre and Meltdown, built on this. In outline (shown here as a concept, with no working exploit): an attacker trains the branch predictor so that a bounds check like the one below is predicted "in range". Then the attacker supplies an out-of-range index. The core speculatively reads memory it should not, and uses the secret value to choose which cache line to touch. The check eventually fails and the work is squashed, but the attacker can time which cache line became fast and so recover the secret one piece at a time.

C
// Read-only illustration, not runnable on this site.
if (index < table_size) {          // predicted "true" after training
    value = table[index];          // speculative, even if index is huge
    probe[value * 64];             // leaves a cache footprint that depends on value
}

The architecture did not do anything wrong: the program-visible state was always correct. The flaw is that the microarchitecture leaks information through a side channel. Responses include operating-system and compiler mitigations (bounds masking, lfence-style barriers, retpolines), microcode updates, separate address spaces for kernel and user code, and redesigns in newer CPUs. Some mitigations cost real performance, which is a reminder that every speed trick has a security and complexity bill.

Putting it together

A modern big core is all of these at once: a wide front end driven by a branch predictor, renaming, an issue queue, many execution units, a reorder buffer of hundreds of entries and a memory system with caches to feed it. Its IPC on typical code is 1 to 3, well under the peak width, because dependences, cache misses and mispredictions keep many slots empty. To use the remaining parallelism, vendors add more cores and vector units rather than ever wider single cores.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A 4-wide superscalar core achieves a CPI of 0.5 on a program. What is its IPC?

    IPC is the reciprocal of CPI: 1 / 0.5 = 2. The core is using half of its 4-wide peak.
  2. 2. Which dependence is a TRUE dependence that renaming cannot remove?

    A RAW dependence means a later instruction really needs the value an earlier one produces. WAR and WAW only share a register name and disappear when each write gets its own physical register.
  3. 3. What is the job of the reorder buffer?

    The ROB holds in-flight instructions in program order and commits only the oldest completed ones, so exceptions and the visible state stay precise.
  4. 4. When a speculated branch turns out to be mispredicted, what happens?

    Speculative results never became architectural, so the core discards them and resumes on the correct path. The only lasting cost is lost time.
  5. 5. Why can speculative execution leak secrets even though wrong-path results are discarded?

    Architectural state is restored, but microarchitectural state such as which lines are in the cache is not, and a timing measurement can observe it.

Summary

  • Superscalar cores issue several instructions per cycle; ILP is limited by true (RAW) dependences, cache misses and branches.
  • Out-of-order execution lets independent instructions bypass a stalled one, and in the demo cut 12 cycles to 6.
  • Register renaming maps architectural names to many physical registers, removing false WAR and WAW dependences.
  • The reorder buffer holds results and commits in program order, which keeps exceptions precise.
  • Speculation runs ahead of unresolved branches and discards wrong-path work; the leftover cache footprint is the basis of Spectre-style side channels.
  • Real IPC is far below peak width, so designers also add cores and vector units.

Next, leave the CPU and study what feeds it data in The Memory Hierarchy and Locality.