Tomasulo's Algorithm, Register Renaming, Reorder Buffer (ROB) & Memory Disambiguation

In modern superscalar computing, statically scheduled in-order pipelines represent a severe bottleneck for instruction throughput. When an instruction encounters a high-latency cache miss or multi-cycle floating-point operation, an in-order pipeline freezes, forcing all subsequent instructions to idle regardless of whether they are completely independent. Out-of-Order (OoO) execution dismantles this sequential constraint by decoupling instruction decoding from instruction execution. Through dynamic scheduling algorithms, hardware register renaming, distributed reservation stations, and reorder buffers, modern microprocessors extract Instruction-Level Parallelism (ILP) from sequential code while rigorously preserving precise architectural state.

1. The Limitations of In-Order Processing & The Out-of-Order (OoO) Mandate#

In a classical in-order 5-stage pipeline, instructions are fetched, decoded, executed, and retired in strict program sequence. Consider the following sequence of instructions:

FDIV.D  F0, F2, F4    # High-latency floating-point division (takes 35 cycles)
FADD.D  F6, F0, F8    # Dependent on F0 (Must wait 35 cycles for FDIV.D)
FSUB.D  F10, F12, F14 # Completely independent of F0, F2, F4, F6, and F8!

In an in-order execution core, FSUB.D is blocked in the decode stage behind FADD.D. Even though FSUB.D has all of its source operands (F12 and F14) immediately available in the register file, and even though the floating-point subtraction execution unit is completely idle, the hardware cannot execute FSUB.D! This artificial serialization, known as Head-of-Line Blocking, wastes vast amounts of execution hardware.

The Out-of-Order Execution Paradigm#

Out-of-Order execution breaks the rigid lockstep of the pipeline by decoupling instruction dispatch from execution:

1. In-Order Fetch & Decode: Instructions are fetched sequentially from the instruction cache and decoded in strict program order.
2. In-Order Rename & Dispatch: Instructions are renamed to eliminate false dependencies and dispatched into waiting buffers.
3. Out-of-Order Issue & Execution: As soon as an instruction's operands become available—regardless of whether older instructions are still waiting for data—the instruction is issued to an available execution port and executed immediately.
4. In-Order Commit & Retirement: To preserve the illusion of sequential execution and support precise exceptions, instructions commit their speculatively computed results to the permanent architectural register file in strict program order.

+----------------------------------------------------------------------------------------------------+
|                                    OUT-OF-ORDER EXECUTION ENGINE                                   |
+----------------------------------------------------------------------------------------------------+
  [ In-Order Front-End ]
  Fetch -> Decode -> Register Renaming -> Dispatch
                          |
                          v
  [ Out-of-Order Execution Core ]
  +--------------------------------------------------------------------+
  | Reservation Stations / Issue Queues                                |
  | (Instructions wait dynamically until source operands are ready)    |
  +--------------------------------------------------------------------+
       |                  |                  |                  |
       v                  v                  v                  v
  [ Integer ALU ]   [ Vector SIMD ]   [ FP Multiplier ]   [ Load/Store ]
       |                  |                  |                  |
       +------------------+------------------+------------------+
                          | Broadcast Result on Common Data Bus (CDB)
                          v
  [ In-Order Back-End: Reorder Buffer (ROB) ]
  Reorder Buffer (ROB) tracks in-flight instructions in strict program order.
  Instructions Commit / Retire In-Order at ROB Head -> Permanent Architectural State.
+----------------------------------------------------------------------------------------------------+

2. Resolving Name Dependencies via Hardware Register Renaming#

To execute instructions out of order, the processor must distinguish between real data dependencies and artificial dependencies caused by register limitations.

True vs. False (Name) Dependencies#

Data dependencies fall into three distinct classes:

1. True Data Dependency (Read-After-Write - RAW):

- Instruction J reads a register value written by an earlier Instruction I.

- Example:

```assembly

ADD x1, x2, x3 # Produces x1

SUB x4, x1, x5 # Consumes x1

```

- Fundamental Constraint: RAW dependencies represent the true mathematical data flow of the program. Instruction J physically cannot execute until Instruction I produces the numerical value. RAW dependencies CANNOT be eliminated.

1. Anti-Dependency (Write-After-Read - WAR):

- Instruction J writes to a register that is read by an earlier Instruction I.

- Example:

```assembly

SUB x4, x1, x5 # Reads x1

ADD x1, x6, x7 # Overwrites x1

```

