Sizing the Window: Why More Entries Stop Paying

Window size is the headline number of an out-of-order core, quoted in specifications and compared between generations. It is also the design parameter whose marginal value falls fastest. Understanding why requires separating three constraints that a single number conceals: how much work the window can hold, how much of that work is actually ready, and what the machine pays for every entry it examines.

The occupancy equation

Model the window as a queue. Instructions enter at rate N per cycle (limited by fetch and decode) and stay until retirement. If a machine could retire instantly and nothing stalled, the occupancy would be the pipeline depth of the execution stage itself. The interesting case is when issue stalls on operand latency: an instruction that waits L cycles for a load occupies an entry for L cycles without doing anything, and the useful work in the window is exactly the work that could be issued while it waits.

The standard figure of merit is IPC as a function of window size, which typically rises quickly for the first few dozen entries, then flattens into a knee, then barely moves. The flattening has three distinct causes, and they are often confused.

The parallelism limit. The program may not contain enough independent instructions to fill a bigger window. Wall’s studies of achievable instruction-level parallelism made this argument empirically: even with perfect branch prediction, unlimited registers, and arbitrarily large windows, the available parallelism in general-purpose integer code saturates. The exact ceiling is workload-dependent, but the shape — a plateau reached within a few hundred instructions ahead — recurs.

The occupancy limit. Even when independent work exists further ahead, it can only be reached if the instructions between it and the stalled instruction are themselves processable. A single long-latency instruction does not block the window from looking past it; a serial chain of them does. Chain length is the binding constraint for latency-tolerance, not window size per se. Each link of a serial chain occupies an entry from rename until its result is ready, so a window of W entries holds at most W links of any one chain. Doubling the window doubles the chain depth that fits — a linear return, unlike the logarithmic return from filling with parallel work.

The bookkeeping limit. Issue selection cost, rename bandwidth, and retirement bandwidth all grow with the window, and past some size the added entries cause more contention than they resolve.

Why the plateau is a plateau

The clean argument is statistical. Suppose instructions have an average latency L and that the probability an instruction is independent of everything in the previous k instructions decays with k. Let P(k) be the probability that an instruction can issue while the previous k are still in flight. The expected number of issuable instructions in a window of size W is

$$S(W) = \sum_{k=0}^{W-1} P(k)$$

If P(k) decays geometrically with ratio r < 1, then S(W) converges to 1 / (1 - r) as W grows. Doubling the window adds S(2W) - S(W) ≈ r^W, which becomes negligible while the cost of the window grows linearly. A design decision made at the knee is therefore not a compromise; it is the point where the marginal return has genuinely gone to zero for the machine’s target workloads.

Real programs are not geometric, and some codes — loop nests with independent iterations, wide reductions with partial accumulators — have heavy tails where large windows do pay. This is why window size is workload-sensitive: a server core running pointer-heavy business logic and a core running dense numeric loops want different sizes, and designs that serve both usually pick the smaller and rely on the compiler to expose parallelism the window cannot reach.

Registers before entries

A window cannot hold more independent operations than it has register names for. This is the constraint that bit designers first, and it is why renaming and window sizing are coupled.

With A architectural registers and P physical registers, the maximum number of simultaneously live values is P - A worth of destinations in flight, plus one per architectural register for the committed values. If each instruction that writes allocates one physical register, the window’s in-flight size is capped by P - A (in the circular-file design) regardless of the reorder buffer’s size. Practical consequence: a machine advertised with a very large reorder buffer and a modest physical register file is limited by the file, and microarchitectural probes show the knee at the file’s limit, not the buffer’s.

The ratio of physical to architectural registers in shipping designs has tended to grow more slowly than the reorder buffer, because the register file’s multiporting cost grows faster than its bit capacity. This is one of the structural reasons the plateau arrives earlier than naive analysis predicts.

The cost side, itemized

Per-entry costs in a large window are small but numerous. A window of 500 entries needs:

• Reorder buffer storage: destination tags, program counters or identifiers, done bits, fault bits, a few bits of bookkeeping — tens of bits per entry, plus the physical register file entries that the buffer’s depth implies.
• Issue queue storage: source tags (two or three per instruction), ready bits, age information for priority arbitration. The age field alone grows with the logarithm of the window, and comparing age across entries is where the select network’s area goes.
• Wakeup wiring: every result bus fans out to every entry’s tag comparators. The wire length and the comparator count both scale with entries, and the interconnect becomes a dominant energy term.
• Squash and restore: the recovery mechanism described in Checkpointing and Recovery from Misprediction must either track the whole window or be pointer-based. Pointer-based recovery is O(1) in window size, which is why it is universal; anything per-entry is not affordable.
• Physical register file: read ports per issue port, write ports per result bus, and the entries themselves. Wide designs partition the file, which turns a port problem into a cross-cluster bypass problem.

