In computer engineering, out-of-order execution, is a paradigm used in most
high-performance microprocessors to make use of instruction cycles that would
otherwise be wasted by a certain type of costly delay. In this paradigm, a
processor executes instructions in an order governed by the availability of
input data, rather than by their original order in a program. In doing
so, the processor can avoid being idle while waiting for the preceding
instruction to complete to retrieve data for the next instruction in a program,
processing instead the next instructions which are able to run immediately and
independently. It can be viewed as a hardware based dynamic recompilation or
just-in-time compilation to improve instruction scheduling.
History Out-of-order execution is a restricted
form of data flow computation, which was a major research area in computer
architecture in the 1970s and early 1980s. Important academic research in
this subject was led by Yale Patt and his HPSm simulator. A paper by James E.
Smith and A.R. Pleszkun, published in 1985 completed the scheme by describing
how the precise behavior of exceptions could be maintained in out-of-order
machines. Arguably the first machine to use
out-of-order execution was the CDC 6600, which used a scoreboard to resolve
conflicts. In modern usage, such scoreboarding is considered to be
in-order execution, not out-of-order execution, since such machines stall on
the first RAW conflict. Strictly speaking, such machines initiate
execution in-order, although they may complete execution out-of-order.
About three years later, the IBM 360/91 introduced Tomasulo's algorithm, which
made full out-of-order execution possible. In 1990, IBM introduced the
first out-of-order microprocessor, the POWER1, although out-of-order execution
was limited to floating point instructions only.
Throughout the 1990s out-of-order execution became more common, and was
featured in the IBM/Motorola PowerPC 601, Fujitsu/HAL SPARC64, Intel Pentium
Pro, MIPS R10000, HP PA-8000, AMD K5 and DEC Alpha 21264. Notable exceptions to
this trend include the Sun UltraSPARC, HP/Intel Itanium, Transmeta Crusoe,
Intel Atom, and the IBM POWER6. The logical complexity of the
out-of-order schemes was the reason that this technique did not reach mainstream
machines until the mid-1990s. Many low-end processors meant for
cost-sensitive markets still do not use this paradigm due to the large silicon
area that is required to build this class of machine. Low power usage is
another design goal that's harder to achieve with an OoOE design.
Basic concept = In-order processors=
In earlier processors, the processing of instructions is normally done in these
steps: Instruction fetch.
If input operands are available, the instruction is dispatched to the
appropriate functional unit. If one or more operands are unavailable during the
current clock cycle, the processor stalls until they are available.
The instruction is executed by the appropriate functional unit.
The functional unit writes the results back to the register file
= Out-of-order processors= This new paradigm breaks up the
processing of instructions into these steps:
Instruction fetch. Instruction dispatch to an instruction
queue. 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.
The instruction is issued to the appropriate functional unit and executed
by that unit. The results are queued.
Only after all older instructions have their results written back to the
register file, then this result is written back to the register file. This
is called the graduation or retire stage.
The key concept of OoOE processing is to allow the processor to avoid a class of
stalls that occur when the data needed to perform an operation are unavailable.
In the outline above, the OoOE processor avoids the stall that occurs in step of
the in-order processor when the instruction is not completely ready to
be processed due to missing data. OoOE 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 runs the
instructions in seemingly random order. The benefit of OoOE processing grows as
the instruction pipeline deepens and the speed difference between main memory and
the processor widens. 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. Dispatch and issue decoupling allows
out-of-order issue One of the differences created by the
new paradigm is the creation of queues which allows the dispatch step to be
decoupled from the issue step and the graduation stage to be decoupled from
the execute stage. An early name for the paradigm was decoupled architecture. In
the earlier in-order processors, these stages operated in a fairly lock-step,
pipelined fashion. To avoid false operand dependencies,
which would decrease the frequency when instructions could be issued out of
order, a technique called register renaming is used. In this scheme, there
are more physical registers than defined by the architecture. The physical
registers are tagged so that multiple versions of the same architectural
register can exist at the same time. Execute and writeback decoupling allows
program restart The queue for results is necessary to
resolve issues such as branch mispredictions and exceptions/traps. The
results queue allows programs to be restarted after an exception, which
requires the instructions to be completed in program order. The queue
allows results to be discarded due to mispredictions on older branch
instructions and exceptions taken on older instructions.
The ability to issue instructions past branches which have yet to resolve is
known as speculative execution. Micro-architectural choices
Are the instructions dispatched to a centralized queue or to multiple
distributed queues? IBM PowerPC processors use queues which
are distributed among the different functional units while other
Out-of-Order processors use a centralized queue. IBM uses the term
reservation stations for their distributed queues.
Is there an actual results queue or are the results written directly into a
register file? For the latter, the queueing function is handled by register
maps which hold the register renaming information for each instruction in
flight. Early Intel out-of-order processors use
a results queue called a re-order buffer, while most later Out-of-Order
processors use register maps. More precisely: Intel P6 family
microprocessors have both a re-order buffer and a register alias table. The
ROB was motivated mainly by branch misprediction recovery.
The Intel P6 family was among the earliest OoOE processors, but was
supplanted by the NetBurst architecture. Years later Netburst proved to be a dead
end due to its long pipeline which assumed the possibility of much higher
operating frequencies. Materials were not able to match the design's ambitious
clock targets due to thermal issues and later designs based on NetBurst, namely
Tejas and Jayhawk were cancelled. Intel reverted to the P6 design as the basis
of the Core and Nehalem microarchitectures. The Sandy Bridge,
Ivy Bridge, and Haswell microarchitectures are a departure from
the reordering techniques used in P6 and employ re-ordering techniques from the
EV6 and the P4 without a long pipeline. See also
Scoreboarding Tomasulo algorithm
Replay system Dataflow architecture
References Further reading
Smith, J. E.; Pleszkun, A. R.. "Implementation of precise interrupts in
pipelined processors". ACM SIGARCH Computer Architecture News 13: 36–44.
doi:10.1145/327070.327125. Smith, J. E.; Pleszkun, A. R..
"Implementing precise interrupts in pipelined processors". IEEE Trans.
Comput. 37: 562–573. doi:10.1109/12.4607.
Smith, J. E.; Pleszkun, A. R.. "Implementation of precise interrupts in
pipelined processors". 25 years of the international symposia on Computer
architecture - ISCA '98. pp. 291–299. doi:10.1145/285930.285988. ISBN
1581130589.