Efficiently prefetching complex address patterns

Manjunath Shevgoor, Sahil Koladiya, Rajeev Balasubramonian, Chris Wilkerson, Seth H. Pugsley, Zeshan Chishti

2015 · 166 citations · 29 references

Concepts

TL;DR

Hardware prefetching research has mainly targeted regular stride streams or irregular patterns, often requiring large hardware structures. This work proposes the Variable Length Delta Prefetcher (VLDP) to predict cache miss order in new pages by building delta histories between successive misses within physical pages. VLDP employs multiple prediction tables indexed by history length, using the longest matching history to predict the next miss, with each table taking 1, 2, … deltas as input.

Abstract

Prior work in hardware prefetching has focused mostly on either predicting regular streams with uniform strides, or predicting irregular access patterns at the cost of large hardware structures. This paper introduces the Variable Length Delta Prefetcher (VLDP), which builds up delta histories between successive cache line misses within physical pages, and then uses these histories to predict the order of cache line misses in new pages. One of VLDP's distinguishing features is its use of multiple prediction tables, each of which stores predictions based on a different length of input history. For example, the first prediction table takes as input only the single most recent delta between cache misses within a page, and attempts to predict the next cache miss in that page. The second prediction table takes as input a sequence of the two most recent deltas between cache misses within a page, and also attempts to predict the next cache miss in that page, and so on with additional tables. Longer histories generally yield more accurate predictions, so VLDP prefers to make predictions based on the longest history table that has a matching entry.

References

29