Lecture 14: Out-of-Order Execution

What this lecture covers

Building on the previous lecture's reorder buffer and register renaming, this lecture asks how to avoid stalling the whole pipeline whenever one instruction is not ready to execute. The answer is out-of-order dispatch: instructions wait in structures called reservation stations until their operands are available, then fire in data-flow order rather than program order, while a separate mechanism (from the earlier lecture) still retires results in program order to preserve precise exceptions.

After the lecture, you should be able to explain why in-order dispatch stalls independent instructions behind a long-latency one, trace by hand how an out-of-order machine with reservation stations, tag broadcast, and value capture executes a short code sequence, and describe how the design evolved from Tomasulo's original algorithm (no precise exceptions) to modern designs with a physical register file that avoids replicating values across reservation stations and the reorder buffer.

Key ideas

• Dynamic instruction scheduling: the hardware, not the compiler, decides at runtime which instructions to send to functional units, effectively building an internal data-flow engine inside a control-flow machine.
• Dispatch stall: in an in-order machine, an instruction that is not ready blocks every instruction behind it from dispatching, even if those instructions are independent.
• Reservation station: a buffer that holds a decoded, renamed instruction until all of its source operands are available; instructions wait here instead of stalling the pipeline.
• Tag broadcast and value capture: when an instruction finishes, it broadcasts its destination tag (and value) on a common data bus; any waiting instruction whose source tag matches captures the value and becomes ready.
• Wakeup and select logic: the circuitry that detects when an instruction's sources are all ready and arbitrates among multiple ready instructions competing for a functional unit; this broadcast-compare-wakeup loop is a critical timing path in real processors.
• Front-end (rename) register file vs. architectural register file: the front-end file is updated speculatively as instructions complete, for renaming purposes; the architectural file is updated only in program order at retirement, and is resynchronized from it on an exception.
• Physical register file: modern designs centralize actual values in one physical register file and let the rename tables, reservation stations, and reorder buffer hold only pointers (tags), avoiding costly replication of 64-bit values throughout the machine.
• Tomasulo's algorithm: the historical basis for this design, from IBM's 360/91 floating-point unit; that machine did not support precise exceptions and was commercially unsuccessful partly because of it.

Walkthrough

Why in-order dispatch still stalls, and the goal for today (12:10)

Even with register renaming and a reorder buffer (from the prior lecture), an in-order dispatch machine still stalls: if the oldest undispatched instruction is waiting on an operand, no later instruction can be sent to a functional unit, even if it is completely independent. The lecture reviews and dismisses three alternatives already covered in the course — compile-time instruction scheduling, value prediction, and fine-grained multithreading — as either too hard for the compiler or unhelpful for single-thread performance, motivating out-of-order dispatch.

Reservation stations and data-flow-order dispatch (21:15)

The fix is to give every decoded instruction a slot in a reservation station, where it waits and monitors its source operands. An instruction becomes ready to fire as soon as all its sources are available, regardless of program order, so instructions are effectively dispatched in data-flow order. The lecture frames this as building a hidden data-flow engine inside a sequential-looking machine, without exposing data flow to the programmer, and cites empirical gains of 30 to 50 percent over aggressive in-order dispatch machines.

The four requirements for out-of-order execution (25:17)

The lecture lists what out-of-order execution needs: correct producer-consumer linking via register renaming, buffering of not-yet-ready instructions in reservation stations, tracking of source readiness via tag broadcast, and dispatch once all sources are ready. It credits Robert Tomasulo's algorithm, first used in the IBM 360/91, as the origin of this approach, noting that machine lacked precise exceptions and was a commercial disappointment despite its technical influence.

Simulating an out-of-order machine cycle by cycle (38:24)

Using a small program with a multiply and several dependent and independent adds, the instructor works through a full cycle-by-cycle simulation: instructions are decoded into reservation stations, their source registers are renamed to reservation-station tags via a register alias table, and independent instructions execute out of order while dependent ones wait for a broadcast tag and value. The example shows in-order dispatch without forwarding taking 31 cycles, with forwarding 25 cycles, and out-of-order dispatch reaching about 19 to 20 cycles for the same code.

Reverse-engineering a data-flow graph from machine state (1:06:43)

As an exercise in understanding, the lecture takes a snapshot of the register alias table and reservation stations mid-simulation and reconstructs the underlying data-flow graph purely from tags and valid bits, showing that the true dependence structure of a program is recoverable from micro-architectural state, and that dependence order is knowable even when full instruction order is not.

Adding precise exceptions and the physical register file (1:20:00)

The lecture then folds precise exceptions back in, similarly to the prior lecture: a front-end register file supports renaming for in-flight instructions, while a separate architectural register file updates only at in-order retirement from the reorder buffer; an exception flushes the pipeline and resynchronizes the front-end file from the architectural one. Because storing full 64-bit values in reservation stations, the reorder buffer, and multiple register files replicates data expensively, modern processors instead centralize values in one physical register file and let every other structure hold only small pointer tags, a change made between Intel's Pentium Pro and Pentium 4 designs.

Real designs and closing examples (1:33:09)

The lecture closes with pictures of real out-of-order cores, including Intel Pentium 4, Alpha 21264, IBM Power4 and Power5, and reverse-engineered estimates of a modern Apple/AMD core's reorder buffer and physical register file sizes, to show how far the mechanisms discussed scale up in production hardware.

Before you watch

• Watch the previous lecture on precise exceptions and the reorder buffer in this course, since this lecture builds directly on register renaming and the reorder-buffer concept introduced there.
• Be comfortable with the register alias table / tag mechanism from that lecture, since this lecture reuses and extends it for reservation stations.
• Recall the course's earlier discussion of data forwarding and multi-cycle functional units, since the walkthrough compares in-order dispatch with and without forwarding against out-of-order dispatch.

Check your understanding

1. Why does an in-order dispatch machine stall independent instructions behind a not-yet-ready instruction, and how do reservation stations fix this?
2. What information does an instruction need to broadcast when it finishes execution, and why do waiting instructions compare tags rather than register numbers?
3. Why was Tomasulo's original IBM 360/91 design commercially unsuccessful despite its technical influence?
4. What is the difference between the front-end (rename) register file and the architectural register file, and what happens to each on an exception?
5. Why do modern processors centralize values in a single physical register file instead of storing values directly in reservation stations and the reorder buffer?