An HPF compiler for the IBM SP2

ABSTRACT

We describe pHPF, an research prototype HPF compiler for the IBM SP series parallel machines. The compiler accepts as input Fortran 90 and Fortran 77 programs, augmented with HPF directives; sequential loops are automatically parallelized. The compiler supports symbolic analysis of expressions. This allows parameters such as the number of processors to be unknown at compile-time without significantly affecting performance. Communication schedules and computation guards are generated in a parameterized form at compile-time. Several novel optimizations and improved versions of well-known optimizations have been implemented in pHPF to exploit parallelism and reduce communication costs. These optimizations include elimination of redundant communication using data-availability analysis; using collective communication; new techniques for mapping scalar variables; coarse-grain wavefronting; and communication reduction in multi-dimensional shift communications. We present experimental results for some well-known benchmark routines. The results show the effectiveness of the compiler in generating efficient code for HPF programs.

REFERENCES

• 1: Saman P. Amarasinghe , Jennifer-Ann M. Anderson , Monica S. Lam , Amy W. Lim, An Overview of a Compiler for Scalable Parallel Machines, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.253-272, August 12-14, 1993
• 2: Prithviraj Banerjee , John A. Chandy , Manish Gupta , Eugene W. Hodges IV , John G. Holm , Antonio Lain , Daniel J. Palermo , Shankar Ramaswamy , Ernesto Su, The Paradigm Compiler for Distributed-Memory Multicomputers, Computer, v.28 n.10, p.37-47, October 1995 [doi>10.1109/2.467577]
• 3: Zeki Bozkus , Alok N. Choudhary , Geoffrey Fox , Tomasz Haupt , Sanjay Ranka, A Compilation Approach for Fortran 90D/ HPF Compilers, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.200-215, August 12-14, 1993
• 4: T. Brandes. ADAPTOR: A compilation system for data-parallel Fortran programs. In C. W. Kessler, editor, Automatic parallelization -- new approaches to code generation, data distribution, and performance prediction. Vieweg Advanced Studies in Computer Science, Vieweg, Wiesbaden, January 1994.
• 5: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 6: Thomas Fahringer , Hans P. Zima, A static parameter based performance prediction tool for parallel programs, Proceedings of the 7th international conference on Supercomputing, p.207-219, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165971]
• 7: ANSI Fortran 90 Standard Committee. Fortran 90, 1990. ANSI standard X3.198-199x, which is identical to ISO standard ISO/IEC 1539:1991.
• 8: High Performance Fortran Forum. High Performance Fortran language specification, version 1.0. Technical Report CRPC-TR92225, Rice University, May 1993.
• 9: Manish Gupta , Prithviraj Banerjee, A methodology for high-level synthesis of communication on multicomputers, Proceedings of the 6th international conference on Supercomputing, p.357-367, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143433]
• 10: Manish Gupta , Edith Schonberg , Harini Srinivasan, A Unified Data-Flow Framework for Optimizing Communication, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.266-282, August 08-10, 1994
• 11: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiling Fortran D for MIMD distributed-memory machines, Communications of the ACM, v.35 n.8, p.66-80, Aug. 1992 [doi>10.1145/135226.135230]
• 12: Doug Kimelman , Pradeep Mittal , Edith Schonberg , Peter F. Sweeney , Ko-Yang Wang , Dror Zernik, Visualizing the execution of High Performance Fortran (HPF) programs, Proceedings of the 9th International Symposium on Parallel Processing, p.750-759, April 25-28, 1995
• 13: 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
• 14: 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]
• 15: J.M. Levesque. Applied Parallel Research's xHPF system. IEEE Parallel & Distributed Technologies, page 71, Fall 1994.
• 16: 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]
• 17: 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
• 18: V.J. Schuster. PGHPF from The Portland Group. IEEE Parallel & Distributed Technologies, page 72, Fall 1994.
• 19: E. Su, D. J. Palermo, and P. Banerjee. Automating parallelization of regular computations for distributed memory multicomputers in the PARADIGM compiler. In Proc. 1993 International Conference on Parallel Processing, St. Charles, IL, August 1993.
• 20: R. Thakur, R. Bordawekar, and A. Choudhary. Compiler and runtime support for out-of-core HPF programs. Technical Report SCCS-597, NPAC, Syracuse University, 1994.
• 21: Reinhard von Hanxleden , Ken Kennedy, GIVE-N-TAKE—a balanced code placement framework, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.107-120, June 20-24, 1994, Orlando, Florida, United States
• 22: M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]
• 23: H. Zima and B. Chapman. Compiling for distributed-memory systems. Proceedings of the IEEE, 81-13(2):264--287, Feb 1993.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.1 Design Styles
          Subjects: Parallel

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

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Design, Performance

Keywords:
compiler, automatic parallelization, distributed memory compilation, communication optimization, optimizing compiler, HPF, Fortran, IBM SP2