Out-of-order execution

In computer engineering, out-of-order execution (or more formally dynamic execution) is a paradigm used in most high-performance central processing units to make use of instruction cycles that would otherwise be wasted. In this paradigm, a processor executes instructions in an order governed by the availability of input data and execution units, 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 and can, in the meantime, process the next instructions that are able to run immediately and independently. In computer engineering, out-of-order execution (or more formally dynamic execution) is a paradigm used in most high-performance central processing units to make use of instruction cycles that would otherwise be wasted. In this paradigm, a processor executes instructions in an order governed by the availability of input data and execution units, 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 and can, in the meantime, process the next instructions that are able to run immediately and independently. 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 is the CDC 6600 (1964), which uses a scoreboard to resolve conflicts (although 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 System/360 Model 91 (1966) introduced Tomasulo's algorithm, which makes full out-of-order execution possible. In 1990, IBM introduced the first out-of-order microprocessor, the POWER1, although out-of-order execution is limited to floating-point instructions (as is also the case on the Model 91). In 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 (1996). Notable exceptions to this trend include the Sun UltraSPARC, HP/Intel Itanium, Intel Atom until Silvermont Architecture, and the IBM POWER6.