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 optimal cache-adaptive algorithm. Cache-oblivious algorithms having this form include Floyd-Warshall all pairs shortest paths, naive 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.

我们介绍了缓存自适应模型，该模型概括了外部内存模型，以应用于环境，在该环境中，可用于算法的内存量可能会波动。缓存自适应模型适用于操作系统，数据库和其他系统，其中存储器对进程的分配随时间而变化。 我们证明，如果最佳的高速缓存算法具有特定的递归结构，那么它也是一种最佳的高速缓存适应算法。具有此形式的合并式算法包括所有最短路径，天真的递归矩阵乘法，矩阵转置和高斯消除。虽然合并缓存的排序算法懒惰的漏斗排序没有这种递归结构，但我们证明它仍然是最佳的缓存自适应。我们还确定，如果合格的算法在“正方形”（良好的）内存配置文件上是最佳的，则给定资源增强，它对所有内存配置文件都是最佳的。 我们为缓存大小动态变化的情况提供了分页算法。我们证明，具有4序和4速增强的LRU具有最佳竞争力。此外，即使缓存尺寸变化，Belady的算法也仍然是最佳的。 合身性与缓存适应性不同。我们展示了一种不具有缓存自适应的算法，并且对于没有最佳缓存解决方案的问题，该算法和缓存自适应算法。