Skip to Main content Skip to Navigation
Conference papers

CRC: Protected LRU Algorithm

Abstract : Additional on-chip transistors as well as more aggressive processors have led the way for an ever expanding memory hierarchy. Multi-core architectures often employ the use of a shared L3 cache to reduce accesses to off chip memory. Such memory structures often incur long latency (as much as 30 cycles in our framework) and are configured to retain sets as large as 16 way. A baseline replacement algorithm that has proven itself over and over again is the Least Recently Used (LRU) policy. This policy seeks to replace lines that were used least recently, which works well thanks to temporal locality. This paper seeks to improve on LRU by taking advantage of the 16 ways available to include a bias for replacement. By keeping track of the relative use of each lines, some frequently used lines may become “protected”. By providing protection for such lines we have managed to reduce the miss rate to 62.89% from LRU's 70.08%. Using a memory reference trace, we also demonstrated that the best replacement algorithm, an oracle which knows about future accesses, could only provide a 58.80% miss rate for our benchmarks.
Document type :
Conference papers
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Thursday, June 17, 2010 - 2:38:29 PM
Last modification on : Wednesday, July 31, 2019 - 1:56:01 PM
Long-term archiving on: : Monday, September 20, 2010 - 5:28:43 PM


Files produced by the author(s)


  • HAL Id : inria-00492945, version 1



yuval Peress, Ian Finlayson, Gary Tyson, David Whalley. CRC: Protected LRU Algorithm. JWAC 2010 - 1st JILP Worshop on Computer Architecture Competitions: cache replacement Championship, Jun 2010, Saint Malo, France. ⟨inria-00492945⟩



Record views


Files downloads