Pseudo-LRU based Cache Partitioning Algorithms

Kamil Kedzierski1, and Miquel Moreto2
Advisors: Francisco J. Cazorla1, and Mateo Valero1

1Barcelona Supercomputing Center, Technical University of Catalonia
2Technical University of Catalonia

Recent studies have shown that cache partitioning is an efficient technique to improve performance in the CMP processors. The cache partitioning algorithms proposed so far assume that the underlying replacement policy is a true LRU. However, the true LRU scheme in highly associative caches, like the L2 caches, introduces a high hardware cost. As a consequence, current high performance processors use other more simple pseudo-LRU replacement algorithms in the L2 cache. Thus, the so far presented cache partitioning solutions cannot be applied in the current real CMP architectures.

In this work, we show the required changes in the hardware components of a cache partitioning algorithm to adapt them to pseudo-LRU algorithms. In particular, we propose a new proŞling technique for the NRU replacement, already implemented in the UltraSPARC T2 processor. The results shows a negligible performance degradation of the presented design with respect to the LRU implementation. We conclude that the shared L2 caches with the NRU replacement policy can be easily extended with the partitioning scheme at the low performance cost.

Long Abstract

Back to Program