 | This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) (Learn how and when to remove this message)
|
Are-order buffer (ROB) is a hardware unit used in an extension toTomasulo's algorithm to supportout-of-order andspeculative instruction execution. The extension forces instructions to be committed in-order.
The buffer is acircular buffer (to provide aFIFO instruction ordering queue) implemented as anarray/vector (which allows recording of results against instructions as they complete out of order).
There are three stages to the Tomasulo algorithm: "Issue", "Execute", "Write Result". In an extension to the algorithm, there is an additional "Commit" stage. During the Commit stage, instruction results are stored in a register or memory. The "Write Result" stage is modified to place results in the re-order buffer. Each instruction is tagged in thereservation station with its index in the ROB for this purpose.
The contents of the buffer are used for data dependencies of other instructions scheduled in the buffer. The head of the buffer will be committed once its result is valid. Its dependencies will have already been calculated and committed since they must be ahead of the instruction in the buffer though not necessarily adjacent to it. Data dependencies between instructions would normally stall the pipeline while an instruction waits for its dependent values. The ROB allows the pipeline to continue to process other instructions while ensuring results are committed in order to preventdata hazards such as read ahead of write (RAW), write ahead of read (WAR) and write ahead of write (WAW).
There are additional fields in every entry of the buffer to support the extended algorithm:
The consequences of the re-order buffer include preciseexceptions and easyrollback control oftarget address mis-predictions (branch or jump). When jump prediction is not correct or a nonrecoverable exception is encountered in the instruction stream, the ROB is cleared of all instructions (by setting the circular queue tail to the head) and reservation stations are re-initialized.
 | Thiscomputer science article is astub. You can help Wikipedia byexpanding it. |
