Automatic data layout for distributed-memory machines

ABSTRACT

The goal of languages like Fortran D or High Performance Fortran (HPF) is to provide a simple yet efficient machine-independent parallel programming model. After the algorithm selection, the data layout choice is the key intellectual challenge in writing an efficient program in such languages. The performance of a data layout depends on the target compilation system, the target machine, the problem size, and the number of available processors. This makes the choice of a good layout extremely difficult for most users of such languages. If languages such as HPF are to find general acceptance, the need for data layout selection support has to be addressed. We beleive that the appropriate way to provide the needed support is through a tool that generates data layout specifications automatically. This article discusses the design and implementation of a data layout selection tool that generates HPF-style data layout specifications automatically. Because layout is done in a tool that is not embedded in the target compiler and hence will be run only a few times during the tuning phase of an application, it can use techniques such as integer programming that may be considered too computationally expensive for inclusion in production compilers. The proposed framework for automatic data layout selection builds and examines search spaces of candidate data layouts. A candidate layout is an efficient layout for some part of the program. After the generation of search spaces, a single candidate layout is selected for each program part, resulting in a data layout for the entire program. A good overall data layout may require the remapping of arrays between program parts. A performance estimator based on a compiler model, an execution model, and a machine model are needed to predict the execution time of each candidate layout and the costs of possible remappings between candidate data layouts. In the proposed framework, instances of NP-complete problems are solved during the construction of candidate layout search spaces and the final selection of candidate layouts from each search space. Rather than resorting to heuristics, the framework capitalizes on state-of-the-art 0-1 integer programming technology to compute optimal solutions of these NP-complete problems. 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 article reports preliminary experimental results. The results indicate that the framework is efficient and allows the generation of data layouts of high quality.

REFERENCES

