Out-of-order execution

What is out-of-order execution?

WHY do we need this?

In-order processors stall when they hit a data dependency or cache miss
Modern instructions have vastly different latencies: register ops (1 cycle), L1 cache (4 cycles), memory (100+ cycles)
Without OoOE, the CPU wastes cycles waiting even when independent work exists

HOW does it work? The CPU separates the instruction lifecycle into phases that can operate independently:

Fetch/Decode (in-order): Instructions enter the pipeline
Dispatch (in-order): Instructions allocated to reservation stations
Execute (OUT-OF-ORDER): Instructions fire when operands ready
Commit/Retire (in-order): Results written back in program order

The Tomasulo algorithm foundation

Modern OoOE traces back to Tomasulo's algorithm (IBM 360/91, 1967). Let's derive the key insight from first principles.

The problem: Register renaming and dynamic scheduling.

Consider this code:

R1 = R2 + R3    ; (I1)
R4 = R1 * R5    ; (I2) - depends on I1
R1 = R6 - R7    ; (I3) - WAW hazard with I1
R8 = R1 + R9    ; (I4) - depends on I3, NOT I1

In-order execution: I2 waits for I1, I3 waits for I2, I4 waits for I3 → serial execution.

The insight: The two uses of R1 are different logical values. If we rename them:

T1 = R2 + R3    ; (I1) renamed
R4 = T1 * R5    ; (I2) 
T2 = R6 - R7    ; (I3) renamed
R8 = T2 + R9    ; (I4)

Now I3 and I1 can execute in parallel! I4 depends only on I3, not I1.

WHY this step? By breaking the false dependencies, we expose the true data-flow graph. The CPU can now issue any instruction whose inputs are ready.

Reservation stations and execution

Derivation of the ready condition:

Let instruction $I$ require operands $\text{src}_1, \text{src}_2$ . Each operand is either:

Ready: value is in the reservation station
Waiting: tagged with producer instruction $P_j$

$\text{Ready}(I) = \text{Ready}(\text{src}_1) \land \text{Ready}(\text{src}_2)$

When producer $P_j$ completes, it broadcasts (tag: Pj, value: V) on the CDB. All reservation stations snoop the CDB and:

$\forall I: (\text{src}_i = P_j) \Rightarrow (\text{src}_i \leftarrow V, \text{Ready}(\text{src}_i) \leftarrow \text{true})$

WHY broadcast? Multiple instructions might wait on the same result. Broadcasting to all stations in parallel avoids sequential wakeup delays.

Worked example Worked example: OoOE in action

Consider this sequence. Assume all ops take 1 cycle except LOAD takes 3 cycles. We count a cycle "used" for each cycle the instruction is executing, and a dependent instruction fires the cycle after its last operand becomes available.

I1: R1 = LOAD [addr1]   ; 3 cycles
I2: R2 = R3 + R4        ; 1 cycle
I3: R5 = R1 + R2        ; 1 cycle - depends on I1 and I2
I4: R6 = R7 * R8        ; 1 cycle - independent

In-order execution timeline:

Cycle: 1   2   3   4   5   6
I1:    L   L   L
I2:                +
I3:                    +
I4:                        *
Total: 6 cycles

I2, I4 wait unnecessarily behind the slow load and its dependent chain.

Out-of-order execution timeline:

Cycle: 1   2   3   4   5
I1:    L   L   L
I2:    +
I4:        *
I3:                +
Total: 5 cycles

Why this step? I2 and I4 have no dependency on I1, so they execute early on free execution ports (I2 in cycle 1, I4 in cycle 2). I1's LOAD occupies cycles 1–3 (its full 3-cycle latency). I3 needs both I1's result (ready end of cycle 3) and I2's result (ready end of cycle 1), so I3 fires in cycle 4. The pipeline drains and I3's result is available by the end of cycle 4; total span including commit settling is 5 cycles.

Speedup: $6/5 = 1.2\times$ on this tiny example. The key point is that OoOE removes the unnecessary stalls of I2 and I4; the residual latency comes from the genuine dependency chain I1 → I3. Real code with more independent work and longer chains sees 2–3× improvements.

The reorder buffer (ROB)

The problem: Out-of-order execution creates out-of-order completion. But we need precise exceptions: if instruction 5 faults, instructions 1-4 must commit, 6+ must not.

Derivation of commit logic:

Let ROB entries be $\{I_1, I_2, \ldots, I_n\}$ in program order. At the head $h$ :

$\text{Can\_Commit}(I_h) = \text{Complete}(I_h) \land \neg\text{Exception}(I_h)$

If $\text{Exception}(I_h)$ :

Flush all entries after $h$
Roll back architectural state to $I_h$ 's input
Signal exception to OS

WHY in-order commit? To maintain the illusion that instructions executed sequentially. External observers (memory system, interrupts, debuggers) see results as if the program ran in-order.

Formula The speculation window (qualitative model)

The instruction window is the set of in-flight instructions between fetch and commit. A larger window lets the CPU look further ahead to find independent work. Qualitatively, achievable IPC is bounded by three competing limits: $\text{IPC} \leq \min\big(\text{Window-limited ILP},\ \text{Execution width},\ \text{Critical-path-limited ILP}\big)$

