Data dependence analysis on multi-dimensional array references

ABSTRACT

An efficient and precise data dependence analysis is the key to the success of a parallelizing compiler because it is required in almost all phases of the parallelism detection and enhancement in such compilers. However, existing test algorithms are quite weak in analyzing multi-dimensional array references, which are usually where the parallelism is in most programs. In this paper, a new algorithm, called &lgr;-test, is presented for an efficient and accurate data dependence analysis on multi-dimensional array references. It achieves high efficiency and high accuracy at the same time, which is in general not allowed in previous algorithms. This algorithm has been implemented in Parafrase [Wolf82]. Some experimental results are also presented to show its effectiveness.

REFERENCES

• Alle83: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• Bane88: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• CoHa78: Patrick Cousot , Nicolas Halbwachs, Automatic discovery of linear restraints among variables of a program, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.84-96, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512770]
• KKPL81: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• Kuhn80: Robert Henry Kuhn, Optimization and interconnection complexity for: parallel processors, single-stage networks, and decision trees, 1980
• Li89: Zhiyuan Li , Pen-Chung Yew, Intraprocedural and interprocedural data dependence analysis for parallel computing, 1989
• LiTh88: 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]
• ShLY89: "An Empirical Study on Array Subscripts and Data Dependences," To appear in Proe. of 1989 Int' Conf. on Parallel Processing.
• Shos81: Robert Shostak, Deciding Linear Inequalities by Computing Loop Residues, Journal of the ACM (JACM), v.28 n.4, p.769-779, Oct. 1981 [doi>10.1145/322276.322288]
• Smit76: B.J. Smith, et al., Matrix Eigensystem Routines - Eispack Guide, Springer- Verlag, Heidelberg, 1976.
• Trio85: R. Triolet, "Interprocedural Analysis for Program Restructuring with Parafrase," CSRD Rpt. No. 538, University of Illinois at Urbana-Champaign, Dec. 1985.
• TrIF86: Rémi Triolet , Francois Irigoin , Paul Feautrier, Direct parallelization of call statements, ACM SIGPLAN Notices, v.21 n.7, p.176-185, July 1986
• Wall88: D. R. Wallace, Dependence of multi-dimensional array references, Proceedings of the 2nd international conference on Supercomputing, p.418-428, June 1988, St. Malo, France [doi>10.1145/55364.55405]
• Wolf82: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

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

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance, Theory, Verification