Seyed Masoud Hosseini · Overview · Study log · Weekly summaries · Ideas · Search · Transcript · RSS feed

Digital Design & Computer Architecture · Lecture 17 of 37 · 1:36:13

Lecture 14: Out-of-Order Execution

Study guide

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

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

Vocabulary

out-of-order execution (noun): Running instructions in whatever order their data becomes ready, not the original written order.
Out-of-order execution lets independent instructions skip ahead of a stalled one.
dynamic instruction scheduling (noun): Deciding at runtime, using hardware, which instruction to run next.
Dynamic instruction scheduling replaces compile-time ordering decisions.
dispatch (verb): To send a decoded instruction to a functional unit to be executed.
An instruction cannot dispatch until all its operands are ready.
reservation station (noun): A hardware buffer that holds an instruction until its input values are all available.
The instruction waits in a reservation station for its missing operand.
tag broadcast (noun): Sending out a completed instruction's identifying tag so waiting instructions know their data is ready.
Tag broadcast lets other instructions know they can now execute.
common data bus (noun): A shared connection used to broadcast a finished instruction's result and tag to the whole machine.
The result travels across the common data bus to all listening reservation stations.
wakeup logic (noun): Circuitry that detects when a waiting instruction's operands have all become ready.
Wakeup logic marks the instruction as ready once its tag matches.
select logic (noun): Circuitry that picks which ready instruction gets to use a functional unit when several compete.
Select logic chooses one of several ready instructions each cycle.
front-end register file (noun): A register file updated speculatively as instructions finish, used for renaming.
The front-end register file may hold values not yet officially committed.
architectural register file (noun): The register file that only updates in program order, representing the official machine state.
The architectural register file is resynchronized after an exception.
physical register file (noun): A single storage of actual register values shared by all internal structures, referenced by tags.
The physical register file avoids copying full values into every reservation station.
producer-consumer (adjective): Describes a relationship where one instruction creates a value and another instruction uses it.
Register renaming correctly links each producer-consumer instruction pair.
instruction window (noun): The set of in-flight instructions a processor can consider scheduling at once.
A larger instruction window can find more independent work to run early.
reverse-engineer (verb): To figure out how something works by studying its behavior or structure.
Researchers reverse-engineer a modern processor's reorder buffer size.
cycle-by-cycle (adjective): Describing something tracked or explained one clock cycle at a time.
The lecture walks through a cycle-by-cycle simulation of the machine.
flush (verb): To clear out instructions or state, usually after an error or misprediction.
An exception causes the pipeline to flush.
resynchronize (verb): To bring two versions of the same state back into agreement.
The front-end register file is resynchronized from the architectural file.
single-thread performance (noun): How fast a processor runs one sequence of instructions, as opposed to running many at once.
Fine-grained multithreading does not directly help single-thread performance.
data-flow order (phrase): The order in which instructions actually become ready to run, based on data availability.
Instructions dispatch in data-flow order rather than program order.
value prediction (noun): Guessing a result before it is actually computed, to avoid waiting.
Value prediction is dismissed as one alternative already covered in the course.
empirical (adjective): Based on measured results rather than theory alone.
The lecture cites empirical gains of 30 to 50 percent.
arbitrate (verb): To decide fairly between several competing requests.
Select logic arbitrates among ready instructions competing for a functional unit.
timing path (noun): A route through a circuit whose delay affects how fast the whole design can run.
The broadcast-compare-wakeup loop is a critical timing path.
centralize (verb): To gather something into one single place instead of spreading it out.
Modern designs centralize values in one physical register file.
replication (noun): Making multiple copies of the same data or hardware.
Storing full values everywhere causes costly replication.
commercial disappointment (phrase): A product that failed to succeed in the market despite technical merit.
The IBM 360/91 was a commercial disappointment.
scale up (phrasal verb): To grow larger while keeping the same basic design.
The mechanisms discussed scale up in production hardware.

From the YouTube description

