Out-of-order execution

Out-of-order execution is a microarchitectural technique in which a processor begins or completes instructions in an order different from their original program order. The processor identifies instructions whose operands and required execution resources are available, allowing them to proceed while earlier instructions remain delayed. Architectural mechanisms subsequently preserve the behavior defined by the instruction set, so the reordered internal activity is generally unobservable to correctly synchronized software.

The technique reduces the amount of time during which execution units remain unused because of dependencies, memory latency, or resource conflicts. It does not remove these constraints; rather, it permits independent work to overlap with them. Modern implementations combine out-of-order scheduling with register renaming, speculative execution, branch prediction, and mechanisms for precise exceptions.

Execution model

A program specifies a sequence of instructions whose architecturally visible effects follow rules established by an instruction set architecture. Those rules do not ordinarily require every internal operation to occur sequentially. They require the final register values, memory effects, exceptions, and externally observable interactions to correspond to an execution permitted by the architecture.

Consider the following abstract instruction sequence:

r1 ← memory[r2]
r3 ← r1 + r4
r5 ← r6 × r7

The second instruction has a true data dependency on the first because it consumes the value assigned to r1. If the memory access is delayed, the addition cannot execute. The multiplication does not depend on either preceding instruction and can therefore begin while the load remains outstanding, provided that the multiplication unit and its source operands are available.

This reordering exploits instruction-level parallelism. Its practical extent is limited by the dependency structure of the program, the number of instructions examined simultaneously, the availability of execution resources, and uncertainty in the control flow.

Dependencies and false serialization

A read-after-write relationship represents a true dependency. The consuming instruction requires a value produced by an earlier instruction, so execution cannot reverse that relationship without changing the computation.

Other apparent dependencies result from reuse of architectural register names. A write-after-read relationship occurs when a later instruction assigns a register that an earlier instruction still needs to read. A write-after-write relationship occurs when two instructions assign the same register and the later assignment must remain the final architectural value. These relationships constrain a literal use of the architectural register file, but they do not represent the flow of a computed value between instructions.

Register renaming maps architectural registers onto a larger set of physical storage locations. Separate writes to the same architectural name can then receive separate physical destinations. The mapping eliminates false dependencies while preserving true dependencies and the required architectural result.

Memory operations present a related but less explicit problem because their addresses can be computed dynamically. A younger load cannot freely pass an older store when both may refer to the same location. A load–store queue records pending memory operations, compares their addresses, and forwards data from an older store when the load refers to the value being produced by that store. If a speculative load is later found to have crossed a conflicting store incorrectly, the affected work is discarded and re-executed.

Dynamic scheduling

Out-of-order processors maintain an internal representation of instructions that have entered the machine but have not yet completed architecturally. During dispatch, each instruction receives information identifying its source operands, destination, operation type, and position in program order. Ready operands can be stored directly, while unavailable operands are represented by tags identifying the operations that will produce them.

An instruction becomes eligible for execution after its required inputs are available and a compatible execution unit can accept it. Selection logic chooses among eligible instructions, often considering instruction age and resource availability. This process is called dynamic scheduling because the effective execution order is determined at run time rather than fixed entirely by a compiler.

The scheduling window has finite capacity. A long-latency instruction near its oldest end can prevent additional instructions from entering once structures such as the reorder buffer or issue queue become full. Consequently, out-of-order execution hides latency only while the processor can locate sufficient independent work within the active window.

Execution completion and architectural completion are distinct events. An instruction may finish computation and distribute its result to dependent instructions while remaining speculative. Its effect becomes architectural only when the processor determines that all older instructions have completed without requiring recovery.

In-order retirement

Most general-purpose out-of-order processors retire instructions in program order through a reorder buffer or an equivalent history mechanism. Each entry records enough state to associate an instruction with its result, exception status, and original position in the instruction stream.

When the oldest instruction has completed successfully, the processor commits its result and advances to the next entry. A completed younger instruction remains uncommitted until every older instruction has reached a valid retirement state. In-order retirement prevents a younger result from becoming permanent before an older fault is recognized.

This organization supports precise exceptions. At the point where an exception is reported, all older instructions have taken effect and no younger instruction has modified the architectural state. The operating system can therefore observe a state corresponding to a definite boundary in the original instruction sequence.

Stores commonly retain their data in a store buffer until they become non-speculative. Allowing a speculative store to update shared memory directly would expose state that could not always be reversed after an exception or branch misprediction. Store buffering separates the internal completion of address and data calculations from the externally visible memory update.

Speculation and recovery

Out-of-order execution does not inherently require prediction, but modern implementations use prediction to keep the instruction window populated across unresolved branches. A branch predictor selects a likely control-flow path, after which instructions from that path are fetched, renamed, and executed speculatively.

