Monotonic evolution: an alternative to induction variable substitution for dependence analysis

ABSTRACT

We present a new approach to dependence testing in the presence of induction variables. Instead of looking for closed form expressions, our method computes monotonic evolution which captures the direction in which the value of a variable changes. This information is then used in the dependence test to help determine whether array references are dependence-free. Under this scheme, closed form computation and induction variable substitution can be delayed until after the dependence test and be performed on-demand. To improve computative efficiency, we also propose an optimized (non-iterative) data-flow algorithm to compute evolution. Experimental results show that dependence tests based on evolution information matches the accuracy of that based on closed-form computation (implemented in Polaris), and when no closed form expressions can be calculated, our method is more accurate than that of Polaris.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Zahira Ammarguellat , W. L. Harrison, III, Automatic recognition of induction variables and recurrence relations by abstract interpretation, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.283-295, June 1990, White Plains, New York, United States
• 3: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 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: 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]
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 8: Rudolf Eigenmann , Jay Hoeflinger , David Padua, On the Automatic Parallelization of the Perfect Benchmarks®, IEEE Transactions on Parallel and Distributed Systems, v.9 n.1, p.5-23, January 1998 [doi>10.1109/71.655238]
• 9: 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]
• 10: Rajiv Gupta , Madalene Spezialetti, Loop monotonic computations: an approach for the efficient run-time detection of races, Proceedings of the symposium on Testing, analysis, and verification, p.98-111, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120816]
• 11: 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]
• 12: Joseph Hummel , Laurie J. Hendren , Alexandru Nicolau, A general data dependence test for dynamic, pointer-based data structures, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.218-229, June 20-24, 1994, Orlando, Florida, United States
• 13: J. B. Kam and J. D. Ullman. Monotone data ow analysis frameworks. Acta Informatica, 7:309-317, 1977.
• 14: Yuan Lin , David Padua, Compiler analysis of irregular memory accesses, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.157-168, June 18-21, 2000, Vancouver, British Columbia, Canada
• 15: B. Pottenger and R. Eigenmann. Parallelization in the presence of generalized induction and reduction variables. In ACM Int. Conf. on Supercomputing (ICS'95), June 1995.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

General Terms:
Algorithms, Design, Theory