Array-data flow analysis and its use in array privatization

ABSTRACT

Data-flow analysis of scalar variables and data dependence analysis on array elements are two important program analyses used in optimizing and parallelizing compilers. Traditional data-flow analysis models accesses of array elements simply as accesses to the entire array, and is inadequate for parallelizing loops in array-based programs. On the other hand, data dependence analysis differentiates between different array elements but is flow-insensitive. This paper studies the combination of these two analyses—data-flow analyses—data-flow analysis of accesses to individual array elements. The problem of finding precise array dataflow information in the domain of loop nests where the loop bounds and array indices are affine functions of loop indices was first formulated by Feautrier. Feautrier's algorithm, based on parametric integer programming techniques, is general but inefficient. This paper presents an efficient algorithm that can find the same precise information for many of the programs found in practice. In this paper, we argue that data-flow analysis of individual array elements is necessary for effective automatic parallelization. In particular, we demonstrate the use of array data-flow analysis in an important optimization known as array privatization. By demonstrating that array data-flow analysis can be computed efficiently and by showing the importance of the optimizations enabled by the analysis, this paper suggests that array data-flow analysis may become just as important in future optimizing and parallelizing compilers as data-flow and data dependence analysis are in today's compilers.

REFERENCES

• 1: R. Allen, D. Callahan, and K. Kennedy. Automatic decomposition of scientific programs for parallel execution, Technical Report Rice COMP TR86-42, Depamnent of Computer Science, Rice University, Nov 1986.
• 2: Corinne Ancourt , François Irigoin, Scanning polyhedra with DO loops, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.39-50, April 21-24, 1991, Williamsburg, Virginia, United States
• 3: M. Ancourt. Generation automatique de codes de transfert pour multiprocesseurs a memoires locales. PhD thesis, University of Paris VI, March 1991.
• 4: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 5: T. Brandes, The importance of direct dependences for automatic parallelization, Proceedings of the 2nd international conference on Supercomputing, p.407-417, June 1988, St. Malo, France [doi>10.1145/55364.55404]
• 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: 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
• 8: M. Berry et al. The PERFECT Club benchmarks: effective pexformance evaluation of supcrcomputers. Technical Report UIUCSRD Rep. No. 827, University of Illinois Urbana-Champaign, 1989.
• 9: 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]
• 10: P. Feautrier. Parametric integer programming. Technical Report 209, Labomtoirc Mcthodologie and Architecture Des Systemes Informatiques, Jan 1988.
• 11: P. Feautrier. Dataflow analysis of army and scalar references. International Journal of Parallel Programming, 20(1):23-52, Feb 1991.
• 12: Elana D. Granston , Alexander V. Veidenbaum, Detecting redundant accesses to array data, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.854-865, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126714]
• 13: T. Gross , P. Steenkiste, Structured dataflow analysis for arrays and its use in an optimizing complier, Software—Practice & Experience, v.20 n.2, p.133-155, February 1990 [doi>10.1002/spe.4380200203]
• 14: Zhiyuan Li, Array privatization for parallel execution of loops, Proceedings of the 6th international conference on Supercomputing, p.313-322, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143426]
• 15: Dror Eliezer Maydan, Accurate analysis of array references, Stanford University, Stanford, CA, 1993
• 16: 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
• 17: D. E. Maydan, j. L. Hennessy, and M. S. Lam. Effectiveness of data dependence analysis. In Proceedings of the NSF-NCRD Workshop on Advanced Compilation Techniques for Novel Architectures, 1992.
• 18: William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125848]
• 19: William Pugh , David Wonnacott, Eliminating false data dependences using the Omega test, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.140-151, June 15-19, 1992, San Francisco, California, United States
• 20: H. Ribas. Obtaining d~pcndene~ vectors for nestedloop computations. In Proceedings of 1990 international Conference on Parallel Processing, pages II-212 to II-219, 1990.
• 21: Carl M. Rosene , Ken W. Kennedy, Incremental dependence analysis, 1990
• 22: J. P. Singh and J. L. Hennessy. An empirical investigation of the effectiveness and limitations of automatic parallelization. In Proceedings of the International Symposium on Shared Memory Multiporcessing " Tokyo, Japan, pages 25-36, 1991.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms