The Tomasulo Algorithm is a dynamic scheduling mechanism designed to optimize instruction execution in microprocessors, allowing subsequent instructions to proceed even when a stall occurs. Introduced by Robert Tomasulo at IBM in 1967 for the IBM System/360 Model 91, it aimed to enhance instruction-level parallelism and execution efficiency by addressing data hazards. This algorithm pioneered implicit register renaming, an approach that mitigates Write After Read (WAR) and Write After Write (WAW) hazards, which can otherwise cause pipeline stalls. Unlike static register renaming, where compilers explicitly allocate different registers to avoid conflicts, Tomasulo’s method dynamically assigns placeholders called Reservation Stations (RS) to instructions, thus preventing conflicts during execution.
The development of the Tomasulo Algorithm was instrumental in shaping modern out-of-order execution architectures. It served as the foundation for high-performance processors such as the Alpha 21264, HP 8000, MIPS 10000, Pentium II, and PowerPC 604. Its primary objective, similar to the Scoreboard Algorithm, is to achieve high runtime performance without requiring specialized compiler optimizations.
Reservation Stations (RS)
Definition
A Reservation Station (RS) is a dedicated buffer positioned in front of a Functional Unit (FU), responsible for temporarily storing operands and computation results before they are written back to registers.
By acting as an intermediary between registers and execution units, Reservation Stations enable out-of-order execution, improving instruction throughput.
Example of Implementation of RS
DIV.D F0, F2, F4ADD.D F6, F0, F8 # RAW F0S.D F6, 0(R1) # RAW F6MUL.D F6, F10, F8 # WAW F6 with ADD.D # WAR F6 with StoreDIV.D F0, F2, F4ADD.D RS1, F0, F8 # RAW F0S.D RS1, 0(R1) # RAW RSMUL.D F6, F10, F8
Instead of directly referencing registers, instructions in the Tomasulo Algorithm use values or pointers to Reservation Stations, facilitating implicit register renaming. This approach dynamically resolves WAR and WAW hazards by allocating RS numbers rather than register file (RF) numbers, ensuring that execution dependencies do not stall the pipeline. Since the number of Reservation Stations typically exceeds the number of physical registers, the Tomasulo Algorithm can perform optimizations beyond what static compiler techniques can achieve.
Definition
A significant aspect of Tomasulo’s design is the Common Data Bus (CDB), which serves as a centralized communication channel. The CDB broadcasts computed results to all relevant Reservation Stations and Store Buffers rather than writing them directly to registers.
This mechanism resembles forwarding, where data dependencies are resolved efficiently by immediately supplying computed values to dependent instructions without requiring intermediate register writes. Furthermore, Store Buffers, which temporarily hold data before committing to memory, function similarly to Reservation Stations, ensuring that memory operations are also handled efficiently without unnecessary stalls.
Reservation Station Components
A Reservation Station (RS) consists of several key components that manage instruction execution, operand storage, and result forwarding. These components play a crucial role in enabling out-of-order execution and avoiding data hazards.
Tag: Each Reservation Station has a unique identifier that distinguishes it from others. This tag helps track which station is assigned to a particular instruction.
Busy: A flag that indicates whether the Reservation Station is currently occupied with an instruction. If set to true, it means the RS is actively processing an instruction and cannot accept new ones.
OP (Operation Type): Specifies the operation that the Functional Unit associated with the RS should perform (e.g., ADD, MUL, LOAD, STORE).
(Source Operand Values): These fields hold the actual values of the source operands required for computation. In the case of Load/Store operations, holds the memory address being accessed.
(Source Operand Tags): These fields store references to the Reservation Stations producing the values of operands and . If (or ), it means that the operand value is already available in registers or buffers, and no active instruction is computing the result.
Important
It is important to note that for each operand, either the V-field (actual value) or the Q-field (dependency tag) is valid, but never both simultaneously. If an operand is immediately available, it is stored in or ; otherwise, a reference to the producing Reservation Station is stored in or until the value becomes available.
Register File and Load/Store Buffers
The Register File (RF) and Store Buffers work together with the Reservation Stations to handle data dependencies and avoid pipeline stalls.
Each entry in the Register File and Store Buffers consists of:
(Value Field): Holds the actual value stored in the register or buffer.
(Pointer Field): Contains a reference to the Reservation Station that is computing the value to be written to this register or store buffer. If , it means the value is readily available and does not depend on any pending instruction.
This mechanism ensures that instructions can execute in an out-of-order fashion while still maintaining correctness, as operands are forwarded dynamically once they become available.
Load and Store operations require additional buffers to manage memory accesses efficiently. The Load Buffers and Store Buffers help track pending memory operations and prevent unnecessary stalls caused by memory dependencies.
Each Load/Store Buffer includes the following components:
Busy Flag: Indicates whether the buffer is currently occupied with an instruction.
Address Field: Stores memory address information necessary for load/store operations. Initially, this field contains the instruction offset (immediate field from the instruction). After address calculation, it is updated with the effective memory address.
For store instructions, the Store Buffer must wait until the corresponding value is computed by either the Register File or a Functional Unit before sending it to the memory unit. This ensures that stores do not commit incorrect values due to unresolved dependencies.
The Tomasulo Algorithm
The algorithm is structured around a distributed control logic model rather than a centralized scoreboard system. Each Functional Unit (FU) manages its own Reservation Stations, reducing contention and enhancing execution parallelism. This decentralized approach offers several advantages:
Dynamic Scheduling: Instructions can execute in an out-of-order fashion, depending on operand availability rather than a fixed program order.
Implicit Register Renaming: By replacing register identifiers with Reservation Station entries, Tomasulo’s scheme eliminates WAR and WAW hazards dynamically.
Increased Parallelism: Since Reservation Stations outnumber registers, Tomasulo’s method allows multiple independent instructions to be executed simultaneously, beyond the constraints imposed by register file size.
Common Data Bus (CDB) Broadcasting: Instead of writing results back to registers immediately, computed values are broadcasted to all Reservation Stations and Store Buffers, minimizing execution delays due to data dependencies.
Optimized Memory Operations: Store Buffers act as an extension of Reservation Stations for memory instructions, ensuring that loads and stores are properly scheduled without creating hazards.
Components of the Tomasulo Architecture
In the context of a Floating Point Unit (FPU), Tomasulo’s architecture consists of several essential components that enable efficient instruction execution:
Reservation Stations (RS): These are buffers associated with functional units that hold instructions waiting for execution. Each station stores the operation, operand values (if available), or tags indicating where operands will become available. Unlike traditional pipeline architectures, where instructions must wait for operands in registers, Tomasulo’s approach allows them to wait in reservation stations until dependencies are resolved.
Common Data Bus (CDB): The CDB is a key element in the architecture that enables communication between execution units and reservation stations. When an instruction completes execution, it broadcasts its result on the CDB so that other instructions waiting for that data can access it immediately. This mechanism eliminates unnecessary stalls caused by waiting for register updates.
Register File with Renaming: Instead of using a fixed set of physical registers, Tomasulo’s algorithm employs register renaming to avoid write-after-write (WAW) and write-after-read (WAR) hazards. Logical registers are dynamically mapped to physical registers or reservation stations, ensuring that instructions do not mistakenly overwrite values that are still needed by subsequent operations.
Floating Point Functional Units (FUs): These execution units perform arithmetic operations such as addition, multiplication, and division. Since floating-point operations typically have longer latencies compared to integer operations, the ability to schedule instructions dynamically ensures better utilization of these units.
How Tomasulo’s Algorithm Works in an FPU
Instruction Issue: When a floating-point instruction enters the pipeline, the control unit checks for an available reservation station. If one is available, the instruction is assigned to it. At this stage, the source operands are checked. If they are available in registers, they are copied to the reservation station. If not, a tag is assigned to track the source operand’s future availability.
Operand Availability and Execution: If both operands are ready, the instruction is sent to the appropriate floating-point functional unit for execution. If an operand is not ready, the instruction waits in the reservation station until it becomes available. The common data bus (CDB) facilitates this by broadcasting newly computed results to all waiting reservation stations, effectively allowing instructions to execute as soon as possible.
Write Back and Register Update: Once execution is complete, the result is broadcast on the CDB, and any waiting instructions that need the result can now proceed. The result is also stored in the designated register, but since Tomasulo’s algorithm uses register renaming, the register write operation does not stall dependent instructions.
Commit and Retirement: In the final stage, the computed result is committed to the architectural state. Since Tomasulo’s approach allows out-of-order execution, this step ensures that instructions complete in the correct order to maintain program correctness. However, the use of reorder buffers (in later implementations such as in modern superscalar processors) ensures that exceptions and control hazards are handled appropriately.
Pros
Cons
Elimination of Stalls Due to Data Hazards: Efficiently handles RAW, WAW, and WAR hazards through register renaming and reservation stations.
Increased Complexity: Requires additional control logic, reservation station buffers, and the common data bus, which can increase power consumption and chip area.
Efficient Utilization of Floating-Point Units: Maximizes the throughput of floating-point arithmetic units by allowing instructions to execute as soon as operands are available.
No Reorder Buffer (ROB) in Original Design: Modern processors integrate reorder buffers to ensure precise exception handling and maintain sequential program execution when necessary.
Dynamic Out-of-Order Execution: Enables instructions to be executed in an order that optimally utilizes available hardware resources.
Reduced Dependency on Compiler Optimization: Hardware handles instruction scheduling dynamically, reducing the need for aggressive compiler reordering to minimize stalls.
Stages of the Tomasulo Algorithm
The Tomasulo Algorithm operates in three main stages—Issue, Start Execution, and Write Results—which enable out-of-order execution while preserving data dependencies and correctness. The algorithm dynamically schedules instructions, resolves hazards, and improves instruction throughput by leveraging reservation stations (RS) and the common data bus (CDB).
Key Characteristics of the Tomasulo Algorithm
In-Order Issue, Out-of-Order Execution & Completion:
Instructions are fetched in FIFO order but can execute out of order as soon as their dependencies are resolved.
Implicit Register Renaming with Reservation Stations:
WAR and WAW hazards are prevented by dynamically renaming registers with RS identifiers instead of fixed register names.
Common Data Bus (CDB) for Result Forwarding:
Instead of writing back to registers immediately, results are broadcast to all dependent instructions via the CDB, reducing unnecessary stalls.
Decentralized Control:
Unlike traditional pipeline control, Tomasulo distributes control among Reservation Stations, allowing independent execution across multiple Functional Units.
Efficient Memory Handling with Load/Store Buffers:
Memory accesses follow a structured approach, maintaining program order for effective address calculation while still allowing parallel execution of non-dependent instructions.
Stage
In-Order
Out-of-Order
Description
Issue
✅
❌
Checks for available Reservation Stations and structural hazards. Renames registers using RS identifiers and tracks data dependencies.
Start Execution
❌
✅
Waits for operand availability and checks for RAW hazards. When operands are ready and FU is available, execution proceeds.
Write Results
❌
✅
Once execution completes, broadcast results to Reservation Stations, Store Buffers, and the Register File via the Common Data Bus. Store operations write data to memory when ready.
1. Issue Stage
In this first stage, an instruction is fetched from the instruction queue in FIFO (First-In, First-Out) order, ensuring that instructions are issued in-order to prevent structural and data hazards. The instruction undergoes the following checks and modifications:
Check for Available Reservation Stations (RS):
If an empty RS is available, the instruction is assigned to it.
If all reservation stations are occupied, the instruction stalls, preventing structural hazards.
Dependency Handling:
If source operands are not immediately available in the Register File (RF), the instruction records the identifier (Q pointer) of the Functional Unit (FU) that will produce the needed data.
If the operand is already available, it is stored directly in the V fields of the RS.
Implicit Register Renaming: Tomasulo dynamically renames registers by replacing them with reservation station identifiers, preventing Write-After-Write (WAW) and Write-After-Read (WAR) hazards.
WAR Resolution: If instruction I writes to register and an earlier instruction has already read from, then retains the correct value through its RS entry. This ensures that is unaffected by subsequent writes.
WAW Resolution: Since instructions are issued in-order, later instructions that write to the same register as a previous instruction are assigned different RS identifiers, preventing conflicts.
At the end of this stage, the instruction is assigned to an available Reservation Station, dependencies are recorded, and operands are tracked.
2. Start Execution Stage
Once an instruction has been issued and placed into a Reservation Station, it must wait until its required operands are available. Execution begins out-of-order, depending on operand readiness and Functional Unit availability.
Check for Operand Readiness:
If both operands are available, the instruction proceeds to execution.
If an operand is unavailable, the instruction monitors the Common Data Bus (CDB) until the required value is broadcast.
Check for Functional Unit (FU) Availability: Once operands are available, execution begins if a Functional Unit is free. If all FUs are occupied, the instruction waits, preventing structural hazards.
Forwarding via the Common Data Bus: When operands become available, they are broadcast on the CDB, allowing dependent instructions to proceed without waiting for a register write-back.
Load/Store Execution (Two-Step Process):
Step 1: Compute the effective memory address when the base register is available. The computed address is stored in the Load/Store Buffer.
Step 2:
Load Instructions: Execute as soon as the memory unit is available.
Store Instructions: Wait until the value to be stored is computed before committing to memory.
Maintaining Program Order for Memory Instructions:
Effective address computation ensures Load and Store instructions remain in program order, preventing memory hazards.
To maintain exception behavior, instructions do not execute until all preceding branches have resolved. If branch prediction is used, speculative execution may take place.
3. Write Results Stage
Once an instruction completes execution, its result is broadcast on the Common Data Bus (CDB) and written to all dependent Reservation Stations and the Register File (RF).
Broadcasting Results: The computed result is sent to:
All Reservation Stations waiting for this result.
The Register File (RF), if no further dependencies exist.
Store Buffers, if the result is a memory write.
Completion of Store Instructions: Store operations commit to memory only when both the memory address and data are available.
Releasing Resources: Once results are written back, the Reservation Station is marked available for future instructions.
This stage ensures efficient instruction completion while allowing subsequent instructions to continue execution without waiting for registers to be updated.
