Tomasulo’s algorithm allows for out-of-order instruction execution. This is called speculative execution. We can allow an instruction to execute and to bypass its results to other instructions, without allowing the instruction to perform any updates that cannot be undone, until we know that the instruction is no longer speculative.

Instruction Commit

When an instruction is no longer speculative, we allow it to update the register file or memory. We call this additional step in the instruction execution sequence instruction commit.

Speculation allows instructions to execute out of order. However, the instructions are committed in order to prevent any irrevocable action (such as updating state or taking an exception).

Reorder Buffer

Adding this commit phase to the instruction execution sequence requires an additional set of hardware buffers (reorder buffer) that hold the results of instructions that have finished execution but have not committed.

With speculation, the register file is not updated until the instruction commits (and we know definitively that the instruction should execute). Thus, the ROB supplies operands in the interval between completion of instruction execution and instruction commit.

Because neither the register values nor any memory values are actually written until an instruction commits, the processor can easily undo its speculative actions when a branch is found to be mispredicted.

In a speculative processor, a store updates memory only when it reaches the head of the ROB. This difference ensures that memory is not updated until an instruction is no longer speculative.

Fields

Each entry in the ROB contains four fields

Instruction Type

The instruction type field indicates whether the instruction is a branch (and has no destination result), a store (which has a memory address destination), or a register operation (ALU operation or load, which has register destinations).

Destination Field

The destination field supplies the register number (for loads and ALU operations) or the memory address (for stores) where the instruction result should be written.

Value Field

The value field is used to hold the value of the instruction result until the instruction commits.

Ready Field

The ready field indicates that the instruction has completed execution, and the value is ready.

Register Renaming

In the presence of a ROB, the renaming function of the reservation stations is replaced by the ROB. A result is tagged using the ROB entry number rather than using the reservation station number.

Exceptions

The use of a ROB with in-order instruction commit provides precise exceptions, in addition to supporting speculative execution.

Exceptions are handled by not recognizing the exception until it is ready to commit. If a speculated instruction raises an exception, the exception is recorded in the ROB. If a branch misprediction arises and the instruction should not have been executed, the exception is flushed along with the instruction when the ROB is cleared. If the instruction reaches the head of the ROB, then we know it is no longer speculative and the exception should really be taken.