A unified semantic approach for the vectorization and parallelization of generalized reductions

ABSTRACT

Generalized reductions include some of the most well known programming idioms, for instance loop invariant variables, induction variables and reduction operations. We propose a unified framework that allows the detection of these paradigms and thus the efficient parallel implementation of programs that use these otherwise parallel-inhibiting constructs. Moreover, using a semantic-based symbolic evaluator, this technique is able to detect parallelizable constructs inside standard benchmarks that no other vectorizer or parallelizer can currently handle. An interesting by-product of our approach is that correctness proofs can be based on the sound and powerful abstract interpretation theory. This method has been implemented in the Velour vectorizer under current development at the Bull Research Center.

REFERENCES

• ASU86: Aho, A. V., Sethi, R., and ~Ullman J. D. Compilers. Addison Wesley, 1986.
• B75: Bledsoe, W. W. A New Method for Proving Certain Presburger Formulas. In ~th IJCAI, Tbilissi, September 1975.
• B84: Barendregt, H. The Lambda-Calculus: Its Syntax and Semantics. North Holland, 1984.
• C86: Chailloux, J. & al, Le_Lisp Version 15.2. INRIA Tech. Rep., May 1986.
• CC77: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• CCKT86: David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.152-161, June 25-27, 1986, Palo Alto, California, United States
• CDL88: D. Callahan , J. Dongarra , D. Levine, Vectorizing compilers: a test suite and results, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.98-105, November 12-17, 1988, Orlando, Florida, United States
• CH78: Patrick Cousot , Nicolas Halbwachs, Automatic discovery of linear restraints among variables of a program, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.84-96, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512770]
• CR81: Clarke, A. L., and Richardson, D. J. Symbolic Evaluation Methods' Implementations and Applications. In Computer Program Testing, North- Holland, 1981.
• DM88: Dehbonei, B., and Memmi, G. Velour: A New Vectorizing Compiler Prototype. in Proceedings of the ICS'88, Boston, May 1988, pp. 431-440.
• E86: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• F88: Feautrier, P. Semantical Analysis and Mathematical Programming. In Int. Workshop on Parallel and Distributed Algorithms, Bonus, September 1988.
• J86: P Jouvelot, Parallelization by semantic detection of reductions, Proc. of the European symposium on programming on ESOP 86, p.223-236, March 1986, Saarbru:9Aicken, Germany
• K88: Keech, M.S. Test Loops for Fortran ~00 Vecto.rizer. FSUCC Tech. Rep. 2, April 88.
• LT85: Lichnewsky, A., and Thomasset, F. Techniques de Base pour t'Ezploitaiion Aulomatique du Paralldlisme duns les Program,n. es. {NRIA Res. Rep. 460, 1985.
• LT88: A. Lichnewsky , F. Thomasset, Introducing symbolic problem solving techniques in the dependence testing phases of a vectorizer, Proceedings of the 2nd international conference on Supercomputing, p.396-406, June 1988, St. Malo, France [doi>10.1145/55364.55403]
• MR79: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• S77: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• TIF86: 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

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.3 Language Constructs and Features
          Subjects: Concurrent programming structures

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Specification techniques

General Terms:
Algorithms, Design, Languages, Management, Measurement, Performance, Theory

Keywords:
induction variable, parallelization, reduction, symbolic evaluation, vectorization