Prefetching
August 3, 2026·25 min read·advanced
The cache hierarchy of Chapter 37 and the advanced techniques of Chapter 39 reduce the AMAT formula by improving the hit rate and the hit time. Prefetching attacks a different term. If the processor can…
The cache hierarchy of Chapter 37 and the advanced techniques of Chapter 39 reduce the AMAT formula by improving the hit rate and the hit time. Prefetching attacks a different term. If the processor can predict an upcoming access and start the fetch before the program demands the data, the access arrives at the cache before the load instruction executes. The load sees a hit instead of a miss, and the entire miss-penalty term in AMAT drops out for that access.
This chapter develops prefetching from first principles, starting with the simplest stride detector and building up to the modern signature-path and Bingo prefetchers that define the current research frontier and are beginning to influence shipping designs. It covers software prefetch instructions, runahead execution, and dependency-graph prefetching for pointer chasing. The treatment is concrete throughout. The reader who works through the chapter will be able to identify prefetcher behavior in a performance counter trace and to predict whether a given workload will benefit from each prefetcher class.
01.Why Prefetching Works
The premise of prefetching is the same as the premise of the cache hierarchy: program access patterns are predictable. The cache exploits the predictability through resident storage. The prefetcher exploits the same predictability through forecasting.
The Simplest Case
A loop that sums an array of one million integers touches a[0], a[1], a[2], and so on in order. The hardware cannot know that the program will visit a[k+1] after a[k], but after observing the first few accesses, the pattern is unmistakable. A simple prefetcher that, on every demand access, issues a prefetch for the next sequential cache line will hide the entire DRAM latency of the array traversal.
Without prefetching, the first access to each new cache line misses. A 1-million-element float32 array spans bytes, or cache lines of 64 bytes each. At 70 ns per DRAM access, that is ms of total memory time. With a perfect prefetcher, every access hits L1, and the memory time drops to the L1 hit latency times the number of accesses, about ms. The prefetcher delivers a 14x improvement on this single loop.
The Three Metrics
Prefetcher quality has three dimensions, and good prefetcher design balances all three.
Accuracy. The fraction of prefetched lines the program actually uses. An inaccurate prefetcher pollutes the cache, displacing useful lines and increasing miss rate on the non-prefetched accesses. A prefetcher with 30-percent accuracy that fetches 100 lines pollutes the cache with 70 unused lines.
Coverage. The fraction of total demand misses that the prefetcher converts into hits. A prefetcher with 90-percent coverage eliminates 90 out of every 100 demand misses. Coverage alone is incomplete. A prefetcher with 100-percent coverage but 1-percent accuracy fetches 100 lines for every 1 useful one.
Timeliness. The fraction of prefetched lines that arrive in the cache before the demand access needs them. A prefetcher that correctly identifies upcoming accesses but issues the prefetch one cycle before the demand sees almost no benefit. The line arrives just as the demand is about to use it, and the demand still pays nearly full miss latency.
A prefetcher that scores well on all three metrics delivers most of the available miss-penalty reduction. A prefetcher that scores poorly on any one of the three can produce a net slowdown.
02.Stride Prefetchers
The simplest useful hardware prefetcher is the stride detector. It observes that many loads in a program access addresses with a constant offset between consecutive executions of the same load instruction. An array sum loop has a constant stride of 4 bytes (or 8, depending on element size) on the load that reads array elements. A matrix-row traversal has a constant stride of the row width.
The Mechanism
The stride prefetcher uses a small table indexed by the load PC. Each entry records:
-
The last address this load referenced.
-
The current stride (last address minus previous address).
-
A confidence counter.
On each new access by the same load PC, the prefetcher computes the new stride (current address minus last address) and compares it to the recorded stride. If they match, increment the confidence counter. If the counter exceeds a threshold (typically 2 or 3), issue a prefetch at the address plus a multiple of the stride.
A typical stride prefetcher prefetches 4 to 8 strides ahead of the current access. For a 4-byte stride on a 64-byte line, this would mean prefetching one or two lines ahead. For a row-stride access through a matrix, it might prefetch several rows ahead.
Strengths and Weaknesses
Stride prefetchers cover a substantial fraction of the misses in numerical workloads. Matrix traversals, vector loops, and packed data structure scans all generate constant-stride access patterns that the prefetcher captures easily.
The weakness is non-stride patterns. A linked list traversal has no stride between consecutive accesses (the next pointer can land anywhere in memory). A hash table lookup also defeats stride detection. A program that switches stride based on a runtime condition can fool the prefetcher into prefetching the wrong sequence.
Practical Use
Almost every modern processor has a stride prefetcher at the L1. Intel has had one since the Pentium III. ARM Cortex-A series includes one starting with A7. SiFive cores include simple stride detectors. The technique is sufficiently cheap and sufficiently useful that no high-performance design omits it.
03.Stream Prefetchers
A stream prefetcher is a sibling of the stride prefetcher that watches the address stream independently of the originating load PC. It detects sequences of addresses that look like they are walking through memory and prefetches ahead of the apparent walk.
The Mechanism
The stream prefetcher tracks a small set of active streams (typically 8 to 16). Each stream has:
-
A current address.
-
A direction (forward or backward in memory).
-
A confidence counter.
On every memory access, the prefetcher checks whether the address extends an existing stream (within a few cache lines of the stream’s current pointer, in the recorded direction). If yes, advance the stream and issue prefetches further ahead.
If the access does not match any existing stream, allocate a new stream entry (potentially replacing the least recent one).
Difference from Stride
A stride prefetcher is per-PC: it tracks the access pattern of each individual load instruction. A stream prefetcher is per- address-range: it tracks sequential walks regardless of which load instruction initiated them.
Stream prefetchers handle the case where two different load PCs collectively walk through memory: for example, an unrolled loop with four loads per iteration, each at a different PC, that together stride through an array. The stride prefetcher would detect four independent strides. The stream prefetcher detects one shared walk and prefetches more aggressively.
Practical Use
Stream prefetchers are common at the L2 and L3, where they see the merged miss stream from all cores and all load PCs. Intel’s "DCU streamer" at the L1 data cache and its "L2 hardware prefetcher" are both stream-style. ARM’s various L2 prefetchers include stream detection. The combination of L1 stride plus L2 stream covers a large fraction of sequential and quasi-sequential access patterns.
04.Global History Buffer Prefetcher
The global history buffer (GHB) prefetcher, introduced by Nesbit and Smith [1], generalizes the per-PC structure of stride prefetchers and the per-address structure of stream prefetchers into a single configurable framework.
Structure
The GHB is a circular buffer that records a sliding window of recent miss addresses, along with metadata identifying which load PC or address range generated each miss. The buffer holds 64 or 128 entries.
Lookup uses a hash table indexed by some feature of the access (load PC, address range, or both). The hash bucket points into the GHB at the entries that match the feature. The pattern of those entries informs the prefetch.
For example, in a "PC/DC" (PC localized, Delta correlated) GHB:
-
Hash lookup finds the most recent entry for this load PC.
-
Walk back through the GHB following the per-PC chain.
-
Compute the deltas (address differences) between consecutive entries.
-
If the delta pattern repeats, predict the next delta and prefetch the corresponding address.
Configurability
The GHB is a framework, not a single algorithm. By changing the hash function and the walk policy, the same hardware can implement stride detection, stream detection, delta-correlation, distance prefetching, and several other modes. A processor can ship one GHB structure and use it for multiple prefetcher types.
Practical Use
GHB-style prefetchers appear in research and in some commercial designs but are less ubiquitous than the simpler stride and stream prefetchers. The reason is engineering complexity. Building a multi-mode prefetcher that switches between modes correctly is harder than building two dedicated prefetchers (one stride, one stream) in parallel.
05.Signature Path Prefetching
A signature path prefetcher (SPP), introduced by Kim et al. [2], addresses patterns that are too complex for stride or stream detection but still repeat across program executions.
The Mechanism
SPP builds a signature for each access by combining recent address deltas. A signature might be the XOR of the last deltas. The prefetcher keeps a table indexed by signature, with each entry recording the next delta that historically followed the signature.
On an access:
-
Compute the current signature from the recent delta history.
-
Look up the signature in the table.
-
If a match is found with high confidence, issue a prefetch at the predicted delta.
-
Recursively, the prefetched address’s signature can be computed (treating the prefetch as a future access) and the next prefetch can be issued, chaining multiple prefetches ahead.
SPP can capture complex patterns like the access sequence of a hash table that repeatedly walks chains, or a tree traversal that follows the same depth-first walk on every call.
Practical Use
SPP and its descendants compete in the academic prefetcher arena (the DPC-3 data prefetching championship in 2019). Commercial disclosures of SPP-style prefetchers are rare, though the underlying ideas (signature-indexed prediction tables) appear in some recent ARM and Intel designs based on public reverse-engineering work.
06.Bingo and IPCP
Two recent prefetcher families that won data prefetching championships are Bingo and IPCP.
Bingo
Bingo, proposed by Bakhshalipour et al. [3], identifies repeated access patterns within fixed-size memory regions. The prefetcher tracks, for each region recently accessed, which sub-blocks within the region the program touched. When a new region is entered, the prefetcher recalls the access pattern from previous visits to similar regions and prefetches the predicted sub-blocks.
The "bingo" name comes from the prefetcher’s appearance: a 2D grid of access positions within a region, with the prefetcher recognizing patterns the way a bingo player recognizes lines or shapes. The technique excels at irregular within-region access patterns that nonetheless repeat across regions, such as struct field accesses in array-of-struct data.
IPCP
IPCP (Instruction-Pointer-Classifier Prefetcher), proposed by Pakalapati and Panda [4], classifies each load PC into one of several categories (constant stride, complex stride, global stream, indirect, irregular) and applies the appropriate prefetch strategy per category. The classifier itself is small. The strategy modules are correspondingly small. The combination matches more patterns than any single-strategy prefetcher.
The Pattern
The Bingo and IPCP families illustrate the trajectory of modern prefetcher research: combine multiple specialized prefetchers, classify accesses to choose between them, and use richer features (region context, instruction context) than the simple PC/stride pair. Commercial adoption lags the research literature by a few years, but the direction is clear.
07.Software Prefetching
Hardware prefetchers handle patterns the hardware can recognize. Many program access patterns are too complex or too program-specific for the hardware to capture but are entirely obvious to the compiler or the programmer. Software prefetching fills this gap by exposing a prefetch instruction in the ISA.
The Mechanism
A software prefetch instruction issues a load that does not produce a result. It moves the target line into the cache (or a specific cache level) and continues. The program subsequently executes a real load that hits the prefetched line.
The C compiler intrinsic __builtin_prefetch maps to the underlying ISA instruction. On x86-64 it emits prefetcht0, prefetcht1, or prefetchnta depending on the target cache level. On ARMv8 it emits prfm. On RISC-V the Zicbop extension provides prefetch.r and prefetch.w instructions.
When to Use Software Prefetching
Software prefetching is most useful when:
-
The access pattern is too complex for hardware prefetchers (graph traversal, hash table lookup, tree walks).
-
The compiler can analyze the pattern statically (loop with predictable but irregular access pattern).
-
The programmer has high-level knowledge the compiler does not have (a known workload phase, a specific data structure layout).
A canonical example is hash table lookup. The hash table is laid out in memory as a series of buckets. A lookup hashes the key, finds the bucket, and follows a chain of nodes. The chain pointer is irregular by design (good hash functions distribute keys evenly). A hardware prefetcher cannot predict the chain. But the compiler, given the source code, can insert a prefetch for the next chain node while the current node is being processed, overlapping memory latency with compute.
Software-prefetched hash chain walk
struct node {
struct node *next;
long key;
long value;
};
long lookup(struct node *head, long key) {
struct node *p = head;
while (p != NULL) {
__builtin_prefetch(p->next, 0, 0); // prefetch read, no temporal
if (p->key == key) return p->value;
p = p->next;
}
return -1;
}The prefetch is issued as soon as p->next is known but before the next iteration of the loop. By the time the loop body finishes processing the current node, the next node’s cache line is on its way to the cache. The DRAM latency overlaps with compute rather than stalling the pipeline.
Pitfalls
Software prefetching is easy to misuse. A prefetch issued too early gets evicted before the demand access. A prefetch issued too late provides no benefit (the demand still pays miss latency). A prefetch for an address that will not actually be used pollutes the cache. Prefetches also consume issue slots and load buffer entries, slowing the program’s compute throughput. Adding software prefetches without careful measurement can produce slowdowns.
The rule of thumb is to use software prefetching only when (a) a profiler identifies a specific load as a major miss source, (b) the access pattern is predictable enough that the prefetch will be accurate, and (c) the prefetch can be placed early enough to give the data time to arrive but not so early that the prefetched line is evicted.
08.Runahead Execution
Runahead execution, proposed by Mutlu et al. [5], addresses a specific weakness of out-of-order execution. When a long-latency load (say, a DRAM miss of 200 cycles) reaches the head of the reorder buffer, the buffer fills up with younger instructions waiting on the load. Once full, the processor stalls until the load completes.
The Mechanism
In runahead mode, when the processor detects a long-latency load about to stall the ROB, it checkpoints architectural state and enters runahead mode. It speculatively executes the program past the stalling load, treating the load’s result as a special INVALID value. Operations that consume an INVALID propagate the INVALID through.
The speculative execution does not modify architectural state, but it does generate memory accesses. Those accesses (loads to other addresses, predicted by the runahead control flow) populate the cache. When the original stalling load finally completes, the processor restores from the checkpoint and resumes normal execution. The cache, now warmed by runahead, sees the formerly- missing accesses as hits.
Effectiveness
Runahead acts as a very accurate, very timely prefetcher for the specific pattern of "future demand misses that will be reached within a few hundred instructions of the current stall." Because the runahead engine is the program itself, the predictions are accurate by construction (the program would have generated these accesses naturally on the demand path).
The downsides are complexity (the runahead checkpoint and recovery machinery is substantial) and the fact that runahead consumes energy without doing useful work in the strict sense (the speculative results are discarded).
Practical Use
Runahead has appeared in several research processors and in a few commercial designs. The Sun ROCK processor (cancelled before release) used runahead extensively. Some recent ARM disclosures mention runahead-like behavior. Intel has not publicly disclosed runahead in production cores. The technique remains an active research area but has not become mainstream.
09.Dependency-Graph Prefetching
Pointer-chasing workloads defeat all the prefetchers covered so far. A linked list traversal has no stride between consecutive nodes. A binary tree walk has no predictable access pattern beyond the local structure of each node. Yet these workloads are common and slow.
Dependency-graph prefetching addresses this by predicting that a recently-loaded value will itself be used as an address soon. The prefetcher identifies values that look like pointers (alignment, in-range addresses) and prefetches their targets.
The Mechanism
The prefetcher observes recent load results. For each loaded value , it tests whether is a plausible memory address (within the program’s virtual address space, properly aligned). If yes, it issues a prefetch to address .
A more sophisticated variant tracks the dependency graph of recent loads. When load produces a value that load consumes as an address, the prefetcher learns this pattern. Future executions of trigger an automatic prefetch of ’s target.
Practical Use
Indirect prefetching is in production at modern Intel and ARM designs, where it appears as an "indirect" or "pointer" prefetcher in performance counter documentation. The benefit is typically modest (5 to 10 percent on pointer-chasing workloads) but the patterns it captures are otherwise unreachable.
10.Prefetching at the Levels
Modern processors deploy multiple prefetchers, one per cache level, each tuned for the access stream it sees.
L1 Prefetchers
The L1 sees the demand access stream directly. Patterns are PC-identifiable and stride-rich. A stride prefetcher at L1 captures most of the constant-stride patterns. An indirect prefetcher captures pointer-chasing patterns.
L1 prefetchers must be conservative on accuracy. Polluting the L1 with unused lines can degrade hot-path hit rates by several percent. Most L1 prefetchers issue only 1 to 2 lines ahead and have strict confidence thresholds.
L2 Prefetchers
The L2 sees the L1 miss stream. The stream has lower temporal density (fewer accesses per cycle) and less PC information (the L1 miss handler dispatches without PC context in many designs). Stream prefetchers dominate at L2 because the address-range context is preserved.
L2 prefetchers can be more aggressive than L1 prefetchers because the cost of polluting L2 is lower (L2 lines are cheaper to evict, since LRU eviction sends them to L3, not to memory). Typical L2 prefetchers issue 4 to 16 lines ahead and have looser confidence thresholds.
L3 Prefetchers
The L3 sees the L2 miss stream, which has even lower density and even less context. Stream prefetchers are typical. Region-based prefetchers like Bingo are also a good fit because the L3 sees enough access volume to identify region-level patterns.
L3 prefetchers can be the most aggressive because the alternative to a successful L3 prefetch is a full DRAM access. Even a 50- percent-accurate L3 prefetcher provides net benefit, because the DRAM miss penalty is so large.
Memory Controller Prefetchers
Some designs put a prefetcher at the memory controller itself. It sees the DRAM access stream and can issue page-row hints to the DRAM, opening rows that will be accessed soon and reducing activation latency. The benefit is small but free in terms of cache pollution (no cache lines are affected).
11.Measuring Prefetcher Performance
Modern processors expose prefetcher behavior through performance counters. The relevant counters are:
-
Demand misses (cache misses generated by load/store instructions).
-
Prefetch hits (cache hits that were brought in by a prefetch).
-
Useless prefetches (prefetched lines evicted before being accessed).
-
Late prefetches (prefetched lines accessed before the prefetch completed).
From these, the three metrics of the equation above can be computed:
-
Coverage .
-
Accuracy .
-
Timeliness .
A workload analysis typically starts by reading these counters, identifying which level’s prefetcher is doing the most work, and deciding whether software prefetch hints could fill the gaps.
12.Looking Ahead
This chapter closes the introductory treatment of the memory hierarchy that began in Chapter 36. The next group of chapters develops virtual memory (Chapter 41), TLB structure and management (Chapter 42), and DRAM organization and memory controllers (Chapter 43). Part IV then continues with non-volatile memory and storage (Chapter 44), I/O architecture (Chapter 45), a cache case study (Chapter 46), a cache-simulator project (Chapter 47), and a memory-modeling lab (Chapter 48). Part V begins at Chapter 49, covering out-of-order execution and the memory-level-parallelism mechanisms that the caches and prefetchers of this part feed.
13.Worked Examples
14.Exercises
References
- [1]Nesbit, Kyle J. and Smith, James E. (2004). “Data Cache Prefetching Using a Global History Buffer.” In Proceedings of the 10th International Symposium on High-Performance Computer Architecture (HPCA), pp. 96--105. doi:10.1109/HPCA.2004.10030
- [2]Kim, Jinchun and Pugsley, Seth H. and Gratz, Paul V. and Reddy, A. L. Narasimha and Wilkerson, Chris and Chishti, Zeshan (2016). “Path Confidence Based Lookahead Prefetching.” In Proceedings of the 49th International Symposium on Microarchitecture (MICRO), pp. 1--12. doi:10.1109/MICRO.2016.7783763
- [3]Bakhshalipour, Mohammad and Shakerinava, Mehran and Lotfi-Kamran, Pejman and Sarbazi-Azad, Hamid (2019). “Bingo.” In Proceedings of the 25th International Symposium on High-Performance Computer Architecture (HPCA), pp. 399--411. doi:10.1109/HPCA.2019.00053
- [4]Pakalapati, Samuel and Panda, Biswabandan (2020). “Bouquet of Instruction Pointers: Instruction Pointer Classifier-Based Spatial Hardware Prefetching.” In Proceedings of the 47th International Symposium on Computer Architecture (ISCA), pp. 118--131. doi:10.1109/ISCA45697.2020.00021
- [5]Mutlu, Onur and Stark, Jared and Wilkerson, Chris and Patt, Yale N. (2003). “Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-Order Processors.” In Proceedings of the 9th International Symposium on High-Performance Computer Architecture (HPCA), pp. 129--140. doi:10.1109/HPCA.2003.1183530