Divide-and-conquer: a bubble replacement for low level caches

ABSTRACT

The widely used LRU replacement policy suffers from the following problems. First, LRU does not exploit fre-quency information of cache accesses. Second, LRU may experience cache thrashing when access to cache exhibits cyclic patterns and the cache capacity is less than the working set. Finally, LRU is expensive to implement in hardware. We propose a bubble replacement for low-level caches, where cache blocks in one set are arranged in a queue for replacement determination. An incoming block enters the queue from the bottom and exchanges its posi-tion with the block above when the block hits, therefore, both recency and frequency information of a program are exploited. A victim block can be chosen from either the bottom or the top block of the queue, which is controlled by a single-bit set-hit flag per set. Choosing the bottom block as the victim makes the bubble replacement resistant to less frequently used blocks from polluting the cache while choosing the top block as the victim makes the bub-ble replacement adaptable to changes in the working set. We also propose to divide the blocks in a cache set into groups where each group implements the bubble replace-ment (we name it the DC-Bubble) to resolve the problems of the bubble replacement. The victim block is chosen ran-domly from the bottom block of each group. The proposed DC-Bubble reduces the average MPKI of the baseline 1MB 16-way L2 cache by 14%, bridges 47% of the gap between LRU and the OPT, reduces the storage require-ment by 61% and simplifies the circuit design compared to LRU.

REFERENCES

• 1: L. A. Belady. A study of replacement algorithms for virtual storage computers. In IBM Systems Journal, pp. 78--101, 1966.
• 2: D. Burger and T. M. Austin. The SimpleScalar Tool Set, Univ. of Wisconsin-Madison. Technical Report #1342, June 1997.
• 3: Haakon Dybdahl , Per Stenström , Lasse Natvig, An LRU-based replacement algorithm augmented with frequency of access in shared chip-multiprocessor caches, ACM SIGARCH Computer Architecture News, v.35 n.4, September 2007 [doi>10.1145/1327312.1327320]
• 4: Erik G. Hallnor , Steven K. Reinhardt, A fully associative software-managed cache design, Proceedings of the 27th annual international symposium on Computer architecture, p.107-116, June 2000, Vancouver, British Columbia, Canada
• 5: Song Jiang , Xiaodong Zhang, LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 6: Teresa L. Johnson , Daniel A. Connors , Matthew C. Merten , Wen-mei W. Hwu, Run-Time Cache Bypassing, IEEE Transactions on Computers, v.48 n.12, p.1338-1354, December 1999 [doi>10.1109/12.817393]
• 7: Erez Perelman , Greg Hamerly , Michael Van Biesbrouck , Timothy Sherwood , Brad Calder, Using SimPoint for accurate and efficient simulation, ACM SIGMETRICS Performance Evaluation Review, v.31 n.1, June 2003
• 8: Jude A. Rivers , Edward S. Tam , Gary S. Tyson , Edward S. Davidson , Matt Farrens, Utilizing reuse information in data cache management, Proceedings of the 12th international conference on Supercomputing, p.449-456, July 1998, Melbourne, Australia [doi>10.1145/277830.277941]
• 9: C. T. Weaver. Pre-compiled SPEC2000 Alpha Binaries. Available at: http://www.simplescalar.org.
• 10: Donghee Lee , Jongmoo Choi , Jong-Hun Kim , Sam H. Noh , Sang Lyul Min , Yookun Cho , Chong Sang Kim, On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.134-143, May 01-04, 1999, Atlanta, Georgia, United States
• 11: Mazen Kharbutli , Yan Solihin, Counter-Based Cache Replacement and Bypassing Algorithms, IEEE Transactions on Computers, v.57 n.4, p.433-447, April 2008 [doi>10.1109/TC.2007.70816]
• 12: W. Wong and J.-L. Baer, Modified LRU Policies for Improving Second-Level Cache Behavior, In HPCA-6, 2000.
• 13: David A. Wood , Mark D. Hill , R. E. Kessler, A model for estimating trace-sample miss ratios, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.79-89, May 21-24, 1991, San Diego, California, United States
• 14: http://users.ece.utexas.edu/~qk/dip/.
• 15: http://users.ece.utexas.edu/~qk/mlp/.
• 16: http://www.patentstorm.us/patents/6240489/description.html
• 17: http://www.cse.ucsd.edu/~calder/simpoint/points/standard/spec2000-multiple-std-100M.html.
• 18: Nimrod Megiddo , Dharmendra S. Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 19: Erez Perelman , Greg Hamerly , Michael Van Biesbrouck , Timothy Sherwood , Brad Calder, Using SimPoint for accurate and efficient simulation, ACM SIGMETRICS Performance Evaluation Review, v.31 n.1, June 2003
• 20: Moinuddin K. Qureshi , Daniel N. Lynch , Onur Mutlu , Yale N. Patt, A Case for MLP-Aware Cache Replacement, Proceedings of the 33rd annual international symposium on Computer Architecture, p.167-178, June 17-21, 2006
• 21: Moinuddin K. Qureshi , Aamer Jaleel , Yale N. Patt , Simon C. Steely , Joel Emer, Adaptive insertion policies for high performance caching, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 22: John T. Robinson , Murthy V. Devarakonda, Data cache management using frequency-based replacement, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.134-142, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 23: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 24: Kimming So , Rudolph N. Rechtschaffen, Cache Operations by MRU Change, IEEE Transactions on Computers, v.37 n.6, p.700-709, June 1988 [doi>10.1109/12.2208]
• 25: Ranjith Subramanian , Yannis Smaragdakis , Gabriel H. Loh, Adaptive Caches: Effective Shaping of Cache Behavior to Workloads, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.385-396, December 09-13, 2006 [doi>10.1109/MICRO.2006.7]
• 26: Standard Performance Evaluation Corporation, http://www.specbench.org/osg/cpu2000/.
• 27: W. Wong and J.-L. Baer, Modified LRU Policies for Improving Second-Level Cache Behavior, In HPCA-6, 2000.
• 28: Yuanyuan Zhou , James Philbin , Kai Li, The Multi-Queue Replacement Algorithm for Second Level Buffer Caches, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.91-104, June 25-30, 2001

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

General Terms:
Design, Measurement, Performance

Keywords:
cache replacement policy, divide-and-conquer, high-performance computing