Algorithms to Take Advantage of Hardware Prefetching

Cache-oblivious and cache-aware algorithms have been developed to minimize cache misses. Some of the newest processors have hardware prefetching where cache misses are avoided by predicting ahead of time what memory will be needed in the future and bringing that memory into the cache before it 13 used. It is shown that hardware prefetching permits the standard Floyd-Warshall algorithm for all-pairs shortest paths to outperform cache-oblivious and cache-aware algorithms. A simple improvement to the standard simple dynamic programming algorithm yields an algorithm that takes advantage of prefetching, and outperforms cache-oblivious and cache-aware algorithms. Finally, it is shown that variants of standard FFT algorithms exhibit good prefetching performance.