Blast from the Past: Least Expected Use (LEU) Cache Replacement with Statistical History
Blast from the Past: Least Expected Use (LEU) Cache Replacement with Statistical History
复制标题
DOI：
10.1145/3591195.3595267
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Sayak Chakraborti;Zhizhou Zhang;Noah Bertram;C. Ding;S. Dwarkadas
中科院分区：
文献类型：
--
作者：
Sayak Chakraborti;Zhizhou Zhang;Noah Bertram;C. Ding;S. Dwarkadas
缓存替换策略通常对过去的访问行为使用某种形式的统计信息。然而，作为一个常见的限制，记录的历史记录的范围要么仅限于缓存中的数据，要么限于最近的更大但仍然有限长度的访问窗口，因为保持长历史记录的成本很容易超过它的好处。本文提出了一种统计方法来跟踪任意长度的基于指令指针的访问重用间隔，并利用这些信息来识别需要替换的最小期望使用（LEU）块。LEU使用由新型硬件支持的动态采样，保持状态以记录任意长的重用间隔。LEU使用Cache Replacement Championship模拟器进行评估，在PolyBench和SPEC上进行测试，并与五种策略进行比较，包括最近使用固定长度历史记录近似最佳缓存的技术。通过维护任意历史的统计数据，LEU在广泛的科学内核中优于以前的技术，这些技术的数据重用时间比计算机体系结构研究中传统使用的跟踪时间长。
Cache replacement policies typically use some form of statistics on past access behavior. As a common limitation, however, the extent of the history being recorded is limited to either just the data in cache or, more recently, a larger but still finite-length window of accesses, because the cost of keeping a long history can easily outweigh its benefit. This paper presents a statistical method to keep track of instruction pointer-based access reuse intervals of arbitrary length and uses this information to identify the Least Expected Use (LEU) blocks for replacement. LEU uses dynamic sampling supported by novel hardware that maintains a state to record arbitrarily long reuse intervals. LEU is evaluated using the Cache Replacement Championship simulator, tested on PolyBench and SPEC, and compared with five policies including a recent technique that approximates optimal caching using a fixed-length history. By maintaining statistics for an arbitrary history, LEU outperforms previous techniques for a broad range of scientific kernels, whose data reuses are longer than those in traces traditionally used in computer architecture studies.