Constraint based vectorization

ABSTRACT

The constraint tree provides a uniform framework for representing many loop transformations. It allows us to estimate the performance of several alternative execution methods before committing to any of the transformations. We introduce the constraint tree, show how it is built, and demonstrate its use for vectorization and parallel decomposition. We show how unconstrained loops can be moved to reduce the costs of memory accesses.

REFERENCES

• Alle83: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• ACK86: J.R. Allen, D. C~llahan, and K. Kennedy, "Automatic Decomposition of Scientific Programs for Parallel Execution", Report TR86-42, Department of Oomputer Science, Rice University, Houston, TX, November, 1986.
• AK87: 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]
• Bane76: U. Banerjee, "D~ta dependence in ordinary programs", Report 76-837, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, II, 1979.
• Call86: D. Callahan,"Dependence testing in PFC: Weak Separability", Supercomputer Software Newsletter ~2, Rice University, August 1986.
• Coha73: W. L. Cohagen, "Vector Optimization for the ASC", Proc. Sever~th Annual Princeton Conferer~ce on Informatio~ Sciences and Systems, Department of Electrical Engineering, Princeton, N J, 1973.
• FOW87: 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]
• IT86: F. Irigoin, R. Triolet, "Computing Dependence Direction Vectors and Dependence Cones with Linear Systems," EBSNP-CAt-87-E94, Ecole des Mines de Paris, Fontainebleau, France. August 1986.
• Kuck78: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• KKLW80a: D. J. Kuck, R. H. Kuhn, B. Leasure, M. Wolfe, "The structure of an advanced vectorizer for pipelined processors'', Proc. IEEE Computer Society Fourth In.t'l Computer Software and Applications Conference,, IEEE,, Chicago, II, October 1980.
• KKLW80b: D. J. Kuck, R. H. Kuhn, B. Leasure, M. Wolfe, "Analysis and transform;rtion of programs for parallel computation", Proc. IEEE Computer Society Fourth Int'l Computer Software and Applications Conference, , IEEE, Chicago, II, October 1980.
• Lamp74: Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
• PW86: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• SK86: 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
• Tarj72: R. Tarjan "Depth first search and linear graph algorithms", SIAM Journal of Computinq, 1,2 1972. pp. 146-160.
• Wolf78: M.J. Wolfe, "Techniques for improving the inherent, parallelism in programs", Repor~ 78-929, Dep~rtlnent: of Computer Science, University of Illinois at Urbana- Champaign, Urbana, I1, July 1978.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Design, Languages, Performance, Theory, Verification