Writeback-Aware Caching
Writeback-Aware Caching
复制标题
DOI：
10.1137/1.9781611976021.1
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Nathan Beckmann;Phillip B. Gibbons;Bernhard Haeupler;Charles McGuffey
中科院分区：
文献类型：
--
作者：
Nathan Beckmann;Phillip B. Gibbons;Bernhard Haeupler;Charles McGuffey
关于缓存替代的文献，虽然详细且广泛地忽略了以新兴记忆技术和记忆带宽和能源消耗的重要性来解释数据流的文献。了解缓存问题。此外，我们表明，最佳的确定性策略忽略了（ω + 1），即使是对问题的简单变体，这些负面结果也很难。数据项具有单位尺寸，单位遗漏成本和单位写入成本（ω= 1）。确定性的替代政策称为写入的房东，并表明它获得了最佳竞争比率。最终，我们对现实世界的痕迹进行了一项实验性研究，表明当写作昂贵时，书面知觉的房东胜过最先进的缓存策略，从而说明了明显的书面记录。
The literature on cache replacement, while both detailed and extensive, neglects to account for the flow of data to storage . Motivated by emerging memory technologies and the increasing importance of memory bandwidth and energy consumption, we seek to fill this gap by studying the Writeback-Aware Caching Problem . This problem modifies traditional caching problems by explicitly accounting for the cost of writing modified data back to memory on eviction. In the offline setting with maximum writeback cost ω > 0, we show that writeback-aware caching is NP-complete and Max-SNP hard. Moreover, we show that Furthest-in-the-Future, the optimal deterministic policy when ignoring writebacks, is only ( ω + 1)-competitive. These negative results hold even for the simple variant of the problem in which data items have unit size, unit miss cost, and unit writeback cost ( ω = 1). To overcome this difficulty, we provide practical algorithms to compute upper and lower bounds for the optimal policy on real traces. In the online setting, we present a deterministic replacement policy called Writeback-Aware Landlord and show that it obtains the optimal competitive ratio. Our bounds on the optimal offline policy and our optimal competitive ratio hold even for the most general variant in which data items have variable sizes, variable miss costs, and variable writeback costs. Finally, we perform an experimental study on real-world traces showing that Writeback-Aware Landlord outperforms state-of-the-art cache replacement policies when writebacks are costly, thereby illustrating the practical gains of explicitly accounting for writebacks.