Digital Design and Computer Architecture, ETH Zürich, Spring 2025 (https://safari.ethz.ch/ddca/spring2025/)

Lecture 14: Out-of-Order Execution
Lecturer: Prof. Onur Mutlu
Date: 4 April 2025

Lecture 14 Slides (pptx): https://safari.ethz.ch/ddca/spring2025/lib/exe/fetch.php?media=onur-ddca-2025-lecture14-out-of-order-execution-afterlecture.pptx
Lecture 14 Slides (pdf): https://safari.ethz.ch/ddca/spring2025/lib/exe/fetch.php?media=onur-ddca-2025-lecture14-out-of-order-execution-afterlecture.pdf

Recommended Reading:
====================
A Modern Primer on Processing in Memory
https://arxiv.org/abs/2012.03112

Intelligent Architectures for Intelligent Computing Systems
https://arxiv.org/abs/2012.12381

RowHammer: A Retrospective
https://people.inf.ethz.ch/omutlu/pub/RowHammer-Retrospective_ieee_tcad19.pdf

Fundamentally Understanding and Solving RowHammer
https://arxiv.org/abs/2211.07613

Recommended Reading:
====================
A Modern Primer on Processing in Memory
https://arxiv.org/pdf/2012.03112.pdf

Memory-Centric Computing: Solving Computing's Memory Problem
https://www.arxiv.org/pdf/2505.00458

Memory-Centric Computing: Recent Advances in Processing-in-DRAM
https://arxiv.org/pdf/2412.19275

Intelligent Architectures for Intelligent Computing Systems
https://people.inf.ethz.ch/omutlu/pub/intelligent-architectures-for-intelligent-computingsystems-invited_paper_DATE21.pdf

RowHammer: A Retrospective
https://people.inf.ethz.ch/omutlu/pub/RowHammer-Retrospective_ieee_tcad19.pdf

Fundamentally Understanding and Solving RowHammer
https://arxiv.org/pdf/2211.07613.pdf

Accelerating Genome Analysis via Algorithm-Architecture Co-Design
https://people.inf.ethz.ch/omutlu/pub/AcceleratingGenomeAnalysis_dac23.pdf

From Molecules to Genomic Variations: Accelerating Genome Analysis via Intelligent Algorithms and Architectures
https://people.inf.ethz.ch/omutlu/pub/IntelligentGenomeAnalysis_csbj22.pdf

RECOMMENDED LECTURE VIDEOS & PLAYLISTS:
========================================
Digital Design and Computer Architecture Spring 2025 Livestream Lectures Playlist:
https://www.youtube.com/watch?v=ubhxKNlOlRg&list=PL5Q2soXY2Zi9Eo29LMgKVcaydS7V1zZW3&index=3

Fundamentals of Computer Architecture Fall 2025 Livestream Lectures Playlist:
https://www.youtube.com/watch?v=uKgMFj1eQQc&list=PL5Q2soXY2Zi_ZMtqz1r-GHm-zzuE1QfIg&index=2

Seminar in Computer Architecture Spring 2025 Livestream Lectures Playlist:
https://www.youtube.com/watch?v=rqeKNZrLzng&list=PL5Q2soXY2Zi-oIW66TLOjtiqQxlDwNHng&index=2

Computer Architecture Fall 2024 Lectures Playlist:
https://www.youtube.com/watch?v=ziMRjDlLEwo&list=PL5Q2soXY2Zi-LfDdGgWyLcTSqzm6a26wD&index=2

Interview with Professor Onur Mutlu:
https://www.youtube.com/watch?v=8ffSEKZhmvo&list=PL5Q2soXY2Zi8VrmOTz44l2WupethSdh-M&index=9

TCuARCH meets Prof. Onur Mutlu
https://www.youtube.com/watch?v=6Hpn4SAX0dI

Arch. Mentoring Workshop @ISCA'21 - Doing Impactful Research
https://www.youtube.com/watch?v=83tlorht7Mc

The Story of RowHammer Lecture:
https://www.youtube.com/watch?v=sgd7PHQQ1AI&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=39

Accelerating Genome Analysis Lecture:
https://www.youtube.com/watch?v=r7sn41lH-4A&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=41

Memory-Centric Computing Systems Tutorial at IEDM 2021:
https://www.youtube.com/watch?v=H3sEaINPBOE&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=35

Intelligent Architectures for Intelligent Machines Lecture:
https://www.youtube.com/watch?v=GTieZPY4Wmc&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=38

Featured Lectures:
https://www.youtube.com/watch?v=jVYCchBGNVc&list=PL5Q2soXY2Zi8VrmOTz44l2WupethSdh-M&index=1

← Lecture 13: Precise Exceptions · Lecture 15: Dataflow, Superscalar Execution and Branch Prediction →