Picture a to-do list where item 3 depends on item 2 finishing first, but item 4 has nothing to do with either of them. A rigid worker would sit idle waiting for item 2 to finish before even glancing at item 4. A smart worker would just start item 4 while waiting. That, in a nutshell, is out-of-order execution (OoOE) — one of the most important and most misunderstood techniques in modern processor design.
This article dives into how CPUs actually reorder instructions internally while still presenting a perfectly sequential, correct result to the programmer, why this matters so much for performance, and what it costs in terms of hardware complexity and even security (Spectre and Meltdown, anyone?).
The Problem Out-of-Order Execution Solves
In the previous article in this series on superscalar architecture, we established that modern CPUs can execute multiple instructions per cycle. But having multiple execution units is only half the battle — you also need to keep them busy. In a strictly in-order processor, instructions execute in exactly the order the compiler generated them. If instruction A takes a long time (say, it’s waiting on a cache miss that takes 200+ cycles), every instruction after it stalls too, even if those later instructions have nothing to do with A.
This is enormously wasteful. Real programs are full of independent operations sitting right next to dependent ones. Out-of-order execution lets the CPU look ahead in the instruction stream, find instructions that are ready to run (their operands are available and an execution unit is free), and execute them ahead of stalled instructions — all while making sure the final results are exactly as if everything had executed in the original order.
The Core Mechanism: Look Ahead, Execute When Ready, Retire In Order
Out-of-order execution generally follows a three-phase discipline:
- In-order fetch and decode — instructions still enter the pipeline in program order.
- Out-of-order execution — once decoded, instructions wait in a scheduling structure until their inputs are ready, then execute whenever an execution unit is free, regardless of program order.
- In-order retirement (commit) — even though execution happened out of order, results are committed to the architectural state (visible registers and memory) in the original program order. This is what preserves correctness.
That last point is critical and often the part people get wrong. The CPU is a chaotic beehive of parallel activity internally, but from the outside — from the perspective of any observer checking results — everything looks perfectly sequential.
Key Hardware Structures
To make this work, several specialized hardware structures are required.
Register Renaming
One of the biggest enablers of out-of-order execution is register renaming. Programs are written using a small, fixed set of architectural registers (e.g., x86-64 has 16 general-purpose registers visible to software). But the CPU internally has many more physical registers — often 100+ in modern designs.
Register renaming maps each architectural register reference to a unique physical register dynamically, which eliminates false dependencies — WAR (write-after-read) and WAW (write-after-write) hazards — that exist only because of register name reuse, not because of any real data dependency. This is what allows instructions that reuse the same register name (a very common occurrence in loops) to still execute out of order safely.
Reservation Stations / Issue Queue
Decoded instructions wait here until their source operands become available. Each cycle, the scheduler scans for instructions whose operands are ready and dispatches them to a free execution unit.
Reorder Buffer (ROB)
The ROB is the structure that enforces in-order retirement. Every instruction gets an entry when it’s decoded, and that entry stays until the instruction has completed execution AND all instructions ahead of it in program order have also retired. This is what allows the CPU to undo speculative work cleanly if something goes wrong (like a mispredicted branch or an exception).
Load/Store Queue
Memory operations need special handling because of aliasing — the CPU often doesn’t know at decode time whether a load and an earlier store touch the same memory address. Load/store queues track pending memory operations and use techniques like memory disambiguation and store-to-load forwarding to allow loads to execute early when it’s safe, or to bypass data directly from an in-flight store to a dependent load.
A Simplified Pipeline View
Program order: I1 I2 I3 I4 I5
| | | | |
Fetch/Decode --> [in-order]
| | | | |
Rename --> [physical registers assigned]
| | | | |
Issue Queue --> [wait until operands ready]
| | |
Execute --> I1 I4 I2 (I3 waits on I2's result)
|
I3
| | | | |
Retire (ROB) --> I1 -> I2 -> I3 -> I4 -> I5 (strictly in order)
Notice how I4, which has no dependency on I2/I3, gets executed early — but it still waits to retire until I2 and I3 have retired ahead of it.
Why This Matters: Hiding Latency
The single biggest benefit of out-of-order execution is latency hiding. Modern memory systems are wildly asymmetric: an L1 cache hit might cost 4-5 cycles, while a full main memory access can cost 200-400+ cycles. Without out-of-order execution, a single cache miss would stall the entire pipeline for hundreds of cycles. With it, the CPU can continue doing useful work on independent instructions while the slow memory operation completes in the background.
This is quantified by the size of the instruction window — how far ahead the CPU can look for independent work. Modern high-performance cores have very large reorder buffers:
| CPU (approximate generation) | Reorder Buffer Size (entries) |
|---|---|
| Intel Skylake | ~224 |
| Intel Golden Cove | ~512 |
| AMD Zen 4 | ~320 |
| Apple M2/M3 | 600+ |
Bigger windows mean the CPU can look further ahead to find independent work, which is especially valuable for hiding long memory latencies — but bigger windows also cost more silicon area and power, and add complexity to nearly every part of the pipeline.
Speculative Execution and Its Relationship to OoOE
Out-of-order execution is closely tied to speculative execution, though they are conceptually distinct. Speculative execution means the CPU guesses an outcome (most commonly, which way a branch will go) and executes instructions based on that guess before it’s confirmed. Out-of-order execution provides the machinery — the ROB, renaming, and issue logic — that makes it practical to discard speculative work cleanly if the guess turns out wrong. The next article in this series covers branch prediction and speculation in much more depth, but it’s worth flagging here because the two techniques are almost always deployed together in real silicon.
Precise Exceptions
A subtle but important benefit of the reorder buffer is that it enables precise exceptions. If instruction I3 causes a page fault or divide-by-zero, the CPU needs to be able to say, cleanly, “everything before I3 is done, nothing from I3 onward has taken effect.” Because retirement is strictly in-order via the ROB, this is straightforward: the processor simply flushes everything from I3 onward, handles the exception, and can resume cleanly. Without in-order retirement, this bookkeeping would be a nightmare.
Performance Considerations
Out-of-order execution provides the biggest wins on workloads with:
- Irregular memory access patterns where cache misses are common and unpredictable.
- Mixed instruction types where some operations (like floating-point division) take much longer than others (like integer addition), creating natural opportunities to overlap work.
- Moderate-to-high ILP — code with genuine independent work available to reorder.
It provides smaller benefits on:
- Tight, dependency-chain-heavy loops where each instruction genuinely needs the previous one’s result (common in some cryptographic or serial algorithms).
- Code that’s already memory-bandwidth-bound rather than latency-bound, where reordering can’t create more bandwidth out of thin air.
Advantages
- Dramatically improves effective IPC by hiding memory and execution latency.
- Requires no changes to existing software or compilers — it’s purely a hardware technique operating transparently.
- Combines naturally with superscalar issue width to maximize execution unit utilization.
- Enables precise exception handling despite internal parallelism.
Limitations and Trade-offs
- Massive hardware complexity. The scheduling logic, renaming tables, and reorder buffer all add substantial die area and design/verification cost.
- Power consumption. All that bookkeeping — tracking dependencies, renaming registers, buffering speculative results — costs energy, which is part of why simpler in-order cores remain popular in extremely power-constrained embedded and IoT designs.
- Security vulnerabilities. The Spectre and Meltdown vulnerability classes, disclosed in 2018, exploit the side effects of speculative and out-of-order execution — specifically, that speculatively executed instructions can leave measurable traces (like cache state changes) even when their results are ultimately discarded. This opened up an entirely new category of side-channel attacks and forced significant architectural and software mitigations across the industry.
- Diminishing returns at very large window sizes. Beyond a certain point, most programs simply don’t have enough independent work available even hundreds of instructions ahead, so growing the reorder buffer further yields shrinking benefits relative to its cost.
Common Misconceptions
“Out-of-order execution changes the results of a program.” It should never do this for correctly written single-threaded code — the entire point of the reorder buffer and in-order retirement is to guarantee results identical to sequential execution. Where it can create surprising behavior is in multithreaded code without proper synchronization, where memory reordering effects (a related but distinct topic involving memory consistency models) can become visible.
“Out-of-order execution and superscalar execution are the same thing.” They’re complementary but distinct: superscalar refers to issuing multiple instructions per cycle; out-of-order refers to reordering instruction execution around dependencies and stalls. You can have one without the other, though modern high-performance CPUs almost always have both.
“More reorder buffer entries always mean proportionally better performance.” As covered above, returns diminish — doubling ROB size rarely doubles performance, and architects balance ROB size against many other design priorities.
A Worked Example: Watching Out-of-Order Execution in Action
It helps to walk through a slightly more concrete example. Consider this small sequence of operations, expressed informally:
I1: load R1, [memory_address_A] ; slow — assume this misses cache
I2: add R2, R3, R4 ; independent of I1, ready immediately
I3: mul R5, R1, R2 ; depends on both I1 and I2
I4: sub R6, R7, R8 ; independent of everything above
I5: store [memory_address_B], R5 ; depends on I3
In a strictly in-order processor, I2 would have to wait behind I1 even though it has no dependency on it, stalling for however long the cache miss from I1 takes — potentially hundreds of cycles. An out-of-order processor instead recognizes that I2 and I4 have no dependency on I1’s slow load, executes them immediately while I1’s memory request is in flight, and only stalls I3 (which genuinely needs both R1 and R2) until I1 actually completes. I5 waits on I3. Meanwhile, all five instructions still retire strictly in the order I1, I2, I3, I4, I5 — preserving perfect program-order correctness for anything observing the final architectural state, even though the actual execution order internally was something like I2, I4, [wait for I1], I1, I3, I5.
This example captures the essential value proposition: out-of-order execution doesn’t change what the program computes, only the internal timing of when each piece of work actually happens, always in service of keeping execution units busy instead of idle.
The Interaction Between Out-of-Order Execution and the Memory Hierarchy
Out-of-order execution and the memory hierarchy (covered in depth elsewhere in this series) are deeply intertwined in practice. The entire value proposition of OoOE is strongest precisely when memory latency is a major bottleneck — which is exactly the scenario the memory hierarchy is designed to minimize through caching. In a hypothetical world with zero memory latency (everything accessed in a single cycle), out-of-order execution would still help somewhat by working around varying instruction latencies (like floating-point division taking longer than integer addition), but its biggest real-world win comes from hiding the hundreds of cycles a main memory access can cost.
This is why modern high-performance cores pair large reorder buffers with equally aggressive prefetching and large, multi-level caches — the goal across all these techniques is the same: minimize the time any given instruction spends waiting, and maximize the number of independent instructions available to fill in the gaps when waiting is unavoidable. Non-blocking caches, which allow multiple outstanding cache misses to be in flight simultaneously rather than blocking on one miss at a time, are a particularly important complementary technology — without them, out-of-order execution’s ability to hide latency by working around one slow load would be sharply limited, since a second slow load couldn’t even begin until the first one resolved.
Out-of-Order Execution in Different Processor Classes
It’s worth noting that not every processor implements out-of-order execution, and the decision to include it (or not) reflects a real design trade-off between performance and power/complexity/cost:
| Processor Class | Typical Approach | Rationale |
|---|---|---|
| High-performance desktop/server CPUs (Intel Core, AMD Zen, Apple M-series, IBM POWER) | Aggressive out-of-order, large ROB | Performance is the primary design goal; power/area budget supports the complexity |
| Mobile/embedded efficiency cores (e.g., ARM Cortex-A5x/A3x low-power tiers) | Often in-order or limited out-of-order | Power and area efficiency prioritized over peak single-thread performance |
| Deeply embedded/microcontroller cores (e.g., ARM Cortex-M series) | Almost always simple in-order | Extreme power/area constraints; workloads often don’t benefit much from OoOE complexity |
| GPU compute cores | Generally in-order, relying instead on massive thread-level parallelism to hide latency | Different parallelism strategy entirely — many simple threads rather than complex per-thread scheduling |
This spread illustrates that out-of-order execution isn’t a universally “correct” choice — it’s a specific trade-off that makes enormous sense for latency-sensitive, single-thread-performance-oriented general-purpose computing, but far less sense for throughput-oriented, massively parallel workloads (like GPUs) or extremely power/area-constrained embedded contexts, where simpler in-order designs, or entirely different parallelism strategies, win out instead.
Debugging and Observing Out-of-Order Behavior
For engineers working close to the hardware, understanding out-of-order execution isn’t purely theoretical — modern CPUs expose performance counters (accessible via tools like Linux’s perf or Intel’s VTune) that let developers measure things like retired instruction counts, pipeline stalls, reorder buffer occupancy, and specific stall reasons (waiting on a load, waiting on a functional unit, and so on). These counters are essential for performance engineers trying to understand whether a given piece of code is genuinely CPU-bound, memory-bound, or limited by some specific microarchitectural resource, and out-of-order execution’s internal behavior is frequently the difference between a naive theoretical performance model and what a profiler actually reports for real running code.
Wrapping Up
Out-of-order execution is the technique that lets modern CPUs stay busy despite the wildly uneven latencies of real-world memory systems and instruction mixes. By decoupling the order of execution from the order of results, processors can dynamically discover and exploit parallelism that a purely sequential reading of the program would never reveal. It’s a beautiful piece of engineering — register renaming eliminates false dependencies, reservation stations track real ones, and the reorder buffer quietly stitches everything back into the correct sequence at the end. It’s also a sobering reminder that performance and security aren’t always aligned, as Spectre and Meltdown demonstrated all too clearly. Understanding OoOE is essential to understanding why modern CPUs perform as well as they do — and why they’re as complicated as they are.