Where:

Window-limited ILP: you can only reorder instructions currently in the window
Execution width: number of parallel execution units / issue ports
Critical-path-limited ILP: even infinite resources cannot beat the longest dependency chain

Modern CPUs: window size ~200-300 instructions (Intel, AMD) to ~600+ (Apple M-series).

WHY this bound (not a precise formula): This is a conjecture-level upper bound, not a derived closed form. The window must be large enough to expose independent work, but if dependencies dominate you hit the critical-path limit, and if resources dominate you hit the execution-width limit. Real IPC depends on branch prediction accuracy, cache behavior, and memory-level parallelism in ways no single clean equation captures.

Worked example ROB commit with exception

ROB: [I1✓, I2✓, I3(fault), I4✓, I5✓]
          ^head

I1 and I2 already committed. I3 is at head and faulted (e.g., divide-by-zero). I4 and I5 executed but are speculatively executed.

Commit logic:

I3 faults → trigger exception handler
Flush I4, I5 from ROB (their results discarded)
Architectural state = post-I2
OS handles exception, possibly fixes and restarts at I3

Why this step? User code sees clean semantics: "I3 faulted, nothing after it happened." Even though I4 and I5 computed results internally, those results never became visible (never committed to architectural registers/memory).

Common mistakes

Common mistake Mistake 2: "Infinite instruction window = infinite speedup"

Why it feels right: More instructions in flight → more parallelism → faster execution.

The steel-man: This would be true if programs had infinite parallelism. Reality:

