Tomasulo's algorithm
/ toh-mah-SOO-loh /
Imagine a workshop where each job ticket carries not the names of shelves but little claim-checks that say 'I am waiting for whatever job number 7 produces'. When job 7 finishes, it shouts its number across the room, and every ticket holding that claim-check grabs the result and proceeds. No one fights over shelf labels, and jobs run in whatever order their parts arrive. Tomasulo's algorithm is this scheme for a CPU: a hardware method, designed by Robert Tomasulo at IBM in 1967, that schedules instructions dynamically using reservation stations and tag-based result broadcasting.
It combines three ideas into one working machine. First, register renaming through reservation-station tags: instead of an operand naming an architectural register, it names the producing station, which dissolves WAR and WAW false dependences automatically. Second, reservation stations buffer each instruction with its known operands and tags for the unknown ones. Third, a common data bus (CDB) on which every finished result is broadcast together with its tag; every waiting station snoops the bus, captures any result whose tag it needs, and fires once complete. The flow per instruction is: issue (allocate a station, rename operands to tags), execute (when operands ready), and write result (broadcast on the CDB).
Its importance is historical and practical: it is the blueprint for virtually all dynamically scheduled out-of-order cores. The original 1967 version did not handle precise exceptions or speculation; the modern combination adds a reorder buffer so that, despite all the out-of-order execution, results still commit in program order and exceptions are precise. So 'Tomasulo plus a reorder buffer' is the standard textbook recipe for a real out-of-order, speculative core.
Station RS3 holds 'div f0 = f2 / f4' but f4 is not ready; RS3 records the tag of f4's producer. When that producer puts its result and tag on the common data bus, RS3 captures it, and the divide proceeds — no architectural register name was ever in the way.
Tags and a broadcast bus replace register names, so false dependences disappear.
Tomasulo's original 1967 design gave out-of-order execution but not precise exceptions or branch speculation — those need a reorder buffer added on top. Crediting Tomasulo alone for the modern speculative core overstates the 1967 algorithm.