Stride Prefetchers and the Timing Problem of Prefetch Distance

A miss that is detected after the load issues has already cost the full latency. Prefetching attacks the problem from the other side: issue the fetch before the demand access, so the demand access hits. The obstacle is that the hardware must guess an address the program has not yet computed. For sequential and strided access — the two patterns that dominate array code — the guess is easy, and the interesting part of the design is not detecting the pattern but deciding when to act on it.

Detecting a delta

A stride prefetcher watches the addresses of demand misses and looks for a constant difference between successive accesses that fall in the same region. The reference implementation keeps a small table indexed by the instruction address of the load, holding the last address the instruction touched and the delta observed between the last two. When a new access from the same instruction differs from the recorded address by the recorded delta, the confidence counter increments; a mismatch resets the delta to the newly observed value and clears the counter.

/* One entry of a stride table, keyed by the load's program counter. */
struct stride_entry {
    unsigned long pc;
    unsigned long last_addr;
    long          delta;       /* bytes between consecutive accesses */
    unsigned      conf;        /* consecutive matches seen */
    unsigned      valid;
};

void observe(struct stride_entry *e, unsigned long pc,
             unsigned long addr, unsigned long *prefetch)
{
    if (!e->valid || e->pc != pc) {           /* first sighting: train */
        e->pc = pc; e->last_addr = addr; e->delta = 0; e->conf = 0; e->valid = 1;
        return;
    }
    long d = (long)(addr - e->last_addr);
    if (d == e->delta && d != 0) {
        if (e->conf < CONF_MAX) e->conf++;
    } else {
        e->delta = d;                          /* new candidate stride */
        e->conf = 1;
    }
    e->last_addr = addr;
    if (e->conf >= CONF_THRESHOLD)             /* only act once the pattern is stable */
        *prefetch = addr + (unsigned long)e->delta;
}

Two design decisions live in that code. The threshold controls when the prefetcher starts acting: a threshold of one reacts immediately but issues fetches for any two accesses that happen to be adjacent, and a threshold of three or four requires a genuinely repeating pattern. The other is what counts as a match. Comparing raw deltas fails for code that alternates between two streams through one load instruction; comparing deltas within a page-sized region, or keeping a short history rather than only the last delta, costs more state and catches more patterns.

Stride prefetchers handle the case where one instruction walks memory with a fixed step: array traversals with a constant element size, column walks with a fixed row pitch, structure-of-arrays accesses at a fixed record length. They do not handle pointer chasing, where the next address is loaded from memory and cannot be predicted from the current one, nor irregular graphs, nor hashed table probes. Those need either software prefetch instructions or a different mechanism entirely. What the prefetcher cannot do is issue a fetch for an address whose translation is not yet known, which ties it to the virtually indexed lookup path.

Distance is a latency budget

The prefetched line must arrive before the demand access needs it, and must not arrive so early that it is evicted before use. If a miss costs L cycles and the loop advances through memory at a rate of one line every s cycles, the prefetch must be issued at least L/s iterations ahead. For a 250-cycle latency and a loop body of ten cycles per line, that is 25 lines ahead — 1600 bytes for 64-byte lines. A distance shorter than that arrives late and the demand access still stalls; a distance much longer keeps lines in the cache longer than necessary and displaces lines that would have been used.

The quantity is genuinely a distance in lines, and the prefetcher does not know the loop’s rate. Real designs therefore fix a distance per stream — typically a handful of lines for an L1 prefetcher and tens for an L2 stream prefetcher — and accept that it is wrong for some loops. Some designs make the distance adaptive: they measure whether prefetched lines are arriving before use, by marking them and checking on the demand access, and increase or decrease the distance accordingly. The feedback signal is the fraction of prefetches that turned out to be useful, which is exactly the accuracy metric.

A prefetcher that is too aggressive has a second cost beyond eviction: it consumes bandwidth. Every prefetch that is not used transfers 64 bytes that could have carried a demanded line. In a bandwidth-limited workload, prefetches compete with demand misses and can lengthen the queue at the memory controller, so a prefetcher with high coverage but low accuracy makes the machine slower. This is why hardware prefetchers are usually throttled by a feedback loop that disables them when the accuracy of recent prefetches falls below a threshold.

