Out-of-order execution
lastmod 2018-08-17created 2015-10-052 edits
Out-of-order execution (OoOE for short) is a paradigm in which high-performance microprocessors make use of instruction cycles that would otherwise be wasted by certain kinds of delays. It is a technique of not processing instructions in order in order to improve instruction execution efficiency, and it is adopted by many processors.
Basic concept
When programmers write a program, they believe the code they wrote will run in order (from top to bottom, if there are no branch statements). An in-order processor executes while keeping exactly this order. But suppose a memory load instruction is suffering a cache miss. If some of the instructions that follow it are unrelated to this load instruction, they could clearly be executed ahead of time. Also, even a single-threaded program clearly has instructions that can be processed at the same time. This is called Instruction Level Parallelism (ILP). An out-of-order processor has the hardware itself find ILP in real time, dramatically increasing instruction throughput. Out-of-order processors are usually built as superscalar processors, because that is what lets them effectively process two or more instructions that can run in parallel at the same time. This instruction-level parallelism is constrained not by the order written in the code but by the flow of data or control. These are called dependencies, with data dependencies, control dependencies, and memory dependencies being the main ones. In short, an out-of-order processor can be seen as a processor that finds and processes the flow of data. However, hardware limitations restrict the range in which ILP can be found. This range is often called the Instruction Window. Modern processors find ILP among roughly 100 or more instructions and execute them out of order.