The Re-order Buffer

Structure

A typical entry in the reorder buffer can be visualized as:

Busy	Instruction Type	Validity	Register Affected	Data
1 bit	2 bit	1 bit	3 bit	16 bits

The values shown above are in accordance with the designed mini-superscalar processor. Whenever an instruction is decoded, an entry is allotted to it in the reorder buffer. Index corresponding to this is returned to the corresponding instruction. The busy bit is set to '1' whenever an entry is allotted to an instruction and is cleared to '0' whenever the instruction is declared as completed.

Completion: An instruction is changed to be completed when all of its preceding instructions are completed. To manage this, a register (R_old) is defined which holds the index value to the oldest instruction. If the validity of this is set to '1' by the execute stage, this instruction is marked to be completed and is transferred to the Complete stage, from where it is then retired.

Reorder Buffer is a circular buffer. We also keep another register (R_new) which holds the index value to the newest entered instruction. If and when R_old = R_new, we stall the instruction fetch and decode to stop getting new instructions. The structure of a Re-order buffer can be visualized as:

Let us now dive into the details of the control part of the ROB.

Control Hardware

The control part of the ROB has to take care of three basic functions:

1. Receiving and managing instructions coming from decode
2. Updating the ROB on receiving the broadcasts from the execute
3. Transferring the completed instructions to the Complete Stage in-order

Let us now go into detail of each of them.

Adding new Instructions

The following tasks are needed to be performed on receiving new instructions:

1. Allot an empty (busy_bit = '0') entry to the new incoming instruction
2. Send the entry tag back to the decode
3. Set the busy bit of the entry to '1'
4. Change the other contents of the entry registers.

Let us visualize the structure for doing so as follows:

Broadcast Handling

The following tasks are needed to be performed on receiving a valid broadcast:

1. Set the validity bit to '1' corresponding to the broadcast tag.
2. Enter the data (if any) into the data entry corresponding to the tag.

Note: We do not change the busy bit and bottom pointer here. This will be done after forwarding the instructions to the complete stage.

Handling the completed instructions

The following tasks are needed to be performed:

1. Finding the top 2 (or 1) instructions that can be transferred to complete stage. Done by using the bottom pointer.
2. Transferring the above found instructions.
3. Updating the bottom pointer.
4. Changing the busy bit of the corresponding entry of the ROB freed

This controlling along with the broadcast can be visualized as follows: