Out-of-order execution

Out-of-order execution

In computer engineering, out-of-order execution (OoOE or OOE) 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 data is retrieved for the next instruction in a program, processing instead the next instructions which is able to run immediately.

Contents

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 probably the CDC 6600 (1964), 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 (Read After Write) 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 (1966) introduced Tomasulo's algorithm, supporting full out-of-order execution.

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 (1993), Fujitsu/HAL SPARC64 (1995), Intel Pentium Pro (1995), MIPS R10000 (1996), HP PA-8000 (1996), AMD K5 (1996) and DEC Alpha 21264 (1998). 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 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:

  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 operand is unavailable during the current clock cycle (generally because they are being fetched from memory), 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 file.

Out-of-order processors

This new paradigm 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.
  6. 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 OoO 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 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.

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 runs the instructions in seemingly random order.

The benefit of OoO processing grows as the instruction pipeline deepens and the speed difference between main memory (or cache 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 ROB re-order buffer and a RAT register map mechanism. The ROB was motivated mainly by branch misprediction recovery.
The Intel P6 family was among the earliest OoO processors, but was supplanted by the Intel Pentium 4 Willamette microarchitecture. Years later it proved to be a dead end due to performance and thermal issues, forcing Intel to go back to the P6 design and continue from there. The result were the Core and Core 2 series of processors and most notably its latest iteration, Sandy Bridge.

See also

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Out-of-order execution — (in etwa: Außer der Reihe Ausführung) bezeichnet die Möglichkeit, Befehle in den Ausführungseinheiten eines (meist) superskalaren Prozessors außerhalb der Programmreihenfolge auszuführen, mit dem Ziel, die Pipelines möglichst gut auszulasten.… …   Deutsch Wikipedia

  • Out-of-Order-Execution — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Out of Order — may refer to: Out of Order (novel), a novel by Phoebe Atwood Taylor Out of Order (Nuclear Assault album) Out of Order (Rod Stewart album) Out of Order (TV series), a miniseries starring Eric Stoltz and Felicity Huffman Out of Order (Curious… …   Wikipedia

  • Out-of-order — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Exécution out-of-order — L exécution out of order (« dans le désordre » en anglais) d instructions par un processeur consiste à réorganiser l ordre dans lequel les instructions d un programme vont s exécuter. Ces instructions ne sont alors pas forcément… …   Wikipédia en Français

  • In-Order Execution — (in etwa: in der Reihe Ausführung) bezeichnet die Beschränkung Befehle nur strikt nach Programmreihenfolge abarbeiten zu können. Im Gegensatz zur Out of order Execution, wo Befehle in den Ausführungseinheiten eines (meist) superskalaren… …   Deutsch Wikipedia

  • order — or·der 1 n 1: a state of peace, freedom from unruly behavior, and respect for law and proper authority maintain law and order 2: an established mode or state of procedure a call to order 3 a: a mandate from a superior authority see also …   Law dictionary

  • order — {{Roman}}I.{{/Roman}} noun 1 way in which people/things are arranged ADJECTIVE ▪ correct, proper, right ▪ wrong ▪ logical ▪ The paragraphs are not in a logical order …   Collocations dictionary

  • Exécution spéculative — En informatique, L exécution spéculative correspond au lancement anticipé d une instruction, c est à dire sans être certain que celle ci ait réellement besoin d être exécutée. Types Généralement, on peut distinguer trois type d instructions et de …   Wikipédia en Français

  • out of commission — Commission Com*mis sion, n. [F., fr. L. commissio. See {Commit}.] 1. The act of committing, doing, or performing; the act of perpetrating. [1913 Webster] Every commission of sin introduces into the soul a certain degree of hardness. South. [1913… …   The Collaborative International Dictionary of English

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”