Title
Cache-adaptive algorithms
Abstract
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 optimal cache-adaptive algorithm. Cache-oblivious algorithms having this form include Floyd-Warshall all pairs shortest paths, naïve recursive matrix multiplication, matrix transpose, and Gaussian elimination. While the cache-oblivious sorting algorithm Lazy Funnel Sort does not have this recursive 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 optimal. 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 having no optimal cache-oblivious solution.
Year
DOI
Venue
2014
10.5555/2634074.2634145
SODA
Keywords
DocType
ISBN
algorithms,design,cache oblivious,memory adaptive,computations on matrices,external memory,path and circuit problems,theory,cache adaptive,paging algorithms
Conference
978-1-61197-338-9
Citations 
PageRank 
References 
1
0.35
29
Authors
6
Name
Order
Citations
PageRank
Michael A. Bender12144138.24
Roozbeh Ebrahimi2233.62
Jeremy T. Fineman358736.10
Golnaz Ghasemiesfeh4223.96
Rob Johnson556239.43
Samuel McCauley6276.91