Model-guided autotuning of high-productivity languages for petascale computing

ABSTRACT

addresses the enormous complexity of mapping applications to current and future highly parallel platforms - including scalable architectures consisting of tens of thousands of nodes, many-core devices with tens to hundreds of cores, and hierarchical systems providing multi-level parallelism. At systems of these scales, for many important algorithms, performance is dominated by the time required to move data across the levels of the memory hierarchy. As a consequence, locality awareness of algorithms and the efficient management of communication are essential requirements for obtaining scalable parallel performance, and are of particular concern for applications characterized by irregular memory access patterns. We describe the design of a programming system that focuses on productivity of application programmers in expressing locality-aware algorithms for high-end architectures, which are then automatically tuned for performance. The approach combines the successes of two novel concepts for managing locality: high-level specification of user-defined data distributions and model-guided autotuning for data locality. The resulting combined system provides a powerful general mechanism for the specification of data distributions, which can express domain-specific knowledge, and facilitates automatic tuning of a distribution to access patterns in algorithms and its application to different levels of a memory hierarchy. Because there is a clean separation between the specification of a data distribution and the algorithms in which it is used, these can be written separately and composed together to quickly develop new applications that can be tuned in the context of their data set and execution environment. We address key issues for a range of codes that include LU Decomposition, Sparse Matrix-Vector Multiply and Knowledge Discovery. The knowledge discovery algorithms, in particular, stress the proposed language and compiler technology and provide a forcing function for developing tools that address inherent challenges of irregular applications.}

REFERENCES

