display | more...
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.

Log in or register to write something here or to contact authors.