Increment - and - Freeze: Every Cache, Everywhere, All of the Time
Increment - and - Freeze: Every Cache, Everywhere, All of the Time
复制标题
增量和冻结：每时每刻、无处不在的每个缓存
DOI：
10.1145/3558481.3591085
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Evan West
中科院分区：
文献类型：
--
作者：
M. A. Bender;Daniel DeLayo;Bradley C. Kuszmaul;William Kuszmaul;Evan West
与缓存相关的最基本的算法问题之一是计算给定轨迹上的 LRU 命中率曲线。不幸的是，已知的算法表现出较差的数据局部性并且无法扩展到大型缓存。人们普遍认为，LRU 命中率曲线的计算效率不足以用于在线生产环境。这导致了关于启发式方法的大量文献的出现，这些文献旨在有效地逼近曲线。在本文中，我们证明过去算法的不良数据局部性是可以避免的。我们引入了一种称为增量和冻结的新算法，用于计算精确的 LRU 命中率曲线。该算法实现了 RAM 模型复杂度 O(n log n)、外部存储器复杂度 O(n over B log n) 和并行度 θ(log n)。我们还提出了增量和冻结的两种理论扩展，一种在外部存储器模型中实现了 SORT 复杂性，另一种在保持工作效率的同时实现了接近线性并行的 O(log2 n) 并行跨度。我们实现了增量和冻结，并在单个处理器上获得了比经典增强树算法高达 9 倍的加速。在 16 个线程上，加速比高达 60 倍。与之前最先进的并行算法相比，当两种算法使用相同数量的线程时，增量和冻结可实现高达 10 倍的加速。
One of the most basic algorithmic problems concerning caches is to compute the LRU hit-rate curve on a given trace. Unfortunately, the known algorithms exhibit poor data locality and fail to scale to large caches. It is widely believed that the LRU hit-rate curve cannot be computed efficiently enough to be used in online production settings. This has led to a large literature on heuristics that aim to approximate the curve efficiently. In this paper, we show that the poor data locality of past algorithms can be avoided. We introduce a new algorithm, called Increment-and-Freeze, for computing exact LRU hit-rate curves. The algorithm achieves RAM-model complexity O(n log n), external-memory complexity O(n over B log n), and parallelism Θ(log n). We also present two theoretical extensions of Increment-and-Freeze, one that achieves SORT complexity in the external-memory model, and one that achieves a parallel span of O(log2 n) which is near linear parallelism, while maintaining work efficiency. We implement Increment-and-Freeze and obtain a speedup of up to 9x over the classical augmented-tree algorithm on a single processor. On 16 threads, the speedup becomes as large as 60x. In comparison to the previous state-of-the-art parallel algorithm, Increment-and-Freeze achieves a speedup of up to 10x when both algorithms use the same number of threads.
可变对象大小的最佳缓存的实际界限
DOI：
10.1145/3224427
发表时间：
2018
期刊：
Proceedings of the ACM on Measurement and Analysis of Computing Systems
影响因子：
--
作者：
Berger, Daniel S.;Beckmann, Nathan;Harchol-Balter, Mor
通讯作者：
Harchol-Balter, Mor