1CS - Computer science [Panama City] (Florida State University Panama City Computer science 4750 Collegiate Drive Panama City, FL 32405-1099 - United States)
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.
https://hal.inria.fr/inria-00492945 Contributor : Ist RennesConnect 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
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⟩