- If ADD were allowed to execute before SUB, SUB would read the newly computed value of x1 rather than the original value!

- Artificial Constraint: Notice that ADD does not depend on the output of SUB. The dependency exists solely because the compiler reused the register name x1 to store an unrelated value due to having a finite architectural register set (e.g., only 32 registers).

1. Output Dependency (Write-After-Write - WAW):

- Instruction J writes to the same destination register as an earlier Instruction I.

- Example:

```assembly

ADD x1, x2, x3 # Writes x1

SUB x1, x4, x5 # Overwrites x1

```

- If SUB completed before ADD, the older value from ADD would overwrite the newer value from SUB, corrupting future reads.

- Artificial Constraint: Like WAR, WAW exists purely because of register name reuse.

The Register Renaming Solution#

Hardware Register Renaming completely eliminates WAR and WAW dependencies by decoupling Architectural Registers from physical storage locations.

• Architectural Registers (ARF): The programmer-visible register names defined by the ISA (e.g., x0 through x31 in RISC-V, or rax, rbx in x86).
• Physical Register File (PRF): A much larger bank of internal physical registers embedded in silicon (e.g., 128 to 256 physical registers p0 through p255).

The processor maintains a Register Alias Table (RAT) (also called the Rename Map):

• When an instruction reads an architectural source register, the RAT translates the architectural name to the physical register that currently holds (or will produce) that value.
• When an instruction writes to an architectural destination register, the hardware allocates a fresh, unused physical register from a Free List and updates the RAT to point the architectural name to this new physical register.

Eliminating False Dependencies: A Concrete Trace#

Consider this assembly sequence:

1. MUL x1, x2, x3    # Produces x1
2. ADD x4, x1, x5    # Reads x1 (RAW with #1)
3. SUB x1, x6, x7    # Overwrites x1 (WAR with #2, WAW with #1)
4. OR  x8, x1, x9    # Reads x1 (RAW with #3)

Renaming with Physical Registers (assuming initial mappings x1->p1, x2->p2, x3->p3, x4->p4, x5->p5, x6->p6, x7->p7, x8->p8, x9->p9):

• Instruction 1 (MUL): Reads p2, p3. Allocates new physical register p10 for destination x1. Update RAT: x1 -> p10.

Renamed: MUL p10, p2, p3.

• Instruction 2 (ADD): Reads x1 (maps to p10), reads p5. Allocates p11 for destination x4. Update RAT: x4 -> p11.

Renamed: ADD p11, p10, p5.

• Instruction 3 (SUB): Reads p6, p7. Allocates fresh physical register p12 for destination x1. Update RAT: x1 -> p12.

Renamed: SUB p12, p6, p7.

• Instruction 4 (OR): Reads x1 (now maps to p12), reads p9. Allocates p13 for destination x8. Update RAT: x8 -> p13.

Renamed: OR p13, p12, p9.

Notice what happened:

• Instruction 2 reads from p10. Instruction 3 writes to p12. The WAR dependency is gone!
• Instruction 1 writes to p10. Instruction 3 writes to p12. The WAW dependency is gone!

Instruction 3 (SUB) can now execute concurrently with or even before Instruction 1 and Instruction 2! True data flow is preserved while all artificial naming bottlenecks evaporate.

3. Tomasulo's Dynamic Scheduling Algorithm & Reservation Stations#

Invented by Robert Tomasulo at IBM in 1967 for the System/360 Model 91, Tomasulo's Algorithm is the foundational hardware mechanism for dynamic scheduling and register renaming.

Key Architectural Structures#

Tomasulo's engine replaces a centralized register file with distributed hardware buffers called Reservation Stations (RS) placed directly at the inputs of execution units.

                       +-----------------------+
                       |   Instruction Queue   |
                       +-----------------------+
                                   |
                          Issue / Rename
                                   v
             +---------------------+---------------------+
             |                                           |
             v                                           v
   [ Reservation Stations ]                    [ Reservation Stations ]
        (Integer / ALU)                             (FP / Multiplier)
             |                                           |
             v                                           v
      [ ALU Pipeline ]                            [ FP Multipliers ]
             |                                           |
             +---------------------+---------------------+
                                   |
                         Broadcast on CDB
                                   v
   +---------------------------------------------------------------+
   |                   Common Data Bus (CDB)                       |
   +---------------------------------------------------------------+
         |                         |                         |
         v                         v                         v
   (Update RAT/Regs)      (Wakeup Waiting RS)         (Commit to ROB)

