Lesson 6: Instruction-Level Parallelism & Out-of-Order Execution (Tomasulo)

Introduction: one core going faster by issuing several instructions at once

Lesson 5 kept the pipeline FULL by predicting which way a branch would go. But the scalar pipeline of Lesson 4 still ISSUES exactly 1 instruction per cycle, always in strict program order. A modern high-performance CPU goes further: it issues several instructions per cycle (superscalar), and lets a LATER instruction finish BEFORE an earlier one when there is no REAL data dependency between them — this is called out-of-order execution (OOO). The price: you must resolve the FALSE data dependencies created by having only a finite set of architectural registers, and you must guarantee the final architectural state is exactly as if everything had run sequentially. This lesson builds the classic algorithm that solves both: Tomasulo.

1. Instruction-level parallelism (ILP) & superscalar CPUs

ILP (instruction-level parallelism) measures how far NEIGHBOURING instructions in a program can run in parallel without changing the result. A scalar CPU issues 1 instruction per cycle; a superscalar CPU has several functional units (ALU, multiplier, load/store unit) and can issue and execute SEVERAL instructions at once — but how much of that it can actually use depends ENTIRELY on whether the program contains enough INDEPENDENT instructions.

2. False data dependencies & register renaming

Besides RAW (the REAL hazard from Lesson 4), there are 2 kinds of dependency that exist only because the PROGRAM reused ONE architectural register name for 2 values that are logically UNRELATED:

Register renaming removes WAR/WAW entirely: every time an instruction WRITES to an architectural register it is given a NEW "version" (in Tomasulo, a ROB index — the reorder buffer), and the register alias table (RAT) records "register X currently points at which version". Later instructions reading or writing that register automatically use the CORRECT version — so there is no longer any physical contention between the different "versions" of one register name.

// RAT[r] = null      -> the CORRECT value of register r lives in regFile
// RAT[r] = robIndex   -> the NEWEST value of r is still "in flight" in the ROB
//                        at position robIndex, NOT yet committed

// When ISSUING an instruction that writes to register dest:
//   RAT[dest] = newlyAllocatedRobIndex   // "RENAME" - create a NEW VERSION
// -> later instructions reading "dest" get this NEW VERSION through the RAT,
//    while earlier ones (which read "dest" at issue time, before the rename)
//    keep their OLD value - untouched by the overwriting instruction.

3. The Tomasulo algorithm: reservation stations + CDB + ROB

Tomasulo (IBM 360/91, 1967) was the first OOO algorithm and is still the foundation of modern OOO CPUs (x86, ARM). It has 3 main parts:

• Reservation Station (RS) — each functional unit has a few "reservation slots" holding instructions that are waiting for operands; as soon as BOTH operands are ready the station starts executing on its own (with no need to wait for earlier instructions it does not depend on).
• CDB (Common Data Bus) — a SHARED data bus that broadcasts results: every reservation station waiting for that value snoops the CDB and updates its operand the moment the value appears. Because it is a SHARED resource, ONLY 1 instruction may write its result per cycle — the LOSER waits another cycle.
• ROB (Reorder Buffer) — a buffer holding EVERY in-flight instruction in strict program order; even though instructions finish COMPUTING out of order, commit (officially writing to the architectural registers) always happens from the HEAD of the ROB — guaranteeing the final architectural state is identical to sequential execution.

// Every cycle, IN THIS ORDER: Commit -> Write-result (1 broadcast per cycle)
// -> decrement `remaining` on the executing RSs -> WAITING->EXECUTING once the
// operands have arrived -> Issue 1 new instruction (renaming dest via the RAT).
function runTomasulo(instructions, opts) {
  // ... see cpu-core.js for the full version - this is the per-cycle main loop ...
  // 1. COMMIT the head of the ROB if it is ready
  // 2. WRITE-RESULT: only 1 broadcast per cycle, LOWER robIndex wins (older first)
  // 3. Decrement `remaining` on the EXECUTING reservation stations
  // 4. WAITING -> EXECUTING once Qj and Qk are both null (operands arrived via CDB)
  // 5. ISSUE 1 instruction: RAT[dest] = the new robIndex (THE RENAME)
}
// Verified: the program MUL R1 / ADD R2 / SUB R1 (WAR on R2, WAW on R1)
// -> totalCycles=9, ipc=3/9=0.333, final R1=18 (from SUB, thanks to in-order commit)

4. Computing real IPC & how effective the algorithm is

First, the unit of measurement. IPC (Instructions Per Cycle — instructions completed per cycle) is simply the reciprocal of the CPI that Lesson 4 used: \(\text{IPC} = 1/\text{CPI}\). Two ways of saying the same thing, differing only in which direction is good — the lower the CPI the better, the cao the IPC the better. On an ideal scalar CPU the maximum IPC is 1; superscalar exists to get past that ceiling. At the 3-instruction scale of the examples below the IPC looks low because pipeline start-up cost dominates — what is worth comparing is the IPC of the versions against each other, not the absolute value.

Verified for real with the engine: the 3-instruction program MUL R1,R2,R3 / ADD R2,R4,R5 (WAR on R2) / SUB R1,R6,R7 (WAW on R1) — renaming resolves both false dependencies, and it runs in exactly 9 cycles, IPC = $3/9 = \mathbf{0.333}$. The final R1 is 18 (from SUB, correct per program order thanks to in-order commit — NOT the 12 from MUL which was overwritten, exactly the WAW meaning of "the later write wins"). Note that ADD (instr2) finishes COMPUTING (writeback in cycle 5) BEFORE MUL (instr1, writeback in cycle 6) — completion is OUT OF ORDER — and yet the commits still follow program order exactly (cycles 7, 8, 9 for instr1, instr2, instr3).

