Conclusions
Stride prefetchers are most mature
- good coverage, timing and high accuracy
Recursive prefetchers
- poor timing and not able to overlap well
Markov prefetcher
- high hardware cost, not a good stand-alone prefetcher, mediocre accuracy
Hybrid prefetching
- need evaluation of which prefetchers to combine
- and how to combine them (e.g., serial prefetching)
Notes:
We have talked about several different prefetching techniques. The stride prefetchers have been well studied and we showed that even on modern processors that issue several instructions per cycle, stride prefetching is possible.
Recursive prefetchers are much more challenging, because data dependencies make it difficult to prefetch far ahead. While current techniques don’t attack this problem very well, we showed that the recursive prefetching technique by Roth, Moshovos, and Sohi has potential to overlap prefetches for tree traversals. Linked list traversals are much more difficult and here compiler techniques that lay out data differently may be the only answer. Luk and Mowry have done some work in this area, but due to the limited time I did not discuss their work today.
We briefly introduced Markov prefetching. Their technique is expensive and does not provide very good accuracy. Joseph and Grunwald also provided some insight into hybrid prefetching. A particularly interesting question would be how well a stride and recursive prefetcher perform in serial and if Markov prefetching would provide additional gains on top of the other two.