Incomputer engineering,out-of-order execution (or more formallydynamic execution) is aninstruction scheduling paradigm used in high-performancecentral processing units to make use ofinstruction cycles that would otherwise be wasted. In this paradigm, a processor executesinstructions in an order governed by the availability of input data and execution units,[1] rather than by their original order in a program.[2][3] 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.[4]
Out-of-order execution is a restricted form ofdataflow architecture, which was a major research area incomputer architecture in the 1970s and early 1980s.
Arguably the first machine to use out-of-order execution is theCDC 6600 (1964), which used ascoreboard to resolve conflicts. The 6600 however lackedWAW conflict handling, choosing instead to stall. This situation was termed a "First Order Conflict" by Thornton.[5] Whilst it had bothRAW conflict resolution (termed "Second Order Conflict"[6]) andWAR conflict resolution (termed "Third Order Conflict"[7]) all of which is sufficient to declare it capable of full out-of-order execution, the 6600 did not have precise exception handling. An early and limited form of Branch prediction was possible as long as the branch was to locations on what was termed the "Instruction Stack" which was limited to within a depth of seven words from the Program Counter.[8]
About two years later, theIBM System/360 Model 91 (1966) introducedregister renaming withTomasulo's algorithm,[9] which dissolves false dependencies (WAW and WAR), making full out-of-order execution possible. An instruction addressing a write into a registerrn can be executed before an earlier instruction using the registerrn is executed, by actually writing into an alternative (renamed) registeralt-rn, which is turned into a normal registerrn only when all the earlier instructions addressingrn have been executed, but until thenrn is given for earlier instructions andalt-rn for later ones addressingrn.
In the Model 91 the register renaming is implemented by abypass termedCommon Data Bus (CDB) and memory source operand buffers, leaving the physical architectural registers unused for many cycles as the oldest state of registers addressed by any unexecuted instruction is found on the CDB. Another advantage the Model 91 has over the 6600 is the ability to execute instructions out-of-order in the sameexecution unit, not just between the units like the 6600[disputed –discuss]. This is accomplished byreservation stations, from which instructions go to the execution unit when ready, as opposed to the FIFO queue[disputed –discuss] of each execution unit of the 6600. The Model 91 is also capable of reordering loads and stores to execute before the preceding loads and stores,[10] unlike the 6600, which only has a limited ability to move loads past loads, and stores past stores, but not loads past stores and stores past loads.[11] Only the floating-point registers of the Model 91 are renamed, making it subject to the same WAW and WAR limitations as the CDC 6600 when running fixed-point calculations. The 91 and 6600 both also suffer fromimprecise exceptions, which needed to be solved before out-of-order execution could be applied generally and made practical outside supercomputers.
To haveprecise exceptions, the proper in-order state of the program's execution must be available upon an exception. By 1985 various approaches were developed as described byJames E. Smith and Andrew R. Pleszkun.[12] TheCDC Cyber 205 was a precursor, as upon a virtual memory interrupt the entire state of the processor (including the information on the partially executed instructions) is saved into aninvisible exchange package, so that it can resume at the same state of execution.[13] However to make all exceptions precise, there has to be a way to cancel the effects of instructions. The CDC Cyber 990 (1984) implements precise interrupts by using a history buffer, which holds the old (overwritten) values of registers that are restored when an exception necessitates the reverting of instructions.[12] Through simulation, Smith determined that adding a reorder buffer (or history buffer or equivalent) to theCray-1S would reduce the performance of executing the first 14Livermore loops (unvectorized) by only 3%.[12] Important academic research in this subject was led byYale Patt with hisHPSm simulator.[14]
In the 1980s many earlyRISC microprocessors, had out-of-order writeback to the registers, invariably resulting in imprecise exceptions. TheMotorola 88100 was one of the few early microprocessors that did not suffer from imprecise exceptions despite out-of-order writes, although it did allow both precise and imprecise floating-point exceptions.[15] Instructions started execution in order, but some (e.g. floating-point) took more cycles to complete execution. However, the single-cycle execution of the most basic instructions greatly reduced the scope of the problem compared to the CDC 6600.
Smith also researched how to make different execution units operate more independently of each other and of the memory, front-end, and branching.[16] He implemented those ideas in theAstronautics ZS-1 (1988), featuring a decoupling of the integer/load/storepipeline from the floating-point pipeline, allowing inter-pipeline reordering. The ZS-1 was also capable of executing loads ahead of preceding stores. In his 1984 paper, he opined that enforcing the precise exceptions only on the integer/memory pipeline should be sufficient for many use cases, as it even permitsvirtual memory. Each pipeline had an instruction buffer to decouple it from the instruction decoder, to prevent the stalling of the front end. To further decouple the memory access from execution, each of the two pipelines was associated with two addressablequeues that effectively performed limited register renaming.[10] A similar decoupled architecture had been used a bit earlier in the Culler 7.[17] The ZS-1's ISA, like IBM's subsequent POWER, aided the early execution of branches.
With thePOWER1 (1990), IBM returned to out-of-order execution. It was the first processor to combine register renaming (though again only floating-point registers) with precise exceptions. It uses aphysical register file (i.e. a dynamically remapped file with both uncommitted and committed values) instead of a reorder buffer, but the ability to cancel instructions is needed only in the branch unit, which implements a history buffer (namedprogram counter stack by IBM) to undo changes to count, link, and condition registers. The reordering capability of even the floating-point instructions is still very limited; due to POWER1's inability to reorder floating-point arithmetic instructions (results became available in-order), their destination registers aren't renamed. POWER1 also doesn't havereservation stations needed for out-of-order use of the same execution unit.[18][19] The next year IBM'sES/9000 model 900 had register renaming added for the general-purpose registers. It also hasreservation stations with six entries for the dual integer unit (each cycle, from the six instructions up to two can be selected and then executed) and six entries for the FPU. Other units have simple FIFO queues. The reordering distance is up to 32 instructions.[20] The A19 ofUnisys'A-series of mainframes was also released in 1991 and was claimed to have out-of-order execution, and one analyst called the A19's technology three to five years ahead of the competition.[21][22]
The firstsuperscalarsingle-chip processors (Intel i960CA in 1989) used a simple scoreboarding scheduling like the CDC 6600 had a quarter of a century earlier. In 1992–1996 a rapid advancement of techniques, enabled byincreasing transistor counts, saw proliferation down topersonal computers. TheMotorola 88110 (1992) used a history buffer to revert instructions.[23] Loads could be executed ahead of preceding stores. While stores and branches were waiting to start execution, subsequent instructions of other types could keep flowing through all the pipeline stages, including writeback. The 12-entry capacity of the history buffer placed a limit on the reorder distance.[24][25][26] ThePowerPC 601 (1993) was an evolution of theRISC Single Chip, itself a simplification of POWER1. The 601 permitted branch and floating-point instructions to overtake the integer instructions already in the fetched instruction queue, the lowest four entries of which were scanned for dispatchability. In the case of a cache miss, loads and stores could be reordered. Only the link and count registers could be renamed.[32] In the fall of 1994NexGen andIBM with Motorola brought the renaming of general-purpose registers to single-chip CPUs. NexGen's Nx586 was the firstx86 processor capable of out-of-order execution and featured a reordering distance of up to 14micro-operations.[33] ThePowerPC 603 renamed both the general-purpose and FP registers. Each of the four non-branch execution units can have one instruction wait in front of it without blocking the instruction flow to the other units. A five-entryreorder buffer lets no more than four instructions overtake an unexecuted instruction. Due to a store buffer, a load can access cache ahead of a preceding store.[34][35]
PowerPC 604 (1995) was the first single-chip processor withexecution unit-level reordering, as three out of its six units each had a two-entry reservation station permitting the newer entry to execute before the older. The reorder buffer capacity is 16 instructions. A four-entry load queue and a six-entry store queue track the reordering of loads and stores upon cache misses.[36]HAL SPARC64 (1995) exceeded the reordering capacity of theES/9000 model 900 by having three 8-entry reservation stations for integer, floating-point, andaddress generation unit, and a 12-entry reservation station for load/store, which permits greater reordering of cache/memory access than preceding processors. Up to 64 instructions can be in a reordered state at a time.[37][38]Pentium Pro (1995) introduced aunified reservation station, which at the 20 micro-OP capacity permitted very flexible reordering, backed by a 40-entry reorder buffer. Loads can be reordered ahead of both loads and stores.[39]
The practically attainableper-cycle rate of execution rose further as full out-of-order execution was further adopted bySGI/MIPS (R10000) andHPPA-RISC (PA-8000) in 1996. The same yearCyrix 6x86 andAMD K5 brought advanced reordering techniques into mainstream personal computers. SinceDEC Alpha gained out-of-order execution in 1998 (Alpha 21264), the top-performing out-of-order processor cores have been unmatched by in-order cores other thanHP/IntelItanium 2 andIBM POWER6, though the latter had an out-of-orderfloating-point unit.[40] The other high-end in-order processors fell far behind, namelySun'sUltraSPARC III/IV, and IBM'smainframes which had lost the out-of-order execution capability for the second time, remaining in-order into thez10 generation. Later big in-order processors were focused on multithreaded performance, but eventually theSPARC T series andXeon Phi changed to out-of-order execution in 2011 and 2016 respectively.[citation needed]
Almost all processors for phones and other lower-end applications remained in-order untilc. 2010. First,Qualcomm'sScorpion (reordering distance of 32) shipped inSnapdragon,[41] and a bit laterArm'sA9 succeededA8. For low-endx86personal computers in-orderBonnell microarchitecture in earlyIntel Atom processors were first challenged byAMD'sBobcat microarchitecture, and in 2013 were succeeded by an out-of-orderSilvermont microarchitecture.[42] Because the complexity of out-of-order execution precludes achieving the lowest minimum power consumption, cost and size, in-order execution is still prevalent inmicrocontrollers andembedded systems, as well as in phone-class cores such as Arm'sA55 andA510 inbig.LITTLE configurations.
Out-of-order execution is more sophisticated relative to the baseline of in-order execution. In pipelined in-order execution processors, execution of instructions overlap in pipelined fashion with each requiring multipleclock cycles to complete. The consequence is that results from a previous instruction will lag behind where they may be needed in the next. In-order execution still has to keep track of these dependencies. Its approach is however quite unsophisticated: stall, every time. Out-of-order uses much more sophisticated data tracking techniques, as described below.
In earlier processors, the processing of instructions is performed in aninstruction cycle normally consisting of the following steps:
Often, an in-order processor has abit vector recording which registers will be written to by a pipeline.[43] If any input operands have the corresponding bit set in this vector, the instruction stalls. Essentially, the vector performs a greatly simplified role of protecting against register hazards. Thus out-of-order execution uses 2D matrices whereas in-order execution uses a 1D vector for hazard avoidance.
This new paradigm breaks up the processing of instructions into these steps:[44]
The key concept of out-of-order 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 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.
Out-of-order processors fill theseslots in time with other instructions thatare ready, then either reorder the results at the end to make it appear that the instructions were processed as normal, record and thus apply the originalprogram order, or commit in uninterruptible batches where order will not cause data corruption.The way the instructions are ordered in the original computer code is known asprogram order, in the processor they are handled indata order, the order in which the data becomes 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 benefit of out-of-order processing grows as theinstruction pipeline deepens and the speed difference betweenmain memory (orcache 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 theoretically processed a large number of instructions.
One of the differences created by the new paradigm is the creation of queues that allow 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 wasdecoupled architecture. In the earlierin-order processors, these stages operated in a fairlylock-step, pipelined fashion.
Thefetch and decode stages is separated from the execute stage in apipelined processor by using abuffer. The buffer's purpose is to partition thememory access and execute functions in a computer program and achieve high performance by exploiting the fine-grainparallelism between the two.[45] In doing so, it effectively hides allmemory latency from the processor's perspective.
A larger buffer can, in theory, increase throughput. However, if the processor has abranch misprediction then the entire buffer may need to be flushed, wasting a lot ofclock cycles and reducing the effectiveness. Furthermore, larger buffers create more heat and use moredie space. For this reason processor designers today favor amulti-threaded design approach.
Decoupled architectures are generally thought of as not useful for general-purpose computing as they do not handle control-intensive code well.[46] Control intensive code include such things as nested branches that occur frequently inoperating system kernels. Decoupled architectures play an important role in scheduling invery long instruction word (VLIW) architectures.[47]
The queue for results is necessary to resolve issues such as branch mispredictions and exceptions. The results queue allows programs to be restarted after an exception and for 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 that have yet to be resolved is known asspeculative execution.
Are the instructions dispatched to a centralized queue or to multiple 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 that hold the register renaming information for each instruction in flight.
don't wait for previous instructions to execute if this instruction does not depend on them
The algorithm "allows sequential instructions that would normally be stalled due to certain dependencies to execute non-sequentially" (also known as out of order execution).[dead link]
This flexibility improves performance since it allows execution with less 'waiting' time.
{{cite book}}:|work= ignored (help)The new A19 relies on "super-scalar" techniques from scientific computers to execute many instructions concurrently. The A19 can overlap as many as 140 operations, more than 10 times as many as conventional mainframes can.