On exact data dependence analysis

ABSTRACT

The GCD test and the Banerjee-Wolfe test are the two tests traditionally used to determine statement data dependence, subject to direction vectors, in automatic vectorization / parallelization of loops. In an earlier study [14] a sufficient condition for the accuracy of the Banerjee-Wolfe test was stated and proved. In the original presentation only the case of general data dependence was considered, i.e., the case of data dependence without direction vector information. In this paper we extend the previous work to the case of data dependence subject to an arbitrary direction vector. We also state and prove a sufficient condition for the accuracy of a combination of the GCD and the Banerjee-Wolfe test. Finally, we demonstrate how these results can be used in actual practice to obtain exact data dependence information.

REFERENCES

• 1: F. Allen , M. Burke , P. Charles , R. Cytron , J. Ferrante, An overview of the PTRAN analysis system for multiprocessing, Proceedings of the 1st International Conference on Supercomputing, p.194-211, March 1988, Athens, Greece
• 2: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• 3: Allen, J.R., and K. Kennedy, "PFC: A program to convert Fortran to parallel form," Supercomputers: Design and Applications, pp 186-205, IEEE Computer Society Press, Silver Spring, MD, 1984.
• 4: 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]
• 5: Banerjee, Utpal, "Data Dependence in Ordinary Programs," M.S. Thesis, University of Illinois at Urbana-Champaign, November 1976.
• 6: Utpal Banerjee, Speedup of ordinary programs, 1979
• 7: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 8: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.162-175, June 25-27, 1986, Palo Alto, California, United States
• 9: M. Gikar , C. Polychronopoulos, Compiling issues for supercomputers, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.164-173, November 12-17, 1988, Orlando, Florida, United States
• 10: David Klappholz , Kleanthis Psarris , Xiangyun Kong, On the perfect accuracy of an approximate subscript analysis test, Proceedings of the 4th international conference on Supercomputing, p.201-212, June 11-15, 1990, Amsterdam, The Netherlands
• 11: 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]
• 12: Constantine D. Polychronopoulos , Milind B. Girkar , Mohammad Reza Haghighat , Chia Ling Lee , Bruce Leung , Dale Schouten, Parafrase-2: an environment for parallelizing, partitioning, synchronizing, and scheduling programs on multiprocessors, International Journal of High Speed Computing, v.1 n.1, p.45-72, May 1989 [doi>10.1142/S0129053389000044]
• 13: Kleanthis Constantine Psarris, A formal study of data dependence analysis for parallelizing compilers, Stevens Institute of Technology, Hoboken, NJ, 1991
• 14: Kleanthis Psarris , David Klappholz , Xiangyun Kong, On the accuracy of the Banerjee test, Journal of Parallel and Distributed Computing, v.12 n.2, p.152-157, June 1991 [doi>10.1016/0743-7315(91)90019-6]
• 15: Psarris, Kleanthis, "A Formal Study of the Data Dependence Tests and their Accuracy," Technical Report 19913, Computer Science Department, Ohio University, September 1991.
• 16: Shen, Z., Z. Li, and P. Yew, "An Empirical Study on Array Subscripts and Data Dependencies," Proceedings of 1989 International Conference on Parallel Processing, St. Charles, IL, August 1989.
• 17: Ross Albert Towle, Control and data dependence for program transformations., 1976
• 18: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
• 19: Michael Wolfe , Utpal Banerjee, Data dependence and its application to parallel processing, International Journal of Parallel Programming, v.16 n.2, p.137-178, April 1987 [doi>10.1007/BF01379099]
• 20: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

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

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Theory