1. Reservation Stations (RS):

Each execution unit has a pool of reservation stations. Each station entry stores:

- Busy: A 1-bit flag indicating whether the reservation station is occupied.

- Op: The operation to perform (ADD, SUB, MULT, DIV).

- Vj, Vk: Value fields holding the actual numerical operand values if they are ready.

- Qj, Qk: Tag fields identifying the specific reservation station (or ROB entry) that will produce the operand if it is not yet ready. A value of zero (or None) means the operand is already available in the V field.

- A: Address field used for memory load/store offsets.

1. Register Status Array (RAT):

For each architectural register, the RAT stores:

- A tag indicating which Reservation Station will produce its future value. If the register holds valid data, the tag is empty (None).

1. The Common Data Bus (CDB):

A high-speed broadcast bus connecting all functional unit outputs to all reservation stations, the register file, and the Reorder Buffer. When an execution unit finishes computing a result, it broadcasts a tuple across the CDB:

Tuple = (Producer_Tag, Computed_Value).

Distributed Tag Snooping & Operand Capture#

The brilliance of Tomasulo's algorithm lies in its decentralized associative wakeup:

• When (Producer_Tag, Computed_Value) appears on the CDB, EVERY reservation station in the entire processor inspects the broadcast in parallel.
• If a waiting reservation station observes that its Qj == Producer_Tag, it immediately latches Computed_Value into its Vj field and sets Qj = None.
• If Qk == Producer_Tag, it latches Computed_Value into Vk and sets Qk = None.
• When both Qj and Qk become None, all operands are present: the instruction is marked READY and issues to its execution unit on the very next cycle!

This eliminates centralized polling: instructions wake up automatically the instant their dependencies are resolved.

The Three Steps of Tomasulo Execution#

1. Issue:

- Retrieve next instruction from the FIFO Instruction Queue.

- Find a free Reservation Station (RS_r) matching the required operation type. If none is free, the pipeline stalls on a Structural Hazard.

- Read source operands:

- If source register rs1 has a valid value in the register file, copy its value into RS_r.Vj.

- If rs1 is waiting on a pending calculation (RAT points to tag T), copy tag T into RS_r.Qj.

- Perform identical lookup for rs2 into Vk / Qk.

- Update destination register rd in the RAT to point to tag RS_r. Mark RS_r.Busy = 1.

1. Execute:

- When an occupied reservation station has Qj == None and Qk == None, its operands are ready.

- The station dispatches its operands to the execution unit.

- Execution proceeds across the required latency (1 cycle for integer ALU, 3 cycles for FP multiply, 20+ cycles for FP divide).

1. Write Result (Broadcast):

- When execution completes, the unit broadcasts its tag and result on the CDB.

- All reservation stations with matching Q tags capture the value.

- The register file (or ROB) updates the destination register if the RAT still points to this tag.

- The reservation station clears its Busy flag to 0, returning to the free pool.

4. The Reorder Buffer (ROB) & Precise Exception Architecture#

While classic Tomasulo scheduling solves out-of-order execution, it introduces a dangerous flaw: Imprecise Interrupts.

The Imprecise Interrupt Catastrophe#

Suppose an instruction sequence executes:

DIV.D  F0, F2, F4   # High-latency divide (takes 30 cycles). Divides by zero!
ADD.D  F6, F8, F10  # 1-cycle add. Executes immediately in Cycle 2!

Under classic Tomasulo scheduling, ADD.D completes and writes its result into architectural register F6 in Cycle 2. Twenty-eight cycles later, DIV.D completes, detects a divide-by-zero fault, and triggers a hardware trap.

The operating system exception handler inspects the architectural state: F6 has already been overwritten by an instruction that chronologically occurred AFTER the faulting instruction!

This violates the fundamental contract of computing:

A processor must guarantee Precise Exceptions:

1. All instructions preceding the faulting instruction must be fully completed and committed to architectural state.
2. The faulting instruction must not have committed any partial state.
3. No instruction following the faulting instruction in program order may have modified ANY architectural register or memory location.

The Reorder Buffer (ROB) Architecture#

Modern out-of-order microarchitectures solve this problem by introducing a Reorder Buffer (ROB).

