Automatic array alignment in data-parallel programs

ABSTRACT

Data-parallel languages like Fortran 90 express parallelism in the form of operations on data aggregates such as arrays. Misalignment of the operands of an array operation can reduce program performance on a distributed-memory parallel machine by requiring nonlocal data accesses. Determining array alignments that reduce communication is therefore a key issue in compiling such languages. We present a framework for the automatic determination of array alignments in data-parallel languages such as Fortran 90. Our language model handles array sectioning, reductions, spreads, transpositions, and masked operations. We decompose alignment functions into three constituents: axis, stride, and offset. For each of these subproblems, we show how to solve the alignment problem for a basic block of code, possibly containing common subexpressions. Alignments are generated for all array objects in the code, both named program variables and intermediate results. The alignments obtained by our algorithms are more general than those provided by the “owner-computes” rule. Finally, we present some ideas for dealing with control flow, replication, and dynamic alignments that depend on loop induction variables.

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: AMERICAN NATIONAL STANDARDS INSTITUTE. Fortran 90: X3J3 internal document $8.118 Submitted as Text /or ANSI X3.198-1991, and ISO/IEC JTC1/SC~2/WG5 internal document N692 Submitted as Text for ISO/IEC 1539:1991, May 1991.
• 3: BALA, V., AND FERRANTE, J. Explicit data placement (XDP): A methodology for explicit compile-time representation and optimization of data movement. In Proceedings o} the Second Workshop on Languages, Compilers, and Runtime Environments/or Distributed Memory Multiprocessors (Boulder, CO, Oct. 1992).
• 4: CHAPMAN, B., MEHROTRA, P., AND ZrMA, H. Programming in Vienna Fortran. Scientific Programming 1, 1 (Fall 1992), 31-50.
• 5: Siddhartha Chatterjee, Compiling data-parallel programs for efficient execution on shared-memory multiprocessors, Carnegie Mellon University, Pittsburgh, PA, 1992
• 6: CHATTERJEE, S., GILBERT, J. R., SCI-tREIBER, R., AND TENG, S.-H. Optimal evaluation of array expressions on massively parallel machines. In Proceedings o} the Second Workshop on Languages, Compilers, and Runtime Environments for Distributed Memory Multi. processors (Boulder, CO, Oct. 1992). Also available as RIACS Technical Report TR 92.17.
• 7: CHEN, M. C., AND WU, J.-J. Optimizing FORTRAN- 90 programs for data motion on massively parallel systems. Tech. Rep. YALEU/DCS/TR-882, Department of Computer Science, Yale University, New Haven, CT, Jan. 1992.
• 8: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 9: Fox, G. C., HmANANDANI, S., KENNEDY, K., KOEL- BEL, C., KREMER, U., TSENG, C.-W., AND WU, M.- Y. Fortran D language specification. Tech. Rep. Rice COMP TR90-141, Department of Computer Science, Rice University, Houston, TX, Dec. 1990.
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: John R. Gilbert , Robert Schreiber, Optimal expression evaluation for data parallel architectures, Journal of Parallel and Distributed Computing, v.13 n.1, p.58-64, Sept. 1991 [doi>10.1016/0743-7315(91)90109-M]
• 12: GILL, P. E., MURRAY, W., AND WRIGHT, M. H. Practical Optimization. Academic Press, Orlando, FL, 1981.
• 13: Manish Gupta, Automatic data partitioning on distributed memory multicomputers, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 14: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 15: HIGH PERFORMANCE FORTRAN FORUM. High Performance Fortran language specification version 1.0. Draft, Sept. 1992.
• 16: HmANANDANI, S., KENNEDY, K., AND TSENG, C.- W. Compiler support for machine-independent parallel programming in Fortran D. Tech. Rep. Rice COMP TR90-149, Department of Computer Science, Rice University, Houston, TX, Feb. 1991.
• 17: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
• 18: KNOBE, K., LUKAS, J. D., AND DALLY, W. J. Dynamic alignment on distributed memory systems. In Proceedings o} the Third Workshop on Compilers }or Parallel Computers (Vienna, Austria, July 1992), Austrian Center for Parallel Computation, pp. 394-404.
• 19: Kathleen Knobe , Joan D. Lukas , Guy L. Stelle, Jr., Data optimization: allocation of arrays to reduce communication on SIMD machines, Journal of Parallel and Distributed Computing, v.8 n.2, p.102-118, February 1990 [doi>10.1016/0743-7315(90)90086-5]
• 20: Charles E. Leiserson, Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, v.34 n.10, p.892-901, Oct. 1985
• 21: Jingke Li , Marina Chen, The data alignment phase in compiling programs for distributed-memory machines, Journal of Parallel and Distributed Computing, v.13 n.2, p.213-221, Oct. 1991 [doi>10.1016/0743-7315(91)90090-V]
• 22: Mary E. Mace, Memory storage patterns in parallel processing, Kluwer Academic Publishers, Norwell, MA, 1987
• 23: MELZAK, Z. On the problem of Steiner. Canadian Mathematical Bulletin ~ (1961), !43-148.
• 24: THINKrNG MACHINES CORPORATION. CM Fortran Re}- erence Manual Versions 1.0 and 1.1. Cambridge, MA, July 1991.
• 25: Skef Wholey, Automatic data mapping for distributed-memory parallel computers, Carnegie Mellon University, Pittsburgh, PA, 1991
• 26: P. Winter, Steiner problem in networks: a survey, Networks, v.17 n.2, p.129-167, Summer 1987 [doi>10.1002/net.3230170203]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages
          Nouns: Fortran 90
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

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

General Terms:
Algorithms, Languages