Cache-adaptive algorithms

We introduce the cache-adaptive model, which generalizes the external-memory model to apply to environments in which the amount of memory available to an algorithm can fluctuate. The cache-adaptive model applies to operating systems, databases, and other systems where the allocation of memory to processes changes over time. We prove that if an optimal cache-oblivious algorithm has a particular recursive structure, then it is also an opti-mal cache-adaptive algorithm. Cache-oblivious algorithms having this form include Floyd-Warshall all pairs shortest paths, naı̈ve recursive matrix multiplication, matrix trans-pose, and Gaussian elimination. While the cache-oblivious sorting algorithm Lazy Funnel Sort does not have this re-cursive structure, we prove that it is nonetheless optimally cache-adaptive. We also establish that if a cache-oblivious algorithm is optimal on “square ” (well-behaved) memory profiles then, given resource augmentation it is optimal on all memory profiles. We give paging algorithms for the case where the cache size changes dynamically. We prove that LRU with 4-memory and 4-speed augmentation is competitive with op-timal. Moreover, Belady’s algorithm remains optimal even when the cache size changes. Cache-obliviousness is distinct from cache-adaptivity. We exhibit a cache-oblivious algorithm that is not cache-adaptive and a cache-adaptive algorithm for a problem hav-ing no optimal cache-oblivious solution.