# Tomasulo’s Algorithm – Reservation Stations (RS)

In Tomasulo’s algorithm, instructions are issued in sequence to Reservation Stations which buffer the instruction as well as the operands of the instruction. If the operand is not available, the Reservation Station listens on a Common Data Bus for the operand to become available. When the operand becomes available, the Reservation Station buffers it, and the execution of the instruction can begin.

Functional Units (such as an adder or a multiplier), each have their own corresponding Reservation Station. The output of the Functional Unit connects to the Common Data Bus, where Reservation Stations are listening for the operands they need.

In the above microarchitecture, the FP Adder has 3 Reservation Stations. The FP Multiplier and Integer Unit both have 2 Reservation Stations

If all the Reservation Stations for a Functional Unit are occupied, the next instruction for that Functional Unit cannot be issued and has to wait.

Only when all the operands are available does the Functional Unit begin execution. When the execution completes that Reservation Station is free to buffer the next instruction.

## Structure

Each Reservation Station has the following fields

### Op

The operation to perform on source operands S1 and S2.

### Qj, Qk

The Reservation Stations that will produce the corresponding source operand; a value of zero indicates that the source operand is already available in Vj or Vk, or is unnecessary.

### Vj, Vk

The value of the source operands. Note that only one of the V fields or the Q field is valid for each operand. For loads, the Vk field is used to hold the offset field.

### Busy

Indicates that this Reservation Station and its accompanying functional unit are occupied.

## Example

Reservation Station Add2 is performing ADD operation. One operand is available – the value in register F4. The other operand is waiting for the result from Reservation Station Add1 to be broadcasted over the Common Data Bus. Once the value is broadcasted it will be available in Vj.