• 1: 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]
• 2: Vikram Adve , John Mellor-Crummey, Advanced code generation for high performance Fortran, Compiler optimizations for scalable parallel systems: languages, compilation techniques, and run time systems, Springer-Verlag New York, Inc., New York, NY, 2001
• 3: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 4: Erik R. Altman , R. Govindarajan , Guang R. Gao, Scheduling and mapping: software pipelining in the presence of structural hazards, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.139-150, June 18-21, 1995, La Jolla, California, United States
• 5: R. Govindarajan , Erik R. Altman , Guang R. Gao, Minimizing register requirements under resource-constrained rate-optimal software pipelining, Proceedings of the 27th annual international symposium on Microarchitecture, p.85-94, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192733]
• 6: Jennifer-Ann Monique Anderson , Monica S. Lam, Automatic computation and data decomposition for multiprocessors, 1997
• 7: 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
• 8: 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
• 9: 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
• 10: 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
• 11: BIXBY, R. 1992. Implementing the Simplex method: The initial basis. ORSA J. Comput. 4, 3, 267-284.
• 12: 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
• 13: CALLAHAN, D. AND KENNEDY, K. 1988. Compiling programs for distributed-memory multiprocessots. J. Supercomput. 2, 151-169.
• 14: Barbara M. Chapman , Piyush Mehrotra , Hans P. Zima, Vienna Fortran—a Fortran language extension for distributed memory multiprocessors, Languages, compilers and run-time environments for distributed memory machines, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 1992
• 15: 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]
• 16: Siddhartha Chatterjee , John R. Gilbert , Robert Schreiber , Shang-Hua Teng, Optimal evaluation of array expressions on massively parallel machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.123-156, Jan. 1995 [doi>10.1145/200994.201004]
• 17: 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
• 18: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 19: Mirela Damian-Iordache , Sriram V. Pemmaraju, Automatic Data Decomposition for Message-Passing Machines, Proceedings of the 10th International Workshop on Languages and Compilers for Parallel Computing, p.64-78, August 07-09, 1997
• 20: D'HOLLANDER, E. 1989. Partitioning and labeling of index sets in do loops with constant dependence. In Proceedings of the 1989 International Conference on Parallel Processing. II139-II144.
• 21: R. Kent Dybvig, The SCHEME programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 22: Paul Feautrier, Fine-Grain Scheduling under Resource Constraints, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.1-15, August 08-10, 1994
• 23: Fox, G., HIRANANDANI, S., KENNEDY, K., KOELBEL, C., KREMER, W., TSENG, C., AND WU, M. 1990. Fortran D language specification. Tech. Rep. TR90-141, Dept. of Computer Science, Rice University, Houston, Tex.
• 24: 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
• 25: GARCIA, J. 1997. Automatic data distribution for massively parallel processors. Ph.D. thesis, Universitat Polit~cnica de Catalunya, Barcelona, Spain.
• 26: GARCIA, J., AYGUADI~, E., AND LABARTA, J. 1995. A novel approach towards automatic data distribution. In Proceedings of the Workshop on Automatic Data Layout and Performance Prediction (AP'95). Available as Rice University Tech. Rep. CRPC-TR95-548.
• 27: Jordi Garcia , Eduard Ayguade , Jesus Labarta, Dynamic data distribution with control flow analysis, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.11-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369048]
• 28: Manish Gupta, Automatic data partitioning on distributed memory multicomputers, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 29: M. Gupta , P. Banerjee, Demonstration of Automatic Data Partitioning Techniques for Parallelizing Compilers on Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.179-193, March 1992 [doi>10.1109/71.127259]
• 30: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 31: Seema Hiranandani , Ken Kennedy , Charles Koelbel , Ulrich Kremer , Chau-Wen Tseng, An Overview of the Fortran D Programming System, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.18-34, August 07-09, 1991
• 32: Chua-Huang Huang , P. Sadayappan, Communication-Free Hyperplane Partitioning of Nested Loops, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.186-200, August 07-09, 1991
• 33: 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
• 34: Wayne Kelly , William Plugh, Minimizing communication while preserving parallelism, Proceedings of the 10th international conference on Supercomputing, p.52-60, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237585]
• 35: Ken Kennedy , Ulrich Kremer, Automatic data layout for high performance Fortran, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.76-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224495]
• 36: 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]
• 37: Kathleen Knobe , Venkataraman Natarajan, Automatic data allocation to minimize communication on SIMD machines, The Journal of Supercomputing, v.7 n.4, p.387-415, Dec. 1993 [doi>10.1007/BF01206043]
• 38: Charles H. Koelbel , David B. Loveman , Robert S. Schreiber , Guy L. Steele, Jr. , Mary E. Zosel, The high performance Fortran handbook, MIT Press, Cambridge, MA, 1994
• 39: C. Koelbel , P. Mehrotra, Compiling Global Name-Space Parallel Loops for Distributed Execution, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.440-451, October 1991 [doi>10.1109/71.97901]
• 40: Ulrich Johannes Kremer, Automatic data layout for distributed memory machines, Rice University, Houston, TX, 1996
• 41: KREMER, U. 1997. Optimal and near-optimM solutions for hard compilation problems. Parallel Process. Lett. 7, 2, 371-378.
• 42: Ulrich Kremer, Automatic Data Layout with Read-Only Replication and Memory Constraints, Proceedings of the 10th International Workshop on Languages and Compilers for Parallel Computing, p.419-422, August 07-09, 1997
• 43: KREMER, U. AND RAMIe, M. 1994. Compositional oil reservoir simulation in Fortran D" A feasibility study on Intel iPSC,/860. Int. J. Supercomput. Appl. 8, 2 (Summer), 119-128.
• 44: LEE, P. AND TSAI, T.-B. 1993. Compiling efficient programs for tightly-coupled distributed mereory computers. In Proceedings of the 1993 International Conference on Parallel Processing. II161-II165.
• 45: Jingke Li, Compiling crystal for distributed-memory machines, Yale University, New Haven, CT, 1992
• 46: J. Li , M. Chen, Compiling Communication-Efficient Programs for Massively Parallel Machines, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.361-376, July 1991 [doi>10.1109/71.86111]
• 47: 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]
• 48: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 49: 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
• 50: Qi Ning , Guang R. Gao, A novel framework of register allocation for software pipelining, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.29-42, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158519]
• 51: Daniel Joseph Palermo , Prithviraj Banerjee, Compiler techniques for optimizing communication and data distribution for distributed-memory multicomputers, 1996
• 52: PALERMO, D. AND BANERJEE, P. 1995. Automatic selection of dynamic data partitioning schemes for distributed-memory multicomputers. Technical Report CRHC-95-09, Center for Reliable and High-Performance Computing, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Ill.
• 53: Daniel J. Palermo , Eugene W. Hodges, IV , Prithviraj Banerjee, Interprocedural Array Redistribution Data-Flow Analysis, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.435-449, August 08-10, 1996
• 54: 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
• 55: PRESBERG, D. L. 1996. Comparison of 3 HPF compilers for the IBM SP. NHSF, Rev. 1996, 2. Available at http://www.crpc.rice.edu/NHSEreview/96-2.html.
• 56: William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125848]
• 57: 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]
• 58: A. Rogers , K. Pingali, Process decomposition through locality of reference, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.69-80, June 19-23, 1989, Portland, Oregon, United States
• 59: ROSE, J. AND STEELE, G. 1987. C*: An extended C language for data parallel programming. Technical Report PL87-5, Thinking Machines, Inc., Cambridge, Mass.
• 60: Thomas J. Sheffler , Robert Schreiber , William Pugh , John R. Gilbert , Siddhartha Chatterjee, Efficient distribution analysis via graph contraction, International Journal of Parallel Programming, v.24 n.6, p.599-620, Dec. 1996
• 61: Sudarsan Tandri , Tarek S. Abdelrahman, Automatic Partitioning of Data and Computations on Scalable Shared Memory Multiprocessors, Proceedings of the international Conference on Parallel Processing, p.64-73, August 11-15, 1997
• 62: Thinking Machines Corp. 1989. CM Fortran Reference Manual, Version 5.2-0.6 ed. Thinking Machines Corp., Cambridge, Mass.
• 63: Chau-Wen Tseng, An optimizing Fortran D compiler for MIMD distributed-memory machines, Rice University, Houston, TX, 1993
• 64: Skef Wholey, Automatic data mapping for distributed-memory parallel computers, Carnegie Mellon University, Pittsburgh, PA, 1991
• 65: Skef Wholey, Automatic data mapping for distributed-memory parallel computers, Proceedings of the 6th international conference on Supercomputing, p.25-34, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143377]
• 66: ZIMA, H., BAST, H.-J., AND GERNDT, M. 1988. SUPERB: A tool for semi-automatic MIMD,/SIMD parallelization. Parallel Comput. 6, 1-18.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

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

General Terms:
Algorithms, Languages, Theory

Keywords:
high performance Fortran