A novel migration-based NUCA design for chip multiprocessors

ABSTRACT

Chip Multiprocessors (CMFs) and Non-Uniform Cache Architectures (NUCAs) represent two emerging trends in computer architecture. Targeting future CMP based systems with NUCA type L2 caches, this paper proposes a novel data migration algorithm for parallel applications and evaluates it. The goal of this migration scheme is to determine a suitable location for each data block within a large L2 space at any given point during execution. A unique characteristic of the proposed scheme is that it models the problem of optimal data placement in the L2 cache space as a two-dimensional post office placement problem, presents a practical architectural implementation of this model, and gives a detailed evaluation of the proposed implementation. In our experimental evaluation, we also compare our approach to a previously-proposed NUCA management scheme using applications from the specomp suite, oltp, specjbb, and specweb. These experiments show that our migration approach generates about 35% improvement, on average, in average L2 access latency over the previous migration scheme, and these L2 latency savings translate, on average, to 9.5% improvement in IPC (instructions per cycle). We also observed during our experiments that both the careful initial placement of data (which itself triggers migrations within the L2 space) and subsequent migrations (due to inter-processor data sharing) play an important role in achieving our performance improvements.

REFERENCES

• 1: AMD Athlon 64X2 Dual-Core Processor for Desktop. http://www.amd.com/us-en/Processors/ProductInformation/0,30_118_9485_13041,00.html
• 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 Caching for Chip Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.264-276, June 17-21, 2006
• 5: Zeshan Chishti , Michael D. Powell , T. N. Vijaykumar, Distance Associativity for High-Performance Energy-Efficient Non-Uniform Cache Architectures, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.55, December 03-05, 2003
• 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: Sangyeun Cho , Lei Jin, Managing Distributed, Shared L2 Caches through OS-Level Page Allocation, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.455-468, December 09-13, 2006 [doi>10.1109/MICRO.2006.31]
• 8: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 9: James Donald , Margaret Martonosi, An Efficient, Practical Parallelization Methodology for Multicore Architecture Simulation, IEEE Computer Architecture Letters, v.5 n.2, p.14, July 2006 [doi>10.1109/L-CA.2006.14]
• 10: S. Borkar et al. Platform 2015: Intel processor and platform evolution for the next decade. Technology@Intel Magazine, Mar. 2005.
• 11: Mark Horowitz , Margaret Martonosi , Todd C. Mowry , Michael D. Smith, Informing memory operations: providing memory performance feedback in modern processors, Proceedings of the 23rd annual international symposium on Computer architecture, p.260-270, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 12: Yatin Hoskote , Sriram Vangal , Arvind Singh , Nitin Borkar , Shekhar Borkar, A 5-GHz Mesh Interconnect for a Teraflops Processor, IEEE Micro, v.27 n.5, p.51-61, September 2007 [doi>10.1109/MM.2007.77]
• 13: Jaehyuk Huh , Changkyu Kim , Hazim Shafi , Lixin Zhang , Doug Burger , Stephen W. Keckler, A NUCA substrate for flexible CMP cache sharing, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088154]
• 14: Intel. Quad-Core Intel Xeon Processor 5400 Series. April 2008. http://download.intel.com/design/xeon/datashts/318589.pdf
• 15: Intel Teraflops Machine. http://www.intel.com/idf/.
• 16: 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]
• 17: J. A. Kahle , M. N. Day , H. P. Hofstee , C. R. Johns , T. R. Maeurer , D. Shippy, Introduction to the cell multiprocessor, IBM Journal of Research and Development, v.49 n.4/5, p.589-604, July 2005
• 18: Changkyu Kim , Doug Burger , Stephen W. Keckler, An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 19: 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]
• 20: 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]
• 21: Feihui Li , Chrysostomos Nicopoulos , Thomas Richardson , Yuan Xie , Vijaykrishnan Narayanan , Mahmut Kandemir, Design and Management of 3D Chip Multiprocessors Using Network-in-Memory, Proceedings of the 33rd annual international symposium on Computer Architecture, p.130-141, June 17-21, 2006
• 22: C. Liu, A. Sivasubramaniam, M. Kandemir, and M. J. Irwin. Enhancing L2 organization for CMPs with a center cell. In Proc. the International Parallel and Distributed Processing Symposium, 2006.
• 23: 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]
• 24: M. Kandemir, F. Li, M. J. Irwin, and S. W. Son. A Novel Migration-Based NUCA Design for Chip Multiprocessor. Technical Report CSE-08-013, The Pennsylvania State University, 2008.
• 25: R. McGowen, Adaptive designs for power and thermal optimization, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.118-121, November 06-10, 2005, San Jose, CA
• 26: http://www.tpc.org/
• 27: Kunle Olukotun , Basem A. Nayfeh , Lance Hammond , Ken Wilson , Kunyung Chang, The case for a single-chip multiprocessor, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.2-11, October 01-04, 1996, Cambridge, Massachusetts, United States
• 28: Kiran Puttaswamy , Gabriel H. Loh, Thermal Herding: Microarchitecture Techniques for Controlling Hotspots in High-Performance 3D-Integrated Processors, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.193-204, February 10-14, 2007 [doi>10.1109/HPCA.2007.346197]
• 29: 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]
• 30: 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]
• 31: Evan Speight , Hazim Shafi , Lixin Zhang , Ram Rajamony, Adaptive Mechanisms and Policies for Managing Cache Hierarchies in Chip Multiprocessors, Proceedings of the 32nd annual international symposium on Computer Architecture, p.346-356, June 04-08, 2005
• 32: 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]
• 33: Standard Performance Evaluation Corporation. Specjbb2000 Java business benchmark. http://www.spec.org/osg/jbb2000/, 1998.
• 34: Standard Performance Evaluation Corporation. SPEC OMP. http://www.spec.org/hpg/omp2001/, Dec. 2005.
• 35: Standard Performance Evaluation Corporation. SPECWEB http://www.spec.org/web2005/
• 36: Thomas Y. Yeh , Glenn Reinman, Fast and fair: data-stream quality of service, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086328]
• 37: 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
• 38: Huiyang Zhou, A Case for Fault Tolerance and Performance Enhancement Using Chip Multi-Processors, IEEE Computer Architecture Letters, v.5 n.1, p.6, January 2006 [doi>10.1109/L-CA.2006.1]

INDEX TERMS

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

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

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

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