The ROB is a circular FIFO queue that buffers speculatively executed instructions until they can commit in strict program order.

       Issue (In-Order) ---> [ ROB Tail ]
                                  |
                                  | Out-of-Order Execution in Flight
                                  v
      Commit (In-Order) <--- [ ROB Head ] (Permanent State Committed)

Each ROB entry contains:

• Entry ID: A unique tag identifying the in-flight instruction (used for renaming).
• Instruction Type: Opcode or operation class (Branch, Store, Load, ALU).
• Destination: The architectural destination register (or memory store address).
• Value: The speculatively computed result.
• Ready Bit: Set to 1 when execution completes and the result is written into the ROB.
• Exception Status: Records whether this instruction encountered a page fault, invalid opcode, or arithmetic exception.

Out-of-Order Execution with In-Order Retirement#

With a Reorder Buffer, instructions progress through four formal phases:

1. Issue (In-Order): Instructions are allocated sequentially at the tail of the ROB. Destination registers are tagged with the ROB entry ID rather than reservation station names.
2. Execute (Out-of-Order): Instructions execute in reservation stations as soon as operands are ready.
3. Write Result: Execution units broadcast (ROB_Tag, Computed_Value) on the CDB. The computed value is written into the designated ROB entry, and Ready is set to 1. Architectural registers are NOT modified!
4. Commit / Retire (In-Order): The processor inspects the head of the ROB:

- If the instruction at the head has Ready == 1 and Exception == 0:

- Its computed value is permanently written to the architectural register file (or committed to memory if a Store).

- The entry is retired, and the ROB head pointer advances.

- If the instruction at the head encountered an exception or a branch misprediction:

- All instructions currently in the ROB (which were speculatively fetched after the fault) are instantly FLUSHED!

- The Register Alias Table is restored to the committed state.

- The processor jumps to the exception handler with pristine architectural registers.

5. Memory Disambiguation & The Load-Store Queue (LSQ)#

While register dependencies are explicitly identifiable at instruction decode time via 5-bit register specifiers, memory dependencies are dynamic and opaque.

The Challenge of Dynamic Memory Aliasing#

Consider this sequence:

SW  x1, 0(x2)    # Store word into memory at address (x2)
LW  x3, 0(x4)    # Load word from memory at address (x4)

At decode time, the processor cannot know whether x2 == x4 because registers x2 and x4 may still be in flight!

• If x2 == x4: A True Memory Dependency (RAW) exists. The LW must receive the exact data written by the SW.
• If x2 != x4: The two operations are completely independent. The LW should be allowed to execute out-of-order immediately, without waiting for the slow store to complete!

Determining whether two memory instructions reference the same physical memory address is known as Memory Disambiguation.

The Load Queue (LQ) & Store Queue (SQ)#

To handle memory operations out of order, processors employ a specialized Load-Store Queue (LSQ):

• Store Queue (SQ): A FIFO buffer tracking all in-flight store instructions in program order.

Crucial Rule: A store instruction NEVER writes directly to the L1 Data Cache while in-flight! It writes exclusively to the Store Queue. A store commits to the cache only when it retires from the head of the ROB.

• Load Queue (LQ): Tracks all in-flight load instructions and their effective memory addresses.

Store-to-Load Forwarding#

When a LOAD computes its effective memory address:

1. It searches the Store Queue for all older pending stores.
2. If an older store has a matching address and its data is ready, data is forwarded directly from the Store Queue into the load's destination register with zero cache latency (Store-to-Load Forwarding).
3. If an older store has an unknown address (its base register is still computing), the processor faces a choice:

- Conservative Disambiguation: Stall the load until all older store addresses are resolved.

- Speculative Disambiguation: Predict that the addresses do not match, execute the load from cache immediately, and check later. If the store address resolves and matches the load address, the processor detects a Memory Order Violation, flushes the pipeline, and replays the load.

6. Production Systems, Hardware Performance Counters & Microarchitecture Profiling#

Understanding out-of-order execution allows software engineers to diagnose production performance bottlenecks.

The Top-Down Microarchitecture Analysis Method (TMAM)#

Intel and AMD processors incorporate hundreds of hardware performance monitoring counters (PMCs) accessible via the Linux perf subsystem. The Top-Down method (developed by Ahmad Yasin at Intel) classifies CPU execution pipeline slots into four mutually exclusive domains:

