Cache-Adaptive Analysis

Previous work showed that some cache-oblivious algorithms (which run efficiently without knowing cache parameters) perform well cache-adaptively. However, these results were limited to a small class of adaptive cache-oblivious algorithms. This left open the question: when exactly is a cache-oblivious algorithm also cache-adaptive (and when is it not)?

Our results give a toolbox for showing when a recursive cache-oblivious algorithm is cache-adaptive. We give a full characterization for a wide class of algorithms, and provide further techniques to analyze other recursive cache-oblivious algorithms. Applying our tools to known cache-oblivious algorithms gives the first examples of algorithms that are provably not cache adaptive, and a greatly expanded class of efficient cache-adaptive algorithms.

Our results are based on a charging argument, which bounds how much work a recursive algorithm does (or fails to do) as the cache size fluctuates adversarially.

(Joint work with Michael Bender, Erik Demaine, Roozbeh Ebrahimi, Jeremy Fineman, Golnaz Ghasemiesfeh, Andrea Lincoln, Rob Johnson, and Jayson Lynch)