Advanced ILP Part 1: Dynamic Scheduling and Out-of-Order Execution (Scoreboarding and Tomasulo)

To exploit Instruction-Level Parallelism (ILP), computer architects rely on scheduling techniques to resolve hazards and prevent pipeline stalls. There are two primary approaches:

1. Static Scheduling: This is a software-based approach where the compiler arranges and reorders instructions prior to runtime (compile time),. The compiler attempts to separate dependent instructions so that hazards are resolved before the code is ever fed to the processor.
2. Dynamic Scheduling: This is a hardware-based approach where the processor itself rearranges the execution order of instructions on the fly (at runtime),. The hardware detects data dependences and allows instructions to bypass stalled predecessors, executing out of order to reduce pipeline stalls while strictly maintaining the original data flow and exception behavior.

Advanced ILP Part 1: Dynamic Scheduling and Out-of-Order Execution (Scoreboarding and Tomasulo)

Scoreboarding: The Central Clearing House

Scoreboarding is a classic technique for implementing dynamic scheduling and allowing out-of-order execution. It was first pioneered in the CDC 6600 mainframe. Introduced in 1964 and prominent into the early 1970s, the CDC 6600 was highly advanced, featuring 11 separate execution units: 7 integer units and 4 floating-point units (consisting of 1 adder, 2 multipliers, and 1 divider).

To manage these resources, the architecture used a Scoreboard, which acts as a central clearing house or “central brain” for tracking and controlling the entire pipeline. Rather than allowing each pipeline stage to act completely independently, every instruction must check in with this centralized controller to get permission to advance.

Pipeline Stages: IS and RO (Replacing Decode)

To support out-of-order execution, scoreboarding eliminates the traditional Instruction Decode (ID) stage and splits its duties into two distinct stages:

1. Issue (IS): This stage replaces the first part of ID. It decodes the instruction and relies on the scoreboard to check for structural hazards and WAW (Write After Write) hazards. If the required functional unit is busy, or if another active instruction is already slated to write to the same destination register, the instruction stalls here in the IS stage.
2. Read Operands (RO): This new stage resolves RAW (Read After Write) hazards dynamically. The scoreboard continuously monitors the availability of source operands.

The Key Difference from the Old Decode Stage

In a standard pipeline, if the ID stage detects a RAW hazard, the instruction stalls and blocks the entire pipeline behind it. In scoreboarding, an instruction with a RAW hazard is allowed to advance from IS into RO. The RO stage features a special buffer where the hazardous instruction is set aside and held by the scoreboard. By buffering the stalled instruction off the main path, the active slot in the RO stage is freed, allowing subsequent, dependency-free instructions to leapfrog the stalled instruction and proceed into the execution phase.

Instruction Flow and Completion

Scoreboarding modifies the fundamental flow of instructions:

• In-Order Fetch and In-Order Issue: Instructions are fetched and issued into the pipeline strictly in their original programmed order.
• Out-of-Order Execution: Because independent instructions can bypass stalled ones in the RO buffer, instructions enter the execute phase out of order.
• Out-of-Order Completion: Instructions with shorter latencies will finish and leave the pipeline before older, longer-latency instructions.

Pipeline Stalls, Buffer Constraints, and the Look-Ahead Window

While scoreboarding heavily reduces stalls, stalls still occur:

• The pipeline stalls in the IS stage for structural and WAW hazards.
• The pipeline stalls in the RO stage if the RO buffer is already full and a new instruction arrives with a RAW hazard. Because it cannot move to the execution unit and cannot be buffered, it occupies the active RO slot and hard-stalls the pipeline behind it.

The size of the RO buffer dictates the look-ahead window, a free design parameter. This window represents the collection of future instructions the scoreboard can scan to find safe, independent operations. A larger buffer increases the look-ahead window and the likelihood of finding a bypassable instruction, but greatly increases hardware complexity.

Crucial Operations: Deadlock Prevention

