Sensitivity analysis for automatic parallelization on multi-cores

ABSTRACT

Sensitivity Analysis (SA) is a novel compiler technique that complements, and integrates with, static automatic parallelization analysis for the cases when relevant program behavior is input sensitive. In this paper we show how SA can extract all the input dependent, statically unavailable, conditions for which loops can be dynamically parallelized. SA generates a sequence of sufficient conditions which, when evaluated dynamically in order of their complexity, can each validate the dynamic parallel execution of the corresponding loop. For example, SA can first attempt to validate parallelization by checking simple conditions related to loop bounds. If such simple conditions cannot be met, then validating dynamic parallelization may require evaluating conditions related to the entire memory reference trace of a loop, thus decreasing the benefits of parallel execution.

We have implemented Sensitivity Analysis in the Polaris compiler and evaluated its performance using 22 industry standard benchmark codes running on two multicore systems. In most cases we have obtained speedups superior to the Intel Ifort compiler because with SA we could complement static analysis with minimum cost dynamic analysis and extract most of the available coarse grained parallelism.

REFERENCES

• 1: Gagan Agrawal , Joel Saltz , Raja Das, Interprocedural partial redundancy elimination and its application to distributed memory compilation, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.258-269, June 18-21, 1995, La Jolla, California, United States
• 2: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 3: William Blume , Ramon Doallo , Rudolf Eigenmann , John Grout , Jay Hoeflinger , Thomas Lawrence , Jaejin Lee , David Padua , Yunheung Paek , Bill Pottenger , Lawrence Rauchwerger , Peng Tu, Parallel Programming with Polaris, Computer, v.29 n.12, p.78-82, December 1996 [doi>10.1109/2.546612]
• 4: William Blume , Rudolf Eigenmann, The range test: a dependence test for symbolic, non-linear expressions, Proceedings of the 1994 conference on Supercomputing, p.528-537, December 1994, Washington, D.C., United States
• 5: Béatrice Creusillet , François Irigoin, Exact versus Approximate Array Region Analyses, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.86-100, August 08-10, 1996
• 6: P. Feautrier. Parametric integer programming. Operations Research, 22(3):243--268, 1988.
• 7: P. Feautrier. Dataflow analysis of array and scalar references. Int. Journal of Par. Prog., 20(1):23--54, 1991.
• 8: Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.15-29, June 24-28, 1991, Toronto, Ontario, Canada
• 9: Manish Gupta , Sayak Mukhopadhyay , Navin Sinha, Automatic parallelization of recursive procedures, International Journal of Parallel Programming, v.28 n.6, p.537-562, Dec. 2000 [doi>10.1023/A:1007560600904]
• 10: Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic analysis for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.477-518, July 1996 [doi>10.1145/233561.233568]
• 11: Mary W. Hall , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Monica S. Lam, Interprocedural parallelization analysis in SUIF, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.4, p.662-731, July 2005 [doi>10.1145/1075382.1075385]
• 12: Jay Philip Hoeflinger , David A. Padua, Interprocedural parallelization using memory classification analysis, University of Illinois at Urbana-Champaign, Champaign, IL, 1998
• 13: Ding-Kai Chen , Josep Torrellas , Pen-Chung Yew, An efficient algorithm for the run-time parallelization of DOACROSS loops, Proceedings of the 1994 conference on Supercomputing, p.518-527, December 1994, Washington, D.C., United States
• 14: X. Kong , D. Klappholz , K. Psarris, The I Test: An Improved Dependence Test for Automatic Parallelization and Vectorization, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.342-349, July 1991 [doi>10.1109/71.86109]
• 15: Shun-Tak Leung , John Zahorjan, Improving the performance of runtime parallelization, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.83-91, May 19-22, 1993, San Diego, California, United States
• 16: Yuan Lin , David A. Padua, Analysis of Irregular Single-Indexed Array Accesses and Its Applications in Compiler Optimizations, Proceedings of the 9th International Conference on Compiler Construction, p.202-218, March 25-April 02, 2000
• 17: Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.1-14, June 24-28, 1991, Toronto, Ontario, Canada
• 18: Sungdo Moon , Mary W. Hall, Evaluation of predicated array data-flow analysis for automatic parallelization, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.84-95, May 04-06, 1999, Atlanta, Georgia, United States
• 19: Sungdo Moon , Mary W. Hall , Brian R. Murphy, Predicated array data-flow analysis for run-time parallelization, Proceedings of the 12th international conference on Supercomputing, p.204-211, July 1998, Melbourne, Australia [doi>10.1145/277830.277874]
• 20: Sungdo Moon , Byoungro So , Mary W. Hall , Brian R. Murphy, A Case for Combining Compile-Time and Run-Time Parallelization, Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.91-106, May 28-30, 1998
• 21: Yunheung Paek , Jay Hoeflinger , David Padua, Efficient and precise array access analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.1, p.65-109, January 2002 [doi>10.1145/509705.509708]
• 22: William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125848]
• 23: William Pugh , David Wonnacott, An Exact Method for Analysis of Value-based Array Data Dependences, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.546-566, August 12-14, 1993
• 24: W. Pugh and D. Wonnacott. Nonlinear array dependence analysis. In Proc. of Workshop on Lang., Comp. and Run-Time Support for Scalable Systems, Kluwer, Boston 1995.
• 25: Carlos García Quiñones , Carlos Madriles , Jesús Sánchez , Pedro Marcuello , Antonio González , Dean M. Tullsen, Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 26: Lawrence Rauchwerger , David Padua, The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.218-232, June 18-21, 1995, La Jolla, California, United States
• 27: Silvius Rus , Lawrence Rauchwerger , Jay Hoeflinger, Hybrid analysis: static & dynamic memory reference analysis, International Journal of Parallel Programming, v.31 n.4, p.251-283, August 2003 [doi>10.1023/A:1024597010150]
• 28: Silvius Rus , Dongmin Zhang , Lawrence Rauchwerger, The Value Evolution Graph and its Use in Memory Reference Analysis, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.243-254, September 29-October 03, 2004 [doi>10.1109/PACT.2004.30]
• 29: Joel H. Salz , Ravi Mirchandaney , Kay Crowley, Run-Time Parallelization and Scheduling of Loops, IEEE Transactions on Computers, v.40 n.5, p.603-612, May 1991 [doi>10.1109/12.88484]
• 30: Robert A. van Engelen , J. Birch , Y. Shou , B. Walsh , Kyle A. Gallivan, A unified framework for nonlinear dependence testing and symbolic analysis, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006226]
• 31: M. Wolfe , C. W. Tseng, The Power Test for Data Dependence, IEEE Transactions on Parallel and Distributed Systems, v.3 n.5, p.591-601, September 1992 [doi>10.1109/71.159042]
• 32: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 33: P. Wu, A. Cohen, and D. Padua. Induction variable analysis without idiom recognition: Beyond monotonicity. In Proc. of Workshop on Lang. and Comp. for Par. Computing, pp. 427--441, Cumberland Falls, KY, 2001, LNCS 2624.
• 34: Hao Yu , Lawrence Rauchwerger, Techniques for Reducing the Overhead of Run-Time Parallelization, Proceedings of the 9th International Conference on Compiler Construction, p.232-248, March 25-April 02, 2000

INDEX TERMS

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

General Terms:
Experimentation, Performance

Keywords:
multicore, parallelism, sensitivity analysis