Out-of-Order Execution
Out-of-order (OoO) execution allows instructions to execute as soon as their operands are ready, regardless of program order. We study Tomasulo's algorithm with reservation stations, the Common Data Bus (CDB), and register renaming to eliminate WAW and WAR hazards.
Learning Objectives
Key Concepts
Dynamic Scheduling & Tomasulo's Algorithm
Tomasulo's algorithm (1967) enables out-of-order execution using:
- -Reservation Stations (RS): buffers that hold instructions waiting for operands
- -Common Data Bus (CDB): broadcasts results to all waiting reservation stations
- -Register renaming: tags replace register names, eliminating WAW and WAR hazards
Three stages: Issue (decode & allocate RS) → Execute (when operands ready) → Write Result (broadcast on CDB).
- -
Issue: instruction decoded, placed in RS. If operand available, copy value; otherwise record tag of producing RS
- -
Execute: begins when all operand tags are resolved (values received via CDB)
- -
Write Result: broadcast result on CDB — all waiting RS capture the value
- -
Register renaming eliminates WAR and WAW hazards — only true RAW dependencies remain
- -
Instructions issue in order but execute and complete out of order
Reorder Buffer (ROB)
The Reorder Buffer enables precise exceptions in an out-of-order processor. Instructions commit (retire) in program order from the ROB, even though they may have completed out of order. If an exception occurs, all instructions after the faulting one can be discarded cleanly.
- -
ROB is a circular buffer holding in-flight instructions in program order
- -
Commit stage: results written to register file in order from ROB head
- -
On exception: flush all ROB entries after the faulting instruction
- -
Speculative execution: branches can execute before being resolved; flush ROB on mispredict