Rethinking Belady's Algorithm to Accommodate Prefetching
Rethinking Belady's Algorithm to Accommodate Prefetching
复制标题
重新思考 Belady 的算法以适应预取
DOI：
10.1109/isca.2018.00020
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Calvin Lin
中科院分区：
文献类型：
--
作者：
Akanksha Jain;Calvin Lin
本文表明，在存在数据预取器的情况下，缓存替换策略面临着巨大的未开发设计空间。特别是，我们观察到，虽然 Belady 的 MIN 算法最大限度地减少了缓存未命中的总数（包括预取行的总数），但它并没有最大限度地减少了需求未命中的数量。为了解决这个缺点，我们引入了 Demand-MIN，它是 Belady 算法的一种变体，可以以增加预取器流量为代价最大限度地减少需求缺失的数量。 MIN 和 Demand-MIN 一起定义了重要设计空间的边界，它们之间有许多中间点。为了解释这个设计空间，我们引入了一个简单的概念框架，我们用它来定义一个名为 Harmony 的新缓存替换策略。我们的实证评估表明，对于在具有跨步预取器的 4 核系统上运行的 SPEC 2006 基准测试的组合，Harmony 比 LRU 基准提高了 7.7% 的 IPC，而之前最先进的技术提高了 3.7%。在 8 核系统上，Harmony 将 IPC 提高了 9.4%，而之前最先进的 IPC 提高了 4.4%。
This paper shows that in the presence of data prefetchers, cache replacement policies are faced with a large unexplored design space. In particular, we observe that while Belady's MIN algorithm minimizes the total number of cache misses—including those for prefetched lines—it does not minimize the number of demand misses. To address this shortcoming, we introduce Demand-MIN, a variant of Belady's algorithm that minimizes the number of demand misses at the cost of increased prefetcher traffic. Together, MIN and Demand-MIN define the boundaries of an important design space, with many intermediate points lying between them. To reason about this design space, we introduce a simple conceptual framework, which we use to define a new cache replacement policy called Harmony. Our empirical evaluation shows that for a mix of SPEC 2006 benchmarks running on a 4-core system with a stride prefetcher, Harmony improves IPC by 7.7% over an LRU baseline, compared to 3.7% for the previous state-of-the-art. On an 8-core system, Harmony improves IPC by 9.4% compared to 4.4% for the previous state-of-the-art.