The energy cost is the one that changed the economics. A fully associative wakeup network switches with every result broadcast, independent of whether any consumer is waiting, so a bigger window costs energy in the idle case. Techniques like segmented queues, selective wakeup, and gating the select network all trade latency or correctness-of-wakeup for reduced activity, and their success depends on the same instruction-level parallelism statistics that determine whether the window is worth enlarging in the first place.

Simulating the knee

The following model computes the aggregate coverage curve for a synthetic dependence structure with a single tuned parameter: the probability that an instruction depends on one of the previous sixteen. It is not a processor simulator; it isolates the occupancy argument.

#include <stdio.h>

#define MAXW 512
#define N 20000

/* Deterministic LCG so the model is reproducible without a library. */
static unsigned long long seed = 12345;
static double urand(void)
{
    seed = seed * 6364136223846793005ULL + 1442695040888963407ULL;
    return (double)((seed >> 33) & 0x7fffffff) / 2147483648.0;
}

int main(void)
{
    static int dep[N];          /* dependency distance in instructions, -1 none */

    for (int i = 0; i < N; i++) {
        if (i > 0 && urand() < 0.45) {
            int d = 1 + (int)(urand() * 16.0);      /* depend on one of the last 16 */
            dep[i] = i - d < 0 ? -1 : d;
        } else {
            dep[i] = -1;
        }
    }

    /* An instruction is covered when its dependency distance is below the
       window: both ends of the edge fit inside the window at once. */
    for (int w = 8; w <= MAXW; w *= 2) {
        long covered = 0;
        for (int i = 0; i < N; i++)
            if (dep[i] < 0 || dep[i] < w) covered++;
        printf("window %4d: covered %.1f%%\n", w, 100.0 * covered / N);
    }
    return 0;
}

The output rises quickly and then flattens once the window covers the longest dependency distance in the stream: entries beyond that reach buy coverage only for edges that do not exist. The real machine’s curve is smoother because latency interacts with occupancy, but the knee location is governed by the same distribution.

Second-order effects that bite at large sizes

Retirement bandwidth. A large buffer with narrow retirement makes completed instructions queue at the head, blocking allocation. Designs with wide issue and narrow retire exist and their effective window is smaller than the advertised one. The mechanics are in The Reorder Buffer and In-Order Retirement.

Store queue and load queue limits. These are sized independently and are usually far smaller than the reorder buffer, so store-heavy regions saturate the store queue long before the window fills. The window’s contribution in such code is measured as zero even though the buffer is not full.

Cache capacity pressure. A larger window brings more memory operations into flight, which increases the number of outstanding misses and the pressure on miss-status holding registers. A machine with a huge window and a small number of miss buffers stalls on the miss buffers; the window then only increases the number of instructions that can be squashed on a misprediction, raising the cost of every recovery without improving throughput.

Power density. Because the wakeup network is active every cycle, the window’s dynamic power does not scale down proportionally at low utilization. This is the main argument for heterogeneous cores in the same package: a narrow core with a small window serves latency-insensitive work at much lower energy, and the wide core is reserved for what needs it.

What a designer can vary instead

Given a plateau, the levers that improve throughput without a bigger window are:

1. Accuracy. Better prediction reduces the number of squashes, which is equivalent to more effective window capacity because squashed instructions wasted entries. The relationship is direct: a misprediction costs roughly the number of entries that had been filled behind the branch.
2. Latency. Shorter memory latency reduces the number of entries consumed by waiting. A prefetcher that turns a DRAM miss into an L1 hit frees window entries in bulk.
3. Diversity of the supply. A wider, better-targeted front end puts more independent instructions into the window per cycle; see Front-End Throughput and the Fetch Bandwidth Ceiling.
4. Partitioned scheduling. Splitting the window into clusters with local wakeup reduces the cost per entry, allowing a larger total for the same energy.

None of these is a substitute for the others, and the historical pattern in high-performance cores is a sequence of shifts between them as each reached its own plateau. The window size that a design ends up with is the point where the marginal throughput of an entry no longer exceeds the marginal cost of issuing to it — a cost that includes not only the entry but the scheduling logic, the register file, and the recovery machinery it implies.