An out of order processor is one that is able to
execute code in an
order that is different from
program order. This is the simplest method to exploit Instruction Level Parallelism (
ILP) in code.
Computer instructions
rely on previously executed instructions. However, not all instructions rely on all other instructions. The following sequence, for instance, can be re-ordered somewhat with no effect on the
result:
1) A = A + 10
2) B = A * 5
3) C = A / 25
Lines 2 and 3 can be
swapped, or even executed
simultaneously, without affecting the end result of each
variable.
The processor uses a typical pipeline (
Fetch,
Decode,
Execute,
Memory,
Writeback, for example) but once the instruction is decoded it is placed into a queue of instructions that haven't been executed yet (
ROB and
RS). Each queue entry also holds information about what it needs before its instruction can be executed. In this case both 2 and 3 require the results of 1 before they can continue. Once 1 is done, 2 and 3 could be executed in an
arbitrary order, quite possibly in different execution units of the processor. If the division takes a long time then the processor might start that first. Perhaps more instructions are waiting for the result of 3 than 2 and so executing 3 first would yield better performance.
There are a lot on issues that must taken into account with such a design, such as
data hazards,
control hazards, and
structural hazards. These are dealt with in algorithms such as
Tomasulo's I, II, and III designs for out of order processors.