Search Knowledge

© 2026 LIBREUNI PROJECT

Computer Architecture/Performance and parallel hardware
Page 14 of 20

Superscalar and Out-of-Order Execution

Instruction-level parallelism, renaming, speculation, and retirement.

Lesson briefPerformance and parallel hardware · 9 h · 3 outcomes

Required knowledge

  • Programming in a systems language
  • Binary arithmetic and basic digital logic

Learning outcomes

  • Explain how issue width, renaming, reservation stations, load/store ordering, speculation, and retirement expose ILP.
  • Trace physical-register, reorder-buffer, and exception state through out-of-order completion and in-order commit.
  • Evaluate an OoO optimization by IPC, energy, recovery, and precise-state invariants.

Assessment target

Given an instruction window and dependencies, produce issue/retirement state and identify the first event that could violate precise exceptions or register liveness.

Scope boundary

  • Simultaneous Multithreading (SMT) resource partitioning (ROB, store queues) is treated in the Multicore module.
  • CISC micro-op fusion and loop stream detectors are omitted to focus on canonical RISC out-of-order pipelines.
  • Transistor-level CAM match line circuit physics are abstracted into logical tag broadcast matching.

An in-order scalar pipeline issues at most one instruction per cycle and waits when the next instruction cannot proceed. Modern high-performance cores attempt to exploit instruction-level parallelism (ILP): independent instructions can execute simultaneously, even when they appear sequentially in the program. A superscalar processor has multiple issue slots or functional pipelines; an out-of-order processor allows a ready younger instruction to execute while an older instruction waits for a cache miss or long-latency operation. The implementation must nevertheless preserve the ISA’s ordered architectural observations.

Limits of instruction-level parallelism

The dependence graph determines the parallelism available in a finite instruction window. Independent additions can execute concurrently; a chain r1=r2+r3; r4=r1+r5; r6=r4+r7 has a critical path of three additions even if the core has many ALUs. Memory aliases, branches, exceptions, and finite registers limit how far the processor can look ahead.

Superscalar width WW is an upper bound on issue per cycle, not a guarantee. If a workload has insufficient independent instructions, one functional unit is busy while others idle. The effective IPC is bounded by dependencies, front-end fetch/decode width, execution-unit availability, cache misses, and retirement bandwidth.

Worked dependency example. For A: r1=r2+r3, B: r4=r5+r6, and C: r7=r1+r4, A and B can execute in parallel on two adders. C waits for both. Define two-cycle latency to mean that an instruction issued at the start of cycle tt has a usable result at the start of t+2t+2 A and B issue at cycle 1, become ready at cycle 3, and C issues at cycle 3 with its result ready at cycle 5. A single-issue machine with a pipelined adder issues A at cycle 1 and B at cycle 2; C waits until cycle 4 and produces its result at cycle 6. Neither schedule includes fetch or retirement latency. Issue width reduces elapsed time here, but does not shorten the true dependence through C.

Renaming and physical registers

Architectural register names create false dependencies. In:

add r1, r2, r3
add r2, r4, r5

the second instruction writes r2 after the first reads it, a WAR anti-dependence. It is not a true flow of data. Register renaming maps each destination to a fresh physical register and records which physical register currently represents each architectural name. The first instruction reads the old physical r2; the second writes a new physical register. WAW hazards similarly disappear because distinct writes use distinct physical destinations.

Renaming does not remove RAW dependencies. If a later instruction reads the architectural register after a new mapping is installed, it receives the producer’s physical register and waits for its readiness. The rename map is speculative state: a branch checkpoint records enough mapping information to restore the pre-branch name map if prediction fails.

Physical registers need reclamation. When a new mapping replaces an old architectural mapping and no in-flight instruction can still read the old physical register, the old register can return to the free list. Reference tracking, retirement maps, or equivalent mechanisms prevent premature reuse. A physical-register leak eventually stalls dispatch even when execution units are idle.

Pause & Predict: Can Renaming Accelerate a Pure RAW Chain? Suppose you have an infinite supply of execution units and physical registers, and you run the following code:

add a0, a1, a2
add a0, a0, a3
add a0, a0, a4
add a0, a0, a5

Will register renaming allow these four instructions to execute concurrently? Commit your reasoning before opening the analysis below.

