Front-End Throughput and the Fetch Bandwidth Ceiling

Every out-of-order design eventually meets a limit that has nothing to do with execution: the machine can only schedule instructions that have been fetched, decoded, and renamed. A core with six issue ports behind a four-instruction-per-cycle fetch stage is, at best, a four-wide machine. The front end is therefore the first thing sized in a new design and the last thing improved when a design ages, because changes there are structural.

What the back end needs

The supply requirement is stated as a rate. If the machine can issue W instructions per cycle and the average instruction takes C cycles to complete, the machine needs W instructions per cycle entering the window in steady state, independent of C. Latency hiding raises the occupancy of the window, but not the throughput needed to keep it full.

The qualification is that the machine does not need W useful instructions per cycle; it needs W instructions whose operands are eventually ready. Branches break the stream, and the fraction of dynamic instructions that are branches determines how often the supply must be redirected. A taken branch every six instructions means a redirect nearly every six cycles, and each redirect costs the front end’s refill latency unless the predictor and the fetch stage can produce a target without interruption.

This yields a rough supply budget:

• Sequential fetch. Fetch width must be at least the issue width, and preferably more, since some fraction of fetched instructions are not issued for a long time or are squashed.
• Across taken branches. The machine must sustain issue-across-predicted-taken-branch at the same rate, which is what separate prediction and fetch-target mechanisms provide.
• After a misprediction. Recovery requires a refill from a new address, and the refill latency is a fixed cost proportional to front-end pipe depth.

A front end that satisfies the first but not the second is a common outcome, and it shows in profiles as issue slots lost while the reorder buffer is not full.

The decode-width wall

Fixed-width instruction sets make decoding cheap: instruction boundaries are arithmetic modulo the instruction size, and a decoder knows at fetch where every instruction starts. Variable-width sets — the 16- to 32-bit family and the variable-length compressed encodings on top of fixed-width sets — make boundaries data-dependent. A fetch block of 16 bytes may contain anywhere from one to eight or more instructions, and the number is not known until the bytes are decoded.

This produces a structural limit that scaling does not remove: the decode stage must both find boundaries and translate instructions, and the two are sequential within a cycle. A design that decodes four instructions per cycle from a variable-width stream must resolve up to four boundary decisions in the same cycle, which is a dependency chain, and it must also handle a block that starts mid-instruction because the fetch was split at a cache line boundary.

The standard architectural responses are:

Predecode. An extra bit per byte, attached to instruction cache lines, marks instruction starts. The boundary-finding work moves to fill time, and the decode stage just walks the marks. The cost is storage proportional to code size and a strict requirement that the marks be invalidated whenever code changes.

The decoder as a queue of length decoders. Start with a queue of pending bytes, extract one instruction at a time in a fixed-width datapath, and accept a variable number per cycle. The width in instructions per cycle then becomes the minimum over a distribution, so the average is below the maximum no matter the input.

Caching decoded instructions. The trace cache is the extreme version: store the decoded operations in the order they executed, indexed by a starting address and a path history, so the front end retrieves ready-made micro-operations rather than bytes. This removes decoding from the critical path for repeated code, and it also allows fetch to cross taken branches because the trace was assembled from a dynamic sequence. The costs are duplication (the same instructions appear in multiple traces), an indexing problem (which trace to fetch?), and invalidation complexity when code is modified. Trace caches were built, and the idea recurs in modern designs as a decoded micro-operation cache with less path specificity.

Fetch, the instruction cache, and the line-boundary problem

Even with plentiful decode, the fetch stage is bounded by the instruction cache’s line size. A 64-byte line holding 4-byte instructions contains 16 instructions, so a 16-byte-per-cycle fetch of 4 instructions needs four cycles per line. The problem is alignment: a predicted taken branch to the middle of a line wastes the rest of that line unless the fetch unit can start at an arbitrary offset, and a fetch block that straddles two lines needs two accesses or a way-predicting cache.

Two further effects are worth knowing:

Instruction TLB reach. Fetch translates addresses through the instruction TLB. A working set of code larger than the TLB’s reach causes fetch-side translation misses, each of which stalls the front end entirely. Huge-page mappings and larger TLBs are standard mitigations, and their absence shows up as a front-end stall indistinguishable from an instruction cache miss in the simplest counters.

Prefetching. Sequential instruction prefetch is cheap and effective for straight-line code, but a taken branch invalidates it. Designs therefore prefetch from predicted targets, sometimes with a dedicated next-line prefetcher attached to the fetch unit. The prefetcher’s accuracy is bounded by the branch predictor’s, which is why the two are usually designed together.

The branch-predictor coupling

Fetch cannot proceed without a prediction for every branch in the block being fetched. A taken-branch prediction in the middle of a block truncates the block; two taken branches in one block would require two redirects. Designs typically accept at most one taken branch per fetch cycle, which means the sustained fetch rate across dense branches is one block per cycle regardless of width.