• 1: Jafar Adibi , Tim Barrett , Spundun Bhatt , Hans Chalupsky , Jacqueline Chame , Mary Hall, Processing-in-memory technology for knowledge discovery algorithms, Proceedings of the 2nd international workshop on Data management on new hardware, June 25-25, 2006, Chicago, Illinois [doi>10.1145/1140402.1140405]
• 2: S. Benkner, G. Lonsdale, and H. Zima. The HPF+ Project: Supporting HPF for Advanced Industrial Applications. Springer Verlag, Toulouse, France, August 1999.
• 3: Siegfried Benkner , Piyush Mehrotra , John Van Rosendale , Hans Zima, High-level management of communication schedules in HPF-like languages, Proceedings of the 12th international conference on Supercomputing, p.109-116, July 1998, Melbourne, Australia [doi>10.1145/277830.277855]
• 4: S. Benkner and M. Pantano. HPF+: Optimizing HPF for Advanced Applications. Supercomputer, 13(2):31-43, 1997.
• 5: Siegfried Benkner , Hans Zima, Compiling high performance Fortran for distributed-memory architectures, Parallel Computing, v.25 n.13-14, p.1785-1825, Dec. 1999 [doi>10.1016/S0167-8191(99)00074-5]
• 6: Siegfried Benkner. Optimizing irregular HPF applications using halos. Concurrency - Practice and Experience, 12(2-3):137-155, 2000.
• 7: M. J. Berger , S. H. Bokhari, A Partitioning Strategy for Nonuniform Problems on Multiprocessors, IEEE Transactions on Computers, v.36 n.5, p.570-580, May 1987 [doi>10.1109/TC.1987.1676942]
• 8: Jeff Bilmes , Krste Asanovic , Chee-Whye Chin , Jim Demmel, Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology, Proceedings of the 11th international conference on Supercomputing, p.340-347, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263662]
• 9: B.L. Chamberlain , D. Callahan , H.P. Zima, Parallel Programmability and the Chapel Language, International Journal of High Performance Computing Applications, v.21 n.3, p.291-312, August 2007 [doi>10.1177/1094342007078442]
• 10: Barbara Chapman , Piyush Mehrotra , Hans Zima, Programming in Vienna Fortran, Scientific Programming, v.1 n.1, p.31-50, January 1992
• 11: Chun Chen , Mary Hall, Model-guided empirical optimization for memory hierarchy, University of Southern California, Los Angeles, CA, 2007
• 12: C. Chen, J. Chame, and M. Hall. Chill: A framework for composing high-level loop transformations. Technical report, University of Southern California, June 2008. Tech Report Number 08-897.
• 13: C. Chen, J. Shin, S. Kintali, J. Chame, and M. Hall. Model-guided empirical optimization for multimedia extension architectures: A case study. In Proceedings of the Workshop on Performance Optimizatoin of High-Level Languages, held in conjunction with IPDPS '07, March 2007.
• 14: Chun Chen , Jacqueline Chame , Mary Hall, Combining Models and Guided Empirical Search to Optimize for Multiple Levels of the Memory Hierarchy, Proceedings of the international symposium on Code generation and optimization, p.111-122, March 20-23, 2005 [doi>10.1109/CGO.2005.10]
• 15: Chun Chen, Jacqueline Chame, and Mary W. Hall. A systematic approach to model-guided empirical search for memory hiearchy optimization. In Proceedings of the 18th International Workshop on Languages and Compilers for Parallel Computing, October 2005.
• 16: Albert Cohen , Marc Sigler , Sylvain Girbal , Olivier Temam , David Parello , Nicolas Vasilache, Facilitating the search for compositions of program transformations, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088169]
• 17: Roxana E. Diaconescu and Hans P. Zima. A new approach to Locality Awareness in High Productivity languages. Technical report, Jet Propulsion Laboratory, California Institute of Technology, May 2006. New Technology Report 44028.
• 18: Roxana E. Diaconescu and Hans P. Zima. Locality Awareness in a High-Productivity Language, pages 463-485. Chapman and Hall/CRC Press, 2008. Chapter 22.
• 19: Kemal Ebcioglu, Vijay Saraswat, and Vivek Sarkar. X10: Programming for hierarchical parallelism and non-uniform data access. In 3rd International Workshop on Language Runtimes, ACM OOPSLA 2004, Vancouver, BC, October 2004.
• 20: Geoffrey Fox, Seema Hiranandani, Ken Kennedy, Charles Koelbel, Ulrich Kremer, Chau-Wen Tseng, and M.-Y. Wu. Fortran D language specification. Technical Report CRPC-TR90079, Rice University, Center for Research on Parallel Computation, Houston, TX, December 1990.
• 21: Matteo Frigo, A fast Fourier transform compiler, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.169-180, May 01-04, 1999, Atlanta, Georgia, United States
• 22: William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI (2nd ed.): portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1999
• 23: High Performance Fortran Forum. HPF-2 scope of work and motivating applications. Technical Report CRPC-TR 94492, Rice University, Department of Computer Science, Houston, TX, 1994.
• 24: High Performance Fortran Forum. High Performance Fortran Language Specification, January 1997.
• 25: Parry Husbands , Costin Iancu , Katherine Yelick, A performance analysis of the Berkeley UPC compiler, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782825]
• 26: C. R. Johns , D. A. Brokenshire, Introduction to the cell broadband engine architecture, IBM Journal of Research and Development, v.51 n.5, p.503-519, September 2007
• 27: Ken Kennedy , Charles Koelbel , Hans Zima, The rise and fall of High Performance Fortran: an historical object lesson, Proceedings of the third ACM SIGPLAN conference on History of programming languages, p.7-1-7-22, June 09-10, 2007, San Diego, California [doi>10.1145/1238844.1238851]
• 28: Piyush Mehrotra , John Van Rosendale , Hans Zima, High performance Fortran: history, status and future, Parallel Computing, v.24 n.3-4, p.325-354, May, 1998 [doi>10.1016/S0167-8191(98)00016-7]
• 29: Manuel Ujaldon , Emilio L. Zapata , Barbara M. Chapman , Hans P. Zima, Vienna-Fortran/HPF Extensions for Sparse and Irregular Problems and Their Compilation, IEEE Transactions on Parallel and Distributed Systems, v.8 n.10, p.1068-1083, October 1997 [doi>10.1109/71.629489]
• 30: Robert W. Numrich , John Reid, Co-array Fortran for parallel programming, ACM SIGPLAN Fortran Forum, v.17 n.2, p.1-31, Aug. 1998 [doi>10.1145/289918.289920]
• 31: Markus Püschel, José M. F. Moura, Jeremy R. Johnson, David Padua, Manuela M. Veloso, Bryan W. Singer, Jianxin Xiong, Franz Franchetti, Aca Ga¿ic, Yevgen Voronenko, Kang Chen, Robert W. Johnson, and Nicholas Rizzolo. SPIRAL: Code generation for DSP transforms. Proceedings of the IEEE: Special Issue on Program Generation, Optimization, and Platform Adaptation, 93(2):232-275, February 2005.
• 32: A. Tiwari, C. Chen, J. Chame, M. Hall, and J. Hollingsworth. Scalable autotuning framework for compiler optimization. In IEEE International Parallel and Distributed Processing Symposium, May 2009.
• 33: R. Clint Whaley, Antoine Petitet, and Jack J. Dongarra. Automated empirical optimization of software and the ATLAS project. Parallel Computing, 27(1-2):3-35, January 2001.
• 34: Katherine Yelick, Luigi Semenzato, Geoff Pike, Carleton Miyamoto, Ben Liblit, Arvind Krishnamurthy, Paul Hilfinger, Susan Graham, David Gay, Phil Colella, and Alex Aiken. Titanium: A high-performance Java dialect. In ACM, editor, ACM 1998 Workshop on Java for High-Performance Network Computing, New York, NY 10036, USA, 1998. ACM Press.
• 35: Hans P. Zima, From FORTRAN 77 to locality-aware high productivity languages for peta-scale computing, Scientific Programming, v.15 n.1, p.45-65, January 2007
• 36: Hans P. Zima, Peter Brezany, Barbara M. Chapman, Piyush Mehrotra, and Andreas Schwald. Vienna Fortran - a language specification. Technical Report 21, ICASE, NASA Langley Research Center, Hampton, VA, March 1992. ICASE Internal Report 21.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

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

General Terms:
Algorithms, Languages, Performance

Keywords:
high-productivity languages, model-guided autotuning, peta-scale computing