Why an In-Order Pipeline Stalls and What an Instruction Window Buys

A five-stage scalar pipeline with forwarding executes one instruction per cycle in steady state, and programmers are often surprised to learn that real processors on the same binaries achieve well under half of that. The gap is not the pipeline depth. It is that the pipeline advances a program counter, and a program counter cannot advance past an instruction whose operands are not ready.

The stall is a property of the issue order

Consider a chain of dependent arithmetic. If an integer multiply takes three cycles and the next instruction adds its result, an in-order machine must hold the add in the decode stage for two cycles while the multiply drains. Nothing else can occupy those cycles: the add is at the head of the queue and the queue only moves forward. Three cycles of multiply latency produce two cycles of total pipeline idle, and a program that is nothing but dependent multiplies runs at one third of peak.

Real programs are worse than a chain. A load that misses the L1 data cache may take tens of cycles; a miss into DRAM costs a few hundred. An in-order machine that reaches a dependant of that load stops feeding its execution units entirely. On a four-wide superscalar that is four lost issue slots per stalled cycle. The cost of a stall is proportional to the machine width, which is exactly the quantity superscalar designs exist to increase, so wide in-order designs are the most sensitive to it.

The classical taxonomy separates three hazard classes: structural (two instructions want the same hardware in the same cycle), data (an instruction needs a value another has not produced), and control (a branch has not resolved). Forwarding removes most data hazards in the sense that the value need not travel through a register file, but it does not remove the latency between producer and consumer. Structural hazards are a function of port count and are solved by replication or banking. Control hazards are handled by prediction, which is a separate mechanism and a separate problem.

What remains after forwarding, prediction, and replication is the latency itself, plus the serialization: the consumer cannot pass the producer.

Static reordering and its ceiling

The obvious fix is to let the compiler reorder. Schedules can interleave independent instructions so that a consumer of a long-latency operation is separated from its producer by enough unrelated work to cover the latency. This is what software pipelining and list scheduling do, and it works well on loops with regular, statically known trip counts.

It fails for three reasons. First, the required separation is a property of the machine, and the compiler must know it; a binary tuned for one implementation’s load latency is mistuned for another. Second, a basic block is small. Typical straight-line code between branches is a handful of instructions, and independent work from after a branch cannot be moved before it without speculating. Third, memory dependencies are not visible to the compiler. Two loads and a store whose addresses are unknown at compile time may or may not alias, and the compiler must assume the worst.

Speculative static scheduling, where the compiler hoists work above branches and the hardware squashes it on misprediction, addresses the second problem but not the first or third. It also puts the burden of recovery on every implementation of the ISA.

The instruction window as a latency buffer

The hardware alternative is to decouple fetch order from issue order. Decode instructions in program order into a buffer — the instruction window — and select for execution each cycle whichever buffered instructions have their operands ready. The window has two independent dimensions:

• Size in instructions. How far ahead of the oldest unexecuted instruction the machine may have looked. This bounds how much independent work can be found.
• Size in cycles. How long an instruction can remain in the window. This bounds how much latency can be hidden, ignoring supply.

If an instruction has, on average, α independent instructions following it before the next dependency chain begins, a window of W instructions can cover roughly α · W / width cycles of latency for a width-wide machine. This is the same Little’s law argument that sizes any queue: with an arrival rate of N instructions per cycle and a residence time of L cycles, the expected occupancy is N·L. A four-wide machine that must hide a 20-cycle load on one instruction in five needs about 4 × 20 / 5 = 16 instructions in flight on average; to tolerate misses with bursts, the window must be several times that.

Practical windows are far larger than the expected occupancy because occupancy is a mean and stalls cluster. Early out-of-order designs used windows of a few tens of instructions. Modern designs use hundreds.

The mechanism that makes this work is the reorder buffer, described in The Reorder Buffer and In-Order Retirement. The essential property is that window selection is a search over the ready set, not a walk down a queue, and the search can be performed by a priority encoder over per-entry ready bits rather than by a scheduler with global knowledge.