Coverage, accuracy, timeliness

The three metrics pull against one another and no design maximises all three.

• Coverage is the fraction of demand misses that were prefetched. It measures how much of the miss latency the mechanism removed.
• Accuracy is the fraction of prefetches that were used before eviction. It measures the wasted bandwidth.
• Timeliness is the fraction of prefetches that arrived early enough to be useful. A prefetch that arrives after the demand access is counted as accurate but useless.

The definitions are entangled. A prefetch that arrives too early is evicted unused and counts against accuracy, which looks like an accuracy failure but is a distance failure. A prefetch that arrives too late may still be counted as accurate if the line is used, even though the stall happened anyway. Any evaluation of a prefetcher has to separate the three, which is why prefetcher papers report them separately and why a single hit-rate improvement is not evidence that prefetching worked.

There is also a correctness-adjacent constraint: prefetches must never change program-visible state. A prefetch to an unmapped or inaccessible page must be dropped silently rather than raising a fault. Hardware prefetchers satisfy this by construction — they only issue fills into the cache, never architectural accesses — but software prefetch instructions have the same requirement in the architectures that define them, which is why an out-of-bounds prefetch in C is not a fault on the architectures where the instruction exists, though it is still undefined behaviour at the language level.

Interaction with the rest of the hierarchy

A prefetch issued by the L1 typically fills into the L2 rather than the L1, because the L1 is small and the prefetched line is not needed yet. The demand access then hits in the L2 and pays the L2 latency, which is much shorter than DRAM but not zero. This is the standard arrangement: the L2 prefetcher covers DRAM latency, the L1 prefetcher covers L2 latency, and the two distances are set independently because the latencies differ by an order of magnitude.

Prefetching also interacts with replacement. A prefetched line that arrives and is never used occupies a way that the replacement policy considers recent, because the fill set its reference bit. This is prefetch pollution, and it is one reason not-recently-used policies insert prefetched lines at a lower priority than demand fills. Some designs mark a prefetched line and allow it to be evicted preferentially if it is still unmarked when the next victim is needed.

At the memory controller, sequential prefetching is usually good news. DRAM is organised in rows that must be activated before any column within them can be read, and an activation costs more than a column access. Sequential prefetches turn scattered demands into bursts within an open row, so the row activation cost is amortised. Prefetching with a large stride does the opposite: it touches a new row for every line, paying activation latency each time and defeating the row buffer. A stride prefetcher that fetches lines several hundred bytes apart can therefore increase DRAM traffic per useful byte even while improving the cache hit rate.

When prefetching makes things worse

The failure cases are specific and worth naming. A prefetcher with a short distance on a loop that moves slowly through memory issues prefetches that are evicted before the loop arrives; the cache fills with lines nobody wants and the miss rate for the actual working set rises. A prefetcher on a workload whose access pattern is a sequence of unrelated pages — a hash table with random probing — issues fetches for lines that will never be touched, and every one is wasted bandwidth. A prefetcher that follows a stride across a page boundary may touch an unmapped page, which is harmless for a hardware prefetcher but costs a wasted TLB lookup.

The mitigations are all forms of restraint: require a confidence threshold before issuing, limit the number of streams tracked per core, disable on low accuracy, and do not prefetch across a page boundary without a translation already in hand. The last rule matters because a prefetch that triggers a page walk costs as much as the miss it was trying to avoid, and a page walk that races with another core’s invalidation adds contention to the very structure the prefetch was meant to relieve.

Software prefetching has different constraints. The instruction is a hint, so it costs an issue slot and a memory request but never a stall; the compiler or programmer must place it far enough ahead, which usually means restructuring the loop to compute addresses for iteration i + d while processing iteration i. That restructuring is the same distance calculation as above, performed statically, and it fails when the trip count is unknown or the loop has a dependency that prevents the lookahead.