+----------------------------------------------------------------------------------------------------+
|                                TOP-DOWN PIPELINE SLOTS CLASSIFICATION                              |
+----------------------------------------------------------------------------------------------------+
  1. Frontend Bound:
     The pipeline was starved because the Instruction Fetch / Decode units could not supply u-ops.
     Causes: L1 Instruction Cache misses, Instruction TLB misses, Branch Target Buffer misses.

  2. Bad Speculation:
     Pipeline slots were allocated to instructions that were ultimately discarded due to branch
     mispredictions or memory order violations.
     Causes: Unpredictable branches, complex data-dependent jumps.

  3. Backend Bound:
     Execution slots were stalled because the execution engine could not accept u-ops.
     Subdivided into:
     - Core Bound: Execution units (ALUs, FP dividers) are saturated with work.
     - Memory Bound: Stalled waiting for L1D, L2, L3 cache misses or DRAM memory controller latency.

  4. Retiring:
     Pipeline slots successfully completed and retired useful, architecturally visible instructions.
     Goal: Maximize Retiring percentage (> 50-70% in well-optimized code).
+----------------------------------------------------------------------------------------------------+

Diagnosing Production Code with Linux Perf#

Engineers run profiling commands to identify execution bottlenecks:

perf stat -e cycles,instructions,branches,branch-misses,L1-dcache-load-misses,cache-misses ./server_app

Interpreting Key Metrics:

• Instructions Per Cycle (IPC = instructions / cycles): If IPC < 0.8 on a 4-wide out-of-order processor, the CPU is severely bottlenecked (Memory Bound or Frontend Bound). An optimized numeric kernel achieves IPC > 2.5 to 3.5.
• Branch Misprediction Rate (branch-misses / branches): A rate exceeding 3-5% signals severe Bad Speculation stalls, demanding branchless algorithms or compiler profile-guided optimization (PGO).

7. Common Architectural Pitfalls & Misconceptions#

Navigating superscalar out-of-order microarchitectures requires clarifying subtle execution semantics.

Pitfall 1: Believing Out-of-Order Execution Alters Program Semantics#

A widespread misconception is that executing instructions out of order introduces race conditions into single-threaded software. This is false: the combination of dynamic register renaming (eliminating WAR/WAW), dataflow issue logic (respecting RAW), memory disambiguation, and in-order retirement via the Reorder Buffer guarantees that single-threaded execution is mathematically and semantically identical to sequential in-order execution.

Pitfall 2: Confusing Reservation Stations with the Reorder Buffer#

Junior engineers often conflate these two buffers:

• Reservation Stations sit at the execution units and hold instructions that are waiting for operands to become ready so they can EXECUTE.
• The Reorder Buffer sits at the retirement stage and holds instructions that have already executed, waiting in strict program order so they can COMMIT to architectural state.

Pitfall 3: Assuming Reorder Buffer Capacity is Unlimited#

In modern processors, the ROB holds 256 to 512 instructions. If an instruction at the head of the ROB experiences a Last-Level Cache (L3) miss (~250 cycles), the head cannot advance. Within 50 to 100 cycles, newly fetched instructions fill all remaining ROB entries. The ROB becomes full, dispatch stalls, and the entire out-of-order processor freezes until the L3 cache line arrives.

8. Comprehensive Checkpoint Practice Problems & Complete Step-by-Step Solutions#

Mastery of dynamic scheduling, renaming, and reorder buffers requires solving rigorous microarchitectural trace problems.

Problem 1 (Hardware Register Renaming & Eliminating False Dependencies):

A superscalar out-of-order processor features 8 architectural registers (R0 through R7) and a Physical Register File containing 16 physical registers (P0 through P15).

The current state of the Register Alias Table (RAT) maps:

• R0 -> P0, R1 -> P1, R2 -> P2, R3 -> P3, R4 -> P4, R5 -> P5, R6 -> P6, R7 -> P7.
• The Free List contains available physical registers in order: [ P8, P9, P10, P11, P12, P13, P14, P15 ].

Consider the following four-instruction program sequence:

• I1: ADD R1, R2, R3 # computes R1 = R2 + R3
• I2: MUL R4, R1, R5 # computes R4 = R1 * R5
• I3: SUB R1, R6, R7 # computes R1 = R6 - R7
• I4: AND R2, R1, R4 # computes R2 = R1 & R4

1. Identify all data dependencies (RAW, WAR, WAW) in the original architectural instruction stream.
2. Step through the renaming process for each instruction: record the allocated physical destination register, the updated RAT mappings, and the renamed instruction with physical registers.
3. Show which false dependencies were eliminated and verify that true data flow is preserved.

Solution:

Step 1: Dependency Analysis in Architectural Code

1. RAW (True Dependencies):

- I1 produces R1; I2 reads R1 (RAW on R1).

- I3 produces R1; I4 reads R1 (RAW on R1).

- I2 produces R4; I4 reads R4 (RAW on R4).

1. WAR (Anti-Dependencies):

- I2 reads R1; I3 overwrites R1 (WAR on R1).

- I1 reads R2; I4 overwrites R2 (WAR on R2).

1. WAW (Output Dependencies):

- I1 writes R1; I3 overwrites R1 (WAW on R1).

Step 2: Step-by-Step Renaming Trace

1. Instruction 1: ADD R1, R2, R3

- Look up source registers in RAT: R2 -> P2, R3 -> P3.

- Allocate fresh physical register from Free List for destination R1: P8.

- Update RAT: R1 -> P8.

- Renamed Instruction: ADD P8, P2, P3.

- Free List remains: [ P9, P10, P11, P12, P13, P14, P15 ].

1. Instruction 2: MUL R4, R1, R5

- Look up source registers in RAT: R1 -> P8 (captures I1's result!), R5 -> P5.

- Allocate fresh physical register for destination R4: P9.

- Update RAT: R4 -> P9.

- Renamed Instruction: MUL P9, P8, P5.

- Free List remains: [ P10, P11, P12, P13, P14, P15 ].

1. Instruction 3: SUB R1, R6, R7

- Look up source registers in RAT: R6 -> P6, R7 -> P7.

- Allocate fresh physical register for destination R1: P10.

- Update RAT: R1 -> P10.

- Renamed Instruction: SUB P10, P6, P7.

- Free List remains: [ P11, P12, P13, P14, P15 ].

1. Instruction 4: AND R2, R1, R4

- Look up source registers in RAT: R1 -> P10 (captures I3's result!), R4 -> P9 (captures I2's result!).

- Allocate fresh physical register for destination R2: P11.

- Update RAT: R2 -> P11.

- Renamed Instruction: AND P11, P10, P9.

- Free List remains: [ P12, P13, P14, P15 ].

Step 3: Verification of Eliminated Dependencies

Compare physical register instructions:

• I1: ADD P8, P2, P3
• I2: MUL P9, P8, P5
• I3: SUB P10, P6, P7
• I4: AND P11, P10, P9

• WAR Elimination: I2 reads P8. I3 writes to P10. Because the registers are physically distinct (P8 vs P10), there is no WAR conflict! I3 can execute immediately in Cycle 1 without waiting for I2.
• WAW Elimination: I1 writes to P8. I3 writes to P10. There is no collision on a single register slot.
• RAW Preservation: I2 correctly waits on P8 (produced by I1), and I4 correctly waits on P10 (produced by I3) and P9 (produced by I2).

All false name dependencies are completely eliminated while true data flow is preserved.

Problem 2 (Tomasulo's Algorithm Reservation Station & CDB Broadcast Simulation):

A processor executes Tomasulo's algorithm with the following functional units:

• 2 Add/Sub units with Reservation Stations ADD1 and ADD2 (execution latency = 2 cycles).
• 1 Multiplier unit with Reservation Station MULT1 (execution latency = 4 cycles).
• Assume instructions issue at a rate of 1 instruction per cycle.
• The processor starts at Cycle 1.

Consider the following program sequence:

• Cycle 1 Issue: MULT.D F0, F2, F4 # latency = 4 cycles
• Cycle 2 Issue: ADD.D F6, F0, F8 # latency = 2 cycles (depends on F0)
• Cycle 3 Issue: SUB.D F8, F10, F14 # latency = 2 cycles (independent!)

Assume registers F2, F4, F8, F10, F14 contain valid floating-point numbers at startup.

1. Determine which reservation station is allocated to each instruction during Issue.
2. For each cycle from Cycle 1 to Cycle 7, trace the state of execution, identifying which instructions are executing, when results complete, and when broadcasts occur on the Common Data Bus (CDB).
3. Specify the exact cycle in which ADD.D begins execution and when it completes.

Solution:

Step 1: Allocation at Issue

• Cycle 1: MULT.D F0, F2, F4 issues.

Allocates MULT1. Operands F2 and F4 are ready in registers -> Copied to Vj, Vk. Qj = None, Qk = None.

RAT updates: F0 -> MULT1.

• Cycle 2: ADD.D F6, F0, F8 issues.

Allocates ADD1. Source F0 is produced by MULT1 -> Qj = MULT1, Vj = None. Source F8 is ready -> Vk = Val(F8), Qk = None.

RAT updates: F6 -> ADD1.

• Cycle 3: SUB.D F8, F10, F14 issues.

Allocates ADD2. Sources F10 and F14 are ready -> Copied to Vj, Vk. Qj = None, Qk = None.

RAT updates: F8 -> ADD2. (Notice: This eliminates the WAR hazard on F8 with ADD.D!).

Step 2: Cycle-by-Cycle Execution Trace

• Cycle 1:

- MULT.D issues to MULT1. Operands ready.

• Cycle 2:

- MULT.D begins execution in MULT1 (Cycle 1 of 4).

- ADD.D issues to ADD1. Waits for MULT1 (Qj = MULT1).

• Cycle 3:

- MULT.D executes (Cycle 2 of 4).

- SUB.D issues to ADD2. Operands ready!

• Cycle 4:

- MULT.D executes (Cycle 3 of 4).

- SUB.D begins execution in ADD2 (Cycle 1 of 2).

- ADD.D still waiting in ADD1.

• Cycle 5:

- MULT.D finishes execution (Cycle 4 of 4).

- SUB.D finishes execution (Cycle 2 of 2).

- Bus Arbitration: SUB.D completes and broadcasts on CDB: (ADD2, Result_SUB).

ADD2 becomes free. Register F8 updated.

• Cycle 6:

- MULT.D broadcasts on CDB: (MULT1, Result_MULT).

- MULT1 becomes free. Register F0 updated.

- SNOOPING EVENT: ADD1 observes MULT1 on CDB! Latches value into Vj, clears Qj = None.

- ADD1 now has all operands ready!

• Cycle 7:

- ADD.D begins execution in ADD1 (Cycle 1 of 2).

• Cycle 8:

- ADD.D executes (Cycle 2 of 2).

• Cycle 9:

- ADD.D broadcasts on CDB: (ADD1, Result_ADD). ADD1 becomes free.

Step 3: Summary of ADD.D Execution

• ADD.D was issued in Cycle 2.
• It was forced to wait through Cycles 2, 3, 4, 5, and 6 for MULT1 to complete.
• It captured its missing operand via CDB broadcast at Cycle 6.
• It began execution in Cycle 7 and finished at the end of Cycle 8, broadcasting its result in Cycle 9.
• Meanwhile, SUB.D executed out-of-order in Cycles 4 and 5, retiring long before ADD.D even started!

Problem 3 (Reorder Buffer (ROB) Execution & Precise Exception Recovery):

An out-of-order processor contains a 4-entry circular Reorder Buffer (ROB1 to ROB4).

Consider the following four instructions issued in program order:

• ROB1: ADD R1, R2, R3 (latency = 1 cycle)
• ROB2: DIV R4, R5, R6 (latency = 8 cycles; executes divide-by-zero!)
• ROB3: SUB R7, R8, R9 (latency = 1 cycle; completely independent)
• ROB4: MUL R10, R11, R12 (latency = 2 cycles; completely independent)

1. Describe the state of the ROB entries after 3 clock cycles: which instructions have executed out of order, which are ready, and which reside at the head of the ROB.
2. In Cycle 9, DIV completes and signals an arithmetic exception (divide-by-zero). Explain the exact sequence of events that occurs when DIV reaches the head of the ROB.
3. Contrast what happens to the results of ROB3 (SUB) and ROB4 (MUL) versus ROB1 (ADD).

Solution:

Step 1: ROB State at Clock Cycle 3

• ROB1 (ADD): Issued at Cycle 1. Executed in Cycle 2. Wrote result to ROB1 on CDB. State: Ready = 1, Exception = 0.

At Cycle 3, ROB1 is at the head of the ROB. It commits in-order! Its result is written into architectural register R1. ROB1 retires, advancing head pointer to ROB2.

• ROB2 (DIV): Issued at Cycle 2. Still executing in floating-point divider (Cycle 2 of 8). State: Ready = 0, Exception = 0.
• ROB3 (SUB): Issued at Cycle 3. Because operands are ready, it executes out of order in Cycle 4 and writes its result into ROB3 in Cycle 5. State: Ready = 1. However, it CANNOT commit because it is not at the head of the ROB!
• ROB4 (MUL): Issued at Cycle 4. Executes out of order in Cycles 5–6, writes result into ROB4 in Cycle 7. State: Ready = 1. It CANNOT commit.

Step 2: Exception Handling at Cycle 9

At Cycle 9:

1. DIV finishes execution, flags an arithmetic exception, and marks ROB2 with Ready = 1, Exception = 1.
2. Because ROB1 previously retired, ROB2 is currently at the head of the Reorder Buffer.
3. The retirement unit inspects the head (ROB2) and observes Exception == 1.
4. The retirement unit refuses to commit ROB2. Architectural register R4 is NEVER updated!
5. Exception Rollback Sequence:

- The processor initiates a pipeline squash.

- All instructions residing in the ROB younger than ROB2 (ROB3 and ROB4) are instantly discarded!

- The Register Alias Table (RAT) is flushed and restored to match the committed Retirement-RAT (R-RAT).

- The Program Counter is loaded with the memory address of the operating system exception vector.

Step 3: Comparison of Results

• ROB1 (ADD): Completely retired and committed to architectural register R1 prior to the exception. Its architectural state is permanently preserved.
• ROB2 (DIV): Faulting instruction. Never committed to R4.
• ROB3 (SUB) and ROB4 (MUL): Although they executed to completion in reservation stations, their computed results existed ONLY speculatively inside the Reorder Buffer. When the exception occurred at ROB2, all speculative results in ROB3 and ROB4 were annihilated without ever modifying architectural registers R7 or R10.

Precise architectural state is rigorously preserved: all instructions before the fault committed, the faulting instruction did not commit, and all subsequent instructions were erased as if they had never executed.

Problem 4 (Memory Disambiguation & Store Queue Forwarding):

An out-of-order processor features a dedicated Load Queue (LQ) and Store Queue (SQ).

Consider the following three memory instructions dispatched into the pipeline:

• S1 (Store): SW x1, 0(x2) # Stores x1 to Address A
• S2 (Store): SW x3, 0(x4) # Stores x3 to Address B
• L1 (Load): LW x5, 0(x6) # Loads from Address C into x5

Case A: Address Resolution & Forwarding

Suppose registers evaluate to: x2 = 0x2000 (Address A = 0x2000), x4 = 0x4000 (Address B = 0x4000), x6 = 0x2000 (Address C = 0x2000).

• Data in x1 has already been computed (x1 = 0xDEADBEEF).
• How does the Load-Store Queue handle L1? Does L1 access the L1 Data Cache?

Case B: Speculative Load Violation

Suppose the processor uses speculative memory disambiguation.

• L1 computes its address (Address C = 0x3000) while S1's base register x2 is still computing (Address A is unknown).
• The processor speculates that Address A ≠ Address C, allowing L1 to read stale data 0x00000000 from the L1 Data Cache immediately.
• Two cycles later, x2 finishes computing: x2 = 0x3000 (Address A = 0x3000)!
• Explain how the Load Queue detects this memory order violation and how the processor recovers.

Solution:

Case A: Store-to-Load Forwarding

1. L1 computes its effective memory address: Address C = 0x2000.
2. L1 snoops the Store Queue in reverse program order (checking youngest store first):

- Compares with S2: Address B = 0x4000. No match (0x2000 != 0x4000).

- Compares with S1: Address A = 0x2000. MATCH DETECTED!

1. S1 holds the data word 0xDEADBEEF ready in the Store Queue.
2. The hardware routes 0xDEADBEEF directly from the Store Queue into the destination register x5 of L1.
3. L1 does NOT access the L1 Data Cache, saving a cache read transaction and resolving in 1 cycle.

Case B: Speculative Memory Order Violation & Recovery

1. Speculative Execution: L1 speculates that S1 does not conflict, reads 0x00000000 from the L1 Data Cache, and passes this stale value to dependent arithmetic instructions down the pipeline.
2. Address Resolution: Two cycles later, S1 computes its address: Address A = 0x3000.
3. Violation Detection: S1 snoops the Load Queue for any younger loads that have already executed. It detects that L1 speculatively read Address 0x3000 BEFORE S1 wrote its new value to that exact address!
4. Pipeline Recovery:

- The Load Queue flags a Memory Order Violation for L1.

- The processor initiates an internal squash of L1 and all instructions speculatively dependent on x5.

- The pipeline rolls back to L1, re-executes L1 (now forwarding the correct data from S1), and resumes execution with valid data.