Out-of-Order Execution
Subject: Computer and Technology noun /ˌaʊt əv ˈɔːr.dər ˌɛk.sɪˈkjuː.ʃən/ 1 definition
- computer-architecture
- cpu-microarchitecture
- instruction-level-parallelism
- dynamic-scheduling
-
Definition (noun)
Entry #355 · UpdatedOut-of-Order Execution (OoOE) is a CPU microarchitecture technique—also known as dynamic execution—in which a processor schedules and executes instructions as soon as their input operands and execution units are ready, rather than strictly following sequential program order. After fetching and decoding instructions sequentially, a modern OoOE core uses hardware register renaming to eliminate false write-after-read (WAR) and write-after-write (WAW) hazards, holding operations in reservation stations or an issue queue until true read-after-write (RAW) dependencies clear so ready instructions dispatch concurrently to idle functional units. Although instructions finish out of sequence, a circular Reorder Buffer (ROB) tracks their original order so the processor commits architectural register updates, buffered memory stores, and precise exceptions strictly sequentially. By overlapping useful computation around stalled instructions such as cache misses, OoOE extracts substantial instruction-level parallelism without altering single-threaded program semantics, though it remains bounded by a finite instruction window and incurs higher silicon area, power draw, and speculative side-channel exposure than in-order cores.
Common Forms
Scoreboarding: Uses a central hardware status table—pioneered in the CDC 6600—to track register and functional-unit readiness so independent instructions execute out of order, though it stalls on WAR and WAW hazards because it lacks register renaming.
Tomasulo's Algorithm: Eliminates false WAR and WAW dependencies using distributed reservation stations, implicit register renaming, and a Common Data Bus (CDB) that broadcasts computed results directly to waiting instructions.
Data-Capture Reorder-Buffer (ROB) OoOE: Combines Tomasulo-style reservation stations with a circular ROB—as used in Intel's P6 microarchitecture—storing speculative operand values directly inside buffer entries before copying committed results to the architectural register file in program order.
Physical-Register-File (PRF) Speculative OoOE: Maintains a large unified PRF alongside a Register Alias Table (RAT) and tag-only issue queues—standard in modern x86-64 and high-performance ARM cores—avoiding redundant data copying while supporting deep branch speculation and precise exceptions.
Example
Suppose an ARM64 core decodes
LDR X1, [X0]—which misses L1 and L2 caches and stalls for roughly 200 cycles waiting on main memory—followed by a dependentADD X2, X1, #1and two independent instructionsMUL X3, X4, X5andSUB X6, X7, X8. WhileLDRandADDwait in the issue queue, the out-of-order scheduler dispatchesMULandSUBimmediately to idle multiplier and ALU ports, buffering their results in physical registers until the Reorder Buffer commitsX1,X2,X3, andX6strictly in original program order.