Dependence of multi-dimensional array references

ABSTRACT

Accurate data dependence analysis is the key function in vectorizing-restructuring compilers for supercomputers. However, the data dependence analysis algorithms currently available have limitations. Those that execute quickly, such as the Banerjee Test [3], [4], [21] are very limited in generality. Those that are general are too slow. 1 Compiler designers have been keenly aware of the need for an algorithm that is both general and fast. The algorithm that follows fills this need simply and uniformly. Aside from fast execution, this algorithm has three main features: It can deal with arbitrary linear constraints whose variables are not limited to loop-control variables It can deal with any number of these linear constraints simultaneously. It only looks at integer solutions. The algorithm organizes the multiple constraints into a constraint matrix and uses a method derived from linear programming techniques. We refer to this as the Constraint-Matrix algorithm. Burke and Cytron [6] have discussed linearization to deal with arrays of greater than one dimension. This approach was also referred to by Towle [18]. Linearization is limited unless additional constraints are added; it cannot deal with arbitrary additional constraints and it does not restrict its solutions to integers. The Constraint-Matrix algorithm is organized specifically for a goal that is different from the standard linear programming problem. This goal is to prove the lack of a solution [i.e. the lack of a dependence) rather than minimize an “objective function.” further, this algorithm is designed to “short-circuit” when its goal is reached, in a way that a standard linear programming algorithm cannot. In order to simplify the exposition, we begin with a precise definition of dependence. To provide some motivation for the later algorithm and to show the advantages of the matrix format, we then present two special case methods (Solvable-Matrix and Matrix-GCD). Finally we present the Constraint-Matrix algorithm.

REFERENCES

• 1: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• 2: 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]
• 3: Banerjee, U., Data Deper,,,der~ce in Ordinary Programs, M.S. Thesis, University of Illinois at Champaign-Urbana, Urbana, Illinois, Department of Computer Science, Report 76-837, November 1976.
• 4: Utpal Banerjee, Speedup of ordinary programs, 1979
• 5: Barsov, A. S., What is Linear Programming f, D. C. Heath, Boston, 1964.
• 6: 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
• 7: Dantzig, G. B., Linear Programming and Eaten. 8ions, Princeton University Press, Princeton, New Jersey, 1963.
• 8: P. Feautrier, Projet Vesta: outil de calcul symbolique, Proceedings of the 6th Colloquium on International Symposium on Programming, p.113-124, April 17-19, 1984
• 9: Gomory, R. E., "All integer programming algorithm," IBM Research Center, Yorktown, Research Report RC 189, January 1960.
• 10: Griffin, H., Elementary Theory of Numbers, McGraw-Hill, New York, New York, 1954.
• 11: Henrici, P., Elements of Numerical Analysis, John Wiley & Sons, New York, 1964.
• 12: Hoffman, Kenneth and Ray Kunze, Linear Algebra, Prentice Hall, Englewood ClifFs, New Jersey, 1951.
• 13: N. Karmarkar, A new polynomial-time algorithm for linear programming, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.302-311, December 1984 [doi>10.1145/800057.808695]
• 14: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 15: 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]
• 16: Smale, S., "The problem of the average speed of the Simplex method," Mathematical Programming, The State of the Art (Bonn 1982) (Bachem et al. eds.), Springer Verlag, Berlin and New York, 1983.
• 17: Smale, S., "On the efficiency of algorithms of analysis," Bull. AMS, Vol. 13 (2), October 1985, pp.87-121.
• 18: Ross Albert Towle, Control and data dependence for program transformations., 1976
• 19: Rémi Triolet , Francois Irigoin , Paul Feautrier, Direct parallelization of call statements, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.176-185, June 25-27, 1986, Palo Alto, California, United States
• 20: Joe Warren, A hierarchical basis for reordering transformations, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.272-282, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800539]
• 21: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

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

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Design, Theory