Towards a holistic approach to auto-parallelization: integrating profile-driven parallelism detection and machine-learning based mapping

ABSTRACT

Compiler-based auto-parallelization is a much studied area, yet has still not found wide-spread application. This is largely due to the poor exploitation of application parallelism, subsequently resulting in performance levels far below those which a skilled expert programmer could achieve. We have identified two weaknesses in traditional parallelizing compilers and propose a novel, integrated approach, resulting in significant performance improvements of the generated parallel code. Using profile-driven parallelism detection we overcome the limitations of static analysis, enabling us to identify more application parallelism and only rely on the user for final approval. In addition, we replace the traditional target-specific and inflexible mapping heuristics with a machine-learning based prediction mechanism, resulting in better mapping decisions while providing more scope for adaptation to different target architectures. We have evaluated our parallelization strategy against the NAS and SPEC OMP benchmarks and two different multi-core platforms (dual quad-core Intel Xeon SMP and dual-socket QS20 Cell blade). We demonstrate that our approach not only yields significant improvements when compared with state-of-the-art parallelizing compilers, but comes close to and sometimes exceeds the performance of manually parallelized codes. On average, our methodology achieves 96% of the performance of the hand-tuned OpenMP NAS and SPEC parallel benchmarks on the Intel Xeon platform and gains a significant speedup for the IBM Cell platform, demonstrating the potential of profile-guided and machine-learning based parallelization for complex multi-core platforms.

REFERENCES

