In computer science, out-of-order execution is a paradigm used in most high-speed microprocessors in order to make use of cycles that would otherwise be wasted by a certain type of costly delay. OoO is an optimization, the same cycles could also be used for other purposes, such as hyperthreading. Almost all modern CPU designs include support for out of order execution. Wikibooks Wikiversity has more about this subject: School of Computer Science Open Directory Project: Computer Science Collection of Computer Science Bibliographies Belief that title science in computer science is inappropriate Categories: Computer science | Academic disciplines ... Microprocessors, including an Intel 80486DX2 and an Intel 80386 A microprocessor (abbreviated as µP or uP) is an electronic computer central processing unit (CPU) made from miniaturized transistors and other circuit elements on a single semiconductor integrated circuit (IC) (aka microchip or just chip). ... In computing, optimization is the process of modifying a system to improve its efficiency. ... Hyper-Threading (HTT = Hyper Threading Technology) is Intels trademark for their implementation of the simultaneous multithreading technology on the Pentium 4 microarchitecture. ...

History

Out-of-order execution is a restricted form of data flow computation, which was a major research area in computer architecture in the 1980s. Important academic research in this subject was led by Yale Patt and his HPSm simulator. A paper by J.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. Dataflow is a term used in computing, and may have various shades of meaning. ... Computer architecture is the theory behind the design of a computer. ... Events and trends The 1980s marked an abrupt shift towards more conservative lifestyles after the momentous cultural revolutions which took place in the 1960s and 1970s and the definition of the AIDS virus in 1981. ... 1985 is a common year starting on Tuesday of the Gregorian calendar. ...

The first machine to use out-of-order execution was probably the CDC 6600 (1964) which used a scoreboard to resolve conflicts. About three years later the IBM 360/91 (1966) introduced Tomasulos algorithm. IBM also introduced the first out-of-order microprocessor, the POWER1 (1990) for its RS/6000. It was the release of the Intel Pentium Pro (1995) which brought the technology to the mainstream. Most other vendors also started to produce OoO designs: IBM/Motorola PowerPC 601 (1992/1993), the Fujitsu/HAL Sparc64 I (1995), the HP PA-8000 (1996), the MIPS R-10000 (1996), the AMD K5 (1996), and the DEC Alpha 21264 (1998). Notable exceptions to this trend are Sun's UltraSparc, HP/Intel's Itanium, and Transmeta's Crusoe. The CDC 6600 was a mainframe computer from Control Data Corporation, first manufactured in 1965. ... The Tomasulo algorithm is an algorithm developed by Robert Tomasulo from IBM to execute instructions out of order. ... Microprocessors, including an Intel 80486DX2 and an Intel 80386 A microprocessor (abbreviated as µP or uP) is an electronic computer central processing unit (CPU) made from miniaturized transistors and other circuit elements on a single semiconductor integrated circuit (IC) (aka microchip or just chip). ... POWER is a RISC CPU architecture designed by IBM. The name stands for Performance Optimization With Enhanced RISC. The POWER series microprocessors are used as the main CPU in many of IBMs servers, minicomputers, workstations, and supercomputers. ... The IBM pSeries, formerly called RS/6000 (for RISC System/6000), is IBMs current RISC/UNIX-based workstation computer line. ... Intel Corporation (NASDAQ: INTC) (founded 1968) is a US-based multinational corporation that is best known for designing and manufacturing microprocessors and specialized integrated circuits. ... The Pentium Pro is a sixth-generation x86 architecture microprocessor by Intel originally intended to replace the original Pentium in a full range of applications, but later reduced to a more narrow role as a server and high-end desktop chip. ... International Business Machines Corporation (IBM, or colloquially, Big Blue) (NYSE: IBM) (incorporated June 15, 1911, in operation since 1888) is headquartered in Armonk, New York, USA. The company manufactures and sells computer hardware, software, and services. ... Motorola (NYSE: MOT) (TYO: 6686) is an electronics company based in Schaumburg, Illinois, a Chicago suburb. ... PowerPC is a RISC microprocessor architecture created by the 1991 Apple-IBM-Motorola alliance, known as AIM. Originally intended for workstations, PowerPC CPUs have since become popular embedded and high-performance processors as well. ... For the district in Saga, Japan, see Fujitsu, Saga. ... The Hewlett-Packard Company (NYSE: HPQ), commonly known as HP, is a very large global company headquartered in Palo Alto, California, United States. ... PA-RISC is a microprocessor architecture developed by Hewlett-Packards Systems & VLSI Technology Operation. ... A MIPS R4400 microprocessor made by Toshiba MIPS, for Microprocessor without interlocked pipeline stages, is a RISC microprocessor architecture developed by MIPS Computer Systems Inc. ... Advanced Micro Devices, Inc. ... The K5 was developed by AMD to compete with Intels Pentium microprocessor range. ... AXP redirects here. ... Sun Microsystems is a computer, semiconductor and software manufacturer headquartered in Santa Clara, California, in Silicon Valley. ... SPARC (Scalable Processor ARChitecture) is a pure big-endian RISC microprocessor architecture originally designed in 1985 by Sun Microsystems. ... The Hewlett-Packard Company (NYSE: HPQ), commonly known as HP, is a very large global company headquartered in Palo Alto, California, United States. ... Intel Corporation (NASDAQ: INTC) (founded 1968) is a US-based multinational corporation that is best known for designing and manufacturing microprocessors and specialized integrated circuits. ... In computing, the Itanium is an IA-64 zmicroprocessor developed jointly by Hewlett-Packard and Intel. ... Transmeta (NASDAQ: TMTA) was founded in 1995 by Dave Ditzel as a US-based corporation that designed VLIW code morphing microprocessors. ... Crusoe is a family of x86-compatible microprocessors from Transmeta. ...

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. Events and trends The 1990s are generally classified as having moved slightly away from the more conservative 1980s, but keeping the same mind-set. ...

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, otherwise 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.

An instruction is a form of information which is communicated in order to explain how an action, behavior, method, or task is to be begun, completed, conducted, or executed. ... Fetch can mean in various contexts: In geography fetch is a term for the length of water over which a given wind has blown. ... In mathematics, an operand is one of the inputs of an operator. ... In computer engineering, an execution unit is a part of a CPU that performs the operations and calculations called for by the program. ... A register file is an array of processor registers in a central processing unit (CPU). ...

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. When all older results have been 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 is not available. 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 effect of OoO processing grows as the instruction pipeline deepens and the speed difference between main memory (or cache memory) and the processor widens. For instance, on modern machines the processor runs many times faster than memory, so waiting for data to arrive over the bus is extremely costly. An instruction pipeline is a technology used on microprocessors to enhance their performance. ... Primary storage is a category of computer storage, often called main memory. ... This article is about the computer term. ...

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. In computer science a decoupled architecture refers to a processor with out-of-order execution that separates the fetch and decode stages from the execute stage in a pipelined processor by using a buffer. ...

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. In computer engineering, register renaming refers to a technique used to avoid unnecessary serialization of program operations imposed by the reuse of registers by those operations. ...

Execute and Writeback Decoupling allows program restart

The queue for results is necessary to resolve issues 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. In computer science, speculative execution is the execution of code whose result may not actually be needed. ...

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 most 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.