Evaluation of compiler optimizations for Fortran D on MIMD distributed memory machines

ABSTRACT

The Fortran D compiler uses data decomposition specifications to automatically translate Fortran programs for execution on MIMD distributed-memory machines. This paper introduces and classifies a number of advanced optimizations needed to achieve acceptable performance; they are analyzed and empirically evaluated for stencil computations. Profitability formulas are derived for each optimization. Results show that exploiting parallelism for pipelined computations, reductions, and scans is vital. Message vectorization, collective communication, and efficient coarse-grain pipelining also significantly affect performance.

REFERENCES

• 1: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 2: Françoise André , Jean-Louis Pazat , Henry Thomas, Pandore: a system to manage data distribution, Proceedings of the 4th international conference on Supercomputing, p.380-388, June 11-15, 1990, Amsterdam, The Netherlands
• 3: V. Balasundaram, G. Fox, K. Kennedy, and U. Kremer. An interactive environment for data partitioning and distribution. In Proceedings of the 5th Distributed Memory Computing Conference, Charleston, SC, April 1990.
• 4: 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
• 5: S. Benkner, B. Chapman, and H. Zima, Vienna Fortran 90. In Proceedings of the 1992 Scalable High Perjormanee Computing Conference, Williamsburg, VA, April 1992.
• 6: S. Bokhari. Complete exchange on the iPSC-860. ICASE Report 91-4, Institute for Computer Application in Science and Engineering, Hampton, VA, January 1991.
• 7: Mark Bromley , Steven Heller , Tim McNerney , Guy L. Steele, Jr., Fortran at ten gigaflops: the connection machine convolution compiler, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.145-156, June 24-28, 1991, Toronto, Ontario, Canada
• 8: D. Callahan, K. Cooper, R. Hood, K. Kennedy, and L. Torczon. ParaScope: A parallel programming environment. The Internatlonal Journal of Supercomputer Applications, 2(4):84-99, Winter 1988.
• 9: D. Callahan and K. Kennedy. Compiling programs for distributed-memory multiprocessors. Journal of Supercom. purist, 2:151-169, October 1988.
• 10: C. Chase, A. Cheung, A. Reeves, and M. Smith. Paragon: A parallel programming environment for scientific applications using communication structures. In Proceedings of the 1991 International Conference on Parallel Processing, St. Charles, IL, August 1991.
• 11: Siddhartha Chatterjee , Guy E. Blelloch , Marco Zagha, Scan primitives for vector computers, Proceedings of the 1990 conference on Supercomputing, p.666-675, October 1990, New York, New York, United States
• 12: G. Fox, S. Hiranandani, K. Kennedy, C. Koelbel, U. Kremet, C. Tseng, and M. Wu. Fortran D language specification. Technical Report TR90-141, Dept. of Computer Science, Rice University, December 1990.
• 13: 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
• 14: E. Gabber, A. Averbuch, and A. Yehudai. Experience with a portable parallelizing Pascal compiler. In Proceedings of the 1991 international Conference on Parallel Processing, St. Charles, IL, August 1991.
• 15: M. Gerndt, Updating distributed variables in local computations, Concurrency: Practice and Experience, v.2 n.3, p.171-193, Sep. 1990 [doi>10.1002/cpe.4330020303]
• 16: Manish Gupta , Prithviraj Banerjee, Compile-Time Estimation of Communication Costs on Multicomputers, Proceedings of the 6th International Parallel Processing Symposium, p.470-475, March 01, 1992
• 17: P. J. Hatcher , M. J. Quinn , A. J. Lapadula , B. K. Seevers , R. J. Anderson , R. R. Jones, Data-Parallel Programming on MIMD Computers, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.377-383, July 1991 [doi>10.1109/71.86112 ]
• 18: P. Havlak , K. Kennedy, An Implementation of Interprocedural Bounded Regular Section Analysis, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.350-360, July 1991 [doi>10.1109/71.86110 ]
• 19: 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
• 20: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiler optimizations for Fortran D on MIMD distributed-memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.86-100, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125886]
• 21: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Computer support for machine-independent parallel programming in Fortran D, Languages, compilers and run-time environments for distributed memory machines, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 1992
• 22: K. Ikudome, G. Fox, A. Kolawa, and J. Flower. An automatic and symbolic parallelization system for distributed memory parallel computers. In Proceedings of the 5th Distributed Memory Computing ConIer~nce, Charleston, SG, April 1990.
• 23: K. Kennedy and U. Kremer. Automatic data alignment and distribution for loosely synchronous problems in an interactive programming environment. Technical Report TR91- 155, Dept. of Computer Science, Rice University, April 1991.
• 24: Ken Kennedy , Kathryn S. McKinley, Optimizing for parallelism and data locality, Proceedings of the 6th international conference on Supercomputing, p.323-334, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143427]
• 25: Ken Kennedy , Kathryn S. McKinley , Chau-Wen Tseng, Analysis and transformation in the ParaScope editor, Proceedings of the 5th international conference on Supercomputing, p.433-447, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109126]
• 26: Charles Koelbel , Piyush Mehrotra, Programming data parallel algorithms on distributed memory using Kali, Proceedings of the 5th international conference on Supercomputing, p.414-423, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109122]
• 27: P. Kogge and H. Stone. A parallel algorithm for the efficient solution of a general class of recurrence equations. IEEE Transactions on Computers, C-22(8):786-793, August 1973.
• 28: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 29: 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 ]
• 30: F. McMahon. The Livermore Fortran Kernels: A computer test of the numerical performance range. Technical Report UCRL-53745, Lawrence Livermore National Laboratory, 1986.
• 31: D. Olander and R. Schnabel. Preliminary experience in developing a parallel thin-layer Navier Stokes code and implications for parallel language design. In Proceedings of the 1992 Scalable High Performance Computing Conference, Williamsburg, VA, April 1992.
• 32: 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
• 33: J. Rose and G. Steele, Jr. C*: An extended C language for data parallel programming. In L. Kartashev and S. Kartashev, editors, Proceedings of the Second International Conference on Supercomputing, Santa Clara, CA, May 1987.
• 34: Matthew Rosing , Robert B. Schnabel , Robert P. Weaver, The DINO parallel programming language, Journal of Parallel and Distributed Computing, v.13 n.1, p.30-42, Sept. 1991 [doi>10.1016/0743-7315(91)90107-K]
• 35: Roland Rühl , Marco Annaratone, Parallelization of FORTRAN code on distributed-memory parallel processors, Proceedings of the 4th international conference on Supercomputing, p.342-353, June 11-15, 1990, Amsterdam, The Netherlands
• 36: P.-S. Tseng. A parallelizing compiler for distributed memory parallel computers, in Proceedings of the SIGPLAN '90 Conference on Program Language Design and Implementation, White Plains, NY, June 1990.
• 37: J. Wu, J. Saltz, S. Hiranandani, and H. Berryman. Runtime compilation methods for multicomputers. In Proceedings of the 1991 International Conference on Parallel Processing, St. Charles, IL, August 1991.
• 38: H. Zima, H.-J. Bast, and M. Gerndt. SUPERB: A tool for semi-automatic MIMD/SIMD parallelization. Parallel Computing, 6:1-18, 1988.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  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; Compilers

General Terms:
Algorithms, Languages, Performance