Show hintExpand

Recall the difference between true data dependencies (RAW) and false name dependencies (WAR, WAW). Which ones can renaming eliminate?

Reveal analysisExpand

Analysis: No! Not by a single cycle. Register renaming eliminates only name dependencies:

  • Write-After-Read (WAR / anti-dependence)
  • Write-After-Write (WAW / output dependence)

It does not eliminate Read-After-Write (RAW / true data dependence). Each instruction strictly consumes the mathematical value produced by its predecessor. Renaming will assign physical registers:

  • P1 = a1 + a2
  • P2 = P1 + a3 (must wait for P1 to be computed)
  • P3 = P2 + a4 (must wait for P2 to be computed)
  • P4 = P3 + a5 (must wait for P3 to be computed)

The critical path remains exactly 4 serial addition latencies. Only algorithmic reassociation (e.g. tree reduction (a1+a2)+(a3+a4)(a1+a2) + (a3+a4) or compiler loop unrolling can expose true ILP from serialized chains.

Execute early, retire in order

A younger independent instruction finishes before an older cache-missing load. A branch older than both is later found mispredicted.

Evaluate which hardware structures and mechanisms preserve precise architectural state in this scenario:

Reservation stations and wakeup

Out-of-order cores hold decoded instructions in issue queues or reservation stations. Each entry stores the operation, source physical-register identifiers, readiness bits or values, destination, and exception/speculation metadata. When a producer completes, a wakeup mechanism marks dependent operands ready. A select mechanism chooses ready instructions for available functional units.

Worked trace: tag wakeup and select. Suppose two reservation-station entries hold

RS1: fadd f3, f0, f4    sources (P10, P4)   ready bits (0, 1)
RS2: fsub f5, f1, f2    sources (P6, P8)    ready bits (1, 1)

and only one FP adder is free. The producer of P10 broadcasts at the end of cycle 3. At that broadcast, RS1 compares P10 against its outstanding source tags, sets the first ready bit, and becomes selectable for cycle 4. RS2 was already selectable; if both request the adder in cycle 4, the selector must choose by age or another policy, and the loser waits. In this timing model the broadcast at the end of cycle 3 cannot also drive an issue earlier in cycle 3. Other designs can combine or pipeline wakeup and select differently, trading latency against the delay of the compare-and-select path. The timing model, not the ISA, decides when a dependent can issue.

Wakeup and select are timing-critical because a wide machine compares many tags every cycle. A centralized issue queue is flexible but expensive; clustered or partitioned designs reduce wiring but can require operand movement between clusters. The architecture is not changed by these choices, but performance and power are.

Long-latency operations create pressure. A cache-miss load may occupy a queue entry and a physical destination while independent work proceeds. If the reorder buffer or load/store queue fills, dispatch eventually stops—a phenomenon called back-end or window pressure. Increasing the window can expose more ILP but raises energy, area, and recovery cost.

Reorder buffer and precise retirement

Execution completes out of order, but retirement commits architectural effects in program order. A reorder buffer (ROB) records program order, destination information, exception state, and completion. The head entry retires when its operation is complete and no older fault exists. Younger completed instructions wait.

This design provides precise exceptions. If instruction 10 faults, instructions 0–9 may retire, instruction 10 records the fault, and instructions 11 onward are discarded even if they executed internally. Stores often enter a store buffer and become globally visible only at retirement or under a carefully defined memory-ordering protocol. Register results can be kept in physical registers while the committed map changes at retirement.

Worked exception trace. Instruction A is an older load that faults; instruction B is a younger add that completes; instruction C is a younger store that completes. The ROB marks B and C done but cannot retire them because A is at the head and faulting. The machine discards B and C, leaves architectural registers and memory as though A had not committed, and enters the handler with A’s fault information. If C had written memory immediately at execute completion, precise exception semantics would be violated.

A ROB entry is allocated in program order at dispatch, before execution completes. Otherwise a younger fast instruction could appear older than a stalled load. The graph separates allocation from completion reporting and from the permission to retire.

Code
rectangle "Dispatch / rename" as D
rectangle "Issue queue" as Q
rectangle "Execution units" as E
rectangle "ROB: program-order entries" as B
rectangle "Retirement / committed map" as C
D --> Q : physical operands + ROB id
D --> B : allocate entry in order
Q --> E : issue when operands ready
E --> Q : wake dependents
E --> B : report done or fault by id
B --> C : only completed, nonfaulting head
note bottom of B
A fault at the head blocks
all younger retirement.
end note
Dispatch / renameIssue queueExecution unitsROB: program-order entriesRetirement / committed mapA fault at the head blocksall younger retirement.physical operands +ROB idallocate entry in orderissue when operandsreadywake dependentsreport done or fault byidonly completed,nonfaulting head

Architectural State Preservation Matrix

0 / 4 answered

Evaluate each statement regarding what an out-of-order superscalar processor must guarantee to software to preserve the sequential execution model:

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
Exceptions must be reported precisely so no younger instructions have modified architectural state when the handler runs.
2
The cycle latency and pipeline depth of all arithmetic functional units must be constant across instructions.
3
Internal issue queue dispatch and execution unit wakeups must strictly preserve original program order.
4
Register values and memory stores must be made architectural strictly in program order at retirement.

Load/store ordering and memory disambiguation

Registers expose explicit dependences, but memory addresses may be unknown until execution. A younger load and older store can execute out of order only if the core proves their addresses do not alias, or if it speculates and can recover when the guess is wrong. The load/store queue records program order, addresses, data, and permissions. Store-to-load forwarding lets a load obtain data from an older store that has not reached cache, provided the addresses and byte masks match.

Partial overlap is difficult. A 4-byte load may overlap two older stores with different byte ranges; forwarding must merge bytes or stall. An address predictor may speculate that a load does not alias an older store; a later conflict triggers replay of the load and its dependents. Memory consistency rules further restrict when stores become visible to other cores.

Worked example: byte-mask forwarding (little-endian). Two older stores are in the load/store queue:

# Assume x1 = 0x100.
S1: sw x5, 0(x1)     bytes 0x100..0x103 = A0 A1 A2 A3
S2: sw x6, 4(x1)     bytes 0x104..0x107 = B0 B1 B2 B3

Assume an implementation that permits these misaligned accesses and can forward bytes from multiple stores. A younger lh x7, 2(x1) reads bytes 0x102..0x103, so it can forward A2 A3 from S1 without waiting for S2. A younger lw x8, 2(x1) reads 0x102..0x105 and needs A2 A3 from S1 and B0 B1 from S2. If S2’s data has not arrived, the load cannot complete by forwarding from S1 alone: it must wait, or it must have speculated and be prepared to replay. A younger lw x9, 0(x1) is fully covered by S1 and can forward the whole word. The byte masks, not just the base addresses, determine whether forwarding is possible; an address match with a partial overlap is not enough.

Speculation and branch recovery

A branch predictor supplies a next PC before the branch resolves. The front end fetches and renames along that path. Each speculative instruction carries a branch-mask or checkpoint identifier. When the branch resolves correctly, the work may continue; when it mispredicts, the core restores the rename map, frees or invalidates younger ROB and issue entries, clears speculative stores, and redirects fetch.

Worked recovery trace. A branch B occupies ROB entry 20 and is predicted taken. The front end fetches and renames 24 younger instructions into ROB entries 21–44. When B resolves mispredicted, the core restores the rename map from B’s checkpoint, marks entries 21–44 invalid, clears any speculative stores from that range, and redirects fetch to the correct target. Instructions older than B are unaffected and may retire.

StateBefore resolutionAfter recovery
Rename mapincludes speculative mappings from 21–44restored to B’s checkpoint
ROB20–44 occupied21–44 squashed; 20 may retire when all older instructions have retired
Store bufferspeculative stores from 21–44those stores discarded
Fetch PCwrong-path targetcorrected target

The invariant is falsifiable: no instruction younger than B may retire or make a store globally visible after the misprediction is known. A machine that lets a wrong-path store drain before the squash violates precise state even if the register results are later discarded. The recovery cost is not just the 24 discarded entries; it includes the refill latency and the time to re-establish the front-end stream.

Recovery bandwidth matters. A machine that can dispatch eight instructions per cycle may need several cycles to clear a large wrong-path window. Predictor accuracy and branch resolution depth determine the average penalty. Speculation also consumes cache and predictor capacity, so wrong-path work can slow the correct path even before a flush.

Exceptions, interrupts, and replay

Out-of-order execution may discover exceptions before an instruction reaches the ROB head. The exception is recorded, but the machine delays architectural entry until older instructions retire. Some operations are restartable; others require suppressing duplicate effects. A speculative page-walk fault, for example, may be handled differently from an architectural load fault depending on the design.

Worked trace: replay is not an exception. An older store S is at ROB entry 9 and a younger load L is at entry 11. L executes before S’s address is known because the memory disambiguator predicts no alias. When S’s address resolves and matches L, the LSQ does not raise an architectural fault: it marks L and its dependents for replay. L re-executes after the store data is available, and the dependents re-execute from the replayed value. No handler runs, no sepc is written, and no architectural register or memory state is exposed for the wrong value.

A true page fault on L follows a different path: the fault is recorded in L’s ROB entry and delivered only when L reaches the head; sepc receives L’s PC, younger entries are squashed, and the handler may retry the load. An interrupt is external and is taken at a precise instruction boundary: older instructions retire, younger speculative work is discarded or held, and the saved PC identifies the next instruction to execute on return.

EventArchitectural fault?Saved PCRecovery
Memory-order violationnononereplay load and dependents
Load page faultyesfaulting load PChandler retries or terminates
Timer interruptno (asynchronous)next instruction to executereturn to saved PC

The common requirement is that no younger effect becomes visible before the event’s architectural boundary.

Interrupts are taken at a precise boundary chosen by the ISA. The implementation must ensure all older effects are committed and all younger effects are recoverable. Replay mechanisms for memory-order violations and cache misses must preserve the same visible instruction ordering. The more aggressively a core speculates, the more state it must retain to restore the architectural model.

Performance and energy trade-offs

Increasing width, window size, physical registers, and speculation can improve IPC on ILP-rich code. It can hurt on branchy, pointer-heavy, or synchronization-heavy code because the extra machinery consumes power and may lengthen critical wakeup/select paths. A high IPC can also be misleading if the code performs more instructions or stalls at memory.

Worked example: width, IPC, and energy per instruction. Compare two same-frequency cores at 3.0 GHz on a workload whose IPC rises from 2.0 to 2.3 when issue width increases from four to six:

CoreWidthIPCPowerTime per instructionEnergy per instructionThroughput per watt
A42.020 W0.167 ns3.33 nJ0.300×1090.300 \times 10^9 instructions/s/W
B62.326 W0.145 ns3.77 nJ0.265×1090.265 \times 10^9 instructions/s/W

Core B executes 15% more instructions per second, reducing time per instruction by about 13%, but uses about 13% more energy per instruction and delivers about 12% fewer instructions per second per watt. The correct choice depends on the objective: B is preferable in a latency- or throughput-constrained system with power headroom, while A is preferable when the system is power- or thermally limited. The table also shows why an IPC claim alone is insufficient: B’s higher IPC is real, but it does not by itself establish a better design point. If B’s frequency also rose to 3.5 GHz, its time and energy per instruction would improve, but only if the power estimate still holds after the voltage increase; a 26 W budget at 3.0 GHz cannot be assumed at 3.5 GHz.

The optimal width depends on workload mix. A wide core may waste energy on a serial dependency chain; a modest core with a better cache or memory system may finish sooner. Architectural evaluation therefore uses traces, counters, and representative suites, not a single synthetic instruction stream.

Verification strategy

An out-of-order implementation is verified against a reference ISA model at retirement. Random instruction streams stress renaming and commit; constrained tests stress dependencies, exceptions, mispredictions, overlapping memory accesses, and full queues. Assertions should ensure that no instruction retires before all older instructions, no physical register is reused while live, and no younger store becomes visible before the allowed commit point.

Formal refinement abstracts away issue order. It relates each microarchitectural state to a sequence of retired architectural states. Internal execution can be arbitrary when it produces no prohibited external effect; retirement must correspond to the next reference transition. This proof style explains why caches, predictors, and speculative values need not appear in the ISA.

Worked Trace: Cycle-by-Cycle Tomasulo Renaming & Out-of-Order Execution

Consider four floating-point instructions dispatched in program order on a 2-way superscalar out-of-order processor:

I1: fld    f0, 0(x1)        # Load: 2 execution cycles (address gen + cache hit)
I2: fmul.d f4, f0, f2        # Multiply: 4 execution cycles (RAW on f0 from I1)
I3: fsub.d f2, f6, f8        # Subtract: 1 execution cycle (WAR on f2 with I2)
I4: fadd.d f6, f4, f2        # Add: 1 execution cycle (RAW on f4 from I2 and f2 from I3)

Suppose the initial map is f0→P0f0\to P_0 f2→P2f2\to P_2 f4→P4f4\to P_4 f6→P6f6\to P_6 f8→P8f8\to P_8 with fresh registers P10,P12,P14,P16P_{10},P_{12},P_{14},P_{16} Define one timing model: at most two instructions dispatch in program order per cycle; execution starts no earlier than the cycle after dispatch; a result broadcasts at the end of its last execution cycle and is usable starting in the next cycle. Separate result paths permit two broadcasts in a cycle. At most two completed ROB entries retire in order per cycle, starting the cycle after broadcast. All input registers and the load’s address are ready initially; the load hits the cache.

InstructionDispatch: destination and sourcesExecutionBroadcastRetirement
I1 fld f0cycle 1: P10P_{10} address readycycles 2–3end of 3cycle 4
I2 fmul f4cycle 1: P12←P10,P2P_{12}\leftarrow P_{10},P_2cycles 4–7end of 7cycle 8
I3 fsub f2cycle 2: P14←P6,P8P_{14}\leftarrow P_6,P_8cycle 3end of 3cycle 8
I4 fadd f6cycle 2: P16←P12,P14P_{16}\leftarrow P_{12},P_{14}cycle 8end of 8cycle 9

At the end of cycle 3, I1 and I3 have broadcast. I2’s reservation station now has both operands; I4 has P14P_{14} but still waits for P12P_{12} I3 can finish first because I2 captured the old P2P_2 at dispatch; I3 writes the distinct P14P_{14} and cannot overwrite I2’s source. The true dependence from I2 to I4 remains: I4 cannot execute until the cycle after I2 broadcasts.

End of cycleROB in program order, after retirementReservation-station state
2I1 executing; I2 waiting; I3 and I4 dispatchedI2 waits for P10P_{10} I4 waits for P12,P14P_{12},P_{14}
3I1 done; I2 waiting; I3 done; I4 waitingI2 ready; I4 waits for P12P_{12}
4I1 retired; I2 executing; I3 done; I4 waitingI4 still waits for P12P_{12}
7I2 done; I3 done; I4 waitingI4 becomes ready after the broadcast
8I2 and I3 retired; I4 doneI4 has broadcast but cannot retire until cycle 9
9emptyno waiting instruction

I3 completes before I2 but cannot retire before it. A different issue width, broadcast bandwidth, cache latency, or retirement policy changes the cycle numbers, not the dependencies or the in-order-retirement requirement.

Counterexample & Failure Mode: Memory Disambiguation Violation (Speculative Load Bypass Hazard)

Unlike registers where dependencies are explicitly encoded in instruction bitfields, memory addresses are computed dynamically at runtime.

Consider the following program sequence:

I1: sw  x5, 0(x1)     # Store word: the load that produces x1 is still waiting on a cache miss
I2: lw  x6, 0(x2)     # Load word: address x2 is known immediately
I3: add x7, x6, x8    # Dependent consumer
  1. Speculative Execution Decision: Because the load producing x1 is stalled on a cache miss, an aggressive memory disambiguator speculates that x1 != x2 (no memory aliasing). The processor executes the load I2 immediately out-of-order and feeds x6 to I3.

  2. The Hazard Manifestation: Five cycles later, the load’s data arrives from L2 cache and writes x1; the hardware then evaluates 0(x1). Crucially, x1 == x2!

    • I1 was supposed to store the new value into memory location 0(x1).
    • I2 speculatively read the stale value prior to I1’s write!
    • I3 and all downstream instructions computed with corrupt, non-architectural data.
  3. Required Microarchitectural Recovery: If the Load-Store Queue (LSQ) fails to detect this address collision when I1 resolves, a silent data corruption bug occurs. A correct out-of-order core must snoop the store address against all younger speculative loads in the LSQ. Upon collision detection, it marks I2 and its dependents for replay; if they have already executed, it squashes and re-executes them after I1’s data is available. The store I1 itself is older and remains; recovery does not roll architectural state back to before I1.

Section Exercises

Deep Practice

Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.

Exercise 4.2.1: Register Renaming for Dependency Resolution

Constructionapplication

Rename an instruction sequence containing RAW, WAR, and WAW dependencies and draw the resulting physical-register mappings.

HintExpand

Assign fresh physical registers to eliminate false WAR and WAW naming hazards while preserving RAW chains.

Worked solutionExpand

Allocate fresh physical destinations for every write, while each read uses the mapping visible at dispatch. WAR and WAW disappear; a consumer still waits for the physical register produced by its true source instruction.

Exercise 4.2.2: Superscalar Dual-Issue Instruction Scheduling

Verificationapplication

Schedule four instructions on two ALUs with one three-cycle multiply and one dependent consumer. State issue, completion, and retirement cycles.

HintExpand

Match independent instructions with complementary functional unit requirements in the same issue cycle.

Worked solutionExpand

The multiply can issue alongside an independent add if units and operands are ready. Its consumer cannot issue until three-cycle completion. Retirement remains in program order even if the independent add finishes first.

Exercise 4.2.3: Memory Disambiguation and Store-to-Load Forwarding

Descriptiontransfer

Explain why an older unresolved store can prevent a younger load from executing even when the load’s register operands are ready.

HintExpand

Explain why unknown older store addresses force younger loads to wait or verify against store queues.

Worked solutionExpand

The store address may equal the load address. Executing the load first could read an older value and violate program order. The queue can prove nonaliasing, forward from the store, or wait and replay if speculation fails.

Exercise 4.2.4: Reorder Buffer Precise Exception Handling

Descriptiontransfer

Trace ROB state for an exception at the head with two younger completed instructions.

HintExpand

Trace instruction retirement at the ROB head to ensure exceptions take effect at exact architectural boundaries.

Worked solutionExpand

Older instructions before the head retire; the faulting head records cause; younger completed entries do not retire and are discarded. Architectural register and memory state contains no younger effects.

Exercise 4.2.5: Branch Misprediction Impact on Out-of-Order IPC

Generalisationtransfer

Derive the expected IPC effect of a branch frequency, prediction accuracy, and recovery cost.

HintExpand

Calculate IPC degradation from branch flush recovery when speculative pipelines retire wrong-path work.

Worked solutionExpand

Branch cost is frequency times misprediction probability times penalty. IPC or CPI must then be combined with base issue width and clock period; a lower CPI does not automatically mean lower wall-clock time.

Exercise 4.2.6: Speculative Checkpointing and Architectural Restore

Descriptionsynthesis

Identify the state that must be checkpointed for branch recovery.

HintExpand

Identify the rename tables and register allocation states that must be restored on branch mispredictions.

Worked solutionExpand

Save the rename map or a recoverable checkpoint, the ROB boundary/branch mask, speculative store state, and fetch PC/target state. Predictor updates may use a separate policy but cannot allow wrong-path architectural effects.

Exercise 4.2.7: Physical Register Free-List Management Invariants

Formalisationsynthesis

Give three assertions that would catch premature physical-register reuse.

HintExpand

Assert that physical registers are released to the free list only when younger overwriting instructions retire.

Worked solutionExpand

Assert that a physical register is allocated only when free, not allocated while referenced by any in-flight source, and not returned to the free list until retirement has removed every architectural and speculative reference.

References & Further Reading

  • Hennessy, J. L., & Patterson, D. A. (2019). Computer Architecture: A Quantitative Approach (6th ed.), Chapter 3 (“Instruction-Level Parallelism and Its Exploitation”). Morgan Kaufmann.
  • Tomasulo, R. M. (1967). An efficient algorithm for exploiting multiple arithmetic units. IBM Journal of Research and Development, 11(1), 25-33.
  • Yeager, K. C. (1996). The MIPS R10000 superscalar microprocessor. IEEE Micro, 16(2), 28-40.