The Tomasulo algorithm
is an algorithm
developed by Robert Tomasulo (not related to R.O.B
) from IBM
to execute instructions out of order. This algorithm differs from scoreboarding because scoreboarding does not have register renaming. Instead, scoreboarding resolves hazards by stalling, whereas the Tomasulo algorithm can still issue instructions. Also, the Tomasulo algorithm uses a common data bus on which computed values are broadcasted to all reservation stations that may need it. This allows for parallel execution of instructions that may have been stalled waiting for this value. This algorithm uses register
renaming (to reservation stations) to avoid WAW and WAR hazards.
It was first implemented for the IBM360/91's floating point unit. The latest known implementation is thought to have been used in the Ozone Processor developed by the CS152DreamTeam at U.C. Berkeley in Fall 2003.