Out-of-Order Execution
Out-of-order execution runs instructions as soon as their inputs are ready rather than in program order, hiding latency.
Beyond In-Order
An in-order pipeline stalls the moment an instruction's inputs are not ready, even if later independent instructions could run. Out-of-order execution lets the processor look past a stalled instruction, execute whatever is ready, and reassemble the results so the program still appears to run in order. This hides the latency of slow operations like cache misses and long-latency arithmetic.
Register Renaming
Reordering exposes false dependencies: two instructions that reuse the same architectural register but are otherwise independent. Register renaming maps each architectural register to a fresh physical register from a large pool, eliminating write-after-write and write-after-read hazards so only true data dependencies constrain the schedule.
Tomasulo's Machinery
The classic mechanism uses reservation stations that hold instructions waiting for operands, and a common data bus that broadcasts results to every waiting station the moment they are produced. An instruction fires when all its operands have arrived, regardless of program order.
- Issue: decode, rename, and place into a reservation station
- Dispatch: fire when operands are ready and a unit is free
- Complete: broadcast the result to waiting instructions
In-Order Retirement
Although instructions execute out of order, they must retire (commit their results and be visible to the program) in order, so exceptions and mispredictions leave a clean, precise state. A reorder buffer holds results until every earlier instruction has retired, then commits them in sequence. If a branch was mispredicted or a fault occurs, everything after the offending instruction is squashed.
Out-of-order execution is the foundation of high-performance CPUs. It is expensive in area and power, so simple, energy-focused cores often stay in-order and rely on other techniques for throughput.