Tomasulo Algorithm for Dynamic Scheduling

Apply reservation stations and common data buses to resolve write-after-read and write-after-write hazards through register renaming.

In this lesson, you will learn how the Tomasulo Algorithm uses reservation stations and a common data bus to eliminate name-based hazards through register renaming.

The Problem: Name Hazards

In standard pipelining, we often hit "name hazards"—Write-After-Read (WAR) and Write-After-Write (WAW) dependencies. These occur not because of true data flow, but because we have a limited number of architectural registers (like R1, R2). If two instructions happen to use the same register name, the pipeline must stall to prevent one from overwriting the other too early.

The Solution: Register Renaming

The Tomasulo Algorithm sidesteps these hazards by introducing Reservation Stations (RS). Instead of reading values directly from a global register file, instructions are dispatched to an RS. If the data isn't ready, the RS "listens" for it.

When a value is computed, it is broadcast on the Common Data Bus (CDB). Any RS waiting for that specific data grabs it immediately. By assigning each operation a unique tag (the identity of the RS that will produce the result), we decouple the instruction from the specific physical register.

Consider this sequence:

ADD R1, R2, R3
SUB R1, R4, R5

A classic pipeline would stall the SUB because it writes to R1 before the ADD finishes. With Tomasulo:

The ADD is dispatched to RS1.
The SUB is dispatched to RS2.
Even though both target R1, the hardware tracks them as independent operations (RS1 vs RS2). The "name" R1 is essentially renamed to the identity of the station. This allows both to proceed without waiting for the other to clear the register file.

Why this matters

By treating the registers as symbolic names and using reservation stations as temporary "holding pens," the CPU can execute instructions out-of-order as soon as their operands are available. The Common Data Bus acts as a broadcast system, ensuring that once a value is computed, it is instantly available to all dependent instructions, effectively bypassing the bottleneck of the register file and preventing artificial stalls.

Key Takeaway: The Tomasulo Algorithm eliminates WAR and WAW hazards by using register renaming in reservation stations and broadcasting results via a Common Data Bus, allowing hardware to resolve dependencies dynamically.