MCAMP: communication optimization on massively parallel machines with hierarchical scratch-pad memory

ABSTRACT

Massively parallel machines that integrate a large number of simple processors and small scratch-pad memories (SPMs) into a single chip can achieve a high peak performance per watt of power. In these machines, communication optimizations are important because the communication bandwidth tends to be a bottleneck. Previously proposed communication optimizations using copy candidates, which have been shown to be effective, detect frequently reused array regions by compile-time analysis and copy the regions to scratch-pad memories nearer to the processors. However, they have been proposed for uniprocessor systems or small parallel machines with one or more layers of scratch-pad memories, and the analysis time increases when they are applied to massively parallel machines. In this paper, we propose Multilayer Copy-candidate Analysis for Massively Parallel machines (MCAMP), a communication optimization method for massively parallel machines. MCAMP re-formalizes the framework used in earlier works and improves the scalability of the analysis by assuming the homogeneity of the target systems. We implemented an MCAMP optimizer, which takes an input program that consists of perfectly nested loops containing array references and computation codes, and generates optimized communication. We measured the performance of the output programs of the MCAMP optimizer by executing them on a real massively parallel machine GRAPE-DR using a software tool chain that we also implemented. We showed that MCAMP can achieve optimal data transfer patterns and comparable performance to that of hand-optimized codes with a short analysis time.

REFERENCES

• 1: lp_solve. version 5.5.0.11 http://sourceforge.net/projects/lpsolve.
• 2: Javed Absar , Francky Catthoor, Reuse analysis of indirectly indexed arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.2, p.282-305, April 2006 [doi>10.1145/1142155.1142157]
• 3: Preston Briggs , Keith D. Cooper , Linda Torczon, Coloring register pairs, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.3-13, March 1992 [doi>10.1145/130616.130617]
• 4: E. Brockmeyer , M. Miranda , H. Corporaal , F. Catthoor, Layer Assignment echniques for Low Energy in Multi-Layered Memory Organisations, Proceedings of the conference on Design, Automation and Test in Europe, p.11070, March 03-07, 2003
• 5: J. Ph. Diguet , S. Wuytack , F. Catthoor , H. De Man, Formalized methodology for data reuse exploration in hierarchical memory mappings, Proceedings of the 1997 international symposium on Low power electronics and design, p.30-35, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263278]
• 6: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiler optimizations for Fortran D on MIMD distributed-memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.86-100, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125886]
• 7: Ilya Issenin , Erik Brockmeyer , Bart Durinck , Nikil Dutt, Multiprocessor system-on-chip data reuse analysis for exploring customized memory hierarchies, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146925]
• 8: Ilya Issenin , Erik Brockmeyer , Miguel Miranda , Nikil Dutt, DRDU: A data reuse analysis technique for efficient scratch-pad memory management, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.2, p.15-es, April 2007 [doi>10.1145/1230800.1230807]
• 9: Ilya Issenin , Nikil Dutt, Data reuse driven energy-aware MPSoC co-synthesis of memory and communication architecture for streaming applications, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176326]
• 10: M. Kandemir , A. Choudhary, Compiler-directed scratch pad memory hierarchy design and management, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514077]
• 11: J. Li , M. Chen, Compiling Communication-Efficient Programs for Massively Parallel Machines, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.361-376, July 1991 [doi>10.1109/71.86111]
• 12: Junichiro Makino , Kei Hiraki , Mary Inaba, GRAPE-DR: 2-Pflops massively-parallel computer with 512-core, 512-Gflops processor chips for scientific computing, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362647]
• 13: Ozcan Ozturk , Mahmut Kandemir , Mary Jane Irwin , Suleyman Tosun, Multi-Level On-Chip Memory Hierarchy Design for Embedded Chip Multiprocessors, Proceedings of the 12th International Conference on Parallel and Distributed Systems, p.383-390, July 12-15, 2006 [doi>10.1109/ICPADS.2006.66]
• 14: T. Van Achteren , G. Deconinck , F. Catthoor , R. Lauwereins, Data Reuse Exploration Techniques for Loop-Dominated Applications, Proceedings of the conference on Design, automation and test in Europe, p.428, March 04-08, 2002

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

General Terms:
Algorithms, Performance

Keywords:
GRAPE-DR, copy candidates, massively parallel architecture, memory hierarchy, scratch-pad memory management