• 1: H. P. Hofstee. Future microprocessors and off-chip SOP interconnect. IEEE Trans. on Advanced Packaging, 27(2), May 2004.
• 2: Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
• 3: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.21 n.7, p.162-175, July 1986
• 4: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 5: A. W. Lim and M. S. Lam. Maximizing parallelism and minimizing synchronization with affine transforms. Parallel Computing, ACM, 1997.
• 6: D. A. Padua, R. Eigenmann, et al. Polaris: A new-generation parallelizing compiler for MPPs. Technical report, In CSRD No. 1306. UIUC, 1993.
• 7: Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996 [doi>10.1109/2.546613]
• 8: Open64. http://www.open64.net.
• 9: Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.212-223, June 17-19, 1998, Montreal, Quebec, Canada
• 10: Michael I. Gordon , William Thies , Michal Karczmarek , Jasper Lin , Ali S. Meli , Andrew A. Lamb , Chris Leger , Jeremy Wong , Henry Hoffmann , David Maze , Saman Amarasinghe, A stream compiler for communication-exposed architectures, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 11: 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]
• 12: Vijay A. Saraswat , Vivek Sarkar , Christoph von Praun, X10: concurrent programming for modern architectures, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229483]
• 13: Shih-Wei Liao , Amer Diwan , Robert P. Bosch, Jr. , Anwar Ghuloum , Monica S. Lam, SUIF Explorer: an interactive and interprocedural parallelizer, ACM SIGPLAN Notices, v.34 n.8, p.37-48, Aug. 1999
• 14: 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
• 15: Lawrence Rauchwerger , Francisco Arzu , Koji Ouchi, Standard Templates Adaptive Parallel Library (STAPL), Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.402-409, May 28-30, 1998
• 16: Jia Guo, Ganesh Bikshandi, et al. Hierarchically tiled arrays for parallelism and locality. IPDPS, 2006.
• 17: François Irigoin , Pierre Jouvelot , Rémi Triolet, Semantical interprocedural parallelization: an overview of the PIPS project, Proceedings of the 5th international conference on Supercomputing, p.244-251, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109086]
• 18: K. Kennedy , K. S. McKinley , C. W. Tseng, Interactive Parallel Programming using the ParaScope Editor, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.329-341, July 1991 [doi>10.1109/71.86108]
• 19: T. Brandes , S. Chaumette , M. C. Counilh , J. Roman , A. Darte , F. Desprez , J. C. Mignot, HPFIT: a set of integrated tools for the parallelization of applications using High Performance Fortran. PART I: HPFIT and the TransTOOL environment, Parallel Computing, v.23 n.1-2, p.71-87, April 1997 [doi>10.1016/S0167-8191(96)00097-X]
• 20: Makoto Ishihara , Hiroki Honda , Mitsuhisa Sato, Development and Implementation of an Interactive Parallelization Assistance Tool for OpenMP: iPat/OMP, IEICE - Transactions on Information and Systems, v.E89-D n.2, p.399-407, February 2006 [doi>10.1093/ietisy/e89-d.2.399]
• 21: S. Rul, H. Vandierendonck, and K. De Bosschere. A dynamic analysis tool for finding coarse-grain parallelism. In HiPEAC Industrial Workshop, 2008.
• 22: W. M. Pottenger. Induction variable substitution and reduction recognition in the Polaris parallelizing compiler. Technical Report, UIUC, 1994.
• 23: Michael O'Boyle , Elena Stöhr, Compile Time Barrier Synchronization Minimization, IEEE Transactions on Parallel and Distributed Systems, v.13 n.6, p.529-543, June 2002 [doi>10.1109/TPDS.2002.1011394]
• 24: Bernhard E. Boser , Isabelle M. Guyon , Vladimir N. Vapnik, A training algorithm for optimal margin classifiers, Proceedings of the fifth annual workshop on Computational learning theory, p.144-152, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130401]
• 25: Heidi Ziegler , Mary Hall, Evaluating heuristics in automatically mapping multi-loop applications to FPGAs, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046216]
• 26: D. H. Bailey, E. Barszcz, et al. The NAS parallel benchmarks. The International Journal of Supercomputer Applications, 5(3), 1991.
• 27: R. E. Grant and A. Afsahi. A Comprehensive Analysis of OpenMP Applications on Dual-Core Intel Xeon SMPs. IPDPS, 2007.
• 28: NAS Parallel Benchmarks 2.3, OpenMP C version. http://phase.hpcc.jp/Omni/benchmarks/NPB/index.html.
• 29: 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
• 30: Steven Wallace , Brad Calder , Dean M. Tullsen, Threaded multiple path execution, Proceedings of the 25th annual international symposium on Computer architecture, p.238-249, June 27-July 02, 1998, Barcelona, Spain
• 31: Jialin Dou , Marcelo Cintra, Compiler Estimation of Load Imbalance Overhead in Speculative Parallelization, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.203-214, September 29-October 03, 2004 [doi>10.1109/PACT.2004.12]
• 32: R. Ramaseshan and F. Mueller. Toward thread-level speculation for coarse-grained parallelism of regular access patterns. MULTIPROG, 2008.
• 33: Matthew Bridges , Neil Vachharajani , Yun Zhang , Thomas Jablin , David August, Revisiting the Sequential Programming Model for Multi-Core, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.69-84, December 01-05, 2007 [doi>10.1109/MICRO.2007.35]
• 34: Silvius Rus , Maikel Pennings , Lawrence Rauchwerger, Sensitivity analysis for automatic parallelization on multi-cores, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1275008]
• 35: P. Peterson , David A. Padua, Dynamic Dependence Analysis: A Novel Method for Data Depndence Evaluation, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.64-81, August 03-05, 1992
• 36: Michael K. Chen , Kunle Olukotun, The Jrpm system for dynamically parallelizing Java programs, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 37: S. Rus and L. Rauchwerger. Hybrid dependence analysis for automatic parallelization. Technical Report, Dept. of CS, Texas A&M U., 2005.
• 38: Chen Ding , Xipeng Shen , Kirk Kelsey , Chris Tice , Ruke Huang , Chengliang Zhang, Software behavior oriented parallelization, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 39: William Thies , Vikram Chandrasekhar , Saman Amarasinghe, A Practical Approach to Exploiting Coarse-Grained Pipeline Parallelism in C Programs, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.356-369, December 01-05, 2007 [doi>10.1109/MICRO.2007.7]
• 40: J. Ramanujam , P. Sadayappan, A methodology for parallelizing programs for multicomputers and complex memory multiprocessors, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.637-646, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76335]
• 41: C. Liao and B. Chapman. A compile-time cost model for OpenMP. IPDPS, 2007.
• 42: Julita Corbalan , Xavier Martorell , Jesus Labarta, Performance-Driven Processor Allocation, IEEE Transactions on Parallel and Distributed Systems, v.16 n.7, p.599-611, July 2005 [doi>10.1109/TPDS.2005.85]
• 43: Yun Zhang , Michael Voss, Runtime Empirical Selection of Loop Schedulers on Hyperthreaded SMPs, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.44.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.386]
• 44: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• 45: Keith D. Cooper , Philip J. Schielke , Devika Subramanian, Optimizing for reduced code space using genetic algorithms, Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, p.1-9, May 05-05, 1999, Atlanta, Georgia, United States
• 46: Antoine Monsifrot , François Bodin , Rene Quiniou, A Machine Learning Approach to Automatic Production of Compiler Heuristics, Proceedings of the 10th International Conference on Artificial Intelligence: Methodology, Systems, and Applications, p.41-50, September 04-06, 2002
• 47: Louis-Noël Pouchet , Cédric Bastoul , Albert Cohen , John Cavazos, Iterative optimization in the polyhedral model: part ii, multidimensional time, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA

INDEX TERMS

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

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

General Terms:
Experimentation, Languages, Measurement, Performance

Keywords:
auto-parallelization, machine-learning based parallelism mapping, openmp, profile-driven parallelism detection