Adaptive set pinning: managing shared caches in chip multiprocessors

ABSTRACT

As part of the trend towards Chip Multiprocessors (CMPs) for the next leap in computing performance, many architectures have explored sharing the last level of cache among different processors for better performance-cost ratio and improved resource allocation. Shared cache management is a crucial CMP design aspect for the performance of the system. This paper first presents a new classification of cache misses - CII: Compulsory, Inter-processor and Intra-processor misses - for CMPs with shared caches to provide a better understanding of the interactions between memory transactions of different processors at the level of shared cache in a CMP. We then propose a novel approach, called set pinning, for eliminating inter-processor misses and reducing intra-processor misses in a shared cache. Furthermore, we show that an adaptive set pinning scheme improves over the benefits obtained by the set pinning scheme by significantly reducing the number of off-chip accesses. Extensive analysis of these approaches with SPEComp 2001 benchmarks is performed using a full system simulator. Our experiments indicate that the set pinning scheme achieves an average improvement of 22.18% in the L2 miss rate while the adaptive set pinning scheme reduces the miss rates by an average of 47.94% as compared to the traditional shared cache scheme. They also improve the performance by 7.24% and 17.88% respectively.

REFERENCES

• 1: Vishal Aslot , Max J. Domeika , Rudolf Eigenmann , Greg Gaertner , Wesley B. Jones , Bodo Parady, SPEComp: A New Benchmark Suite for Measuring Parallel Computer Performance, Proceedings of the International Workshop on OpenMP Applications and Tools: OpenMP Shared Memory Parallel Programming, p.1-10, July 30-31, 2001
• 2: Bradford M. Beckmann , Michael R. Marty , David A. Wood, ASR: Adaptive Selective Replication for CMP Caches, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.443-454, December 09-13, 2006 [doi>10.1109/MICRO.2006.10]
• 3: Bradford M. Beckmann , David A. Wood, Managing Wire Delay in Large Chip-Multiprocessor Caches, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.319-330, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.21]
• 4: 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]
• 5: Jichuan Chang , Gurindar S. Sohi, Cooperative Caching for Chip Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.264-276, June 17-21, 2006
• 6: Zeshan Chishti , Michael D. Powell , T. N. Vijaykumar, Optimizing Replication, Communication, and Capacity Allocation in CMPs, Proceedings of the 32nd annual international symposium on Computer Architecture, p.357-368, June 04-08, 2005
• 7: Jamison D. Collins , Dean M. Tullsen, Runtime identification of cache conflict misses: The adaptive miss buffer, ACM Transactions on Computer Systems (TOCS), v.19 n.4, p.413-439, November 2001 [doi>10.1145/502912.502913]
• 8: Michel Dubois , Jonas Skeppstedt , Livio Ricciulli , Krishnan Ramamurthy , Per Stenström, The detection and elimination of useless misses in multiprocessors, Proceedings of the 20th annual international symposium on Computer architecture, p.88-97, May 16-19, 1993, San Diego, California, United States
• 9: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 10: Mark Donald Hill , Alan Jay Smith, Aspects of cache memory and instruction buffer performance, University of California, Berkeley, 1987
• 11: M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
• 12: Lisa Hsu , Ravi Iyer , Srihari Makineni , Steve Reinhardt , Donald Newell, Exploring the cache design space for large scale CMPs, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005 [doi>10.1145/1105734.1105739]
• 13: 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
• 14: 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]
• 15: 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]
• 16: Chun Liu , Anand Sivasubramaniam , Mahmut Kandemir, Organizing the Last Line of Defense before Hitting the Memory Wall for CMPs, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.176, February 14-18, 2004 [doi>10.1109/HPCA.2004.10017]
• 17: Jiwei Lu , Abhinav Das , Wei-Chung Hsu , Khoa Nguyen , Santosh G. Abraham, Dynamic Helper Threaded Prefetching on the Sun UltraSPARC CMP Processor, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.93-104, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.18]
• 18: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 19: Gokhan Memik , Glenn Reinman , William H. Mangione-Smith, Just Say No: Benefits of Early Cache Miss Determination, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.307, February 08-12, 2003
• 20: Gokhan Memik , Glenn Reinman , William H. Mangione-Smith, Reducing energy and delay using efficient victim caches, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871571]
• 21: P. Petoumenos, G. Keramidas, H. Zeffer, S. Kaxiras, and E. Hagersten. Modeling cache sharing on chip multiprocessor architectures. In Proc. of the IEEE International Symposium on Workload Characterization, 2006.
• 22: 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]
• 23: Nauman Rafique , Won-Taek Lim , Mithuna Thottethodi, Architectural support for operating system-driven CMP cache management, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152160]
• 24: X. Shi, Z. Yang, J. Peir, L. Peng, Y.-K. Chen, Lee, and Liang. Coterminous locality and coterminous group data prefetching on chipmultiprocessors. In Proc. of the 20th International Parallel and Distributed Processing Symposium, Rhodes Island, 2006.
• 25: B. Sinharoy , R. N. Kalla , J. M. Tendler , R. J. Eickemeyer , J. B. Joyner, POWER5 System microarchitecture, IBM Journal of Research and Development, v.49 n.4/5, p.505-521, July 2005
• 26: B. Sonah , M. R. Ito, Modeling Rate-Based Dynamic Cache Sharing for Distributed VOD Systems, Proceedings of the The International Conference on Information Technology: Coding and Computing (ITCC'00), p.489, March 27-29, 2000
• 27: Lawrence Spracklen , Yuan Chou , Santosh G. Abraham, Effective Instruction Prefetching in Chip Multiprocessors for Modern Commercial Applications, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.225-236, February 12-16, 2005 [doi>10.1109/HPCA.2005.13]
• 28: Rabin Andrew Sugumar, Multi-configuration simulation algorithms for the evaluation of computer architecture designs, University of Michigan, Ann Arbor, MI, 1993
• 29: Rabin A. Sugumar , Santosh G. Abraham, Efficient simulation of caches under optimal replacement with applications to miss characterization, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.24-35, May 10-14, 1993, Santa Clara, California, United States
• 30: 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]
• 31: D. Tam, R. Azimi, L. Soares, and M. Stumm. Managing shared l2 caches on multicore systems in software. In Proc. of the Workshop on the Interaction between Operating Systems and Computer Architecture, San Diego, 2007.
• 32: Nigel Topham , Antonio González , José González, The design and performance of a conflict-avoiding cache, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.71-80, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 33: Hans Vandierendonck , Philippe Manet , Jean-Didier Legat, Application-specific reconfigurable XOR-indexing to eliminate cache conflict misses, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 34: Alaa R. Alameldeen , David A. Wood, Interactions Between Compression and Prefetching in Chip Multiprocessors, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.228-239, February 10-14, 2007 [doi>10.1109/HPCA.2007.346200]
• 35: Chuanjun Zhang, Balanced Cache: Reducing Conflict Misses of Direct-Mapped Caches, Proceedings of the 33rd annual international symposium on Computer Architecture, p.155-166, June 17-21, 2006
• 36: Michael Zhang , Krste Asanovic, Victim Replication: Maximizing Capacity while Hiding Wire Delay in Tiled Chip Multiprocessors, Proceedings of the 32nd annual international symposium on Computer Architecture, p.336-345, June 04-08, 2005

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.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Algorithms, Design, Experimentation, Management, Performance

Keywords:
CMP, inter-processor, intra-processor, set pinning, shared cache