Part V·Advanced ILP and Out-of-Order Execution·Chapter 49 of 66

Part VAdvanced ILP and Out-of-Order Execution

Limits of In-Order Execution

August 3, 2026·26 min read·advanced

The five-stage pipeline of Chapter 29 and the deeper in-order variants of Chapter 32 share a strict discipline. Instructions move through the pipeline in the order the program writes them. When an older instruction stalls, every younger instruction behind it stalls with it, even if their own operands are ready and their own functional units are idle. The pipeline’s throughput is pinned to whichever instruction happens to be at the front of the queue.

In Part IV the cache hierarchy was shown to deliver an effective memory-access time of a few cycles on the average hit but tens to hundreds of cycles on a miss. A load that misses in L1 spends roughly ten cycles waiting for the L2 response. A load that misses all the way to DRAM spends three hundred cycles or more. In an in-order pipeline, every one of those cycles is a cycle in which the entire pipeline behind the load is frozen. The independent arithmetic, the independent loads, the independent stores that the program also contains all sit idle, blocked by a single instruction that happens to be earliest in program order.

This chapter develops the quantitative argument for why the in-order discipline becomes the bottleneck once the cache miss rate, the multi-cycle functional-unit count, and the issue width exceed modest values. It revisits the load-use stall introduced in Chapter 30 and shows how the cost scales with miss penalty. It surveys the structural hazards that arise in superscalar in-order designs. It walks through three modern in-order cores (ARM Cortex-A53, SiFive S76, and the historical Intel Atom Bonnell) to show where each hits the diminishing-returns wall. It closes by framing out-of-order execution as the direct response to those limits, motivating the algorithms developed across the next four chapters.

01.The Single-Stall Multiplier

The in-order pipeline’s defining property is that one stalled instruction stalls every instruction behind it. To put a number on the cost, consider a five-stage pipeline running an instruction mix in which one instruction out of every twenty suffers an L1 miss that takes ten cycles to resolve. The miss rate at the load level is higher than one in twenty, because not every instruction is a load. A typical integer mix has around 25 percent loads and 10 percent stores, so a one-in-twenty overall miss rate corresponds to a one-in-five miss rate on loads. Modern L1 caches achieve miss rates below 5 percent on SPEC integer workloads, so the one-in-five figure used here is deliberately pessimistic, chosen to keep the stall mechanism visible in round numbers.

Without misses the pipeline runs at CPI 1.0. Each ten-cycle miss adds ten stall cycles to the pipeline. The miss contributes $\text{CPI}_{\text{miss}} \;=\; 0.05 \times 10 \;=\; 0.5$ to the average cycles per instruction. The effective CPI rises to 1.5. The pipeline’s effective throughput is therefore two-thirds of its peak rate, lost entirely because the in-order discipline cannot bypass the missing load.

Suppose now that the workload contains independent work that could profitably overlap with the miss. A typical SPECint trace contains five to ten instructions of independent work within twenty instructions of an L1 miss. None of that independent work can run in an in-order pipeline because the missing load sits in front of it. If those five-to-ten cycles of independent work could be issued during the miss, the effective CPI would fall back toward 1.0. The whole gap between 1.0 and 1.5 is the architect’s payoff for going out-of-order.

The argument generalizes beyond cache misses. Any operation whose latency exceeds the average issue interval imposes the same penalty. Integer multiply on a typical in-order core takes three to five cycles. Integer divide takes ten to forty cycles. Floating-point divide takes twenty to fifty. A non-pipelined divider in an in-order pipeline stalls every subsequent instruction for its entire latency, even when none of those instructions consume the quotient.

02.Load-Use Stalls Dominate

Chapter 30 introduced the load-use hazard and quantified the one-cycle bubble per back-to-back load-then-use pair on the five-stage pipeline. Compilers schedule around the hazard by separating the load from its consumer with an unrelated instruction. On classic RISC benchmarks the compiler succeeds roughly 70 to 80 percent of the time. The remaining 20 to 30 percent of load-use pairs hit the bubble.

The bubble grows when the load misses in the L1 cache. A hit costs one cycle in the original five-stage pipeline. A miss that resolves from the L2 cache costs roughly ten cycles. A miss that resolves from DRAM costs roughly three hundred cycles. In an in-order pipeline these are not bubbles, they are full pipeline stalls. The penalty scales linearly with the miss latency.

Consider the loop body

LW x1, 0(x10)
ADD x2, x1, x3
SW x2, 0(x11)
ADDI x10, x10, 4
ADDI x11, x11, 4
BNE x10, x12, loop

Six instructions. The load on line one produces x1, the add on line two consumes x1. If LW hits the L1 and the compiler has scheduled an instruction between the load and the add, the loop runs at CPI close to 1.0. If LW misses to the L2, the second instruction stalls for ten cycles. The store on line three needs x2 and would wait for the add in any case, but the remaining three instructions, which share no dependence with the missing load, stall behind the add as well.

The cost per miss is therefore not just the miss latency. It is the miss latency multiplied by the number of independent instructions that could have run in parallel but were trapped by the in-order discipline. In the loop above, three independent instructions sit in the queue, none of them able to make progress until the missing load returns.

Table 1. Load-use stall scaling across the cache hierarchy on a 5-stage in-order pipeline

Hit level	Latency (cycles)	Stall bubbles	Trapped independent insns
L1 hit, scheduled	1	0	—
L1 hit, unscheduled	1	1	0 to 1
L2 hit	10	9	4 to 8
L3 hit	35	34	15 to 30
DRAM	300	299	150 to 250

The third column counts the bubble cycles that the pipeline inserts in the worst case (the case in which the compiler could not find any unrelated instruction to fill the slot). The fourth column estimates the count of independent instructions that a wider, out-of-order machine could have issued during the wait. The product of cache miss rate, miss penalty, and the count in the fourth column is the upper bound on the speedup the architect can extract by going out-of-order.

03.Structural Hazards on Shared Functional Units

The single-issue five-stage pipeline has one ALU, one shifter, and one memory port. There is no structural hazard between two arithmetic instructions, because each one passes through its functional unit on its own cycle. Once the pipeline widens to issue two or more instructions per cycle, the picture changes.

A two-wide in-order pipeline (the canonical example is the ARM Cortex-A53) has two pipelines side by side, often called Pipe 0 and Pipe 1. Pipe 0 is symmetric and can execute any instruction. Pipe 1 is asymmetric and lacks the divider, the multiplier, or the load-store unit, depending on the implementation. When two instructions arrive at the dispatch stage and both need the resource that only Pipe 0 has, the second one stalls. The pipeline drops from issuing two instructions per cycle to issuing one. The throughput is halved for the duration of the structural conflict.

The table below estimates the rate at which structural hazards arise on a generic two-wide in-order design with asymmetric pipes. The numbers come from the SPEC CPU2017 integer mix as published in vendor disclosures. The share of multiplies, divides, and floating-point operations is small in absolute terms but enough to noticeably reduce the realized issue rate.

Table 2. Estimated structural-hazard rate on a 2-wide in-order design with one asymmetric pipe

Operation class	Fraction of instructions	Pipe-0 only
Integer ALU	0.42	no
Loads	0.25	no
Stores	0.10	no
Branches	0.15	no
Integer multiply	0.04	yes
Integer divide	0.005	yes
FP add/mul	0.03	yes

The Pipe-0-only fraction sums to about 7.5 percent. When two adjacent instructions in the dispatch queue both fall into this group, the second one stalls for one cycle. The probability is small but the cumulative cost over a long program is measurable. On SPEC integer the structural-hazard penalty on Cortex-A53 amounts to roughly 4 to 6 percent of total cycles. On SPEC floating-point, where the floating-point operations cluster, it rises to 8 to 12 percent.

Out-of-order execution sidesteps the structural problem by decoupling dispatch from issue. The dispatcher places instructions into reservation stations, the issue logic chooses which instructions in the stations have ready operands and free functional units, and the in-program-order constraint is lifted within the execution stage. A young multiply does not block a young add even if both ended up in the same dispatch window.

04.Superscalar In-Order in Practice

The ARM Cortex-A53, the SiFive S76, and the historical Intel Atom Bonnell illustrate the shape of the in-order superscalar curve. All three are two-wide. Each widens the fetch and dispatch path over a scalar design, adds duplicated functional units, and yet plateaus at an IPC well below its width. The gap between issue width and realized IPC is the unspent ILP that in-order execution leaves on the table.

That all three settled on two-wide is itself the point. Two is where the in-order superscalar market converged, because the third slot costs dispatch logic and a third set of functional units while returning very little on real code, for the reasons the structural-hazard section gave.

ARM Cortex-A53

The Cortex-A53 is the workhorse little core in many ARM big.LITTLE configurations. It is an in-order, dual-issue, eight-stage pipeline. The two pipes are asymmetric, with one of them hosting the multiplier and the divider. Branch prediction is a two-level adaptive predictor with a small branch target buffer. The L1 instruction and data caches are 32 KiB each.

Published Hot Chips disclosures place its SPEC CPU2006 integer score around 0.7 to 0.9 IPC depending on workload. The width allows two instructions per cycle, so the realized IPC is well below half of peak. Three measurable stall sources account for part of the gap.

Load-use stalls when the compiler cannot schedule into the load delay slot. Roughly 6 to 8 percent of cycles.
L1 miss penalties (about 9 cycles to L2) that block the entire pipeline. Roughly 8 to 12 percent of cycles.
Structural hazards when two adjacent instructions both need the asymmetric pipe. Roughly 4 to 6 percent of cycles.

Adding the three sources gives 18 to 26 percent of cycles lost to outright stalls, which is well short of the roughly 57 percent shortfall implied by a realized 0.85 IPC against a 2.0 peak. The rest of the gap is not stall at all. It is the far more common case in which the pipeline advances but issues only one instruction, because the next two instructions in program order depend on one another, or map to the same pipe, or sit on opposite sides of a taken branch. The Cortex-A53 is not slow in absolute terms (it powers billions of devices), but its peak-to-realized ratio is roughly 0.4. The same workload on a Cortex-A55 successor, which retains the in-order discipline but tightens load-use forwarding and adds a small structural queue, lifts realized IPC by about 15 percent. Going to the out-of-order Cortex-A78 lifts realized IPC by another factor of two on the same workloads, because the out-of-order issue window absorbs the L1 misses that froze the A53.

SiFive S76

The SiFive S76 is a dual-issue in-order RISC-V core targeted at high-performance embedded workloads. Its pipeline is eight stages, with a 32 KiB L1 instruction cache and a 32 KiB L1 data cache. The two pipes are asymmetric in the same way as the Cortex-A53’s, with loads, stores and the multiplier confined to one of them.

The published SPEC CPU2006 IPC for the S76 sits around 1.1 to 1.3. The width permits two instructions per cycle, so the realized fraction is 0.55 to 0.65. The dominant loss is the same load-use and L1-miss combination as on the Cortex-A53.

The comparison with the Cortex-A53 is the useful one, because the two cores have the same width and the same pipeline depth and still differ by roughly 0.4 IPC. None of that gap comes from issue width. It comes from the branch predictor, the memory system, and how early the pipeline resolves a load-use dependence. At a fixed width, those are the levers that remain, and they are the levers an in-order design runs out of first.

Intel Atom Bonnell

The original Intel Atom (codename Bonnell, 2008) is the canonical example of an x86 in-order superscalar that hit the wall hard. It was a two-wide, sixteen-stage in-order pipeline targeting low-power netbook and mobile workloads. The pipeline length came from the x86 decode complexity rather than from deeper integer or memory work. Branch resolution sat at stage 13, so each misprediction cost twelve cycles.

Bonnell’s SPECint score per gigahertz came in around 0.7, roughly half that of the contemporary out-of-order Core 2 at 1.4 to 1.6 per gigahertz. The gap was not a clock-frequency gap, both ran in the 1.6 to 2.0 GHz range. The gap was almost entirely the in-order discipline failing to overlap memory latency. Intel’s response was Silvermont (2013), the first out-of-order Atom. Silvermont preserved the low-power target but moved to out-of-order execution with a 32-entry reorder buffer. Realized IPC on SPECint roughly doubled at the same clock, because the out-of-order window finally let the core run during L1 misses.

05.Amdahl on Instruction-Level Parallelism

Chapter 2 introduced Amdahl’s law as the upper bound on the speedup any optimization can achieve. The same law applies to instruction-level parallelism. Let $f$ be the fraction of dynamic instructions that can in principle run in parallel, and let $w$ be the issue width of the out-of-order machine. The speedup over a single-issue baseline is bounded by

If $f = 0.5$ (half of the program is serial, half is parallel) and $w = 4$ , the speedup is $1 / (0.5 + 0.125) = 1.6$ . Widening to $w = 8$ gives $1 / (0.5 + 0.0625) = 1.78$ . Widening to $w = \infty$ gives $1 / 0.5 = 2.0$ . Doubling the issue width from four to eight buys 0.18 of additional speedup. Going all the way to infinite width buys only another 0.22. The remaining serial 50 percent caps the speedup at 2.

The in-order machine’s parallel fraction $f$ is lower than the out-of-order machine’s, because the in-order discipline artificially serializes instructions that are independent in dataflow but trapped behind a stall. Measured ILP windows on SPEC integer hover around $f = 0.7$ to $0.8$ for the best compilers and aggressive scheduling. The out-of-order window recovers an additional $0.1$ to $0.2$ of $f$ by tolerating cache misses. Even with that recovery, the program’s serial critical path through true RAW dependences imposes a ceiling.

06.Why Compilers Do Not Solve the Problem

A natural counterargument is that a sufficiently aggressive compiler could schedule around every stall. The compiler sees the entire program statically, knows the latency of each operation, and can rearrange independent instructions to fill delay slots. The early MIPS R-series CPUs leaned heavily on this argument and exposed the branch delay slot and the load delay slot directly in the ISA.

The compiler’s argument fails for three reasons that are structural rather than incidental.

First, the cache miss latency is not a property of the instruction, it is a property of the memory access pattern. The compiler cannot know in general whether a load will hit or miss. Profile-guided optimization can predict it for the training data set but not for arbitrary inputs. A load that hits 99 percent of the time on the training data may miss 50 percent of the time on a customer’s actual workload, and the compiler’s schedule for the hit case turns into a stall storm on the miss case.

Second, the branch direction is dynamic. The compiler can arrange code so that the predicted-taken side is the fast path, but the actual branch outcome depends on data values that the compiler cannot see. A mispredicted branch in an in-order pipeline costs the depth-of-resolution number of cycles regardless of compiler scheduling.

Third, the compiler’s scheduling window is bounded by the basic-block boundary in many cases. Software pipelining and trace scheduling extend the window across basic blocks at the cost of code bloat and dependence-tracking complexity. The compiler can in principle expand the window arbitrarily wide, but the bookkeeping grows quadratically and the schedule becomes brittle under input variation. Modern compilers typically schedule across at most a few hundred instructions. The out-of-order machine’s window of two hundred to six hundred in-flight instructions is comparable in size, but dynamic, which lets it adapt to input variation.

07.The Motivation for Out-of-Order Execution

Pulling the threads together, the in-order pipeline hits a hard ceiling because three independent forces conspire against it. Cache misses freeze the pipeline for tens to hundreds of cycles. Long-latency arithmetic units block all subsequent work. The asymmetric functional-unit problem reduces the realized issue rate in superscalar designs. Compilers help but cannot eliminate any of the three.

The out-of-order machine attacks the first two forces directly by issuing instructions in dataflow order. A load that misses in the L1 cache no longer blocks the pipeline. The hardware finds independent instructions further down the program and issues them while the miss resolves. The third force is attacked structurally by replicating functional units and letting the issue logic match each ready instruction to the right unit.

The remaining chapters of Part V build the out-of-order machine piece by piece. Chapter 50 presents Tomasulo’s algorithm, the 1967 IBM design that introduced reservation stations and the common data bus and that remains the conceptual backbone of every modern out-of-order core. Chapter 51 develops register renaming, the technique that decouples the architectural register namespace from the physical register file and eliminates WAR and WAW hazards. Chapter 52 introduces the reorder buffer, the hardware structure that maintains in-order retirement even when execution is out-of-order, and that delivers precise exceptions in the face of arbitrary speculation. Chapter 53 develops the issue queue, the scheduler that picks ready instructions out of the in-flight window, and surveys the wakeup-select critical path that dominates the design.

Subsequent chapters in Part V handle branch prediction at scale, speculative execution and recovery, memory ordering in out-of-order pipelines, and the modern microarchitectures that combine all of these techniques. The unifying thread is that every mechanism in Part V exists to lift one of the three in-order ceilings established in this chapter.

08.Worked Examples

Example: The cost of trapped independent work

A program contains a chain of independent instructions of average length 6 that runs between successive L2 misses. Each L2 miss costs 35 cycles. The L2 miss rate per instruction is 0.5 percent. On an in-order pipeline, what fraction of the miss latency is wasted on instructions that could in principle have run during the miss?

Solution. During each 35-cycle stall, 6 independent instructions sit in the queue. At one instruction per cycle peak, those 6 instructions would consume 6 cycles. The wasted fraction is $6 / 35 \approx 0.17$ . The remaining 29 cycles are genuinely unavoidable wait. The 17 percent is what an out-of-order window of depth at least 7 could recover.

Across the program, the L2 misses cost $0.005 \times 35 = 0.175$ stall cycles per instruction. Recovering 17 percent of those costs gives $0.175 \times 0.17 \approx 0.030$ cycles per instruction back, or about 3 percent of CPI on a baseline of 1.0. The benefit grows linearly with the average length of the trapped independent chain.

Example: Amdahl bound on a 4-wide machine

A program has parallel fraction $f = 0.75$ . Compute the speedup achievable over a 1-wide baseline at $w = 2, 4, 8, 16, \infty$ .

Solution. Apply the equation above.

$w$	$S(w)$
2	$1 / (0.25 + 0.375) = 1.60$
4	$1 / (0.25 + 0.1875) = 2.29$
8	$1 / (0.25 + 0.09375) = 2.91$
16	$1 / (0.25 + 0.046875) = 3.37$
$\infty$	$1 / 0.25 = 4.00$

The diminishing return is sharp. Going from 4-wide to 8-wide buys 27 percent. Going from 8-wide to 16-wide buys 16 percent. The hard ceiling at 4.0 reflects the 25 percent of the program that remains serial regardless of width.

Example: Structural hazard rate on 2-wide design

On a 2-wide in-order design, 8 percent of instructions can only run on Pipe 0. Two adjacent instructions in the dispatch queue both want Pipe 0 if both fall in that group. Assuming independence, compute the probability that any given dispatch slot suffers a structural hazard.

Solution. The probability that both adjacent instructions are Pipe-0-only is $0.08 \times 0.08 = 0.0064$ . The probability that any single dispatch cycle has the hazard is roughly twice that, since the conflict can occur in either of the two adjacent slots, so about 1.3 percent of dispatch cycles. Each such cycle costs one bubble. The CPI penalty is about 0.013, or 1.3 percent. Smaller than the load-use and miss penalties but not negligible.

Example: In-order vs out-of-order on a single load

A load that misses in the L1 cache resolves from the L2 in 10 cycles. Eight instructions following the load are independent of its result. Compute the CPI cost of the miss on (a) an in-order pipeline, (b) an out-of-order pipeline with issue width 2 and a reorder buffer of 16 entries.

Solution. (a) The in-order pipeline stalls for 10 cycles. CPI cost is 10 cycles divided over the 9 instructions in the affected window, or about 1.1 extra cycles per instruction during the event. The 8 independent instructions sit idle.

(b) The out-of-order pipeline issues the 8 independent instructions at peak rate (2 per cycle, so 4 cycles to complete them). After 4 cycles, the pipeline runs out of independent work and stalls for the remaining 6 cycles of the miss. CPI cost is roughly 6 cycles over 9 instructions, or 0.67 cycles per instruction. The out-of-order machine recovered 4 of the 10 stall cycles, a 40 percent reduction of the miss penalty.

09.Exercises

Exercises