Dependency chains create serial bottlenecks (Amdahl's law)
Execution unit contention: only so many ALUs, load/store ports
Power and area: larger windows need more associative lookups (superlinear cost)

The fix: Speedup saturates around 150-300 instruction windows for most code. Diminishing returns kick in because the critical path (longest dependency chain) dominates.

$\text{Speedup} \leq \frac{\text{Latency}_{\text{in-order}}}{\text{Latency}_{\text{critical path}}}$

Common mistake Mistake 3: "OoOE can reorder stores freely"

Why it feels right: If stores are independent, execute them out-of-order for speed.

The steel-man: This breaks memory consistency models. Consider:

Thread 1:        Thread 2:
store [X] = 1    load r1 = [Y]
store [Y] = 1    load r2 = [X]

If Thread 1 reorders stores, Thread 2 might see r1=1, r2=0 (Y written but not X yet), violating sequential consistency.

The fix: OoOE must respect memory ordering rules:

x86: Total Store Order (TSO) → stores commit in program order
ARM/RISC-V: relaxed models allow reordering but provide fence instructions The store buffer queues stores and drains them in order (or with explicit fences).

Memory model interaction

How OoOE interacts with multi-core:

Each core's OoOE engine maintains single-threaded illusion. But caches are shared/coherent. The memory consistency model defines what reorderings are visible across cores.

For x86 TSO, the allowed and forbidden reorderings are:

Loads are NOT reordered with older loads (Load→Load order preserved)
Loads MAY pass older stores to a different address (Store→Load reordering allowed; this is the one relaxation TSO permits)
Stores are NOT reordered with older stores (Store→Store order preserved, enforced at commit)
Stores are NOT reordered with older loads (Load→Store order preserved)

WHY these rules? Balance performance (allow the common Store→Load relaxation via the store buffer) vs. programmer sanity (preserve intuitive ordering everywhere else).

Worked example OoOE + cache coherence

Core 0:              Core 1:
store [X] = 1        load r1 = [Y]
store [Y] = 1        load r2 = [X]

Core 0's OoOE might compute both stores early, but they sit in the store buffer. The ROB commits them in-order, sending cache coherence invalidations in program order. Core 1's loads snoop these invalidations via the MESI protocol. Under TSO, Core 1's two loads also stay in order, so it cannot observe r1=1 (Y=1) together with r2=0 (X still 0).

Performance metrics

The ILP wall: typical programs have ~2-3 independent instructions per cycle on average. Even perfect OoOE hits this limit. Modern CPUs compensate with:

Wider issue (4-6 wide dispatch)
Deeper speculation (branch prediction)
Simultaneous multithreading (SMT/Hyper-Threading)

Connections

5.1.01-Pipelining: OoOE extends pipelining by decoupling stages
5.3.01-Superscalar-architecture: OoOE enables superscalar (multiple issue per cycle)
5.3.03-Speculative-execution: OoOE + branch prediction = speculative execution
5.3.04-Register-renaming: The RAT mechanism in detail
5.4.01-Cache-coherence: How OoOE respects MESI/MOESI in multicore
5.5.02-Memory-consistency-models: TSO, relaxed models, and fence instructions
6.2.03-Branch-prediction: Predicting control flow to keep the window full
7.1.01-Instruction-level-parallelism: Theoretical limits (data-flow graphs)

Recall Explain to a 12-year-old

Imagine you're doing homework with 5 problems. Problem 1 needs a book from the library (your parent will bring it in 10 minutes). Problem 2, 3, 4 are easy math you can do now. Problem 5 needs problem 1's answer.

Bad strategy (in-order): Wait for problem 1 (10 min), do it, do 2, 3, 4, then 5. Total: 10 + 1 + 1 + 1 = 14 minutes.

Smart strategy (out-of-order): Do problems 2, 3, 4 right now (3 min). When the book arrives, do 1 (1 min), then 5 (1 min). Total: 3 + 1 + 1 = 5 minutes.

You finish 3× faster! The CPU does the same: while waiting for slow memory (the "library book"), it works on other instructions (the "easy math"). It keeps the final answers in the correct order so the teacher (the programmer) never knows you did them out-of-order.

#flashcards/hardware

What is the key difference between in-order and out-of-order execution?

In-order executes instructions strictly in program order, stalling on dependencies. Out-of-order reorders execution dynamically to issue instructions as soon as operands are ready, while maintaining in-order commit for correct architectural state.

What are the three types of hazards, and which can register renaming eliminate?

RAW (Read-After-Write) = true dependency, cannot eliminate. WAR (Write-After-Read) and WAW (Write-After-Write) = false dependencies caused by register reuse, eliminated by renaming to different physical registers.

What is the purpose of the reorder buffer (ROB)?

The ROB maintains in-order commit even though execution is out-of-order. It enables precise exceptions by flushing speculative instructions after a fault and ensures architectural state updates in program order.

How does a reservation station know when an instruction is ready to execute?

An instruction is ready when all source operands are either (1) already present with values, or (2) their producer tags have been broadcast on the Common Data Bus (CDB). The station snoops the CDB and updates operands as results arrive.

Under x86 TSO, which single reordering is allowed?

Only Store→Load reordering to different addresses: a load may pass an older store to a different address (via the store buffer). Load→Load, Store→Store, and Load→Store orderings are all preserved.

What limits IPC scaling even with infinite instruction window size?

The critical path (longest dependency chain) and Amdahl's law. Programs have limited instruction-level parallelism due to data dependencies, so even unlimited resources cannot parallelize serial bottlenecks. Typical saturation at IPC ≈ 2-4.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, modern CPU ka ek kamaal ka trick hai jo core idea hai out-of-order execution ka. Normally hum sochte hain ki processor jis order mein humne instructions likhe, usi order mein execute karega. Lekin actually mein aisa nahi hota! CPU smart hai — agar ek instruction slow operation ka wait kar raha hai (jaise memory se data laana, jismein 100+ cycles lag sakte hain), toh processor idle nahi baithta. Woh dusre instructions ko dhoondhta hai jinke operands ready hain aur unhe abhi execute kar deta hai. Bilkul restaurant kitchen jaisa — agar ek dish oven mein wait kar rahi hai, toh chef khaali khada nahi rehta, woh doosri dishes banane lag jaata hai jo abhi ho sakti hain. Aur haan, programmer ko lagta hai sab kuch order mein hi ho raha hai, kyunki final results architectural state mein sahi order mein commit hote hain — yeh illusion maintain rehta hai.

Ab yahaan ek important concept aata hai — register renaming. Kai baar do instructions same register (jaise R1) use karte hain, lekin actually mein woh alag-alag logical values hote hain. Iss reuse ki wajah se "false dependencies" ban jaati hain (WAR aur WAW hazards), jo unnecessarily instructions ko serial bana dete hain. Trick yeh hai ki CPU internally bahut saare physical registers rakhta hai (~168) jabki programmer ko sirf 16-32 architectural registers dikhte hain. Register Alias Table (RAT) inhe dynamically map karta hai. Jab hum R1 ke do alag uses ko T1 aur T2 mein rename kar dete hain, toh false dependency khatam ho jaati hai aur woh instructions parallel mein chal sakte hain! Sirf true dependency (RAW — jab ek instruction dusre ka result padhta hai) hi bachti hai, jo genuinely reorder nahi ki ja sakti.

Yeh sab matter kyun karta hai? Kyunki performance ka pura khel throughput ka hai — execution units ko busy rakhna hai, waste cycles nahi hone dene. Reservation stations woh buffers hain jahaan instructions apne operands ka wait karte hue baithte hain, aur woh Common Data Bus (CDB) ko continuously "snoop" karte rehte hain. Jaise hi koi producer instruction apna result broadcast karta hai, saare waiting instructions parallel mein apne operands update kar lete hain — isiliye broadcast use hota hai, taaki sequential wakeup ki delay na ho. Yeh Tomasulo algorithm (1967, IBM 360/91) se aaya hai aur aaj bhi har modern processor ki foundation hai. Agar tum hardware ya computer architecture mein aage badhna chahte ho, toh yeh concept samajhna zaroori hai, kyunki yahi real-world CPUs ko itna fast banata hai.

What is out-of-order execution?

The Tomasulo algorithm foundation

Reservation stations and execution

The reorder buffer (ROB)

Common mistakes

Memory model interaction

Performance metrics

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Advanced Microarchitecture

Connections