What the window does not fix

The window is not free, and the costs are the subject of the rest of this cluster.

Registers are limited. If independent instructions are only independent because they happen to write different architectural registers, the supply of registers caps the window size. A machine with 32 architectural registers cannot have 200 independent operations in flight without reusing names — hence register renaming, which converts the architectural namespace into a physical one an order of magnitude larger.

Issue selection is quadratic-ish in the naive formulation. Each cycle, every waiting instruction’s operands must be checked against every completing result. The standard fix is the wakeup-select loop described in Issue Queue Wakeup and Select, which trades a broadcast network for a comparator tree.

Precise exceptions survive only because retirement is in order, and the cost of keeping that property grows with window size, as Precise Exceptions from an Imprecise Machine explains.

And the window finds parallelism within a program’s dynamic instruction stream. If the stream contains few independent instructions — pointer chasing, a long reduction, a serial dependency chain — the window sits mostly empty and the machine degenerates to an in-order one with more bookkeeping.

Measuring the limit on an in-order machine

A compact way to see the effect is to model the issue stage of an in-order machine against a windowed one. The following simulation uses only the C standard library and a simple latency table; it counts lost issue slots for a program described as a list of dependencies.

#include <stdio.h>

/* Latency in cycles, and the index of the instruction it waits on (-1 none). */
struct insn { int latency; int dep; };

/* Issue up to `width` ready instructions per cycle, out of order, but only
   within `window` entries of the oldest unretired instruction. In-order issue
   is the special case window = width = 1. Idle cycles are counted. */
static int run(const struct insn *p, int n, int window, int width, int *idle)
{
    int issue_at[64], done_at[64], retired = 0, cycle = 0;
    for (int i = 0; i < n; i++) issue_at[i] = -1;
    *idle = 0;
    while (retired < n) {
        int issued = 0;
        for (int i = retired; i < n && issued < width; i++) {
            if (issue_at[i] >= 0) continue;
            if (i - retired >= window) break;
            if (p[i].dep >= 0 &&
                (issue_at[p[i].dep] < 0 || done_at[p[i].dep] > cycle)) continue;
            issue_at[i] = cycle;
            done_at[i] = cycle + p[i].latency;
            issued++;
        }
        if (issued == 0) (*idle)++;
        cycle++;
        while (retired < n && issue_at[retired] >= 0 && done_at[retired] <= cycle)
            retired++;
    }
    return cycle;
}

int main(void)
{
    struct insn chain[] = { { 3, -1 }, { 1, 0 }, { 3, 1 }, { 1, 2 } };
    int idle = 0, cycles;
    cycles = run(chain, 4, 1, 1, &idle);            /* in-order, one per cycle */
    printf("in-order: %d cycles, %d idle\n", cycles, idle);
    printf("windowed: %d cycles\n", run(chain, 4, 16, 4, &idle));
    return 0;
}

The point of the exercise is the shape of the answer, not the numbers: on a pure dependent chain the two machines behave identically, because there is nothing to find. The window only pays when the instruction stream contains independent work, which is a property of the program rather than of the microarchitecture. This is why the classic limits on instruction-level parallelism — the work by Wall on achievable ILP, and the branch and window studies that followed — are about how much parallelism real code exposes, not about how much a machine could exploit.

Why the window is the right abstraction

An alternative design could expose the parallelism to software: very long instruction word machines bundle independent operations into a single wide instruction and let the compiler do the scheduling. That approach was tried, and it works when the compiler can see the machine, but it ties binaries to machine parameters and does not help with dynamic memory latency — a cache miss is discovered at run time regardless of what the compiler believed.

The window’s advantage is that it can be enlarged or restructured without changing the instruction set. A wider window, a deeper reorder buffer, a larger physical register file: all are microarchitectural changes invisible to the binary. That flexibility is why every high-performance general-purpose core since the mid-1990s has been built around a window rather than around static bundles, and why the research questions in this area are about how to fill, feed, and retire from a window of a few hundred instructions without the bookkeeping dominating the energy and area budget.