Adapting cache partitioning algorithms to pseudo-LRU replacement policies
Adapting cache partitioning algorithms to pseudo-LRU replacement policies
复制标题
DOI：
10.1109/ipdps.2010.5470352
复制
发表时间：
2010-04
期刊：
影响因子：
--
通讯作者：
Kamil Kedzierski;Miquel Moretó;F. Cazorla;M. Valero
中科院分区：
文献类型：
--
作者：
Kamil Kedzierski;Miquel Moretó;F. Cazorla;M. Valero
最近的研究表明，缓存分区是一种有效的技术，以提高吞吐量，公平性和服务质量（QoS）的CMP处理器。目前提出的该高速缓存划分算法都假设最近最少使用（LRU）作为底层替换策略。然而，它已被证明，真正的LRU实施时，高关联性高速缓存，如最后一级高速缓存的异常复杂性和面积开销。因此，目前市场上可用的处理器使用伪LRU替换策略，该策略提供与LRU类似的行为，同时降低硬件复杂性。因此，目前提出的基于LRU的高速缓存分区解决方案不能应用于真实的CMP架构。本文提出了一个完整的分区系统的缓存使用伪LRU更换政策。特别是，本文重点介绍了由Sun Microsystems和IBM提出的伪LRU实现，分别称为最近未使用（NRU）和二叉树（BT）。我们提出了一个高精度的分析逻辑和高速缓存分区硬件这两个计划。我们评估我们的建议的硬件成本方面的面积和功率，并比较它们对LRU分区算法。总的来说，本文提出了两种硬件技术，以适应现有的缓存分区算法真实的更换政策。结果表明，我们的解决方案强加的LRU的性能下降可以忽略不计。
Recent studies have shown that cache partitioning is an efficient technique to improve throughput, fairness and Quality of Service (QoS) in CMP processors. The cache partitioning algorithms proposed so far assume Least Recently Used (LRU) as the underlying replacement policy. However, it has been shown that the true LRU imposes extraordinary complexity and area overheads when implemented on high associativity caches, such as last level caches. As a consequence, current processors available on the market use pseudo-LRU replacement policies, which provide similar behavior as LRU, while reducing the hardware complexity. Thus, the presented so far LRU-based cache partitioning solutions cannot be applied to real CMP architectures. This paper proposes a complete partitioning system for caches using the pseudo-LRU replacement policy. In particular, the paper focuses on the pseudo-LRU implementations proposed by Sun Microsystems and IBM, called Not Recently Used (NRU) and Binary Tree (BT), respectively. We propose a high accuracy profiling logic and a cache partitioning hardware for both schemes. We evaluate our proposals' hardware costs in terms of area and power, and compare them against the LRU partitioning algorithm. Overall, this paper presents two hardware techniques to adapt the existing cache partitioning algorithms to real replacement policies. The results show that our solutions impose negligible performance degradation with respect to the LRU.