Instruction         Issue  ExecStart  Writeback  Commit
MUL R1, R2, R3        1        2          6          7
ADD R2, R4, R5        2        3          5          8
SUB R1, R6, R7        3        4          7          9

# ADD (writeback=5) finishes BEFORE MUL (writeback=6) - completion is OUT OF ORDER.
# But the commits still follow program order: 7, 8, 9 (MUL, ADD, SUB).
# 9 cycles in total, IPC = 3/9 = 0.333.

The control: the SAME 3 operations written as a REAL RAW chain (each instruction using the result of the one before) takes 11 cycles, an IPC of only $3/11 = \mathbf{0.273}$ — clearly slower, because a real dependency CANNOT be removed by any means, exactly as the pitfall in section 1 said.

// Program A: MUL R1 / ADD R2 (WAR) / SUB R1 (WAW) -> 9 cycles, IPC=0.333
// Program B: MUL R1 / ADD R2,R1 (real RAW) / SUB R3,R2 (real RAW)
//            -> 11 cycles, IPC=0.273 (slower, because the dependency is REAL)
// Program C: MUL R1 / ADD R4 / SUB R5 (no conflicts at all)
//            -> ALSO 9 cycles, same as program A - proof that renaming made A
//               exactly AS FAST AS having no conflict in the first place!

5. Why the ROB has to exist: precise exceptions

The ROB has appeared dozens of times so far in the role of "commit in order so the final result is right". But if the final result were all that mattered, a structure this expensive would not be needed — section 2 showed that register renaming on its own preserves data-flow semantics. The real reason the ROB exists lies elsewhere, and it only shows up when something goes wrong midway.

Suppose an instruction raises an exception : a divide by zero, an overflow, or most commonly of all — touching an address that is not in memory yet (a page fault, Lesson 8). The CPU has to jump into the operating system's handler, deal with it, and then resume the program. To be able to resume, the register state at that moment must be precise : exactly as if the program had run sequentially up to that instruction and stopped — not one instruction before it missing, and not one instruction after it applied.

But this CPU executes OUT of order. Section 4 measured it: instruction 2 writes back in cycle 5, instruction 1 not until cycle 6. So what does the register state look like if a fault lands in between? Run both kinds of machine on exactly the WAR/WAW program from section 4:

// Same program as section 4. Writeback cycles measured: [6, 5, 7]
// instr2 (ADD) finishes at cycle 5 - BEFORE instr1 (MUL) at cycle 6

// Case A: instruction 1 (MUL) faults
architecturalStateOnFault(program, { initialRegs, faultAt: 0 });
// with ROB    -> R2 = 3   (initial value: nothing has committed yet)
// without ROB -> R2 = 11  written by instr2, which has NOT run yet in program order

// Case B: instruction 2 (ADD) faults
architecturalStateOnFault(program, { initialRegs, faultAt: 1 });
// with ROB    -> R1 = 12  instr1 committed, exactly as the program requires
// without ROB -> R1 = 10  instr1 comes BEFORE the fault yet has not taken effect

That is exactly the ROB's job: let execution be as disorderly as it likes on the inside, while the effect on the architectural registers follows program order absolutely. At every instant there is a clean boundary — everything committed is settled past, everything still in the ROB is computation that does not officially exist yet.

6. Hands-on: a miniature interactive Tomasulo simulator

Pick one of the sample programs below to see the REAL Tomasulo schedule (issue / exec start / writeback / commit for each instruction) — comparing a WAR/WAW program (which renaming solves) directly against a real RAW chain (which it cannot) and a program with no conflicts at all:

Summary

• ✅ A superscalar CPU issues several instructions per cycle but is bottlenecked by REAL data dependencies (RAW) — verified: the real RAW chain takes 11 cycles against 9 for the WAR/WAW version.
• ✅ WAR/WAW are FALSE dependencies (purely register-name collisions) — register renaming (the RAT) removes them COMPLETELY, unlike RAW which cannot be removed.
• ✅ Tomasulo = reservation stations (waiting for operands) + the CDB (broadcast, 1 instruction per cycle) + the ROB (committing in program order despite out-of-order completion).
• ✅ Verified: the final R1 is 18 (from SUB, the LATER write in the program) — in-order commit preserves the correct WAW meaning even though ADD finished computing before MUL.
• ✅ Pitfall: a full ROB (usually caused by one instruction stuck at its head) triggers a ROB stall, halting instruction issue completely.
• ✅ The real reason a ROB is needed is precise exceptions: verified, when instruction 1 faults, the machine with a ROB keeps R2 = 3 (nothing has committed) while the machine without one already shows R2 = 11 — the value of an instruction that was NOT yet allowed to run.
• ✅ Verified in the opposite direction: with the fault at instruction 2, the machine without a ROB shows R1 = 10, meaning instruction 1 — which comes BEFORE the fault — has not taken effect. The state matches no point in the program, so it cannot be resumed.
• ✅ The same mechanism squashes mispredicted branches — so the ROB is a precondition for both out-of-order execution and branch prediction (Lesson 5), and the reason Spectre leaves its trace in the cache rather than in the registers.

Review quiz