TOMOSULO'S ALGORITHM

Well basically this algorithm intends to incorporate the benefits of OOO execution in a sequential pipeline by making changes to the pipeline, by way of introducing some new stages. We consider that each functional unit has a buffer of its own and instructions are issued to these buffers (known as Reservation Stations). Then after the execution of these instructions, the corresponding register file entries are updated and the instruction is in essence retired!

In Simplescalar, basically all instructions are stored in a ROB (Re-Order-Buffer) and the state field of the instruction tells us which stage the instruction typically should be in. Some of the important states that must be described are as follolws:

1. ISSUE : The instruction has been dispatched into both the ROB and the issue queues.

2. READY : If all of the instruction's register source operands are "ready", but issue bandwidth is unavailable in this cycle, the instruction transitions from ISSUE to the next wait state READY.

3. REGREAD : Upon issuing (ISSUE/READY -> REGREAD), the instruction reads the register file. Reading the register is performed in the REGREAD state.

4. EXECUTE : All instructions except loads/stores spend a fixed number of cycles in the EXECUTE state, corresponding to the instruction's latency.

5. WRITEBACK : Any completed instruction transistions to this state. Retire() function checks the instruction at the head of the reorder buffer, and if it is in the WRITEBACK state, it can be retired.

Back to Report-2.