Effective CPI under cache misses. A 5-stage in-order pipeline runs a workload with 28 percent loads. The L1 data-cache miss rate on loads is 3 percent. The L1 miss penalty to the L2 is 12 cycles. The L2 miss rate on L1 misses is 25 percent, and the L2 miss penalty to DRAM is 280 cycles. Compute the effective CPI on a baseline of 1.0.
Amdahl bound at varying parallel fraction. Plot $S(w)$ for $f = 0.5, 0.7, 0.9, 0.95$ at $w = 2, 4, 8, 16$ . At which combination does going from $w = 8$ to $w = 16$ buy less than 5 percent additional speedup?
Structural hazards at higher width. A 4-wide in-order design has one Pipe with the divider and the floating-point multiplier. Five percent of instructions need that pipe. Estimate the probability that a 4-instruction dispatch window contains at least two instructions wanting that pipe.
Compiler scheduling success rate. A compiler succeeds in filling the load-delay slot 75 percent of the time. The remaining 25 percent of load-use pairs incur a 1-cycle bubble on the 5-stage pipeline. Loads are 25 percent of instructions. Of those, half are immediately followed by a dependent use. Compute the CPI contribution of unfilled load-use slots.
Critical-path length. A SPEC integer trace has a critical-path length of 150 instructions through a basic block of 800 instructions. The remaining 650 instructions are independent of the critical path. What is the upper bound on speedup with infinite issue width? With width 8?
Cortex-A53 IPC analysis. The published Cortex-A53 SPECint score is 0.85 IPC on a 2-wide machine. The peak IPC is 2.0. Using the stall percentages given in the chapter, work out how much of the gap of 1.15 the three enumerated stall sources (load-use, miss-induced stall, structural hazard) account for, and how much is left over for cycles in which the core issues only one instruction. What would a compiler scheduler that eliminates half of load-use stalls deliver?
Long-latency divide. An integer divide takes 24 cycles and is not pipelined. Each divide stalls every subsequent instruction in an in-order pipeline. Divides are 0.5 percent of instructions. The average number of independent instructions trapped behind a divide is 18. Compute the CPI cost on (a) in-order, (b) out-of-order with sufficient window.
Atom Bonnell case study. The Bonnell SPECint score was 0.7 per GHz. Silvermont, the out-of-order successor, scored 1.4 per GHz at the same clock. The two designs share the same ISA, similar L1 caches, and similar fetch width. Identify the dominant source of the 2x gap and write 3 sentences explaining why out-of-order recovered that gap.
Asymmetric pipe penalty. A 3-wide in-order machine has Pipe 0 for loads and stores, Pipe 1 for branches and multiplies, and Pipe 2 for integer ALU only. On a workload with 25 percent loads, 10 percent stores, 15 percent branches, 5 percent multiplies, and 45 percent ALU, what fraction of triples in the dispatch queue have no valid mapping?
Critical-path sensitivity. If a compiler shortens a program’s critical-path length from 150 to 100 by aggressive instruction selection, by what factor does the upper bound on speedup at infinite issue width improve?
Cache-miss overlap. A workload has L1-miss rate 4 percent and L2 hit latency 10 cycles. The out-of-order machine has a reorder buffer of 32 entries and issue width 2. Independent work behind each miss averages 12 instructions. Compute the miss-induced CPI on (a) in-order, (b) out-of-order.
Multiple outstanding misses. The L1 cache supports up to 4 outstanding misses (4 MSHRs). The L2 latency is 12 cycles. The compiler emits 4 independent loads that all miss. On an in-order pipeline, what is the total stall time? On an out-of-order pipeline with 4 MSHRs, what is the total stall time?
Branch misprediction in-order vs out-of-order. A 12-stage in-order pipeline resolves branches at stage 9. A 12-stage out-of-order pipeline also resolves branches at stage 9 but lets independent instructions issue during the misprediction window. Branch misprediction rate is 5 percent and branches are 15 percent of instructions. Compute the CPI penalty for both designs.
Frequency vs IPC tradeoff. Design A: 2-wide in-order at 2.5 GHz, IPC 0.9. Design B: 4-wide out-of-order at 2.0 GHz, IPC 2.4. Which has higher SPEC throughput? At what clock would Design A match Design B’s throughput?
Argument for in-order in the embedded space. In one paragraph, summarize why in-order designs remain dominant for microcontrollers, real-time controllers, and low-power embedded cores even though out-of-order delivers much higher SPEC performance. What workload properties favor in-order?

Book mode