Out-of-Order Execution

When you write a program, you order its instructions one after another. The CPU executes them — but not necessarily in that order.

Modern processors run at billions of cycles per second, yet a single load from main memory can stall the pipeline for hundreds of cycles. If the processor dutifully waited for every instruction to finish before starting the next, those hundreds of cycles would be wasted. So it doesn't.

Out-of-order execution lets the CPU look ahead, find instructions whose inputs are already ready, and execute them while the slow one is still waiting. The result arrives in program order; the journey is a controlled scramble behind the scenes.

The technique was formalized in 1967 by Robert Tomasulo at IBM, working on the System/360 Model 91 floating-point unit. His Tomasulo algorithm introduced two key ideas — reservation stations that hold an instruction until its operands arrive, and register renaming that eliminates false dependencies — and both are still the conceptual backbone of every high-performance processor built today.

Below is a simplified pipeline with four instructions. Instruction I2 takes several cycles to load from memory. Watch what happens to I3 and I4, which don't depend on I2's result.

<!-- {{c_html_intro}} -->
<div class="controls">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <span id="cycle-label" class="cycle-label">{{cycle_label_prefix}} <span id="cycle-num">0</span></span>
</div>
<div class="legend">
  <span class="swatch swatch-wait"></span>{{legend_wait}}
  <span class="swatch swatch-exec"></span>{{legend_exec}}
  <span class="swatch swatch-done"></span>{{legend_done}}
  <span class="swatch swatch-stall"></span>{{legend_stall}}
</div>
<!-- {{c_pipeline_table}} -->
<table id="pipeline" class="pipeline">
  <thead>
    <tr>
      <th>{{th_instr}}</th>
      <th>{{th_op}}</th>
      <th>{{th_deps}}</th>
      <th id="th-c1">C1</th>
      <th id="th-c2">C2</th>
      <th id="th-c3">C3</th>
      <th id="th-c4">C4</th>
      <th id="th-c5">C5</th>
      <th id="th-c6">C6</th>
      <th id="th-c7">C7</th>
      <th id="th-c8">C8</th>
    </tr>
  </thead>
  <tbody id="tbody"></tbody>
</table>
<div id="status-bar" class="status-bar"></div>
<p class="hint-para">{{hint_para}}</p>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; font-size: 14px; color: #222; margin: 0; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.cycle-label { font-size: .9rem; color: #555; margin-left: .4rem; }
.legend { display: flex; gap: .7rem; align-items: center; font-size: .82rem; margin-bottom: .5rem; flex-wrap: wrap; }
.swatch { display: inline-block; width: 14px; height: 14px; border-radius: 3px; margin-right: 3px; vertical-align: middle; }
.swatch-wait  { background: #d6dbe0; }
.swatch-exec  { background: #4ea8de; }
.swatch-done  { background: #52b788; }
.swatch-stall { background: #e76f51; }
/* {{c_table_style}} */
.pipeline { border-collapse: collapse; width: 100%; table-layout: fixed; }
.pipeline th, .pipeline td { border: 1px solid #c8d0d8; padding: .32rem .45rem; text-align: center; font-size: .82rem; }
.pipeline th { background: #eef1f4; font-weight: 700; }
.pipeline td:nth-child(1) { font-weight: 700; font-size: .85rem; }
.pipeline td:nth-child(2) { font-family: ui-monospace, monospace; font-size: .78rem; text-align: left; padding-left: .5rem; }
.pipeline td:nth-child(3) { color: #555; font-size: .78rem; }
/* {{c_cell_states}} */
.cell-wait  { background: #d6dbe0; }
.cell-exec  { background: #4ea8de; color: #fff; font-weight: 700; }
.cell-done  { background: #52b788; color: #fff; font-weight: 700; }
.cell-stall { background: #e76f51; color: #fff; font-weight: 700; }
.cell-future { background: transparent; color: transparent; }
.status-bar { font-size: .95rem; font-weight: 600; min-height: 1.3em; margin: .4rem 0; color: #1d3557; }
.hint-para { font-size: .83rem; color: #555; margin: .5rem 0 0; line-height: 1.45; }

// Code not found

Notice that I3 and I4 finish before I2 even completes — their operands were ready so the CPU didn't make them wait. I1's result feeds I2, so I2 must wait for I1 to finish first; I3 and I4 are fully independent and sprint ahead. This is the heart of out-of-order execution: work that can proceed does proceed, regardless of its position in program text.

Running instructions out of order is harder than it looks. Three classes of data hazard threaten correctness:

• RAW (Read After Write): instruction B reads a value that A hasn't written yet. This is a true dependency — B genuinely needs A's result. Out-of-order execution can't remove it; it can only fill the wait with other independent work.
• WAR (Write After Read): instruction B writes a register that A still needs to read. If B runs first, A gets the wrong value. This is a false dependency — both just happen to use the same register name.
• WAW (Write After Write): two instructions write the same register. Whichever finishes last must win. Another false dependency from register-name reuse.

Tomasulo's solution to WAR and WAW is elegant: register renaming. Each instruction is assigned a fresh internal tag instead of the architectural register name. Now two instructions can "use the same register" without interfering — they are actually writing to different physical locations. The reorder buffer (ROB) tracks the mapping and retires results in program order, preserving the illusion of sequential execution.

The algorithm is considered solved — Tomasulo published it in 1967, and modern processors add superscalar width, speculative execution and branch prediction on top, but the core mechanism is unchanged. It is a triumph of computer architecture rather than an open algorithmic question.

True RAW hazards are the only unavoidable stall; a deep out-of-order window (hundreds of instructions in flight simultaneously) hides even those by finding independent work further down the instruction stream. See also scheduling for the discrete-math cousin of this problem.

Out-of-order execution is not a niche optimization — it is the default mode of every high-performance processor:

• Superscalar CPUs: Intel, AMD, and ARM cores execute several instructions per cycle and look dozens or hundreds of instructions ahead for independent work. The ROB in a modern Intel core can hold over 500 instructions in flight simultaneously.
• Compiler design: compilers analyze data-flow graphs to schedule instructions and expose more independent work for the hardware to exploit. The compiler and the CPU are partners in extracting instruction-level parallelism.
• Hardware verification: proving that an out-of-order core produces the same results as an in-order specification is a formal verification problem. Bugs here are catastrophic and very hard to find by testing alone.
• Security — Spectre and Meltdown: in 2018, researchers showed that the CPU's speculative, out-of-order reads could leave traces in cache timing that an attacker could measure. The same mechanism that makes processors fast became a side-channel. Every major operating system and chip vendor had to issue patches.
• Embedded and real-time systems: timing-predictable cores deliberately disable out-of-order execution so software can reason about worst-case execution times — safety-critical code needs guarantees, not averages.

Robert Tomasulo's 1967 insight was simple and profound: instructions should execute as soon as their inputs are ready, not when their turn in the queue arrives. Register renaming removes the false dependencies that would block them; the reorder buffer commits results in order so the programmer never notices the scramble.

The technique solved a fundamental tension in computer architecture — sequential programs on parallel hardware — and it solved it so well that half a century of progress has added layers on top without replacing the core. The next time your browser tab, your game, or your server workload runs fast, a small piece of that speed traces back to a reservation station waiting patiently for an operand that hasn't arrived yet.