7 - Reorder Buffer

---

Hardware-based speculation is a powerful technique that extends the concepts of dynamic scheduling to handle branch instructions and speculative execution. This approach allows processors to execute instructions before the resolution of control dependencies, significantly improving instruction throughput. If a branch prediction is incorrect, the effects of the speculatively executed instructions can be undone, ensuring program correctness.

The key components of hardware-based speculation include dynamic branch prediction, speculation, and dynamic scheduling beyond branches.

• Dynamic branch prediction provides the processor with an estimate of the branch’s outcome, reducing stalls caused by control dependencies.
• Speculation, on the other hand, permits the execution of instructions before determining the actual outcome of branches.

Lastly, dynamic scheduling ensures instructions can continue executing even in the presence of unresolved branches, leading to increased instruction-level parallelism.

Speculative Execution and ReOrder Buffer (ROB)

To enable speculation, the processor needs a mechanism to temporarily store the results of instructions until their validity is confirmed. The ReOrder Buffer (ROB) serves this purpose. Introduced in 1988, the ROB is a hardware structure that holds the results of instructions that have completed execution but are not yet committed to the register file or memory. By delaying the commitment of results, the ROB maintains the precise interrupt model, ensuring that instructions are committed in the correct program order even when they are executed out of order.

The primary responsibilities of the ROB include:

• Supporting Out-of-Order Execution with In-Order Commit: While instructions may execute out of order to maximize parallelism, the ROB ensures that their results are committed in program order. This preserves the correct state in case an exception or branch misprediction occurs.
• Maintaining Precise Interrupts: Since instructions are committed sequentially, exceptions are reported with accurate information, maintaining the precise interrupt model.
• Passing Results Between Speculative Instructions: The ROB can supply the results of speculative instructions to other instructions without waiting for commitment, thereby reducing stalls and further enhancing parallelism.
• Avoiding WAR and WAW Hazards: The ROB acts as a temporary register storage, eliminating false dependencies and preventing write-after-read (WAR) and write-after-write (WAW) hazards.

Structure and Operation of the ReOrder Buffer

The ROB is a circular buffer with two primary pointers:

• Head Pointer: This points to the oldest instruction that is ready to commit. Instructions are committed in sequence, ensuring in-order commit.
• Tail Pointer: This indicates the next available ROB entry where a new instruction’s result will be stored.

Each entry in the ROB contains several fields to track the status and data of an instruction:

• Busy Field: This indicates whether the entry is currently occupied by an instruction.
• Instruction Type Field: It identifies the type of instruction, whether it is a branch, store, load, or ALU operation.
• Destination Field:
  • For store instructions, this field holds the memory address where the result will be written.
  • For load and ALU instructions, it stores the register number that will receive the result.
• Value Field: After execution, this field temporarily holds the instruction’s result until it is committed.
• Ready Field: This flag indicates whether the instruction has finished execution and the result is available.
• Speculative Field: This flag specifies whether the instruction was executed speculatively, meaning its effect might need to be discarded if a misprediction occurs.

Example

The table below illustrates a simplified example of a ReOrder Buffer with a head and tail pointer:

ROB Entry	Busy	Instruction Type	Ready	Destination	Value	Speculative	Pointer
ROB0	Yes	Load (In)	No	F0	-	No	Head
ROB1	No	-	-	-	-	-	Tail
ROB2	No	-	-	-	-	-
ROB3	No	-	-	-	-	-

In this case, ROB0 contains an incomplete load instruction with a result that has not yet been marked as ready. The tail pointer, positioned at ROB1, indicates that a new instruction can be issued to this entry. The head pointer remains at ROB0, awaiting the completion and commitment of the current instruction.

Speculative Execution and Recovery

When speculative instructions are issued, their results are stored in the ROB until the branch outcome is confirmed.

• If the branch prediction is correct, the speculative instructions are committed in program order, and their results are written to the register file or memory.
• If a branch misprediction occurs, the processor must discard all speculative instructions and their results. The ROB facilitates this by simply marking the speculative entries as invalid, ensuring a rapid and clean recovery.

