Spatial Locality and Granularity Change in Caching
Spatial Locality and Granularity Change in Caching
复制标题
缓存的空间局部性和粒度变化
DOI：
10.48550/arxiv.2205.14543
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Charles McGuffey
中科院分区：
文献类型：
--
作者：
Nathan Beckmann;Phillip B. Gibbons;Charles McGuffey
高速缓存利用时间和空间局部性来允许小的存储器提供对存储在大的、慢的存储器中的数据的快速访问。地方性的时间方面已经得到了很好的研究和理解，但空间方面的研究和理解就少得多了。我们试图通过定义和研究粒度变化缓存问题来增加对空间局部性的理解。这个问题通过将数据项分组到块中来修改传统的缓存设置，使得缓存可以选择块的任何子集来加载，其成本与加载块中的任何单个项相同。我们表明，这种空间局部性的建模显着改变了缓存问题。这首先证明了粒度变化缓存在流水线设置中是NP完全的，即使所有项目都有单位大小，所有块都有单位负载成本。在在线设置中，我们显示了确定性策略的竞争比的下限，这比传统的缓存要差得多。此外，我们提出了一个确定性的替换策略，称为项目块分层分区，并表明它获得了接近该下限的竞争比。此外，我们的边界揭示了一个新的问题，出现在粒度变化缓存问题，在选择的缓存大小的影响不同的在线算法相对于彼此的竞争力。为了解决这个问题，我们扩展了一个先验（时间）局部性模型来考虑空间局部性，并提供了一个一般的下界，除了项目块分层分区的上限。
Caches exploit temporal and spatial locality to allow a small memory to provide fast access to data stored in large, slow memory. The temporal aspect of locality is extremely well studied and understood, but the spatial aspect much less so. We seek to gain an increased understanding of spatial locality by defining and studying the Granularity-Change Caching Problem . This problem modifies the traditional caching setup by grouping data items into blocks, such that a cache can choose any subset of a block to load for the same cost as loading any individual item in the block. We show that modeling such spatial locality significantly changes the caching problem. This begins with a proof that Granularity-Change Caching is NP-Complete in the offline setting, even when all items have unit size and all blocks have unit load cost. In the online setting, we show a lower bound for competitive ratios of deterministic policies that is significantly worse than traditional caching. Moreover, we present a deterministic replacement policy called Item-Block Layered Partitioning and show that it obtains a competitive ratio close to that lower bound. Moreover, our bounds reveal a new issue arising in the Granularity-Change Caching Problem, where the choice of offline cache size affects the competitiveness of different online algorithms relative to one another. To deal with this issue, we extend a prior (temporal) locality model to account for spatial locality, and provide a general lower bound in addition to an upper bound for Item-Block Layered Partitioning.
可变对象大小的最佳缓存的实际界限
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