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
, for example) but once the instruction is decoded it is placed into a queue of instructions that haven't been executed yet (ROB
). 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 hazard
s, control hazard
s, and structural hazard
s. These are dealt with in algorithms such as Tomasulo
's I, II, and III designs for out of order processors.