Out-of-order execution

Out-of-order execution lets a processor run instructions as their inputs become available, even when earlier instructions are stalled. Results are committed in program order to preserve the appearance of sequential execution.

Tomasulo algorithm: A dynamic scheduling algorithm that tracks operand availability and lets instructions execute when their inputs are ready. Its reservation stations and register renaming established a classic way to schedule instructions dynamically.
Instruction pipeline: A processor design that divides instruction processing into stages so multiple instructions can overlap. Out-of-order execution changes how a pipelined processor schedules overlapping instructions.
In-order execution: A processor scheduling policy that issues or executes instructions in program order. It avoids much scheduling complexity but lets an early stall delay later independent instructions.
Instruction window: The set of instructions a processor can inspect and keep in flight at one time. A larger window gives the scheduler more chances to find independent work.
Reservation station: A processor buffer that holds an instruction until its operands are available and an execution unit can accept it. Instructions wait here rather than blocking the processor while an earlier operation stalls.
Data dependency: A constraint requiring one instruction to wait for another because it uses a value that instruction produces or changes. True data dependencies still prevent an instruction from running before its required values exist.
Scoreboarding: A hardware scheduling method that tracks instruction and resource hazards to permit safe out-of-order execution. It offers dynamic scheduling without Tomasulo's register-renaming approach.
Branch predictor: A processor component that predicts the direction or target of control-flow instructions. Accurate predictions keep the instruction window supplied with useful work.
Register renaming: A technique that maps architectural registers to physical registers to remove false dependencies between instructions. It lets independent instructions proceed without being held back by reused register names.
Data hazard: A pipeline conflict in which instruction timing or dependencies can produce an incorrect result or delay execution. Dynamic scheduling works around some hazards while respecting dependencies that affect correctness.

Linked from 8 pages