Introduction

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.

Try It

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.

<!-- Main layout — controls, legend, pipeline table, status bar -->
<div class="controls">
  <button id="btn-step" type="button">Step (1 cycle)</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
  <span id="cycle-label" class="cycle-label">Cycle: <span id="cycle-num">0</span></span>
</div>
<div class="legend">
  <span class="swatch swatch-wait"></span>Waiting
  <span class="swatch swatch-exec"></span>Executing
  <span class="swatch swatch-done"></span>Done
  <span class="swatch swatch-stall"></span>Stalled (dependency)
</div>
<!-- Pipeline table — one row per instruction, one column per cycle -->
<table id="pipeline" class="pipeline">
  <thead>
    <tr>
      <th>Instr</th>
      <th>Operation</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">I2 depends on I1 (RAW hazard). I3 and I4 are independent — they execute out of order and finish before I2 even completes. Step through cycle by cycle to watch the overtake.</p>

/* Styles for pipeline visualizer */
* { 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; }
/* Table layout */
.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; }
/* Cell color 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; }

// Out-of-order execution pipeline simulator (Tomasulo-style)
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Instruction table with dependency, start cycle, and execution latency
// Each instruction: id, display label, pseudo-op, dependencies, execution cycles,
// and latency (how many cycles the execution unit takes).
const INSTRUCTIONS = [
  { id: 'I1', op: 'R1 = ADD R0, 4',  dep: '-',   startCycle: 1, latency: 1 },
  { id: 'I2', op: 'R2 = LOAD [R1]',  dep: 'I1',  startCycle: 2, latency: 5 },
  { id: 'I3', op: 'R3 = MUL R5, R6', dep: '-',   startCycle: 1, latency: 2 },
  { id: 'I4', op: 'R4 = SUB R7, 1',  dep: '-',   startCycle: 1, latency: 1 },
];

const TOTAL_CYCLES = 8;
// Cell state constants
const S_FUTURE = 'future';
const S_WAIT   = 'wait';
const S_EXEC   = 'exec';
const S_STALL  = 'stall';
const S_DONE   = 'done';

// Build per-instruction timeline respecting data dependencies
// Build the cycle-by-cycle state for each instruction using Tomasulo-style rules:
// An instruction starts executing as soon as its dependency is done (or cycle 1 if none).
// It stalls if its dependency result is not yet available.
function buildTimeline() {
  const finishedAt = {};
  const timeline = {};
  for (const instr of INSTRUCTIONS) {
    const depDone = instr.dep === '-' ? 0 : (finishedAt[instr.dep] ?? 0);
    // Earliest cycle this instruction can start executing
    const canStart = Math.max(instr.startCycle, depDone + 1);
    const endCycle = canStart + instr.latency - 1;
    finishedAt[instr.id] = endCycle;
    const states = [];
    for (let c = 1; c <= TOTAL_CYCLES; c++) {
      if (c < canStart) {
        // Before canStart — show stall if blocked on a dep, else wait
        states.push(instr.dep !== '-' && depDone >= c ? S_STALL : S_WAIT);
      } else if (c <= endCycle) {
        states.push(S_EXEC);
      } else {
        states.push(S_DONE);
      }
    }
    timeline[instr.id] = { states, canStart, endCycle };
  }
  return timeline;
}

const TIMELINE = buildTimeline();

// Render the pipeline table up to the revealed cycle
function renderTable(revealUpTo) {
  const tbody = document.getElementById('tbody');
  tbody.innerHTML = '';
  for (const instr of INSTRUCTIONS) {
    const tl = TIMELINE[instr.id];
    const tr = document.createElement('tr');
    // Instruction id, op, and dep cells
    const tdId  = document.createElement('td'); tdId.textContent = instr.id; tr.appendChild(tdId);
    const tdOp  = document.createElement('td'); tdOp.textContent = instr.op; tr.appendChild(tdOp);
    const tdDep = document.createElement('td'); tdDep.textContent = instr.dep; tr.appendChild(tdDep);
    for (let c = 1; c <= TOTAL_CYCLES; c++) {
      const td = document.createElement('td');
      if (c > revealUpTo) {
        td.className = 'cell-future';
        td.textContent = '';
      } else {
        const st = tl.states[c - 1];
        td.className = 'cell-' + st;
        if (st === S_EXEC)  td.textContent = 'EX';
        if (st === S_DONE)  td.textContent = '✓';
        if (st === S_STALL) td.textContent = 'wait';
        if (st === S_WAIT)  td.textContent = '';
      }
      tr.appendChild(td);
    }
    tbody.appendChild(tr);
  }
}

// Update the status bar for the current cycle
function updateStatus(cycle) {
  const bar = document.getElementById('status-bar');
  if (cycle === 0) { bar.textContent = ''; return; }
  const executing = INSTRUCTIONS.filter(i => TIMELINE[i.id].states[cycle - 1] === S_EXEC).map(i => i.id);
  const stalling  = INSTRUCTIONS.filter(i => TIMELINE[i.id].states[cycle - 1] === S_STALL).map(i => i.id);
  if (cycle >= TOTAL_CYCLES) {
    bar.textContent = 'All instructions complete.';
    return;
  }
  let msg = '';
  if (executing.length)
    msg += i18nFmt('Executing: %ids%.', { ids: executing.join(', ') });
  if (stalling.length)
    msg += (msg ? ' ' : '') + i18nFmt('Stalled: %ids%.', { ids: stalling.join(', ') });
  if (!msg) msg = 'All units idle this cycle.';
  bar.textContent = msg;
}

let currentCycle = 0;
let runInterval = null;

function step() {
  if (currentCycle >= TOTAL_CYCLES) return;
  currentCycle++;
  document.getElementById('cycle-num').textContent = currentCycle;
  renderTable(currentCycle);
  updateStatus(currentCycle);
  document.getElementById('btn-step').disabled = currentCycle >= TOTAL_CYCLES;
  if (currentCycle >= TOTAL_CYCLES && runInterval) {
    clearInterval(runInterval);
    runInterval = null;
    document.getElementById('btn-run').disabled = true;
  }
}

function run() {
  if (runInterval) return;
  document.getElementById('btn-run').disabled = true;
  // Advance one cycle every 600 ms
  runInterval = setInterval(() => {
    step();
    if (currentCycle >= TOTAL_CYCLES) {
      clearInterval(runInterval);
      runInterval = null;
    }
  }, 600);
}

function reset() {
  clearInterval(runInterval);
  runInterval = null;
  currentCycle = 0;
  document.getElementById('cycle-num').textContent = '0';
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-run').disabled = false;
  renderTable(0);
  updateStatus(0);
}

document.getElementById('btn-step').addEventListener('click', step);
document.getElementById('btn-run').addEventListener('click', run);
document.getElementById('btn-reset').addEventListener('click', reset);

// Initialize with empty grid
reset();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/out-of-order-execution/Content licensed under CC BY-NC 4.0.