Interprocedural compilation of irregular applications for distributed memory machines

ABSTRACT

Data parallel languages like High Performance Fortran (HPF) are emerging as the architecture independent mode of programming distributed memory parallel machines. In this paper, we present the interprocedural optimizations required for compiling applications having irregular data access patterns, when coded in such data parallel languages. We have developed an Interprocedural Partial Redundancy Elimination (IPRE) algorithm for optimized placement of runtime preprocessing routine and collective communication routines inserted for managing communication in such codes. We also present two new interprocedural optimizations, placement of scatter routines and use of coalescing and incremental routines. We then describe how program slicing can be used for further applying IPRE in more complex scenarios. We have done a preliminary implementation of the schemes presented here using the Fortran D compilation system as the necessary infrastructure. We present experimental results from two codes compiled using our system to demonstrate the efficacy of the presented schemes.

REFERENCES

• 1: Gagan Agrawal , Joel Saltz, Interprocedural communication optimizations for distributed memory compilation, University of Maryland at College Park, College Park, MD, 1994
• 2: Gagan Agrawal , Joel Saltz , Raja Das, Interprocedural partial redundancy elimination and its application to distributed memory compilation, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.258-269, June 18-21, 1995, La Jolla, California, United States
• 3: G. Agrawal , A. Sussman , J. Saltz, Compiler and runtime support for structured and block structured applications, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.578-587, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169801]
• 4: Gagan Agrawal, Alan Sussman, and Joel Saltz. Efficient runtime support for parallelizing block structured applications. In Proceedings of the Scalable High Performance Computing Conference (SHPCC-94), pages 158--167. IEEE Computer Society Press, May 1994.
• 5: Gagan Agrawal , Alan Sussman , Joel Saltz, An integrated runtime and compile-time approach for parallelizing structured and block structured applications, University of Maryland at College Park, College Park, MD, 1993
• 6: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 7: Aart J. C. Bik , Harry A. G. Wijshoff, Annotations for a Sparse Compiler, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.500-514, August 10-12, 1995
• 8: Zeki Bozkus , Alok Choudhary , Geoffrey Fox , Tomasz Haupt , Sanjay Ranka , Min-You Wu, Compiling Fortran 90D/HPF for distributed memory MIMD computers, Journal of Parallel and Distributed Computing, v.21 n.1, p.15-26, April 1994 [doi>10.1006/jpdc.1994.1039]
• 9: B. R. Brooks, R. E. Bruccoleri, B. D. Olafson, D. J. States, S. Swaminathan, and M. Karplus. Charmm: A program for macromolecular energy, minimization, and dy namics calculations. Journal of Computational Chemistry, 4:187, 1983.
• 10: D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.47-56, June 20-24, 1988, Atlanta, Georgia, United States
• 11: A. Choudhary, G. Fox, S. Hiranandani, K. Kennedy, C. Koelbel, S. Ranka, and J. Saltz. Software support for irregular and loosely synchronous problems. Computing Systems in Engineering, 3(1--4):43--52, 1992. Papers presented at the Symposium on High-Performance Computing for Flight Vehicles, December 1992.
• 12: Keith D. Cooper , Ken Kennedy , Linda Torczon, The impact of interprocedural analysis and optimization in the Rⁿ programming environment, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.491-523, Oct. 1986 [doi>10.1145/6465.6489]
• 13: R. Das, D. J. Mavriplis, J. Saltz, S. Gupta, and R. Ponnusamy. The design and implementation of a parallel unstructured Euler solver using software primitives. AIAA Journal, 32(3):489--496, March 1994.
• 14: Raja Das , Joel Saltz , Reinhard von Hanxleden, Slicing analysis and indirect accesses to distributed arrays, University of Maryland at College Park, College Park, MD, 1993
• 15: Raja Das, Joel Saltz, Ken Kennedy, and Paul Havlak. Index array flattening through program transformation. Submitted to PLDI '95, November 1994.
• 16: D. M. Dhamdhere , Harish Patil, An elimination algorithm for bidirectional data flow problems using edge placement, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.2, p.312-336, April 1993 [doi>10.1145/169701.169684]
• 17: Guy Edjlali , Gagan Agrawal , Alan Sussman , Joel H. Saltz, Data parallel programming in an adaptive environment, Proceedings of the 9th International Symposium on Parallel Processing, p.827-832, April 25-28, 1995
• 18: 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
• 19: Mary Wolcott Hall, Managing interprocedural optimization, Rice University, Houston, TX, 1992
• 20: Mary W. Hall , John M. Mellor-Crummey , Alan Carle , René G. Rodríguez, FIAT: A Framework for Interprocedural Analysis and Transfomation, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.522-545, August 12-14, 1993
• 21: M. W. Hall , S. Hiranandani , K. Kennedy , C.-W. Tseng, Interprocedural compilation of Fortran D for MIMD distributed-memory machines, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.522-534, November 16-20, 1992, Minneapolis, Minnesota, United States
• 22: R. v. Hanxleden, K. Kennedy, and J. Saltz. Value-based distributions in Fortran D -- a preliminary report. Technical Report CRPC-TR93365-S, Center for Research on Parallel Computation, Rice University, December 1993. Submitted to Journal of Programming Languages - Special Issue on Compiling and Run-Time Issues for Distributed Address Space Machines.
• 23: Reinhard v. Hanxleden. Handling irregular problems with Fortran D - a preliminary report. In Proceedings of the Fourth Workshop on Compilers for Parallel Computers, Delft, The Netherlands, December 1993. Also available as CRPC Technical Report CRPC-TR93339-S.
• 24: 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
• 25: Mary Jean Harrold , Mary Lou Soffa, Efficient computation of interprocedural definition-use chains, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.2, p.175-204, March 1994 [doi>10.1145/174662.174663]
• 26: 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]
• 27: Yuan-Shin Hwang , Raja Das , Joel Saltz , Bernard Brooks , Milan Hodošček, Parallelizing molecular dynamics programs for distributed memory machines: an application of the CHAOS runtime support library, University of Maryland at College Park, College Park, MD, 1994
• 28: 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
• 29: 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]
• 30: Vladimir Kotlyar , Keshav Pingali , Paul Stodghill, Automatic Parallelization of the Conjugate Gradient Algorithm, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.480-499, August 10-12, 1995
• 31: Antonio Lain , Prithviraj Banerjee, Exploiting spatial regularity in irregular iterative applications, Proceedings of the 9th International Symposium on Parallel Processing, p.820-826, April 25-28, 1995
• 32: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 33: Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
• 34: R. Ponnusamy , J. Saltz , A. Choudhary, Runtime compilation techniques for data partitioning and communication schedule reuse, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.361-370, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169752]
• 35: Shamik D. Sharma , Ravi Ponnusamy , Bongki Moon , Yuan-Shin Hwang , Raja Das , Joel Saltz, Run-time and compile-time support for adaptive irregular problems, Proceedings of the 1994 conference on Supercomputing, p.97-106, December 1994, Washington, D.C., United States
• 36: Alan Sussman , Gagan Agrawal , Joel Saltz, A manual for the multiblock PARTI runtime primitives, University of Maryland at College Park, College Park, MD, 1994
• 37: Mark Weiser. Program slicing. IEEE Transactions on Software Engineering, 10:352--357, 1984.
• 38: Raja Das , Janet Wu , Joel Saltz , Harry Berryman , Seema Hiranandani, Distributed Memory Compiler Design For Sparse Problems, IEEE Transactions on Computers, v.44 n.6, p.737-753, June 1995 [doi>10.1109/12.391186]

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
      C.1.3 Other Architecture Styles
          Subjects: Data-flow 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: Preprocessors

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

General Terms:
Design, Languages, Performance