Out-of-order execution

In computer engineering, out-of-order execution, OoOE, is a technique used in most high-performance microprocessors to make use of cycles that would otherwise be wasted by a certain type of costly delay. Most modern CPU designs include support for out of order execution.

The key concept of OoO processing is to allow the processor to avoid a class of delays (termed: "stalls ") that occur when the data needed to perform an operation are unavailable.

OoO processors fill these "slots" in time with other instructions that are ready, then re-order the results at the end to make it appear that the instructions were processed as normal. The way the instructions are ordered in the original computer code is known as program order, in the processor they are handled in data order (the order in which the data, operands, become available in the processor's registers). Fairly complex circuitry is needed to convert from one ordering to the other and maintain a logical ordering of the output; the processor itself appears to be running the instructions in random order.

The benefit of OoO processing grows as the instruction pipeline expands and the speed difference between main memory (or cache memory) and the processor increases. On modern machines, the processor runs many times faster than the memory, so during the time an in-order processor spends waiting for data to arrive, it could have processed a large number of instructions.

In earlier In-order processors, the processing of instructions is normally done in these steps:

1. Instruction fetch.
2. If input operands are available (in registers for instance), the instruction is dispatched to the appropriate functional unit. If one or more operands is unavailable during the current clock cycle (generally because they are being fetched from memory), however, the processor stalls until they are available.
3. The instruction is executed by the appropriate functional unit.
4. The functional unit writes the results back to the register.

Out-of-order processors breaks up the processing of instructions into these steps:

1. Instruction fetch.
2. Instruction dispatch to an instruction queue (also called instruction buffer or reservation stations).
3. The instruction waits in the queue until its input operands are available. The instruction is then allowed to leave the queue before earlier, older instructions.
4. The instruction is issued to the appropriate functional unit and executed by that unit.
5. The results are queued (Re-order Buffer).
6. Only after all older instructions have their results written back to the register file, then this result is written back to the register. This is called the graduation or retire stage.

In the examples outlined above, the OoO processor avoids the stall that occurs in step (2) of the in-order processor when the instruction is not completely ready to be processed due to missing data.

• Parallel computing
• Instruction-level parallelism

• "Implementation of precise interrupts in pipelined processors", a paper by Smith and Pleszkun (1985).

This short article about technology can be made longer. You can help Wikipedia by adding to it.