The mechanism that changes this is the predictor’s ability to supply a whole sequence of targets in advance — a branch target buffer wide enough to predict several branches, plus a fetch-target queue that holds predirected targets so the front end need not recompute them. With such a queue, the front end follows a chain of predictions without stalling on the predictor’s latency, and the effective fetch rate decouples from the predictor’s access time. The cost is a queue that must be flushed on a misprediction and a predictor that must be read ahead of the current fetch address.

Prediction accuracy is not a front-end parameter but it dominates outcomes: a predictor that is wrong one time in a hundred on a dense-branch workload costs a refill every few hundred cycles, and the refill is the front end’s worst case.

Measuring supply against demand

The diagnostic that separates front-end limits from back-end limits is a pair of counters: cycles in which no instruction was dispatched to the reorder buffer (front-end stall) versus cycles in which the buffer was occupied but nothing was issued (back-end stall). The following model computes the stall attribution for a simple configuration and shows why an increase in window size alone cannot fix a supply problem.

#include <stdio.h>

struct config { int fetch; int decode; int issue; int window; };

/* A rough throughput model: each stage's service rate, plus a fixed penalty
   for every redirect (taken branch or misprediction). Returns sustained IPC. */
static double ipc(const struct config *c, double branch_freq, double mispred_rate,
                  int redirect_penalty)
{
    double stage_rate = c->fetch < c->decode ? c->fetch : c->decode;
    if (stage_rate > c->issue) stage_rate = c->issue;

    /* a mispredicted branch costs a refill on top of the base issue rate */
    double redirects_per_insn = branch_freq;
    double cycles_per_insn = 1.0 / stage_rate
        + redirects_per_insn * mispred_rate * redirect_penalty;
    return 1.0 / cycles_per_insn;
}

int main(void)
{
    struct config narrow = { .fetch = 4, .decode = 4, .issue = 6, .window = 200 };
    struct config wide   = { .fetch = 8, .decode = 4, .issue = 6, .window = 200 };
    struct config wide2  = { .fetch = 8, .decode = 8, .issue = 6, .window = 200 };

    printf("narrow: %.2f IPC\n", ipc(&narrow, 1.0 / 6, 0.03, 15));
    printf("wide fetch: %.2f IPC\n", ipc(&wide, 1.0 / 6, 0.03, 15));
    printf("wide fetch+decode: %.2f IPC\n", ipc(&wide2, 1.0 / 6, 0.03, 15));
    return 0;
}

The structure of the answer is the lesson: doubling fetch alone does nothing when decode is the narrowest stage, and doubling both moves the limit to issue and to the redirect penalty. Meanwhile an increase in window has no effect in this model at all — the window is an occupancy resource, not a throughput resource, and a machine with insufficient supply fills it slowly rather than using it. The interaction is the one analyzed in Sizing the Window: Why More Entries Stop Paying, where the same quantity appears from the other end: a window whose marginal entry is only reachable by fetching at a rate the front end cannot sustain is capacity that never converts into throughput.

The supply-side failure modes

Decode bubbles from boundary splits. A block that crosses a cache line or a page boundary cannot be decoded in one cycle; the split instruction is deferred and the decoder idles for the remainder of the cycle. Code alignment matters: loops that straddle a boundary run measurably below loops that do not, which is a property of the binary layout rather than of the algorithm.

Microcoded instruction expansion. A single instruction that expands into many micro-operations consumes the decode stage for multiple cycles and the reorder buffer for many entries. The front end stalls while the expansion is generated, and the effect on surrounding code is a window full of one instruction’s micro-operations, which offers little independent work — see The Reorder Buffer and In-Order Retirement for how that space is accounted.

Prediction latency and the fetch-target queue. A predictor that must be read before fetch can begin, and that has a multi-cycle latency, must be pipelined ahead. If the fetch-target queue is exhausted by a long run of taken branches, the front end stalls even though it is predicting correctly.

Instruction cache aliasing. Virtually indexed fetch risks two addresses with the same index mapping to one entry; designs use page-size-aligned indexing or physical tagging to avoid it. Either way the constraint is that the fetch stage must not be able to observe an alias, and the cost is either a restriction on cache geometry or a translation delay on the critical path.

Squash refill interactions. After a misprediction the front end restarts, and the checkpoint pool described in Checkpointing and Recovery from Misprediction may be full, adding a stall on top of the refill. A machine with a deep speculative capacity but a shallow checkpoint pool converts a control-flow problem into a resource problem at exactly the wrong moment.

Where the balance sits

Modern cores devote a large share of their area to the front end: a large predictor with several structures, a micro-operation cache, a wide but variable-width decode, and a fetch-target queue. The reason is that the back end’s return on investment saturates. Adding a window entry costs a comparator and delivers value only if the program has parallelism left; adding a fetch byte costs a wire and delivers value whenever the machine is starved. The two are related by the same argument that makes the window useful in the first place: the window’s ability to find independent work is capped by the diversity of the instruction stream it holds, and the front end determines that diversity.