Hardware Prefetching
A hardware prefetcher predicts which memory a program will need next and fetches it into cache before the request arrives.
Fetching Ahead of Demand
A cache miss stalls the processor for many cycles while data comes from main memory. A hardware prefetcher reduces these stalls by predicting future memory accesses and bringing the data into cache early, so that by the time the program actually requests it, the data is already close. Done well, prefetching hides memory latency behind other work; done poorly, it wastes bandwidth and pollutes the cache.
Detecting Patterns
Prefetchers exploit the regularity in how programs touch memory. The simplest, next-line prefetching, fetches the following cache block on a miss, exploiting spatial locality. A stride prefetcher detects constant-distance access patterns, such as walking an array with a fixed step, and continues that stride ahead of the program. More elaborate prefetchers learn irregular but repeating patterns, including pointer-chasing sequences.
- Next-line: fetch the adjacent block, cheap and general
- Stride: detect a constant step and run ahead of it
- Correlation-based: learn repeating irregular access patterns
Accuracy, Timeliness, Coverage
A prefetcher is judged on three things. Accuracy: how often prefetched data is actually used, since wrong guesses waste bandwidth and can evict useful data (cache pollution). Timeliness: whether the data arrives neither too late to help nor so early it is evicted before use. Coverage: what fraction of would-be misses it eliminates. These pull against each other, and aggressive prefetching can hurt if bandwidth is scarce.
Where It Fits
Prefetchers operate at multiple cache levels and can be triggered by hardware pattern detection or by software prefetch instructions the compiler inserts. They are one of the main tools, alongside deep caches and multithreading, for coping with the growing gap between processor and memory speed. For the large, regular data sweeps common in scientific simulation, stride prefetching in particular recovers much of the latency that would otherwise dominate memory-bound loops.