Emulating Optimal Replacement with a Shepherd Cache

Proceedings of the International Symposium on Microarchitecture (MICRO-40)
Chicago, Illinois, USA, December 1--5, 2007

Authors

1. Kaushik Rajan, Supercomputer Education and Research Centre
2. R. Govindarajan, Supercomputer Education and Research Centre; Department of Computer Science and Automation

Abstract

The inherent temporal locality in memory accesses is filtered out by the L1 cache. As a consequence, an L2 cache with LRU replacement incurs significantly higher misses than the optimal replacement policy (OPT). We propose to narrow this gap through a novel replacement strategy that mimics the replacement decisions of OPT. The L2 cache is logically divided into two components, a Shepherd Cache (SC) with a simple FIFO replacement and a Main Cache (MC) with an emulation of optimal replacement. The SC plays the dual role of caching lines and guiding the replacement decisions in MC. Our proposed organization can cover 40% of the gap between OPT and LRU for a 2MB cache resulting in 7% overall speedup. Comparison with the dynamic insertion policy, a victim buffer, a V-Way cache and an LRU based fully associative cache demonstrates that our scheme performs better than all these strategies.

Download

Full Text