With multiple instructions buffered in RO vying to advance, the scoreboard must decide which one is granted the execution unit. To prevent deadlock, the scoreboard must strictly enforce the oldest instruction priority. Whenever there is a resource conflict, the instruction that was fetched earliest in the program sequence is allowed to advance, preventing younger instructions from permanently blocking older ones.

Scoreboarding in Action

Consider the following floating-point sequence:

1. fmul.s f2, f1, f4
2. fadd.s f1, f2, f3
3. fadd.s f6, f7, f8

Scoreboarding handles three hazard scenarios simultaneously: a RAW hazard on f2 buffers fadd.s f1,f2,f3 in the RO stage for 6 cycles; an independent fadd.s f6,f7,f8 bypasses the stalled instruction entirely, demonstrating out-of-order execution and out-of-order completion; and downstream instructions are stalled early in IS to prevent a structural hazard at the WB stage.

The pipeline diagram above shows three instructions running through a scoreboarded pipeline, where the standard ID stage is split into IS (Issue) and RO (Read Operands). At the IS stage, the scoreboard checks for structural hazards (is the functional unit free?) and WAW hazards (is another instruction already writing to the same destination register?). If either is detected, the instruction stalls right there in IS. At the RO stage, the scoreboard checks for RAW hazards — if a source operand is still being computed by an earlier instruction, the instruction is moved into a RO buffer (marked as RO⑧ in the diagram) and waits there until the result is broadcast. This is exactly what happens to fadd.s f1,f2,f3 — it detects a RAW hazard on f2 (still being computed by fmul.s) and sits buffered from CC4 all the way through CC9, only reading its operands at CC10 once fmul.s finishes. Meanwhile, fadd.s f6,f7,f8 has no dependencies, so it leapfrogs the buffered instruction and executes completely out of order — this is out-of-order execution. Notice also the bottom-most instruction stalling in IS (IS/S) at CC7–CC9. This is deliberate: the scoreboard stalls it early to prevent a structural hazard on the WB stage, since multiple instructions finishing around the same time cannot all write results simultaneously. The scoreboard catches this conflict early in IS rather than letting it propagate to WB.

Overhead and the Bottleneck of Scoreboarding

The massive overhead of scoreboarding stems from the fact that this central brain must micromanage every detail of the pipeline via huge matrices of data and countless extra buses connecting every stage to the scoreboard. The scoreboard actively performs:

1. Register Tracking: For every single register, it records exactly which active functional unit is slated to write a result to it.
2. Instruction Tracking: It records the exact pipeline stage of every single active instruction on the fly to detect real-time hazards.
3. Functional Unit Tracking: It tracks the busy/free status of all 11 execution units to prevent structural hazards at the Issue stage.

Ultimately, the scoreboard itself becomes the biggest bottleneck. Because every instruction must query the centralized controller before advancing anywhere in the pipeline, clock frequencies are severely limited. To scale performance further, computer architects had to abandon the centralized scoreboard in favor of a decentralized, distributed algorithm known as Tomasulo’s Algorithm, which utilizes hardware register renaming through distributed reservation stations.

Tomasulo’s algorithm

Tomasulo’s algorithm is a sophisticated dynamic scheduling technique invented by Robert Tomasulo for the IBM System/360 Model 91 floating-point unit. At the time, the IBM 360 architecture only provided four double-precision floating-point registers, which severely limited the compiler’s ability to schedule instructions and avoid pipeline stalls. Tomasulo’s algorithm was specifically designed to overcome this severe shortage of architectural registers, mask long memory access times, and allow overlapping execution of floating-point operations.

The Main Idea: Distributed Hardware Register Renaming

The fundamental idea driving Tomasulo’s algorithm is hardware register renaming implemented in a decentralized, distributed manner. Unlike earlier dynamic scheduling techniques like scoreboarding — which relied on a centralized “brain” or clearinghouse to control all instruction advancement — Tomasulo’s algorithm distributes hazard detection and execution control directly to the hardware units.

