Modern CPU Execution: Pipelines, Branch Prediction, and Out-of-Order Work

A processor appears to execute a program one instruction after another. Under that architectural contract, an addition reads defined registers, a load observes memory according to the machine’s memory model, and an exception points to a particular instruction. A modern high-performance core can implement that contract very differently. It overlaps many instructions, predicts control flow, renames registers, starts operations when their inputs become ready, and may execute a later instruction before an earlier one.

The central invariant is not that work happens in source order. It is that the machine commits architectural effects in an order that software is allowed to observe. Everything before commitment is provisional. That distinction explains both the speed and the limits of speculative, out-of-order execution: the core wins when it can look past temporary delays and find independent work, but it must discard that work when a prediction or dependency assumption proves wrong.

Separate the Architectural Contract from the Engine #

An instruction-set architecture, or ISA, defines the interface between software and the processor. It names instructions and registers, specifies visible results, and establishes rules for exceptions, privilege, and memory. Two processors can implement the same ISA with radically different pipelines and still run the same binary correctly.

The implementation beneath that interface is the microarchitecture. A small core might execute one instruction at a time. A wider core may fetch several instructions each cycle, translate them into simpler internal operations, and keep hundreds of those operations in flight. Terms such as pipeline depth, issue width, reorder-buffer capacity, execution ports, and branch-predictor design describe this internal machinery rather than the ISA.

This boundary prevents a common reasoning error. Assembly is not a cycle-by-cycle script. Adjacent instructions need not begin or finish in textual order, and one mnemonic may become multiple internal operations. Conversely, a high-level statement may compile into no instructions at all. The binary defines required behavior; the microarchitecture chooses a legal schedule.

Three kinds of order are therefore worth separating:

Out-of-order execution is not permission to violate data dependencies. If instruction B needs a value produced by A, B must wait. The opportunity lies in running unrelated C and D while A is delayed, then retiring all of them in the required order.

Turn an Instruction Stream into a Pipeline #

Pipelining divides instruction handling into stages so different instructions can occupy different stages simultaneously. A conceptual path includes fetching bytes, predicting the next address, decoding instructions, renaming registers, dispatching work, executing it, accessing memory, writing results, and retiring completed operations. Real designs combine or split these stages, but the model reveals where throughput and latency differ.

An operation with four cycles of latency does not necessarily limit the core to one operation every four cycles. If its execution unit is pipelined, it may accept new independent work each cycle even though each result appears later. Throughput describes how often new operations can start; latency describes how long one dependency must wait for its result. Dependency chains care about latency. Independent batches care more about throughput and available width.

A superscalar front end attempts to process several instructions per cycle. Width is useful only if every stage can sustain it and the program offers enough independent operations. Fetch can be limited by instruction-cache misses or difficult control flow. Decode can be limited by complex encodings. The back end can run out of queue entries, physical registers, execution ports, or room for outstanding memory operations. Retirement can stall behind one old, unfinished instruction even when many younger instructions have completed.

These constraints make a pipeline behave less like a single conveyor belt and more like a network of bounded queues. When a downstream structure fills, backpressure eventually stops dispatch and then fetch. A stall’s visible location may therefore be far from its original cause.

Preserve Dependencies with Register Renaming #

Some instruction relationships are true data dependencies. If r3 = r1 + r2 is followed by r5 = r3 * r4, the multiply cannot use the correct input until the addition produces r3. This read-after-write relationship is unavoidable unless the algorithm changes.

Other apparent dependencies arise only because the ISA exposes a small set of register names. Consider this sequence:

1: r1 = load [account]
2: r4 = r1 + 7
3: r1 = load [status]
4: r6 = r1 & 1

Instruction 3 writes the architectural name r1 after instruction 2 reads it. Naively, the later load appears unable to proceed until the earlier read finishes. Yet the two loads produce unrelated values. Register renaming maps each write to a fresh physical register: the first r1 might become p18, and the second might become p31. Instruction 2 reads p18; instruction 4 reads p31. The false name dependency disappears.

Renaming removes write-after-read and write-after-write hazards, but it cannot remove a true read-after-write dependency. After renaming, the scheduler can see the actual graph: each internal operation names the physical registers it consumes and produces. Operations wait in issue queues or reservation structures until their inputs and a suitable execution unit are available. A ready younger operation can then issue while an older one waits.

Memory introduces a harder form of dependency because addresses may not be known immediately. A load after an older store can proceed only if the core determines that their addresses do not overlap, or predicts that they do not and verifies later. Load and store queues track these operations, forward a stored value directly to a matching younger load when possible, and detect ordering mistakes. A bad memory-dependence prediction causes replay or pipeline recovery, which is another reminder that provisional speed requires a correctness check.

Speculate Across Branches, Then Recover #

A conditional branch chooses the next instruction address. Waiting until every branch resolves would frequently starve a deep, wide pipeline, so the front end predicts both whether the branch is taken and where execution should continue. It fetches and executes along that path before the condition is known.

Prediction uses past behavior and branch identity to infer future behavior. A target structure remembers likely destination addresses; a direction predictor learns patterns such as a loop branch being taken repeatedly and then not taken on exit. Indirect calls and returns need specialized target prediction because one instruction can lead to several destinations. The details vary by processor, but the contract is the same: predictions may guide provisional work, never final correctness.

When a prediction is right, useful operations are already moving through the back end. When it is wrong, all younger work from the incorrect path must be invalidated, the rename state restored, and fetching restarted at the correct address. The cost is not one universal number. It depends on where the branch resolves, how much wrong-path work occupied scarce structures, and whether the correct path’s instructions and data are ready.

Branchless code is therefore not automatically faster. Replacing an easy-to-predict branch with extra arithmetic can increase the dependency chain and consume execution bandwidth. Predication or conditional-move instructions may compute both alternatives even when one side is expensive. The right question is whether a particular branch is unpredictable in the representative workload and whether its replacement costs less on the target processors.

Speculation also has a security boundary. Wrong-path operations are prevented from retiring, but they can alter microarchitectural state such as caches and predictors. Software cannot normally read that state as an architectural result, yet timing can reveal it. Correct architectural rollback is therefore necessary but not sufficient for isolation; sensitive systems also need platform mitigations and disciplined bounds around untrusted indexing.

Retire Through the Reorder Buffer #

The reorder buffer, or an equivalent retirement structure, tracks operations in program order while they execute out of order. Each entry records whether an operation has completed, where its result belongs, and whether it encountered an exception or prediction failure. Results can be forwarded to dependent operations as soon as they are ready, but architectural commitment waits at the oldest end of the buffer.

Suppose an old load misses in cache while five later additions have already completed. Those additions cannot retire past the load. If the load eventually succeeds, retirement advances in order and the completed work becomes visible. If it instead raises a page fault, the core reports the fault at the old load and discards younger speculative state. Software sees a precise exception: all older instructions have taken effect, and no younger instruction has.

This mechanism creates a retirement bottleneck. A single long-latency operation at the head can block commitment, eventually filling the reorder buffer. Once no entries remain, the core cannot dispatch more work even if execution units are idle. Out-of-order machinery hides latency only within its finite window; it cannot look indefinitely far ahead.

The retirement rule also clarifies stores. A speculative store must not modify globally visible memory before the core knows it is on the correct path and free of an older exception. Store data and addresses are held in controlled structures until commitment, then enter the memory hierarchy according to ordering rules. A store being retired does not necessarily mean its bytes have reached main memory; retirement concerns architectural acceptance, while cache coherence and durability are separate layers.

Work Through an Illustrative Execution Window #

Consider this simplified sequence. Assume the first load takes several illustrative cycles because its data is not immediately available, additions use one arithmetic unit, and the branch prediction says r8 is nonzero.

1: r1 = load [A]
2: r2 = r1 + 1
3: r3 = r4 + r5
4: r6 = r3 * 2
5: if r8 == 0 jump slow_path
6: r9 = r10 + r11

After renaming, instruction 2 truly depends on 1, and 4 depends on 3. Instructions 3, 5, and 6 are independent of the missed load. A plausible schedule is:

The core has hidden part of the load delay by completing independent arithmetic. It has not made instruction 2 independent, and it has not retired instructions 3 through 6 ahead of instruction 1. If instruction 5 was mispredicted, instruction 6 is discarded even if its addition finished. If instruction 1 faults, every younger result is discarded and the exception is delivered at instruction 1.

Now change the sequence so every operation consumes the previous result. The execution window can hold many instructions, but almost none can issue early. This dependency-chain case explains why adding cores or widening a core does not guarantee lower latency for one serial computation. Instruction-level parallelism must exist in the program and be visible within the hardware window.

Classify Stalls and Their Tradeoffs #

Performance limitations often combine rather than appearing as one clean stall. A useful classification starts with the resource that prevents progress:

• Front-end starvation: instruction-cache or translation misses, difficult branch targets, or decode limits leave the back end without enough work.
• Dependency latency: a chain waits for arithmetic, a cache miss, address calculation, or another true producer.
• Execution pressure: too many ready operations need the same ports or functional units.
• Memory ordering pressure: loads and stores wait for addresses, forwarding, queue entries, or dependency checks.
• Window exhaustion: the reorder buffer, scheduler, physical registers, or load/store queues fill behind an old delay.
• Recovery work: branch or memory-order mispredictions discard operations that consumed time and bandwidth.

Optimizations can move pressure between categories. Unrolling a loop exposes more independent work but expands code and consumes registers. Vectorization reduces instruction count but may add setup, alignment handling, and frequency or port pressure on some processors. Prefetching can overlap memory latency but wastes bandwidth and cache capacity when access predictions are wrong. Reordering data can help cache behavior while increasing conversion cost elsewhere.

Source-level intuition is especially unreliable around compilers. A compiler may eliminate a branch, hoist a load, vectorize a loop, or decline an optimization because aliasing is possible. Managed runtimes add tiered compilation and deoptimization. The observed instruction stream is thus a product of source, inputs, compiler, runtime, and target ISA. Any claim about a microarchitectural bottleneck needs evidence at the level where it is made.

Measure Without Confusing Models for Evidence #

Begin with a user-visible symptom and a controlled workload. Record the binary, compiler options, runtime, processor model, operating-system policy, input distribution, thread placement, and warm-up state. Frequency scaling, migration between cores, interrupts, simultaneous multithreading, and background work can all change timing. A single elapsed duration cannot identify branch prediction or reorder-buffer pressure.

Use layers of evidence. Wall-clock distributions establish whether the problem matters. Sampling profiles locate hot instruction regions. Hardware performance counters can estimate events such as retired instructions, cycles, branch misses, cache misses, and stalled slots. Disassembly or annotated profiles connect those events to generated code. Counter names and semantics are processor-specific, so interpret them with the vendor documentation and the profiling tool’s multiplexing rules.

Useful ratios include instructions retired per cycle and branch misses per executed branch, but neither is a universal score. Low instructions per cycle may be expected for a dependency-bound algorithm. High instructions per cycle can accompany wasted work or poor end-to-end latency. Cache-miss counts need the access volume and miss level. Multiplexed counters may be scaled estimates rather than simultaneous observations.

A disciplined verification loop is:

1. State a falsifiable mechanism, such as an unpredictable branch limiting a particular loop.
2. Preserve a correctness oracle and representative input distribution.
3. Collect repeated baseline timings plus relevant counters on an otherwise controlled host.
4. Make one change that should alter the proposed mechanism.
5. Confirm both the predicted counter movement and the end-to-end timing effect.
6. Test other processors and edge-case inputs before making the optimization permanent.

For the worked sequence, a simulator or instruction-level tracing tool can verify dependency reasoning, but it does not prove production impact. For real code, compare outputs bit for bit or through domain invariants, randomize benchmark order, and retain raw samples. If a supposedly branch-focused change improves time while branch misses remain unchanged, the original explanation is incomplete even if the change is useful.

Modern CPU execution is best understood as bounded speculative scheduling around an ordered retirement contract. Pipelines overlap stages, renaming exposes true dependencies, prediction supplies a likely future, and the out-of-order back end searches a finite window for ready work. The reorder buffer makes those aggressive choices appear precise to software. Once that invariant is clear, stalls stop being mysterious pauses and become specific limits on dependencies, prediction, resources, or the amount of independent work the core can see.