Out-of-order execution: Question bank — Hardware deep dive

Before you start, make sure these words feel solid. If any feel fuzzy, they are all built from zero in the parent note.

True or false — justify

TF1. "Out-of-order execution can change the answer a single-threaded program computes."

False — true (RAW) data dependencies are always respected, and results become visible only at in-order commit, so the observable answer is identical to in-order execution.

TF2. "If instructions commit in order, then they must also execute in order."

False — execute and commit are separate phases; instructions execute whenever their operands are ready (out of order) but the ROB forces the commit step back into program order.

TF3. "Register renaming can remove a RAW (read-after-write) dependency."

False — renaming only removes false dependencies (WAR/WAW) caused by reusing register names; a RAW is genuine data-flow, so the reader must still wait for the real value. See 5.3.04-Register-renaming.

TF4. "A wider issue width (more execution units) always increases IPC."

False — IPC is bounded by the minimum of window-limited ILP, execution width, and critical-path ILP; if a long dependency chain dominates, extra ports sit idle.

TF5. "The reorder buffer stores instructions in the order they finish executing."

False — the ROB is a circular queue in program order; instructions may fill their result slots out of order, but the head always points at the oldest un-committed instruction.

TF6. "A speculatively executed instruction that later gets squashed still modifies a real register."

False — its result lives only in a physical register / ROB slot and is discarded on a flush; it never reaches architectural state, so no real register or memory changes.

TF7. "OoOE removes the need for branch prediction."

False — the CPU still must guess which instructions to fetch past a branch to fill the window; wrong guesses are cleaned up by the ROB flush, but without 6.2.03-Branch-prediction the window would starve. See 5.3.03-Speculative-execution.

TF8. "With enough physical registers, WAW hazards disappear entirely."

True — a WAW hazard is a name collision; giving each write a fresh physical name means two writes to the same architectural register never contend, which is exactly what renaming does.

TF9. "In-order commit means the CPU is essentially in-order and gains nothing."

False — only the final visibility step is ordered; all the latency-hiding happens in the out-of-order execute phase where independent work fires during a slow load's shadow.

Spot the error

SE1. "I renamed R1 in R1=R2+R3 then R4=R1*R5, so now those two can run in parallel."

Wrong — the second instruction reads R1 that the first writes (a RAW), which renaming cannot break; only the two independent writers of a reused register become parallel.

SE2. "The Common Data Bus sends each result to exactly one waiting reservation station."

Wrong — the CDB broadcasts; every reservation station snoops it simultaneously so all instructions waiting on the same tag wake up in parallel, avoiding sequential wakeup delays.

SE3. "Instruction 5 faulted, so the CPU commits 1–4 and then also commits 5's already-computed result before jumping to the handler."

Wrong — a faulting instruction is not committed; its own result and everything after it are flushed, architectural state stays at instruction 4, then the exception handler runs.

SE4. "A 600-entry instruction window gives 600× the parallelism of a 1-entry window."

Wrong — window size only bounds how far ahead you can look; actual parallelism is capped by the true dependency chains (critical path) and the number of execution ports.

SE5. "Since I4 and I5 executed before I3 faulted, their side effects on memory are already done."

Wrong — stores are held in a buffer and only released at commit; because I4/I5 never commit, their memory writes never become visible, preserving precise exceptions.

SE6. "A reservation station holds an instruction until an execution unit is free, so operands are irrelevant."

Wrong — an instruction only becomes ready when both operands have arrived (Ready(src1) ∧ Ready(src2)); it competes for an execution unit only after that, so operand availability is the primary gate.

SE7. "Because OoOE reorders loads and stores, two threads will always see consistent memory automatically."

Wrong — single-thread ordering is preserved, but across cores the reordering interacts with 5.5.02-Memory-consistency-models and 5.4.01-Cache-coherence; other threads can observe reordered effects unless fences/protocols constrain them.

Why questions

WQ1. "Why commit in program order at all if execution is out of order?"

To keep precise, sequential-looking architectural state so exceptions, interrupts, and debuggers see a clean point where "everything before happened, nothing after did."

WQ2. "Why are physical registers far more numerous than architectural registers?"

Each in-flight write needs its own physical name to break WAR/WAW false dependencies; with ~200 instructions in flight you need many more physical names than the 16–32 the ISA exposes.

WQ3. "Why does OoOE pair naturally with superscalar and speculative execution?"

5.3.01-Superscalar-architecture provides multiple ports so several ready instructions issue per cycle, and 5.3.03-Speculative-execution keeps the window full past branches — OoOE is the scheduler that exploits both to maximize 7.1.01-Instruction-level-parallelism.

WQ4. "Why can't we just build an infinitely large instruction window and reach infinite IPC?"

Because the critical dependency path sets a hard floor: even with infinite window and infinite ports, a chain A→B→C→D must execute serially, so IPC saturates at the ILP the data-flow graph allows.

WQ5. "Why does a slow LOAD not stall independent arithmetic in OoOE?"

The independent arithmetic has no RAW dependency on the load's result, so it fires on a free port during the load's multi-cycle shadow rather than waiting behind it, as 5.1.01-Pipelining alone could not achieve.

WQ6. "Why must the RAT be updated dynamically rather than fixed at compile time?"

The mapping from architectural to physical registers changes every time an architectural register is written; only the running machine knows the current in-flight state, so the Register Alias Table is updated per-instruction at rename time.

Edge cases

EC1. "What happens when the reorder buffer is completely full?"

The front-end must stall — no new instruction can be dispatched until the head commits and frees a slot, so a long-latency load at the head can back-pressure and halt fetching.

EC2. "What if two ready instructions want the same execution port in the same cycle?"

They contend and only one issues; the other waits (still ready) for the next cycle, which is why execution width is one of the three IPC-limiting factors.

EC3. "What happens to a store's result between execution and commit?"

It sits in a store buffer and is not written to cache/memory until commit, so a mispredicted or faulting path never leaks its memory writes.

EC4. "What if every instruction in a block depends on the previous one (a pure chain)?"

OoOE gives no speedup — the critical-path limit dominates, each instruction waits on its predecessor, and a huge window and many ports are wasted.

EC5. "What if a branch prediction turns out wrong after dependent work already executed?"

All instructions fetched on the wrong path are flushed from the ROB and their physical registers reclaimed; architectural state rolls back to the branch, then correct-path fetch resumes.

EC6. "What happens to WAR/WAW hazards when the machine runs out of free physical registers?"

Renaming can no longer proceed, so the rename/dispatch stage stalls — the hazards themselves are still logically removable, but the physical resource to remove them is exhausted.

EC7. "What is the observable difference between in-order and out-of-order execution for a correct single-threaded program?"

None in the final architectural result — only timing (fewer stall cycles) differs; the values in registers and memory at each commit boundary are identical.

Recall One-line summary to lock in

OoOE reorders execution to hide latency but never reorders observable commit, so single-thread results are unchanged; every trap above comes from confusing internal (speculative, out-of-order) state with visible (committed, in-order) architectural state.