Parallelization spectroscopy: analysis of thread-level parallelism in hpc programs

ABSTRACT

In this paper, we present a method - parallelization spectroscopy - for analyzing the thread-level parallelism available in production High Performance Computing (HPC) codes.We survey a number of techniques that are commonly used for parallelization and classify all the loops in the case study presented using a sensitivity metric: how likely is a particular technique is successful in parallelizing the loop.

REFERENCES

• 1: Ganesh Bikshandi , Jia Guo , Daniel Hoeflinger , Gheorghe Almasi , Basilio B. Fraguela , María J. Garzarán , David Padua , Christoph von Praun, Programming for parallelism and locality with hierarchically tiled arrays, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122981]
• 2: Pradip Bose, Workload characterization: A key aspect of microarchitecture design, IEEE Micro, v.26 n.2, p.5-6, March 2006 [doi>10.1109/MM.2006.44]
• 3: Chapel. http://chapel.cs.washington.edu.
• 4: CPMD Consortium page. http://www.cpmd.org.
• 5: Project Fortree Overview. http://projectfortress.sun.com.
• 6: Arun Kejariwal , Xinmin Tian , Wei Li , Milind Girkar , Sergey Kozhukhov , Hideki Saito , Utpal Banerjee , Alexandru Nicolau , Alexander V. Veidenbaum , Constantine D. Polychronopoulos, On the performance potential of different types of speculative thread-level parallelism: The DL version of this paper includes corrections that were not made available in the printed proceedings, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia [doi>10.1145/1183401.1183407]
• 7: Milind Kulkarni , Keshav Pingali , Bruce Walter , Ganesh Ramanarayanan , Kavita Bala , L. Paul Chew, Optimistic parallelism requires abstractions, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 8: LAM MPI Parallel Computing. http://www.lam-mpi.org/.
• 9: (Linear Algebra PACKage). http://www.netlib.org/lapack/.
• 10: OpenMP Specification, version 2.5. http://www.openmp.org.
• 11: UPC. http://upc.gwu.edu/.
• 12: Christoph von Praun , Rajesh Bordawekar , Calin Cascaval, Modeling optimistic concurrency using quantitative dependence analysis, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345234]
• 13: M. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.655-664, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76337]
• 14: Peng Wu , Arun Kejariwal , Călin Caşcaval, Compiler-Driven Dependence Profiling to Guide Program Parallelization, Languages and Compilers for Parallel Computing: 21th International Workshop, LCPC 2008, Edmonton, Canada, July 31 - August 2, 2008, Revised Selected Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-89740-8_16]
• 15: The X10 Programming Language. http://www.x10-lang.org.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Measurement, Performance

Keywords:
loop transofrmations, multithreading, parallelism