Simple Penalty-Sensitive Cache Replacement Policies
Simple Penalty-Sensitive Cache Replacement Policies
复制标题
简单的惩罚敏感缓存替换策略
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
M. Dubois
中科院分区：
文献类型：
--
作者：
Jaeheon Jeong;P. Stenström;M. Dubois
传统的高速缓存替换策略假定未命中成本是一致的。然而，未命中率和缓存性能之间的关系不像过去那么直接了。归根结底，未命中的真正性能代价应该是其访问代价，即由于未命中而损失的实际处理带宽。与负载相反，存储的损失大多隐藏在现代处理器中。为了利用这一观察，我们提出了一种简单的方案，将加载未命中替换为存储未命中。我们扩展了LRU(最近最少使用)来减少总的未命中惩罚，而不是未命中计数。新策略称为PS-LRU(惩罚敏感LRU)，并在本文的大部分内容中进行了部署。PS-LRU系统地首先用存储替换预测要被访问的块。该策略最大限度地减少了加载未命中的数量，从而损害了存储未命中。此策略中的一个关键问题是预测块的下一访问类型，以便为下一次使用存储访问的块提供更高的替换优先级。我们介绍和评估了基于指令的各种预测方案，并广泛受到分支预测器的启发。为了指导设计，我们在具有多种缓存配置的八个spec95基准测试上运行了广泛的跟踪驱动模拟，并观察到在大多数基准测试和缓存配置中，PS-LRU比传统LRU产生了积极的加载未命中改进。在某些情况下，改进是非常大的。尽管在我们的简单策略下，加载未命中的总数是最小的，但存储未命中的数量和内存通信量都会增加。此外，商店错过也不是完全“免费”的。为了评估这种权衡，我们将DCL和ACL(两个先前提出的对成本敏感的LRU策略)应用于加载/存储未命中惩罚问题。这些算法比PS-LRU更具竞争力。DCL和ACL都提供了有吸引力的折衷方案，其中比PS-LRU节省了更少的加载未命中，但减少了存储未命中流量。
Classic cache replacement policies assume that miss costs are uniform. However, the correlation between miss rate and cache performance is not as straightforward as it used to be. Ultimately, the true performance cost of a miss should be its access penalty, i.e. the actual processing bandwidth lost because of the miss. Contrary to loads, the penalty of stores is mostly hidden in modern processors. To take advantage of this observation, we propose a simple scheme to replace load misses by store misses. We extend LRU (Least Recently Used) to reduce the aggregate miss penalty instead of the miss count. The new policy is called PS-LRU (Penalty-Sensitive LRU) and is deployed throughout most of this paper. PS-LRU systematically replaces first a block predicted to be accessed with a store next. This policy minimizes the number of load misses to the detriment of store misses. One key issue in this policy is to predict the next access type to a block, so that higher replacement priority is given to blocks that will be accessed next with a store. We introduce and evaluate various prediction schemes based on instructions and broadly inspired from branch predictors. To guide the design we run extensive trace-driven simulations on eight Spec95 benchmarks with a wide range of cache configurations and observe that PS-LRU yield positive load miss improvements over classic LRU across most the benchmarks and cache configurations. In some cases the improvements are very large. Although the total number of load misses is minimized under our simple policy, the number of store misses and the amount of memory traffic both increase. Moreover store misses are not totally "free". To evaluate this trade-off, we apply DCL and ACL (two previously proposed cost-sensitive LRU policies) to the problem of load/store miss penalty. These algorithms are more competitive than PS-LRU. Both DCL and ACL provide attractive trade-offs in which less load misses are saved than in PS-LRU, but the store miss traffic is reduced.