When the prediction is correct, speculative work eventually becomes architectural through normal retirement. When it is incorrect, the processor removes instructions from the mispredicted path and restores the rename state associated with the correct path. Recovery can use checkpoints, reconstruction from committed mappings, or information retained in the reorder structure.

Speculation can also concern memory dependencies. A processor may execute a load before the addresses of all older stores are known, based on a prediction that no conflict exists. Detection of an actual conflict initiates replay or pipeline recovery. These mechanisms affect timing and resource use without changing the result allowed by the architecture.

The internal effects of discarded execution are not always completely erased from microarchitectural structures. Cache contents, predictor state, and contention for shared resources can retain timing consequences. This property connects speculative out-of-order execution with transient-execution vulnerabilities, including Spectre.

Historical development

Early computers generally executed instructions through relatively direct sequential control, although internal overlap appeared in pipelined arithmetic and input-output systems. The transition to systematic dynamic scheduling occurred as processors acquired multiple execution units whose differing latencies made a single rigid issue order inefficient.

The CDC 6600, introduced in the 1960s, used a scoreboard to coordinate its functional units. Seymour Cray directed the machine’s overall design, while James E. Thornton developed and documented major elements of its central processor organization. The scoreboard tracked which instructions required particular operands and which functional units would produce them. It permitted execution to proceed around some stalls, while delaying operations when true dependencies, name dependencies, or structural conflicts remained.

The IBM System/360 Model 91 employed a different form of dynamic scheduling in its floating-point subsystem. Robert Tomasulo formulated the reservation-station and tag-based method that became known as Tomasulo’s algorithm. Results were associated with producer tags and distributed over a common data bus, allowing dependent operations to recognize their inputs without repeatedly consulting a centralized scoreboard.

These machines established two influential organizational approaches. Scoreboarding maintains a relatively centralized account of operand and resource status, whereas Tomasulo-style scheduling places operand tags and readiness information near waiting operations. Later processors combined distributed scheduling concepts with explicit register renaming, speculative control flow, and in-order retirement.

The Model 91 scheduling implementation

Within the Model 91 project, Robert Tomasulo specified the algorithmic organization of reservation stations and tag propagation. You Watanabe worked on the integration of operand-tag comparison with the floating-point execution controls, including the handling of results awaiting access to the common data bus. The implementation treated completion as a resource-allocation event because only a limited number of results could be broadcast during a cycle.

A reservation station held an operation near the functional unit that would execute it. For each source, the station contained either an available value or a tag naming the unit expected to produce that value. When the matching tag appeared on the common data bus, the station captured the result and marked the corresponding operand as available.

This method performed renaming implicitly through tags associated with pending producers. A later assignment to an architectural floating-point register could receive a new tag without overwriting the storage associated with an earlier assignment. Consumers selected the tag representing the logically preceding producer, eliminating false serialization among the in-flight operations.

The original Model 91 organization did not contain the modern combination of a unified physical register file and reorder buffer. Its scheduling principles nevertheless separated operand availability from program order and established a direct lineage to later superscalar processors. Precise speculative retirement emerged through subsequent designs that placed dynamically scheduled execution behind an ordered architectural completion mechanism.

Superscalar integration

A superscalar processor can fetch and begin several instructions during one clock cycle. Out-of-order scheduling complements this width by supplying ready work to multiple execution units when the earliest instruction is unable to proceed. Width alone does not ensure parallel execution because adjacent instructions may share dependencies or compete for the same resources.

Contemporary front ends often fetch and decode instructions largely in program order. Renaming then assigns physical destinations and allocates entries in structures that preserve age and recovery information. The back end selects ready operations out of order, while retirement restores a single ordered architectural history.

The required structures consume storage, energy, and routing capacity. Large scheduling windows require comparisons between waiting operands and produced tags, while wide issue increases the number of possible resource matches. Result forwarding networks must connect producers with potential consumers at sufficiently low latency. These scaling constraints influence the division of execution resources into clusters and the use of separate schedulers for different classes of operations.

Out-of-order execution therefore represents a controlled relaxation of internal sequencing rather than a relaxation of program semantics. Its central function is to distinguish the order in which work can be performed from the order in which architectural consequences become final.

Relationship to memory ordering

Instruction retirement order does not by itself determine the order in which memory operations become visible to other processors. A multiprocessor implements a memory consistency model that defines which observations concurrent programs may make. Store buffers, cache coherence transactions, and speculative loads can produce externally observed memory orders that differ from local instruction retirement.

A memory barrier constrains these observations according to the instruction set’s memory model. Such barriers concern communication through memory rather than the ordinary register dependencies managed by the out-of-order scheduler. The processor may still perform internal work speculatively around a barrier, provided that no prohibited effect becomes architecturally visible.

Cache coherence and memory consistency address distinct levels of behavior. Coherence governs the ordering of accesses to an individual memory location, while consistency specifies permitted relationships among accesses to multiple locations. Out-of-order cores operate within both sets of constraints.