Re-order buffer
A re-order buffer (ROB) is used in a Tomasulo algorithm for out-of-order instruction execution. It allows instructions to be committed in-order.
Normally, there are three stages of instructions: "Issue", "Execute", "Write Result". In Tomasulo algorithm, there is an additional stage "Commit". In this stage, the results of instructions will be stored in a register or memory. In the "Write Result" stage, the results are just put in the re-order buffer. All contents in this buffer can then be used when executing other instructions depending on these.
There are additional fields in every entry of the buffer:
- Instruction type (jump, store to memory, store to register)
- Destination (either memory address or register number)
- Result (value that goes to destination or indication of a (un)successful jump)
- Validity (does the result already exist?)
Additional benefits of the re-order buffer include allowing for precise exceptions and easy rollback control of target address mispredictions (branch or jump). The ROB works by storing instructions in their original fetched order. The ROB can also be accessed from the side since each reservation station (in Tomasulo algorithm) has an additional parameter that points to instruction in the ROB. When jump prediction is not correct or a nonrecoverable exception is encountered in the instruction stream, the ROB is cleared of all instructions and reservation stations are re-initialized.