An empirical evaluation of chains of recurrences for array dependence testing

ABSTRACT

Code restructuring compilers rely heavily on program analysis techniques to automatically detect data dependences between program statements. Dependences between statement instances in the iteration space of a loop nest impose ordering constraints that must be preserved in order to produce valid optimized, vectorized, and parallelized loop nests. This paper evaluates a new approach for fast and accurate nonlinear array dependence testing using Chains of Recurrences (CRs). A flow-sensitive loop analysis algorithm is presented for constructing the CR forms of array index expressions. Unlike other approaches, the CR forms are directly integrated into a standard dependence test to solve nonlinear CR-based dependence equations. To study the coverage and performance of the proposed CR-based enhancements of a standard test, we chose the inexact Banerjee test. We implemented a new CR-based Banerjee test in the Polaris compiler and compared the results to the Omega test and Range test on a set of SPEC and LAPACK Benchmark programs. The experimental results suggest that a CR enhancement can dramatically increase the effectiveness of a dependence test without a significant cost increase. More surprisingly, the findings indicate that the enhanced test exceeds the capabilities of the Omega and Range tests for many nonlinear dependence relations detected in the PERFECT Club and LAPACK Benchmark programs.

REFERENCES

• 1: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 2: O. Bachmann. Chains of recurrences for functions of two variables and their applicat ion to surface plotting. In N. Kajler, editor, Human Interaction for Symbolic Computation. Springer-Verlag, 1996.
• 3: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 4: D. Berlin, D. Edelsohn, and S. Pop. High-level loop optimizations for GCC. In Proceedings of the 2004 GCC Developers' Summit, pages 37--54, 2004.
• 5: J. Birch, R. A. van Engelen, and K. A. Gallivan. Value range analysis of conditionally updated variables and pointers. In In Proceedings of Compilers for Parallel Computing (CPC '04), pages 265--276, 2004.
• 6: William J Blume, Symbolic analysis techniques for effective automatic parallelization, University of Illinois at Urbana-Champaign, Champaign, IL, 1995
• 7: 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]
• 8: 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
• 9: William Blume , Rudolf Eigenmann, Nonlinear and Symbolic Data Dependence Testing, IEEE Transactions on Parallel and Distributed Systems, v.9 n.12, p.1180-1194, December 1998 [doi>10.1109/71.737695]
• 10: G. B. Dantzig and B. C. Eaves. Fourier-motzkin elimination and its dual. Journal of Combinatorial Theory (A), 14(3):288--297, 1973.
• 11: Björn Franke , Michael O'boyle, Array recovery and high-level transformations for DSP applications, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.132-162, May 2003 [doi>10.1145/643470.643472]
• 12: Björn Franke , Michael F. P. O'Boyle, Compiler Transformation of Pointers to Explicit Array Accesses in DSP Applications, Proceedings of the 10th International Conference on Compiler Construction, p.69-85, April 02-06, 2001
• 13: Michael P. Gerlek , Eric Stoltz , Michael Wolfe, Beyond induction variables: detecting and classifying sequences using a demand-driven SSA form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.85-122, Jan. 1995 [doi>10.1145/200994.201003]
• 14: 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
• 15: Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic Analysis: A Basis for Parallelization, Optimization, and Scheduling of Programs, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.567-585, August 12-14, 1993
• 16: 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]
• 17: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 18: 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]
• 19: K. Kyriakopoulos and K. Psarris. Addressing the issues in data dependence analysis. In Proceedings of the ISCA 18th International Conference on Parallel and Distributed Computing Systems (PDCS '05), 2005.
• 20: Konstantinos Kyriakopoulos , Kleanthis Psarris, Efficient Techniques for Advanced Data Dependence Analysis, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.143-156, September 17-21, 2005 [doi>10.1109/PACT.2005.19]
• 21: Vijay Menon , Keshav Pingali , Nikolay Mateev, Fractal symbolic analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.6, p.776-813, November 2003 [doi>10.1145/945885.945888]
• 22: K. Psarris , X. Kong , D. Klappholz, The Direction Vector I Test, IEEE Transactions on Parallel and Distributed Systems, v.4 n.11, p.1280-1290, November 1993 [doi>10.1109/71.250105]
• 23: Kleanthis Psarris , Konstantinos Kyriakopoulos, Data Dependence Testing in Practice, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.264, October 12-16, 1999
• 24: 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]
• 25: William Pugh , David Wonnacott, Eliminating false data dependences using the Omega test, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.140-151, June 15-19, 1992, San Francisco, California, United States
• 26: Yixin Shou , Robert A. van Engelen , Johnnie Birch , Kyle A. Gallivan, Toward efficient flow-sensitive induction variable analysis and dependence testing for loop optimization, Proceedings of the 44th annual Southeast regional conference, March 10-12, 2006, Melbourne, Florida [doi>10.1145/1185448.1185450]
• 27: R. A. van Engelen. Symbolic evaluation of chains of recurrences for loop optimization. Technical Report TR-000102, Florida State University, 2000.
• 28: Robert van Engelen, Efficient Symbolic Analysis for Optimizing Compilers, Proceedings of the 10th International Conference on Compiler Construction, p.118-132, April 02-06, 2001
• 29: Robert A. van Engelen , Johnnie Birch , Kyle A. Gallivan, Array Data Dependence Testing with the Chains of Recurrences Algebra, Proceedings of the Innovative Architecture for Future Generation High-Performance Processors and Systems (IWIA'04), p.70-81, January 12-14, 2004
• 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: An Efficient Algorithm for Pointer-to-Array Access Conversion for Compiling and Optimizing DSP Applications, Proceedings of the Innovative Architecture for Future Generation High-Performance Processors and Systems (IWIA'01), p.80, January 18-19, 2001
• 32: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 33: Peng Wu , Albert Cohen , Jay Hoeflinger , David Padua, Monotonic evolution: an alternative to induction variable substitution for dependence analysis, Proceedings of the 15th international conference on Supercomputing, p.78-91, June 2001, Sorrento, Italy [doi>10.1145/377792.377809]
• 34: Eugene V. Zima, Simplification and optimization transformations of chains of recurrences, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.42-50, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220352]

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
chains of recurrences, dependence testing, loop optimization