By dynamically renaming architectural registers to internal hardware buffer identifiers, Tomasulo’s algorithm successfully eliminates name dependencies — specifically Write-After-Write (WAW) and Write-After-Read (WAR) hazards. This renaming process prevents out-of-order writes from affecting instructions that depend on earlier versions of an operand, massively increasing the processor’s ability to execute instructions out of order without stalling.

Reservation Stations

The core physical mechanisms used to achieve this distributed hardware renaming are called Reservation Stations (RS).

• Definition: Reservation stations are specialized hardware buffers or wrappers placed directly in front of the functional execution units (such as ALUs, multipliers, or memory load/store units).
• Virtual vs. Real: Processors typically implement more reservation stations than actual execution units. For instance, a CPU might have one floating-point multiplier but two reservation stations managing it. When an instruction is simply sitting in the buffer waiting for its operands, the RS acts as a “virtual” reservation station. It only becomes a “real” reservation station when it actively utilizes the functional execution unit

Duties Managed by the Reservation Station

The reservation station acts as a “mini control unit” dedicated solely to managing the execution phase for its specific functional unit. Its duties include:

• Fetching and Buffering Operands: The RS fetches and holds operand values as soon as they become available. This eliminates the need to route back to the centralized register file later to retrieve operands.
• Managing Execution Access (“Just-in-Time” Execution): The RS determines exactly when an instruction is safe to begin execution at the functional unit. By storing the instruction physically next to the functional unit and releasing it the very instant its final operand arrives, it implements a “just-in-time” manufacturing model for instruction execution.
• Monitoring the Bus: Every RS continuously monitors the broadcasting medium (the Common Data Bus) to “snoop” for the specific results it is waiting for to complete its pending operands.

Stages of Tomasulo’s Algorithm

Tomasulo’s algorithm replaces traditional pipeline phases with three arbitrary-length stages:

1. Issue: The processor fetches the next instruction from the queue. If there is an empty reservation station that matches the instruction’s type, the instruction is issued to the RS. If the required operands are already sitting in the register file, their actual numerical values are copied directly into the RS. If the operands are not yet computed, the RS instead records the identifier of the other reservation station that will eventually compute them. This exact step achieves register renaming and eliminates WAR and WAW hazards. If no RS is available, the issue stage suffers a structural hazard and stalls.
2. Execute: If one or more operands are not yet available, the instruction safely waits in the RS and monitors the Common Data Bus. When the needed operand is broadcast, the RS grabs it. Once all operands are present, the instruction immediately begins execution at the functional unit. Delaying execution until this point successfully prevents RAW (Read-After-Write) hazards.
3. Write Result: When the functional unit computes the final result, it is immediately broadcast on the Common Data Bus. From there, it is written to the destination register in the register file and simultaneously grabbed by any waiting reservation stations.

Application in the RISC-V Pipeline

When applying Tomasulo’s algorithm to the standard RISC-V pipeline, the traditional Instruction Decode (ID) stage is split into two distinct sub-stages:

• Decode (D): This stage determines the identity of the required operands. If the operands are ready, it fetches their values. If they are not ready, the decoder queries its tables to determine the specific reservation station that is currently slated to produce those operands.
• Issue (IS): This stage physically routes the instruction to an available virtual or real reservation station, sending along either the operand values or the reservation station identifiers.

How Instructions Bypass Each Other via the Common Data Bus (CDB)

A critical feature of Tomasulo’s algorithm is how it distributes results using the Common Data Bus (CDB). In older architectures, results had to be written into the centralized register file before subsequent instructions could read them. In Tomasulo’s, the result is broadcast directly from the execution unit onto the CDB. Because every reservation station monitors the CDB, multiple instructions waiting on that single result can grab the data simultaneously and instantly begin execution on the very next clock cycle. This bypasses the register file completely, allowing independent instructions to freely leapfrog stalled ones.

Data Maintained

To track dependencies without a centralized scoreboard, the distributed hardware maintains several data structures:

• Instruction Status: Tracks the current pipeline stage of every active instruction in the system (e.g., issued, executing, or writing result).
• Reservation Station Status: Each RS entry holds 7 fields: Op (the operation), Vj and Vk (the buffered values of ready source operands), Qj and Qk (the tags of the reservation stations that will produce pending operands), A (memory address calculations), and a Busy flag.
• Register Status Table: The register file maintains a field called Qi for every single architectural register. This field tracks the identifier of the reservation station that is currently slated to write the next result into that register.

Tomasulo’s Algorithm Example

Unlike scoreboarding, Tomasulo’s algorithm assigns RS tags at the D stage, renaming registers in-flight and eliminating WAR/WAW hazards without IS stalls. RAW hazards still cause instructions to wait in their reservation stations () for results broadcast on the CDB. The shared ALU structural hazard between addwi and or is the only remaining source of stalls — one functional unit, one instruction at a time.*

In this sequence, the mul.w instruction relies on the result of div.w for x5 (a true RAW dependency), meaning it must wait for the long-latency division to finish. Furthermore, both the mul.w and the add.iw target the same destination register x1, creating a WAW (output) dependency. Under Tomasulo's algorithm, the faster add.iw and or instructions are issued to integer reservation stations and are allowed to execute completely out of order while the floating-point instructions slowly compute. When the add.iw is decoded, the register status table for x1 is immediately updated to point to the add.iw's reservation station, dynamically replacing the older pointer from the mul.w. Because of this renaming, when the slow mul.w finally finishes 20+ cycles later and broadcasts its result, the register file simply ignores it, eliminating the WAW hazard without ever stalling the pipeline.

Differences Between Scoreboarding and Tomasulo’s Algorithm (Hazard Handling)

Scoreboarding and Tomasulo’s algorithm take fundamentally different approaches to handling pipeline hazards:

Centralization vs. Decentralization: Scoreboarding utilizes a centralized brain (the scoreboard) that meticulously tracks all functional units, registers, and instruction locations to explicitly grant permission for every instruction to advance. Tomasulo’s algorithm relies on distributed logic; the reservation stations inherently govern themselves based on data availability.

Handling RAW Hazards:

• Scoreboarding: Detects RAW hazards and stalls the instruction in the Read Operands (RO) stage by moving it into an RO buffer, preventing it from entering the execution unit.
• Tomasulo: Handles RAW hazards directly inside the Reservation Station (Execute stage). The instruction sits in the RS wrapper safely waiting for the Common Data Bus to deliver the missing operands, allowing the Issue stage to remain completely free for incoming instructions.

Handling WAW Hazards:

• Scoreboarding: The pipeline explicitly stalls in the Issue (IS) stage if it detects that an active instruction will write to the same destination register as another currently executing instruction.
• Tomasulo: Eliminates WAW hazards dynamically. Because the destination register is renamed to the unique identifier of the reservation station handling it, the pipeline never stalls for a WAW hazard.

Handling WAR Hazards:

• Scoreboarding: The pipeline allows the instruction causing the WAR hazard to advance, but traps and stalls it in the Write Back (WB) buffer. It is prevented from finalizing the write until the preceding instruction has safely read the old value from the register file.
• Tomasulo: Eliminates WAR hazards dynamically in the Issue (IS) stage. Because available operands are immediately copied out of the register file and buffered directly into the reservation station, subsequent out-of-order writes to the architectural register simply do not affect the buffered instruction.

Handling Structural Hazards:

Both architectures stall in the Issue (IS) stage for structural hazards. However, in scoreboarding, the stall happens if the physical execution unit itself is busy. In Tomasulo’s algorithm, because of the hardware wrappers, the pipeline only stalls if it runs out of available reservation stations for that specific functional unit.

🔙 Back to all notes 𝕏 Let’s Connect

Backlinks: *Computer Architecture Notes: A Quantitative Guide to Modern Computing*