Automatic decomposition of scientific programs for parallel execution

ABSTRACT

An algorithm for transforming sequential programs into equivalent parallel programs is presented. The method concentrates on finding loops whose separate iterations can be run in parallel without synchronization. Although a simple version of the method can be shown to be optimal, the problem of generating optimal code when loop interchange is employed is shown to be intractable. These methods are implemented in an experimental translation system developed at Rice University.

REFERENCES

• AhHU 74: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• Alle 83: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• AllK 84: J.R. Allen and K. Kennedy, "PFC: a program to convert Fortran to parallel form," Supercomputere: Design and Applicatione, K Hwang, ed., IEEE Computer Society Press, Silver Spring, MD, 1984, 186-203.
• AllK 85: J.R. Allen and K. Kennedy, "A parallel programming environment," IEEE Software 2(4), July 1085, 21-29.
• Bane 76: U. Banerjee, "Data dependence in ordinary programs," Report 76-837, Dept. of Computer Science, University of illinois at Urbana- Champaign, Urbana, Illinois, November I976.
• Bern 66: A.J. Bernstein, "Analysis of programs for parallel processing," IEEE Trans. Electronic Compttters 15(5), October 1966.
• Call 87: C. D. Callahan, II, A global approach to detection of parallelism, Rice University, Houston, TX, 1987
• CCKT 86: 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
• Cytr 82: Ronald Gary Cytron, Compile-time scheduling and optimization for asynchronous machines (multiprocessor, compiler, parallel processing), 1984
• FlaK 85: H.P. Flatt and K. Kennedy, "Performance of Parallel Processors," Rice COMP TR85-22, Department of Computer Science, Rice University, Houston, Texas, June 1985.
• GGKM 83: A. Gottlieb, R. Grishman, C.P. Kruskal, K.P. MeAuliffe, L. Rudolph, and M. Snir, "The NYU uitracomputer-- designing an MIMD shared memory parallel computer," IF, BE Trans. on Computers c-32(2), February 1983, 175-189.
• GKLS 84: D. Gajski, D. Kuck, D. Lawrie and A. Sarneh, "Cedar," Supereomputere: Design and Applications, K. Hwang, ed., IEEE Computer Society Press, Silver Spring, MD, 1984, 251-275.
• Kenn 80: K. Kennedy, "Automatic translation of Fortran programs to vector form," Rice Technical Report 476-029-4, Rice University, October 1980.
• Kuck 78: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• Padu 79: D.A. Padua, "Multiprocessors: discussion of some theoretical and practical problems," TR UIUCDCS-R-79-90, University of Illinois at Urbana-Champaign, Urbana, Ill., November 1979.
• PBGH 85: GF. Pfister, W.C. Brantley, D.A. George, S.L. Harvey, W.J.Kleintelder, K.P. McAuliffe, E.A. Melton, V.A. Norton and J. Weiss, "The IBM research parallel processor prototype (RP3): introduction and architecture," RC 11060, IBM T.J. Watson Research Center, Yorktown Heights, NY, March 1985.
• Seit 85: Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
• Wolf 82: M.J. Wolfe, "Optimizing supercompilers for supercomputers," TR UIUCDCS-R-82-1105, Department, of Computer Science, University of Illinois at Urbana-Champaign, October 1982.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

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

General Terms:
Algorithms, Languages, Theory