Lazy array data-flow dependence analysis

ABSTRACT

Automatic parallelization of real FORTRAN programs does not live up to users expectations yet, and dependence analysis algorithms which either produce too many false dependences or are too slow to contribute significantly to this. In this paper we introduce dataflow dependence analysis algorithm which exactly computes value-based dependence relations for program fragments in which all subscripts, loop bound and IF conditions are affine. Our algorithm also computes good affine approximations of dependence relations for non-affine program fragments. Actually, we do not know about any other algorithm which can compute better approximations. And our algorithm is efficient too, because it is lazy. When searching for write statements that supply values used by a given read statement, it starts with statements which are lexicographically close to the read statement in iteration space. Then if some of the read statement instances are not “satisfied” with these close writes, the algorithm broadens its search scope by looking into more distant writes. The search scope keeps broadening until all read instances are satisfied or no write candidates are left. We timed our algorithm on several benchmark programs and the timing results suggest that our algorithm is fast enough to be used in commercial compilers—it usually takes 5 to 15 percent of f77 -02 compilation time to analyze a program. Most programs in the 100-line range take less than 1 second to analyze on a SUN SparcStation IPX.

REFERENCES

• AK87: 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]
• AL93: Saman P. Amarasinghe , Monica S. Lam, Communication optimization and code generation for distributed memory machines, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.126-138, June 21-25, 1993, Albuquerque, New Mexico, United States
• B+89: M. Berry et al. The PERFECT Club benchmarks: Effective performance evaluation of supercomputers. International Journal of Supercomputing Applications, 3(3):5--40, March 1989.
• Blu92: William Joseph Blume. Success And Limitations in Automatic Parallelization of the Perfect BenchmarksTM Programs. PhD thesis, Dept. of Computer Science, U. of Illinois at Urbana- Champaign, 1992. M.S. Thesis.
• EHLP91: Rudolf Eigenmann , Jay Hoeflinger , Z. Li , David A. Padua, Experience in the Automatic Parallelization of Four Perfect-Benchmark Programs, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.65-83, August 07-09, 1991
• Fea88a: P. Feautrier. Parametric integer prograanming. Operationnelle/Operations Research, 22(3):243- 268, September 1988.
• Fea88b: P. Feautrier, Array expansion, Proceedings of the 2nd international conference on Supercomputing, p.429-441, June 1988, St. Malo, France [doi>10.1145/55364.55406]
• Fea91: Paul Feautder. Dataflow analysis of array and scalar references. International Journal o.f Parallel Programming, 20(1), February 1991.
• Fea92a: Paul Feantrier. Some efficient solutions to the a~ne scheduling problem, Part I, Onedimensional time. Technical Report 92.28, IBP/MASI, April 1992.
• Fea92b: Paul Feantrier. Some efficient solutions to the affine scheduling problem, Part II, Multidimensional time. Technical Report 92.78, IBP/MASI, Oct 1992.
• HP91: Mohammand Reza Haghighat and Costantine D. Polychronopoulos. Symbolic dependence analysis for high-performance parallelizing compilers, in Advances in Languages and Compilers for Parallel Processing, pages 310-330. The MIT Press, 1991.
• KP93: Wayne Kelly , William Pugh, A framework for unifying reordering transformations, University of Maryland at College Park, College Park, MD, 1993
• LT88: A. Lichnewsky , F. Thomasset, Introducing symbolic problem solving techniques in the dependence testing phases of a vectorizer, Proceedings of the 2nd international conference on Supercomputing, p.396-406, June 1988, St. Malo, France [doi>10.1145/55364.55403]
• MAL93: Dror E. Maydan , Saman P. Amarasinghe , Monica S. Lam, Array-data flow analysis and its use in array privatization, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.2-15, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158515]
• May92: Dror Eliezer Maydan. Accurate Analysis of Array References. PhD thesis, Computer Systems Laboratory, Stanford U., September 1992.
• MHL91: 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
• Mur71: Yoichi Muraoka, Parallelism exposure and exploitation in programs, 1971
• Pug91: William Pugh, Uniform techniques for loop optimization, Proceedings of the 5th international conference on Supercomputing, p.341-352, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109108]
• Pug92: William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
• PW92: William Pugh and David Wonnacott. Going beyond integer programming with the Omega test to eliminate false data dependences. Technical Report CS-TR-2993, Dept. of Computer Science, University of Maryland, College Park, December 1992. An earlier version of this paper appeared at the SIGPLAN PLDI'92 conference.
• PW93a: 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
• PW93b: William Pugh , David Wonnacott, Static analysis of upper and lower bounds on dependences and parallelism, University of Maryland at College Park, College Park, MD, 1993
• Voe92a: V. V. Voevodin, Mathematical Foundation of Parallel Computing, World Scientific Publishing Co., Inc., River Edge, NJ, 1992
• Voe92b: Valentin V. Voevodin. Theory and practice of sequential programs parallelism investigation. Programmirovaniye (Programming and Computer Software), March 1992.
• Wol82: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
• Wol92: Michael Wolfe, Beyond induction variables, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.162-174, June 15-19, 1992, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Algorithms, Measurement, Performance, Theory