Less reused filter: improving l2 cache performance via filtering less reused lines

ABSTRACT

The L2 cache is commonly managed using LRU policy. For workloads that have a working set larger than L2 cache, LRU behaves poorly, resulting in a great number of less reused lines that are never reused or reused for few times. In this case, the cache performance can be improved through retaining a portion of working set in cache for a period long enough. Previous schemes approach this by bypassing never reused lines. Nevertheless, severely constrained by the number of never reused lines, sometimes they deliver no benefit due to the lack of never reused lines.

This paper proposes a new filtering mechanism that filters out the less reused lines rather than just never reused lines. The extended scope of bypassing provides more opportunities to fit the working set into cache. This paper also proposes a Less Reused Filter (LRF), a separate structure that precedes L2 cache, to implement the above mechanism. LRF employs a reuse frequency predictor to accurately identify the less reused lines from incoming lines. Meanwhile, based on our observation that most less reused lines have a short life span, LRF places the filtered lines into a small filter buffer to fully utilize them, avoiding extra misses.

Our evaluation, for 24 SPEC 2000 benchmarks, shows that augmenting a 512KB LRU-managed L2 cache with a LRF having 32KB filter buffer reduces the average MPKI by 27.5%, narrowing the gap between LRU and OPT by 74.4%.

REFERENCES

• 1: Arkaprava Basu , Nevin Kirman , Meyrem Kirman , Mainak Chaudhuri , Jose Martinez, Scavenger: A New Last Level Cache Architecture with Global Block Priority, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.421-432, December 01-05, 2007 [doi>10.1109/MICRO.2007.36]
• 2: L. A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems journal, pages 78--101, 1966.
• 3: Haakon Dybdahl , Per Stenström , Lasse Natvig, An LRU-based replacement algorithm augmented with frequency of access in shared chip-multiprocessor caches, Proceedings of the 2006 workshop on MEmory performance: DEaling with Applications, systems and architectures, p.45-52, September 16-20, 2006, Seattle, Washington [doi>10.1145/1166133.1166139]
• 4: Masamichi Takagi , Kei Hiraki, Inter-reference gap distribution replacement: an improved replacement algorithm for set-associative caches, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006213]
• 5: 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]
• 6: W. A. Wong and J.-L. Baer. Modified lru policies for improving second-level cache behavior. In HPCA-6, 2000.
• 7: Kaushik Rajan , Govindarajan Ramaswamy, Emulating Optimal Replacement with a Shepherd Cache, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.445-454, December 01-05, 2007 [doi>10.1109/MICRO.2007.14]
• 8: 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
• 9: A. González, C. Aliagas, and M. Valero. A data cache with multiple caching strategies tuned to different types of locality. In ICS-9, 1995.
• 10: Moinuddin K. Qureshi , David Thompson , Yale N. Patt, The V-Way Cache: Demand Based Associativity via Global Replacement, Proceedings of the 32nd annual international symposium on Computer Architecture, p.544-555, June 04-08, 2005
• 11: Yannis Smaragdakis , Scott Kaplan , Paul Wilson, The EELRU adaptive replacement algorithm, Performance Evaluation, v.53 n.2, p.93-123, July 2003 [doi>10.1016/S0166-5316(02)00226-2]
• 12: Koji Inoue , Tohru Ishihara , Kazuaki Murakami, Way-predicting set-associative cache for high performance and low energy consumption, Proceedings of the 1999 international symposium on Low power electronics and design, p.273-275, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313948]
• 13: Brad Calder , Dirk Grunwald, Next cache line and set prediction, Proceedings of the 22nd annual international symposium on Computer architecture, p.287-296, June 22-24, 1995, S. Margherita Ligure, Italy
• 14: Zhigang Hu , Stefanos Kaxiras , Margaret Martonosi, Timekeeping in the memory system: predicting and optimizing memory behavior, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 15: An-Chow Lai , Cem Fide , Babak Falsafi, Dead-block prediction & dead-block correlating prefetchers, Proceedings of the 28th annual international symposium on Computer architecture, p.144-154, June 30-July 04, 2001, Göteborg, Sweden
• 16: P. Pujara and A. Aggarwal. Increasing the cache efficiency by eliminating noise. In HPCA-12, 2006.
• 17: W. Lin and S. Reinhardt. Predicting last-touch references under optimal replacement. Technical Report CSE-TR-447-02, University of Michigan, 2002.
• 18: Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.297-306, May 25-28, 1993, Washington, D.C., United States
• 19: Thomas Roberts Puzak, Analysis of cache replacement-algorithms, University of Massachusetts Amherst, 1985
• 20: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 21: D. Lee , J. Choi , J. H. Kim , S. H. Noh , S. L. Min , Y. Cho , C. S. Kim, LRFU: A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies, IEEE Transactions on Computers, v.50 n.12, p.1352-1361, December 2001 [doi>10.1109/TC.2001.970573]
• 22: Haiming Liu , Michael Ferdman , Jaehyuk Huh , Doug Burger, Cache bursts: A new approach for eliminating dead blocks and increasing cache efficiency, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.222-233, November 08-12, 2008 [doi>10.1109/MICRO.2008.4771793]
• 23: 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
• 24: Jaume Abella , Antonio González , Xavier Vera , Michael F. P. O'Boyle, IATAC: a smart predictor to turn-off L2 cache lines, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.1, p.55-77, March 2005 [doi>10.1145/1061267.1061271]
• 25: Mazen Kharbutli , Yan Solihin, Counter-Based Cache Replacement Algorithms, Proceedings of the 2005 International Conference on Computer Design, p.61-68, October 02-05, 2005 [doi>10.1109/ICCD.2005.41]
• 26: 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
• 27: C.-H. Chi and H. Dietz. Improving cache performance by selective cache bypass. System Sciences, 1989. Vol.I: Architecture Track, Proceedings of the Twenty-Second Annual Hawaii International Conference on, 1:277--285 vol.1, 1989.
• 28: Youfeng Wu , Ryan Rakvic , Li-Ling Chen , Chyi-Chang Miao , George Chrysos , Jesse Fang, Compiler managed micro-cache bypassing for high performance EPIC processors, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 29: J. Rivers and E. Davidson. Reducing conflicts in direct-mapped caches with a temporality-based design. In ICPP'96, 1996.
• 30: Teresa L. Johnson , Wen-mei W. Hwu, Run-time adaptive cache hierarchy management via reference analysis, Proceedings of the 24th annual international symposium on Computer architecture, p.315-326, June 01-04, 1997, Denver, Colorado, United States
• 31: 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]
• 32: Yoav Etsion , Dror G. Feitelson, L1 Cache Filtering Through Random Selection of Memory References, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.235-244, September 15-19, 2007 [doi>10.1109/PACT.2007.44]
• 33: Edward S. Tam , Jude A. Rivers , Vijayalakshmi Srinivasan , Gary S. Tyson , Edward S. Davidson, Active Management of Data Caches by Exploiting Reuse Information, IEEE Transactions on Computers, v.48 n.11, p.1244-1259, November 1999 [doi>10.1109/12.811113]
• 34: J. Jalminger and P. Stenstrom. A novel approach to cache block reuse predictions. In ICPP'03, 2003.
• 35: Sanjeev Kumar , Christopher Wilkerson, Exploiting spatial locality in data caches using spatial footprints, Proceedings of the 25th annual international symposium on Computer architecture, p.357-368, June 27-July 02, 1998, Barcelona, Spain
• 36: 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

INDEX TERMS

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

General Terms:
Design, Performance

Keywords:
cache filtering, less reused line