Adaptive insertion policies for managing shared caches

ABSTRACT

Chip Multiprocessors (CMPs) allow different applications to concurrently execute on a single chip. When applications with differing demands for memory compete for a shared cache, the conventional LRU replacement policy can significantly degrade cache performance when the aggregate working set size is greater than the shared cache. In such cases, shared cache performance can be significantly improved by preserving the entire working set of applications that can co-exist in the cache and preserving some portion of the working set of the remaining applications.

This paper investigates the use of adaptive insertion policies to manage shared caches. We show that directly extending the recently proposed dynamic insertion policy (DIP) is inadequate for shared caches since DIP is unaware of the characteristics of individual applications. We propose Thread-Aware Dynamic Insertion Policy (TADIP) that can take into account the memory requirements of each of the concurrently executing applications. Our evaluation with multi-programmed workloads for 2-core, 4-core, 8-core, and 16-core CMPs show that a TADIP-managed shared cache improves overall throughput by as much as 94%, 64%, 26%, and 16% respectively (on average 14%, 18%, 15%, and 17%) over the baseline LRU policy. The performance benefit of TADIP is 2.6x compared to DIP and 1.3x compared to the recently proposed Utility-based Cache Partitioning (UCP) scheme. We also show that a TADIP-managed shared cache provides performance benefits similar to doubling the size of an LRU-managed cache. Furthermore, TADIP requires a total storage overhead of less than two bytes per core, does not require changes to the existing cache structure, and performs similar to LRU for LRU friendly workloads.

REFERENCES

• 1: Intel Corporation. Next leap in microprocessor architecture: Intel core duo. White paper. http://ces2006.akamai.com.edgesuite.net/yonahassets/CoreDuo_WhitePaper.pdf.
• 2: Hussein Al-Zoubi , Aleksandar Milenkovic , Milena Milenkovic, Performance evaluation of cache replacement policies for the SPEC CPU2000 benchmark suite, Proceedings of the 42nd annual Southeast regional conference, April 02-03, 2004, Huntsville, Alabama [doi>10.1145/986537.986601]
• 3: Jichuan Chang , Gurindar S. Sohi, Cooperative cache partitioning for chip multiprocessors, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1275005]
• 4: Ravi Iyer, CQoS: a framework for enabling QoS in shared caches of CMP platforms, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006246]
• 5: A. Jaleel, R. S. Cohn, C. K. Luk, and B. Jacob. CMP$im: A Pin-Based On-The-Fly Multi-Core Cache Simulator. In MoBS, 2008.
• 6: Ron Kalla , Balaram Sinharoy , Joel M. Tendler, IBM Power5 Chip: A Dual-Core Multithreaded Processor, IEEE Micro, v.24 n.2, p.40-47, March 2004 [doi>10.1109/MM.2004.1289290]
• 7: Seongbeom Kim , Dhruba Chandra , Yan Solihin, Fair Cache Sharing and Partitioning in a Chip Multiprocessor Architecture, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.111-122, September 29-October 03, 2004 [doi>10.1109/PACT.2004.15]
• 8: Poonacha Kongetira , Kathirgamar Aingaran , Kunle Olukotun, Niagara: A 32-Way Multithreaded Sparc Processor, IEEE Micro, v.25 n.2, p.21-29, March 2005 [doi>10.1109/MM.2005.35]
• 9: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 10: K. Luo, J. Gummaraju, and M. Franklin. Balancing throughput and fairness in smt processors. In ISPASS, pages 164--171, 2001.
• 11: Kyle J. Nesbit , James Laudon , James E. Smith, Virtual private caches, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 12: 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
• 13: Moinuddin K. Qureshi , Yale N. Patt, Utility-Based Cache Partitioning: A Low-Overhead, High-Performance, Runtime Mechanism to Partition Shared Caches, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.423-432, December 09-13, 2006 [doi>10.1109/MICRO.2006.49]
• 14: 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
• 15: Santhosh Srinath , Onur Mutlu , Hyesoon Kim , Yale N. Patt, Feedback Directed Prefetching: Improving the Performance and Bandwidth-Efficiency of Hardware Prefetchers, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.63-74, February 10-14, 2007 [doi>10.1109/HPCA.2007.346185]
• 16: Allan Snavely , Dean M. Tullsen, Symbiotic jobscheduling for a simultaneous multithreaded processor, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.234-244, November 2000, Cambridge, Massachusetts, United States
• 17: Harold S. Stone , John Turek , Joel L. Wolf, Optimal Partitioning of Cache Memory, IEEE Transactions on Computers, v.41 n.9, p.1054-1068, September 1992 [doi>10.1109/12.165388]
• 18: G. E. Suh , L. Rudolph , S. Devadas, Dynamic Partitioning of Shared Cache Memory, The Journal of Supercomputing, v.28 n.1, p.7-26, April 2004 [doi>10.1023/B:SUPE.0000014800.27383.8f]
• 19: J. Tendler, S. Dodson, S. Fields, H. Le, and B. Sinharoy. POWER4 system microarchitecture. IBM Technical White Paper, Oct. 2001.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Design, Performance

Keywords:
cache partitioning, replacement, set dueling, shared cache