Out-of-Order Execution (OoOE)

The Reorder Buffer (ROB) is the central data structure enabling OoOE. It acts as a temporary staging area for instructions between dispatch and retirement, preserving the illusion of in-order execution for the program. Key functions include:

• Instruction Dispatch: Instructions are placed in the ROB after being decoded.
• Out-of-Order Execution: Instructions are issued from the ROB to execution units as soon as their operands are ready, regardless of program order.
• In-Order Retirement: Completed instructions are retired from the ROB in strict program order to maintain architectural state consistency.

The Register Alias Table (RAT) is a critical structure that manages data dependencies in the presence of OoOE. It solves the WAR (Write-After-Read) and WAW (Write-After-Write) hazards that arise when instructions execute out of order.

• Dynamic Renaming: The RAT maps architectural registers (e.g., RAX) to physical registers in a larger register file, eliminating false dependencies (name hazards).
• Dependency Tracking: By assigning a new physical register to each instruction that writes a result, the RAT ensures consumers read the correct, most recent value.
• This mechanism, combined with the ROB, ensures correct dataflow execution.

Reservation Stations are buffers attached to execution units (ALUs, FPUs, load/store units) that enable true out-of-order scheduling.

• Operand Waiting: When an instruction is dispatched, it waits in a reservation station until all its source operands are available.
• Wake-Up Logic: When a result is broadcast on the Common Data Bus (CDB), reservation stations compare tags to see if the arriving data is needed by a waiting instruction.
• Tag-Based Execution: This Tomasulo's algorithm-inspired design allows instructions to execute immediately when data arrives, decoupling execution from the issue order.

OoOE exists within a constrained pipeline: an in-order front-end feeds it, and an in-order back-end commits its results.

• In-Order Front-End: Instruction fetch, decode, and rename stages proceed in program order. Branch prediction is critical here to keep the front-end fed with the likely correct instruction stream.
• Out-of-Order Core: The scheduler and execution units operate in the OoOE window.
• In-Order Back-End: The commit/retire stage writes results to the architectural register file and memory in original program order. This ensures precise interrupts and maintains a simple, consistent architectural state for the software.

OoOE is fundamentally reliant on speculative execution driven by accurate branch prediction.

• Speculative Dispatch: Instructions from predicted paths are fetched, renamed, and placed into the ROB and reservation stations.
• Speculative Execution: These instructions execute out-of-order using predicted data.
• Misprediction Recovery: On a branch misprediction, the pipeline must be flushed. The ROB is cleared of all speculatively executed instructions from the wrong path, and the RAT is restored to a checkpoint. This recovery mechanism is a major complexity and power cost of OoOE designs.

While powerful, OoOE has inherent limits and trade-offs, especially relevant in the age of accelerators.

• Power & Complexity: The ROB, RAT, large physical register files, and wake-up logic consume significant die area and power.
• Memory Latency Wall: OoOE can hide short latencies (e.g., cache hits), but long-latency operations (e.g., DRAM accesses) can still stall the ROB.
• Contrast with NPUs/GPUs: These accelerators often use in-order execution with massive multithreading (SIMT). Latency is hidden by switching between thousands of threads, not by reordering instructions within a single thread. This is often more area- and power-efficient for highly parallel, predictable workloads.

Instruction-level parallelism is the number of independent instructions within a program that can be executed simultaneously by a processor's functional units. It is the primary resource that OoOE aims to exploit.

• OoOE is a hardware technique to dynamically uncover and exploit ILP at runtime.
• Compiler techniques like software pipelining and loop unrolling are static methods to increase ILP for the hardware to schedule.
• The effectiveness of OoOE is limited by the true data dependencies (RAW hazards) present in the instruction stream.

Branch prediction is a complementary hardware mechanism that speculatively fetches and executes instructions along a predicted program path before the actual branch direction is known.

• It is critical for OoOE because it provides a continuous stream of instructions to keep the execution units busy.
• Mispredictions force the pipeline to flush speculatively executed instructions, causing a significant performance penalty.
• Modern predictors use complex algorithms (e.g., TAGE, perceptron-based) to achieve high accuracy, often above 95%.

Register renaming is a microarchitectural technique that eliminates false dependencies (WAR and WAW hazards) by dynamically mapping architectural registers to a larger pool of physical registers.

• It is an enabling technology for OoOE. Without it, many instructions would be serialized unnecessarily.
• The reorder buffer (ROB) tracks the original program order of renamed instructions to ensure precise exceptions and retirement in-order.
• This allows multiple instructions that write to the same architectural register to execute out-of-order and in parallel.

A superscalar processor can issue multiple instructions to different execution units in a single clock cycle. OoOE is typically implemented within a superscalar design.

• Issue width (e.g., 4-wide, 6-wide) defines how many instructions can be dispatched per cycle.
• OoOE's scheduler examines a window of ready instructions (the instruction window) to select the best candidates for issue each cycle.
• The combination of superscalar issue and OoOE is what allows modern CPUs to achieve high instructions per cycle (IPC).

Software pipelining is a compiler optimization that restructures loops to overlap the execution of instructions from different iterations, creating an instruction-level pipeline.

• It is the compiler's static analog to hardware OoOE, explicitly exposing ILP to the hardware.
• The compiler generates a prologue, a steady-state kernel, and an epilogue to manage the overlapped execution.
• This technique is highly effective for loops with long-latency operations (e.g., floating-point computations, memory loads), hiding latency by keeping the pipeline full.

In-order execution is the simpler microarchitectural paradigm where instructions are fetched, executed, and committed strictly in the order specified by the program.

• It serves as the conceptual baseline against which OoOE is compared.
• In-order processors stall the pipeline whenever an instruction cannot proceed (e.g., waiting for a cache miss), leaving execution units idle.
• It is still used in many high-efficiency cores (e.g., ARM Cortex-A55, Intel Atom) and most GPU shader cores due to its simpler, lower-power design.