Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis
Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis
复制标题
缩小缓存无关分析和缓存自适应分析之间的差距
DOI：
10.1145/3350755.3400274
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Helen Xu
中科院分区：
文献类型：
--
作者：
M. A. Bender;R. Chowdhury;Rathish Das;Rob Johnson;William Kuszmaul;Andrea Lincoln;Quanquan C. Liu;J. Lynch;Helen Xu
引入缓存自适应分析来分析当可用于算法的该高速缓存（或内部存储器）的大小动态变化时算法的性能。实际上，这些内存大小波动是多核机器中的常见情况，在多核机器中，线程共享缓存和RAM。如果一个算法实现了对动态变化的高速缓存的最佳利用，则该算法被称为高效的高速缓存自适应算法。缓存自适应分析的灵感来自于缓存无关分析。许多（甚至大多数）最优的高速缓存无关算法都有一个$（a，B，c）$-正则递归结构。此类$（a，B，c）$正则算法包括最长公共子序列、所有对最短路径、矩阵乘法、编辑距离、高斯消除范式等。Bender等人（2016）表明，即使缓存动态变化大小，这些最佳缓存无关算法中的一些仍然是最佳的，但一般来说，它们可能与最佳值相差对数因子。然而，他们的分析依赖于构建一个高度结构化的、最坏情况下的内存配置文件，或者高速缓存大小的波动序列。这些最坏情况下的轮廓似乎很脆弱，表明对数差距可能是一个不切实际的强大对手的人工制品。我们关闭缓存不经意和缓存自适应分析之间的差距，通过展示如何使缓存自适应算法的平滑分析，通过随机重新洗牌的内存波动。值得注意的是，我们还展示了几种自然平滑形式的限制，包括该高速缓存大小的随机扰动和随机化算法的开始时间。尽管如此，我们表明，如果一个任意的配置文件，并执行随机洗牌时，“重大事件”发生在配置文件中，然后洗牌配置文件成为最佳缓存自适应的预期，即使当初始配置文件是adversarially构建。这些结果表明，高速缓存遗忘是一个坚实的基础，实现高速缓存自适应时，内存配置文件是不是过于定制的算法结构。
Cache-adaptive analysis was introduced to analyze the performance of an algorithm when the cache (or internal memory) available to the algorithm dynamically changes size. These memory-size fluctuations are, in fact, the common case in multi-core machines, where threads share cache and RAM. An algorithm is said to be efficiently cache-adaptive if it achieves optimal utilization of the dynamically changing cache. Cache-adaptive analysis was inspired by cache-oblivious analysis. Many (or even most) optimal cache-oblivious algorithms have an $(a,b,c)$-regular recursive structure. Such $(a, b, c)$-regular algorithms include Longest Common Subsequence, All Pairs Shortest Paths, Matrix Multiplication, Edit Distance, Gaussian Elimination Paradigm, etc. Bender et al. (2016) showed that some of these optimal cache-oblivious algorithms remain optimal even when cache changes size dynamically, but that in general they can be as much as logarithmic factor away from optimal. However, their analysis depends on constructing a highly structured, worst-case memory profile, or sequences of fluctuations in cache size. These worst-case profiles seem fragile, suggesting that the logarithmic gap may be an artifact of an unrealistically powerful adversary. We close the gap between cache-oblivious and cache-adaptive analysis by showing how to make a smoothed analysis of cache-adaptive algorithms via random reshuffling of memory fluctuations. Remarkably, we also show the limits of several natural forms of smoothing, including random perturbations of the cache size and randomizing the algorithm's starting time. Nonetheless, we show that if one takes an arbitrary profile and performs a random shuffle on when "significant events'' occur within the profile, then the shuffled profile becomes optimally cache-adaptive in expectation, even when the initial profile is adversarially constructed. These results suggest that cache-obliviousness is a solid foundation for achieving cache-adaptivity when the memory profile is not overly tailored to the algorithm structure.
DOI：
10.1109/focs.2017.90
发表时间：
2017-05
期刊：
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
D. Durfee;John Peebles;Richard Peng;Anup B. Rao
通讯作者：
D. Durfee;John Peebles;Richard Peng;Anup B. Rao