Symbolic array dataflow analysis for array privatization and program parallelization

ABSTRACT

Array dataflow information plays an important role for successful automatic parallelization of Fortran programs. This paper proposes a powerful symbolic array dataflow analysis to support array privatization and loop parallelization for programs with arbitrary control flow graphs and acyclic call graphs. Our scheme summarizes array access information using guarded array regions and propagates such regions over a Hierarchical Supergraph (HSG). The use of guards allows us to use the information in IF conditions to sharpen the array dataflow analysis and thereby to handle difficult cases which elude other existing techniques. The guarded array regions retain the simplicity of set operations for regular array regions in common cases, and they enhance regular array regions in complicated cases by using guards to handle complex symbolic expressions and array shapes. Scalar values that appear in array subscripts and loop limits are substituted on the fly during the array information propagation, which disambiguates the symbolic values precisely for set operations. We present efficient algorithms that implement our scheme. Initial experiments of applying our analysis to Perfect Benchmarks show promising results of improved array privatization.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 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: Vasanth Balasundaram, A mechanism for keeping useful internal information in parallel programming tools: the data access descriptor, Journal of Parallel and Distributed Computing, v.9 n.2, p.154-170, June 1990 [doi>10.1016/0743-7315(90)90043-O]
• 4: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 5: Utpal K. Banerjee, Loop Transformations for Restructuring Compilers: The Foundations, Kluwer Academic Publishers, Norwell, MA, 1993
• 6: M. Berry, D. Chen, P. Koss, D. Kuck, and S. Lo. the Perfect club benchmarks: Effective performance evaluation of supercomputers. Technical Report CSRD-827, University of Illinois, Urbana, IL, May 1989.
• 7: William J Blume, Symbolic analysis techniques for effective automatic parallelization, University of Illinois at Urbana-Champaign, Champaign, IL, 1995
• 8: W. Blume , R. Eigenmann, Performance Analysis of Parallelizing Compilers on the Perfect Benchmarks Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.6, p.643-656, November 1992 [doi>10.1109/71.180621]
• 9: William Blume and Rudolf Eigenmann. The range test: A dependence test for non-linear expressions. Technical Report CSRD-Report-1345, Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, April 1994.
• 10: D. Callahan and K. Kennedy. Analysis of interprocedural side effects in a parallel programming environment. In ACM SIGPLAN '86 Symp. Compiler Construction, pages 162-175, June 1986.
• 11: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, A practical data flow framework for array reference analysis and its use in optimizations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.68-77, June 21-25, 1993, Albuquerque, New Mexico, United States
• 12: R. Eigenmann, J. Hoe inger, G. Jaxon, Z. Li, and D. Padua. Experience with Fortran program restructuring for Cedar multiprocessor. Concurrency - Experience and Practice, 5(7):553-573, October 1993.
• 13: R. Eigenmann, J. Hoe inger, Z. Li, and D. Padua. Experience in the automatic parallelization of four Perfect benchmark programs. In Lecture Notes in Computer Science, 589. Springer-Verlag, 1992.
• 14: Paul Feautrier. Data ow analysis of array and scalar references. International Journal of Parallel Programming, 2(1):23-53, February 1991.
• 15: 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]
• 16: 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]
• 17: P. Havlak , K. Kennedy, An Implementation of Interprocedural Bounded Regular Section Analysis, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.350-360, July 1991 [doi>10.1109/71.86110]
• 18: François Irigoin , Pierre Jouvelot , Rémi Triolet, Semantical interprocedural parallelization: an overview of the PIPS project, Proceedings of the 5th international conference on Supercomputing, p.244-251, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109086]
• 19: X. Kong , D. Klappholz , K. Psarris, The I Test: An Improved Dependence Test for Automatic Parallelization and Vectorization, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.342-349, July 1991 [doi>10.1109/71.86109]
• 20: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 21: Robert Henry Kuhn, Optimization and interconnection complexity for: parallel processors, single-stage networks, and decision trees, 1980
• 22: 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]
• 23: Z. Li. Propagating symbolic relations on an interprocedural and hierarchical control ow graph. Technical Report CSci-93-87, Computer Science Department, University of Minnesota, Minneapolis, MN, 1993.
• 24: Zhiyuan Li , Pen-Chung Yew, Some results on exact data dependence analysis, Selected papers of the second workshop on Languages and compilers for parallel computing, p.374-401, May 1990, Urbana, Illinois, United States
• 25: Z. Li , P. C. Yew , C. Q. Zhu, An Efficient Data Dependence Analysis for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.26-34, January 1990 [doi>10.1109/71.80122]
• 26: Vadim Maslov, Lazy array data-flow dependence analysis, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-325, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177911]
• 27: 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]
• 28: Dror Eliezer Maydan, Accurate analysis of array references, Stanford University, Stanford, CA, 1993
• 29: Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
• 30: 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
• 31: 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]
• 32: Carl Rosene. Incremental dependence analysis. Technical Report CRPC-TR90044, PhD thesis, Computer Science Department, Rice University, March 1990.
• 33: Z. Shen , Z. Li , P. C. Yew, An Empirical Study of Fortran Programs for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.356-364, July 1990 [doi>10.1109/71.80162]
• 34: 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
• 35: Remi Triolet. Interprocedural analysis for program restructuring with parafrase. Technical Report CSRD Rpt. No.538, Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, December 1985.
• 36: Peng Tu , David A. Padua, Automatic Array Privatization, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.500-521, August 12-14, 1993
• 37: 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]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Data-flow architectures
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques
  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.2 Language Classifications

          Nouns: FORTRAN

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

General Terms:
Algorithms, Measurement, Performance