Merging Similar Patterns for Hardware Prefetching

One critical challenge of designing an efficient prefetcher is to strike a balance between performance and hardware overhead. Some state-of-the-art prefetchers achieve very high performance at the price of a very large storage requirement, which makes them not amenable to hardware implementations in commercial processors. We argue that merging memory access patterns can be a feasible solution to reducing storage overhead while obtaining high performance, although no existing prefetchers, to the best of our knowledge, have succeeded in doing so because of the difficulty of designing an effective merging strategy. After analysis of a large number of patterns, we find that the address offset of the first access in a certain memory region is a good feature for clustering highly similar patterns. Based on this observation, we propose a novel hardware data prefetcher, named Pattern Merging Prefetcher (PMP), which achieves high performance at a low cost. The storage requirement for storing patterns is largely reduced and, at the same time, the prefetch accuracy is guaranteed by merging similar patterns in the training process. In the prefetching process, a strategy based on access frequencies of prefetch candidates is applied to accurately extract prefetch targets from merged patterns. According to the experimental results on a wide range of various workloads, PMP outperforms the enhanced Bingo by 2.6% with 30× lesser storage overhead and Pythia by 8.2% with 6× lesser storage overhead.