The Machine Beneath the ISA: How modern processors stop waiting politely for slow instructions, dynamically discover independent operations, and yet guarantee the illusion of strict sequential execution.
The Instruction Set Architecture (ISA) promises the programmer that instructions execute one after another in strict program order: Instruction N+1 sees all changes made by Instruction N.
Microarchitectures are free to violate this internal execution order as long as the program-visible outcome is 100% indistinguishable from sequential execution.
Programs are not purely serial strings of math. Many instructions compute completely unrelated values on disjoint registers.
ILP is the potential to execute multiple independent instructions concurrently within a single program thread. Dynamic out-of-order execution is the hardware engine that finds and exploits this ILP at runtime.
Physical physics and arithmetic complexity dictate that operations cannot take equal time. An integer bitwise OR finishes in picoseconds; a double-precision floating-point divide or cache miss takes orders of magnitude longer.
Bit shifts, additions, bitwise AND/OR. Single-cycle combinational datapath.
In an in-order processor, instructions march down the pipeline like soldiers in single file. If instruction I2 requires an operand produced by instruction I1 that has not yet completed, the pipeline registers must inject bubbles (stalls).
Even if instructions further down the stream (like I4 or I5) are ready to compute, the in-order dispatch stage refuses to advance them. Valuable functional units—adders, multipliers, memory ports—sit completely idle.
Notice: I2 (MUL.D) has a true data dependency on I1 (L.D) for F6. That waiting is mathematically necessary.
However, I3, I4, and I5 waiting behind I2 simply because they were written later in the assembly file is an artifact of scheduling policy, not physical necessity!
34(R2). Takes 2 cycles.F6 from I1. (RAW True Dependency).F0 from I2.F8 from I3.Instructions are fetched and decoded strictly in program order. Operands are renamed to isolate dependencies before entering waiting stations.
Instructions sit in reservation stations snooping for their operands. As soon as all required inputs arrive and a functional unit is free, execution fires immediately.
Results complete out of order, but in modern processors, architectural registers and memory stores are only made permanent in strict program order via a Reorder Buffer (ROB).
A common beginner misconception is that out-of-order processors fetch or decode instructions randomly. They do not.
Strictly IN-ORDER. The hardware reads the program sequence consecutively to accurately track data dependencies.
OUT-OF-ORDER. Governed purely by dataflow readiness (when operands are valid), completely decoupled from program position.
Strictly IN-ORDER (in ROB architectures) to guarantee precise interrupts, branch misprediction recovery, and sequential semantics.
Notice how the long-latency DIV.D (6 cycles) completely overlaps with the execution of ADD.D F6, F8, F2.
In 1967, computer engineer Robert M. Tomasulo introduced his dynamic scheduling algorithm at IBM for the System/360 Model 91 floating-point execution unit. His goal was to maximize floating-point throughput across multiple arithmetic units without forcing software compilers to be hand-tuned to the specific pipeline latencies of the Model 91.
Instead of instructions waiting in a centralized register file or stalled pipeline register, each functional unit has distributed buffer slots called Reservation Stations.
Get the next instruction from the program queue. Find a free reservation station for this instruction's opcode. If no reservation station is free, stall instruction issue (Structural Hazard). Otherwise, allocate the station.
while instructions_remain_in_program():
// 1. ISSUE STAGE (Strict Program Order)
if next_instruction_ready_to_issue() and free_reservation_station_available():
allocate_station(inst)
capture_ready_operands_or_record_producer_tags(inst)
rename_destination_register(inst.dest, station.tag)
// 2. EXECUTE STAGE (Out-of-Order / Dataflow Driven)
for each station in busy_reservation_stations:
if station.operands_ready() and functional_unit_available():
execute_operation_cycle(station)
if station.execution_finished():
mark_ready_for_cdb_broadcast(station)
// 3. WRITE RESULT / BROADCAST STAGE (CDB Arbitration)
if station_ready_to_write_result():
broadcast_on_cdb(station.tag, station.result_value)
wake_up_waiting_reservation_stations(matching_tag)
update_register_status_and_value(matching_tag)
release_reservation_station(station)
// 4. COMMIT STAGE (Modern Reorder Buffer Extension)
if using_reorder_buffer() and rob_head.is_ready():
retire_instruction_in_order(rob_head)
commit_to_architectural_state(rob_head)A consumer instruction requires a numerical value produced by an earlier instruction. ADD.D requires the product computed by MUL.D. Register renaming cannot eliminate this hazard because the data physically does not exist yet. The consumer must wait until the producer broadcasts.
No! True data dependencies represent fundamental physical dataflow. You cannot compute an answer before its inputs are produced.
If all 2 Multiplier stations (Mul1, Mul2) are full, dispatch must STALL until one completes and broadcasts.
If multiple reservation stations have ready operands simultaneously, they arbitrate for limited ALU ports.
If Add1 and Mul1 finish in the same clock cycle, only one can broadcast on the single CDB. Priority arbitration decides who wins.
Architectural Purpose: Holds pending operations and their operands right at the functional unit inputs, decoupling issue from execution.
Busy flag, Opcode, Vj & Vk (operand values), Qj & Qk (waiting producer tags), Dest tag.
Constantly snoops the Common Data Bus, comparing Qj/Qk tags with broadcast tags.
Operands from Register File / RAT at issue; broadcast results from Common Data Bus (CDB).
Operands and start signals to Arithmetic Functional Units when all operands are valid.
Comparison of independent operations vs sequentially dependent operations across pioneering architectures.
| Machine | Year | Independent (MFLOPS) | Dependent (MFLOPS) | Parallelism Ratio | Microarchitecture Key Innovation |
|---|---|---|---|---|---|
| IBM 7090 | 1959 | 0.046 | 0.046 | 1.0× | Sequential vacuum-tube/transistor baseline |
| CDC 6600 | 1964 | 4 | 1.3 | 3.08× | Central Scoreboard with 10 functional units |
| IBM S/360 M91 | 1967 | 11 | 6.7 | 1.64× | Robert Tomasulo's reservation stations & CDB |
| ACS-1 | 1968 est. | 160 | 27 | 5.93× | Advanced Computing Systems out-of-order design |
These are historical performance estimates across distinct physical computer systems designed over a nine-year period (1959–1968), NOT a controlled ablation experiment comparing Tomasulo's Algorithm against an identical in-order core. The machines differ in clock frequencies (e.g. 7090 at ~450 kHz vs Model 91 at 16.6 MHz), transistor logic family, memory hierarchies, and functional unit counts. The graph illustrates the theoretical headroom of instruction-level parallelism under dependent vs independent code; it must not be interpreted as attributing all performance differences solely to Tomasulo's algorithm.
Simulation reset to Cycle 0. Ready to issue the first instruction (L.D F6, 34(R2)).
| Select | Instruction | Issue | Exec Start–End | CDB Write | Current State |
|---|---|---|---|---|---|
| 👉 | L.D F6, 34(R2) | — | — | — | Waiting |
| #2 | MUL.D F0, F4, F6[Consumer] | — | — | — | Waiting |
| #3 | ADD.D F8, F0, F2 | — | — | — | Waiting |
| #4 | DIV.D F10, F0, F6[Consumer] | — | — | — | Waiting |
| #5 | ADD.D F6, F8, F2 | — | — | — | Waiting |
| Reg | Producer Qi | Architectural Value |
|---|---|---|
| F0 | — | 0.0 |
| F2 | — | 2.0 |
| F4 | — | 4.0 |
| F6 | — | 0.0 |
| F8 | — | 0.0 |
| F10 | — | 0.0 |
| R2 | — | 100.0 |
| Station | Busy | Op | Vj (Ready Val) | Vk (Ready Val) | Qj (Wait Tag) | Qk (Wait Tag) | Dest | Remaining Latency |
|---|---|---|---|---|---|---|---|---|
| Load1 | no | — | — | — | — | — | — | — |
| Add1 | no | — | — | — | — | — | — | — |
| Add2 | no | — | — | — | — | — | — | — |
| Mul1 | no | — | — | — | — | — | — | — |
| Mul2 | no | — | — | — | — | — | — | — |
Modern high-performance processors (such as Intel Golden Cove, AMD Zen 5, and Apple M4) still rely on the foundational dynamic scheduling principles invented by Robert Tomasulo in 1967, but adapt them into scalable, modern microarchitectures:
| Concept | 1967 Classic Tomasulo | Modern OoO Processors |
|---|---|---|
| Renaming | Distributed in Reservation Stations | Physical Register File (PRF) + RAT |
| Queues | Small distributed stations (2–3 entries) | Unified Issue Queues (128–256+ entries) |
| Retirement | Imprecise, updates registers on CDB | In-order Reorder Buffer (ROB 512+ entries) |
| Branching | Static branch handling / stalls | Branch Predictors + Speculative Commit |
Hides long operation latencies (memory cache misses, complex divides)
Exploits hidden Instruction-Level Parallelism dynamically
High silicon area and static power consumption
Extreme verification complexity for branch misprediction rollbacks
Out-of-order execution is an engineering trade-off: spending millions of transistors and watts of electrical energy on rename tables, wake-up comparators, and reorder buffers in exchange for running single-threaded sequential code as close to theoretical dataflow speed as possible.
“Execute when ready. Broadcast once. Retire in order.”
The three-part creed that governs every modern high-performance microarchitecture.