Tomasulo's Algorithm: Out-of-Order Execution & Register Renaming

The Problem: Dependencies That Are Not Really There

Data dependencies between instructions come in three flavors, and only one of them is a genuine, unavoidable data dependency. A read-after-write (RAW) hazard, where an instruction needs a value a previous instruction has not yet produced, is a true dependency that must be respected no matter what. But write-after-write (WAW) and write-after-read (WAR) hazards are artifacts of a finite set of architectural register names being reused across a program, not genuine data flow. If instruction 1 writes register R1, instruction 2 reads R1, and instruction 3 later writes R1 again with a completely unrelated value, a naive in-order machine executing out of order would risk instruction 3 overwriting R1 before instruction 2 has read the original value, or results being written back in the wrong order and leaving R1 holding a stale value. These are called false dependencies precisely because they carry no actual information from one instruction to the other, they exist only because the compiler ran out of register names and recycled R1 for something new. Early processors either accepted the resulting stalls or required a smart compiler to work around them by choosing different registers. Tomasulo's insight was that the hardware itself could eliminate these false dependencies dynamically, at execution time, without the compiler even being aware, by giving each new write to a register a fresh internal tag rather than reusing a fixed physical slot.

Reservation Stations: Buffering Until Ready

At the heart of Tomasulo's design sit reservation stations, small buffers associated with each functional unit, such as adders or multipliers, that hold a dispatched instruction along with its operand values or, if a value is not yet available, a tag identifying which in-flight instruction will eventually produce it. When an instruction is dispatched, it is assigned to a free reservation station for the appropriate functional unit; if both its operands are already available in the register file or forwarded from a just-completed instruction, they are copied in immediately, otherwise the reservation station records the producing instruction's tag instead of a value. Crucially, dispatch does not stall waiting for operands, the instruction simply sits in its reservation station, and execution can begin the moment all its tagged operands have actually arrived, regardless of what program order says should happen next. This is precisely how independent instructions get executed out of order: an instruction whose operands are ready can begin executing even while an earlier, still-dispatched instruction sits waiting on a slow-to-produce value. Reservation stations effectively decouple the question of when an instruction is fetched and decoded from when it actually has everything it needs to run, turning program order into a loose suggestion for the execution stage rather than a hard requirement.

Register Renaming Through Tags

Tomasulo's algorithm implements register renaming without a separate, explicit physical register file the way later designs like the MIPS R10000 would; instead it uses a simple but powerful bookkeeping trick. A register status table tracks, for every architectural register, which reservation station (if any) currently holds the instruction that will produce its next value. When an instruction that writes to register R1 is dispatched, the register status table is immediately updated to point at that instruction's reservation station tag, so any later instruction that reads R1 before the write completes automatically picks up the correct, most recent producer's tag rather than a stale value. This single mechanism resolves WAW and WAR hazards for free: because each write gets a fresh tag rather than overwriting a fixed physical location, a later write to the same architectural register simply becomes a different tag, and any earlier reads that already captured the previous tag are unaffected by what happens to that register afterward. In effect, the small, fixed set of architecturally visible registers is dynamically mapped onto a much larger, implicit space of tagged values, one for every in-flight instruction that writes a register, which is exactly what modern register renaming does explicitly with large physical register files. The genius of Tomasulo's original scheme is that it achieved this renaming behavior as an emergent property of tag-based reservation stations rather than requiring dedicated renaming hardware.

The Common Data Bus and Out-of-Order Completion

Once an instruction finishes executing, its result needs to reach every reservation station and register status entry that is waiting on it, potentially several consumers simultaneously. Tomasulo's algorithm solves this with the common data bus (CDB), a broadcast bus that carries a completed result tagged with the producing instruction's identifier to all functional units and the register file at once, in a single cycle. Every reservation station continuously compares the tags it is waiting on against whatever tag currently appears on the CDB; any match causes that reservation station to latch the broadcast value into its own operand slot immediately, potentially making it ready to execute on the very next cycle. Because results broadcast in whatever order instructions actually finish, not the order they were dispatched, instructions complete strictly out of order relative to the program, a fast, independent addition might broadcast its result before a much earlier multiply has even finished. This is the direct payoff of the entire scheme: instructions execute and complete purely according to data availability, not program order, so a long-latency operation no longer blocks unrelated work behind it. The CDB does introduce a structural constraint of its own, since only one result can broadcast per cycle in the simplest designs, which is why modern superscalar processors extend the idea to multiple parallel result buses or forwarding networks rather than a single shared bus.

From the IBM 360/91 to Every Modern CPU

Robert Tomasulo designed this scheme specifically to let the IBM System/360 Model 91's floating-point unit, which had multiply and divide units with wildly different latencies, keep independent operations flowing instead of stalling behind the slowest unit. For roughly two decades the idea remained something of an academic curiosity outside of specialized supercomputers, until the early 1990s when it became the foundation for essentially every mainstream out-of-order microarchitecture: Intel's Pentium Pro introduced a unified reservation station and reorder buffer directly inspired by Tomasulo's approach, and its descendants extend through every subsequent Intel Core generation. AMD, ARM's high-performance cores, and IBM's own POWER line all use conceptually equivalent structures today, generally paired with a separate reorder buffer that tracks program order so that results, even though computed out of order, are committed to architectural state (retired) in the correct order, which is essential for precise exceptions and for the illusion of sequential execution that software correctness depends on. Modern implementations use explicit large physical register files and rename tables rather than Tomasulo's original CDB-broadcast tag matching, since a shared broadcast bus does not scale to the dozens of simultaneously in-flight instructions on today's chips, but the conceptual lineage is direct and unmistakable. When you use any modern high-performance CPU, from a smartphone to a data center server, the instructions are almost certainly being scheduled by hardware descended in spirit from a design built to speed up floating-point math on a 1967 mainframe.

Frequently asked questions

Try it live

Everything above runs in your browser — open Tomasulo's Algorithm: Out-of-Order Execution & Register Renaming and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.