The program dependence graph and vectorization

ABSTRACT

Previous attempts at vectorizing programs written in a sequential high level language focused on converting control dependences to data dependences using a mechanism known as IF-conversion. After IF-conversion vector optimizations are performed on a data dependence graph. However, IF-conversion is an irrevocable process which can introduce high run-time overhead if the input program is not amenable to vectorization. This paper uses a program dependence graph as the intermediate representation for a vectorizing compiler. A program dependence graph explicitly represents both control and data dependences, allowing guard values to be generated for vectorized statements. Techniques have been developed to perform code motion on vectorization candidates, to validly eliminate all unnecessary control and data dependence cycles, and to regenerate the newly vectorized program consistent with a topological ordering based on the control and data dependences.

REFERENCES

• ALLE 82: J. Allen, K. Kennedy, "PFC: a program to convert programs to parallel form", Technical Report, Department of Mathematical Sciences, Rice University, Houston, TX, March, 1982.
• ALLE 83: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• BANE 76: U. Banerjee, "Data Dependence in Ordinary Programs", Master's Thesis, Dept. of Computer Science, University of Illinois at Urbana- Champaign, Urbana, Illinois, November, 1976.
• BAXT 88: W. Baxter, "V~ctorizmg Sequential Programs and Related Optimizations", Master's Thesis, Dept. of Computer Science, University of Wyoming, Laramie, Wyoming, August, 1988.
• BURK 86: M. Burke, R. Cytron, "Interprocedural Dependence Analysis and Parallelization (Extended Version)", Computer Science Department, IBM T. J. Watson Research Center, Yorktown Heights, New York, 1986.
• FERR 83: Jeanne Ferrante , Karl J. Ottenstein, A program form based on data dependency in predicate regions, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.217-236, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567089]
• FERR 84: J. Ferrante, K. Ottenstein, J. Warren, "The program dependence graph and its use in optimization", Lecture Notes in Computer Science, Vol. 167, Springer-Verlag, 1984, pp. 125-132.
• FERR 85: Jeanne Ferrante , Mary Mace, On linearizing parallel code, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.179-190, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318636]
• FERR 87: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• KENN 80: K. Kennedy, "Automatic Translation of Fortran Programs to Vector Form", Rice Technical Report 476-029-4, Dept. of Mathematical Sciences, Rice University, Houston, TX, October 1980.
• KUCK 72: D. Kuck, Y. Muraoka, S. Chen, "On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speed-up", IEEE Transactions on Computers, C- 21, No. 12, December, 1972, pp. 1293-1310.
• KUCK 81: 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]
• OTTE 84: Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.177-184, April 1984
• SCAR 86: Randolf G Scarborough , Harwood G Kolsky, A vectorizing Fortran compiler, IBM Journal of Research and Development, v.30 n.2, p.163-171, March 1986
• WOLF 78: M. Wolfe, 'q'echniques for Improving the Inherent Parallelism in Programs", Report 78-929, Dept. of Computer Science, University of Illinois at Urbana- Champaign, Urbana, Illinois, July 1978.
• WOLF 82: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Programmer workbench**; Structured programming**

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Design, Languages, Performance, Theory