The ROB can be efficiently flushed by adjusting the head and tail pointers to the correct state, reverting the processor to the last known good state. Since speculative instructions are not committed until verified, no incorrect data can propagate to memory or registers.

Example

Speculative Tomasulo Architecture with ReOrder Buffer (ROB)

The Tomasulo Algorithm is a hardware-based dynamic scheduling mechanism that enhances instruction-level parallelism (ILP) by resolving data hazards and allowing out-of-order execution. When integrated with a ReOrder Buffer (ROB), the Tomasulo algorithm gains the ability to support speculative execution, handle branch mispredictions, and maintain a precise interrupt model.

In the speculative Tomasulo architecture, the ROB stores the results of instructions that have completed execution but are not yet committed to memory or the register file. By holding these results temporarily, the ROB ensures that speculative instructions do not overwrite actual data. Instead of directly writing results to the register file, the processor first stores them in the ROB, allowing it to discard speculative results in the event of a misprediction.

Additionally, the ROB provides implicit register renaming. Instead of referring to physical registers or reservation stations, instructions reference ROB entries. This eliminates Write After Read (WAR) and Write After Write (WAW) hazards. Register or memory updates occur only when the instruction reaches the head of the ROB and is deemed safe for commitment. This separation between execution and commitment maintains correct program order, even in out-of-order execution scenarios.

Advantages of Using the ROB

Integrating the ROB into Tomasulo’s Algorithm introduces several benefits:

1. Precise Exception Handling: The ROB ensures that exceptions are raised accurately since instructions are committed in-order. This maintains a consistent program state in case of faults.
2. Branch Misprediction Recovery: On a branch misprediction, the ROB can be efficiently flushed to discard speculative results. Execution resumes from the correct instruction path.
3. Implicit Register Renaming: By using ROB entries instead of physical registers, WAR and WAW hazards are eliminated.
4. Efficient Speculation Management: Speculative results are safely stored without affecting the actual program state until their correctness is confirmed.

Phases of the Speculative Tomasulo Algorithm

The speculative Tomasulo algorithm operates in four distinct phases: Issue, Execution, Write-Back, and Commit. Each phase is carefully managed to ensure proper execution flow, with support for branch prediction and speculative execution.

1. Issue (Dispatch)

• During the issue phase, instructions are fetched from the instruction queue.
• The processor checks for an available Reservation Station and an empty ROB entry.
• If both resources are available, the instruction is dispatched to the RS and a corresponding ROB entry is created.
• If any source operand is available in the register file or ROB, it is sent to the RS. Otherwise, the RS monitors the CDB for the required operand.
• The ROB entry is tagged to track the result of the instruction.
• If resources are unavailable (e.g., all RS or ROB entries are occupied), the instruction is stalled.

2. Execution Start

• Once both operands are ready, the instruction begins execution in the appropriate functional unit (FU).
• The RS monitors the CDB to detect when missing operands become available, resolving Read After Write (RAW) hazards dynamically.
• For store instructions, the effective memory address is computed first, even if the value to store is not yet available.

3. Execution Complete and Write-Back

• After completing execution, the instruction writes its result to the CDB. The result is broadcast to any dependent instructions and the corresponding ROB entry is updated with the result.
• The RS entry is marked as free, making it available for subsequent instructions.
• For store instructions, the result is written to the ROB value field, and the CDB is monitored until the value is broadcast.

4. Commit

The commit phase ensures that instructions are applied in-order to maintain program correctness. The processor checks the head of the ROB and performs one of the following actions:

1. Normal Commit:
   • If the instruction at the head has completed and its result is ready, it is written to the register file.
   • The ROB entry is then removed, freeing it for future instructions.
2. Store Commit:
   • In the case of a store instruction, the value is written to memory instead of the register file.
   • The instruction is then removed from the ROB.
3. Branch Misprediction Recovery:
   • If the instruction at the head is a mispredicted branch, the ROB is flushed. All speculative instructions are discarded, and execution resumes from the correct branch target.
   • If the branch was correctly predicted, it is marked as completed, and subsequent instructions proceed.

Example of ROB Operation