Automatic data layout for high performance Fortran

ABSTRACT

High Performance Fortran (HPF) is rapidly gaining acceptance as a language for parallel programming. The goal of HPF is to provide a simple yet efficient machine independent parallel programming model. Besides the algorithm selection, the data layout choice is the key intellectual step in writing an efficient HPF program. The developers of HPF did not believe that data layouts can be determined automatically in all cases, Therefore HPF requires the user to specify the data layout. It is the task of the HPF compiler to generate efficient code for the user supplied data layout. The choice of a good data layout depends on the HPF compiler used, the target architecture, the problem size, and the number of available processors. Allowing remapping of arrays at specific points in the program makes the selection of an efficient data layout even harder. Although finding an efficient data layout fully automatically may not be possible in all cases. HPF users will need support during the data layout selection process. In particular, this support is necessary if the user is not familiar with the characteristics of the target HPF compiler and target architecture, or even with HPF itself. Therefore, tools for automatic data layout and performance estimation will be crucial if the HPF is to find general acceptance in the scientific community. This paper discusses a framework for automatic data layout for use in a data layout assistant tool for a data-parallel language such as HPF. The envisioned tool can be used to generate a first data layout for a sequential Fortran program without data layout statements, or to extend a partially specified data layout in a HPF program to a totally specified data layout. Since the data layout assistant is not embedded in a compiler and will run only a few times during the tuning process of an application program, the framework can use techniques that may be too computationally expensive to be included in a compiler. A prototype data layout assistant tool based on our framework has been implemented as part of the D system currently under development at Rice University. The paper reports preliminary experimental results. The results indicate that the framework is efficient and generates data layouts of high quality.

REFERENCES

• ACG+94: Vikram Adve , Alan Carle , Elana Granston , Seema Hiranandani , Ken Kennedy , Charles Koelbel , Ulrich Kremer , John Mellor-Crummey , Scott Warren , Chau-Wen Tseng, Requirements for Data-Parallel Programming Environments, IEEE Parallel & Distributed Technology: Systems & Technology, v.2 n.3, p.48-58, September 1994 [doi>10.1109/M-PDT.1994.329801]
• AGG+94: Eduard Ayguadé , Jordi Garcia , Mercè Gironés , Jesús Labarta , Jordi Torres , Mateo Valero, Detecting and Using Affinity in an Automatic Data Distribution Tool, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.61-75, August 08-10, 1994
• AL93: Jennifer M. Anderson , Monica S. Lam, Global optimizations for parallelism and locality on scalable parallel machines, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.112-125, June 21-25, 1993, Albuquerque, New Mexico, United States
• ASU86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• BFKK91: Vasanth Balasundaram , Geoffrey Fox , Ken Kennedy , Ulrich Kremer, A static performance estimator to guide data partitioning decisions, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.213-223, April 21-24, 1991, Williamsburg, Virginia, United States
• Bix92: R. Bixby. Implementing the Simplex method: The initial basis. ORSA Journal on Computing, 4(3), 1992.
• BKK+94a: David Bau , Induprakas Kodukula , Vladimir Kotlyar , Keshav Pingali , Paul Stodghill, Solving Alignment Using Elementary Linear Algebra, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.46-60, August 08-10, 1994
• BKK94b: Robert E. Bixby , Ken Kennedy , Ulrich Kremer, Automatic Data Layout Using 0-1 Integer Programming, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.111-122, August 24-26, 1994
• CGS93: Siddhartha Chatterjee , John R. Gilbert , Robert Schreiber, The Alignment-Distribution Graph, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.234-252, August 12-14, 1993
• CGSS94: Siddhartha Chatterjee , Robert Schreiber , Thomas J. Sheffler , John R. Gilbert, Array Distribution in Data-Parallel Programs, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.76-91, August 08-10, 1994
• CGST93: Siddhartha Chatterjee , John R. Gilbert , Robert Schreiber , Shang-Hua Teng, Automatic array alignment in data-parallel programs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.16-28, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158517]
• FHK+90: G. Fox, S. Hiranandani, K. Kennedy, C. Koelbel, U. Kremer, C. Tseng, and M. Wu. Fortran D language specification. Technical Report TR90-141, Dept. of Computer Science, Rice University, December 1990.
• FJL+88: Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• GAL95: J. Garcia, E. Ayguad~, and J. Labarta. A novel approach towards automatic data distribution. In Proceedings of the Workshop on Automatic Data Layout and Performance Prediction (AP'95), Houston, TX, April 1995.
• Gup92: Manish Gupta, Automatic data partitioning on distributed memory multicomputers, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• HA90: David E. Hudak , Santosh G. Abraham, Compiler techniques for data partitioning of sequentially iterated parallel loops, Proceedings of the 4th international conference on Supercomputing, p.187-200, June 11-15, 1990, Amsterdam, The Netherlands
• Hec77: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• Keß93: C.W. Ke~ler. Knowledge-based automatic parallelization by pattern recognition. In C.W. Ke~ler, editor, Automatic Parallelization -- New Approaches to Code Generation, Data Distribution, and Performance Prediction, pages 110-135. Verlag Vieweg, Wiesbaden, Germany, 1993.
• KLD92: K. Knobe, J.D. Lukas, and W.J. Dally. Dynamic alignment on distributed memory systems. In Proceedings of the Third Workshop on Compilers for Parallel Computers, Vienna, Austria, July 1992.
• KLS90: 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]
• Kre93: U. Kremer. NP-completeness of dynamic remapping. In Proceedings of the Fourth Workshop on Compilers for Parallel Computers, Delft, The Netherlands, December 1993. Also available as technical report CRPC-TR93-330-S (D Newsletter #8), Rice University.
• Kre95: Ulrich Johannes Kremer, Automatic data layout for distributed memory machines, Rice University, Houston, TX, 1996
• LC90: J. Li and M. Chen. Index domain alignment: Minimizing cost of cross-referencing between distributed arrays. In Frontiers90: The 3rd Symposium on the Frontiers of Massively Parallel Computation, College Park, MD, October 1990.
• LT93: P. Lee and T-B. Tsai. Compiling efficient programs for tightly-coupled distributed memory computers. In Proceedings of the 1993 International Conference on Parallel Processing, St. Charles, IL, August 1993.
• NDG95: Qi Ning , V. Van Dongen , G. R. Gao, Automatic data and computation decomposition for distributed memory machines, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.103, January 04-07, 1995
• NW88: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• Phi95: Michael Philippsen, Automatic alignment of array data and processes to reduce communication time on DMPPs, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.156-165, July 19-21, 1995, Santa Barbara, California, United States
• RS89: J. Ramanujam , P. Sadayappan, A methodology for parallelizing programs for multicomputers and complex memory multiprocessors, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.637-646, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76335]
• SSP+95: Thomas J. Sheffler , Robert Schreiber , William Pugh , John R. Gilbert , Siddhartha Chatterjee, Efficient Distribution Analysis via Graph Contraction, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.377-391, August 10-12, 1995
• Tse93: Chau-Wen Tseng, An optimizing Fortran D compiler for MIMD distributed-memory machines, Rice University, Houston, TX, 1993
• Who91: Skef Wholey, Automatic data mapping for distributed-memory parallel computers, Carnegie Mellon University, Pittsburgh, PA, 1991

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

General Terms:
Algorithms, Experimentation, Languages, Performance