Compiling stencils in high performance Fortran

ABSTRACT

For many Fortran90 and HPF programs performing dense matrix computations, the main computational portion of the program belongs to a class of kernels known as stencils. Stencil computations are commonly used in solving partial differential equations, image processing, and geometric modeling. The efficient handling of such stencils is critical for achieving high performance on distributed-memory machines. Compiling stencils into efficient code is viewed as so important that some companies have built special-purpose compilers for handling them and others have added stencil-recognizers to existing compilers.In this paper we present a general compilation strategy for stencils written using Fortran90 array constructs. Our strategy is capable of optimizing single or multi-statement stencils and is applicable to stencils specified with shift intrinsics or with array-syntax all equally well. The strategy eliminates the need for pattern-recognition algorithms by orchestrating a set of optimizations that address the overhead of both intraprocessor and interprocessor data movement that results from the translation of Fortran90 array constructs. Our experimental results show that code produced by this strategy beats or matches the best code produced by the special-purpose compilers or pattern-recognition schemes that are known to us. In addition, our strategy produces highly optimized code in situations where the others fail, producing several orders of magnitude performance improvement, and thus provides a stencil compilation strategy that is more robust than its predecessors.

REFERENCES

• 1: Z. Bozkus, L. Meadows, D. Miles, S. Nakamoto, V. Schuster, and M. Young. Techniques for compiling and executing HPF programs on shared-memory and distributed-memory parallel systems. In Proceedings of the First International Workshop on Parallel Processing, Bangalore, India, December 1994.
• 2: Zeki Bozkus , Larry Meadows , Steven Nakamoto , Vincent Schuster , Mark Young, PGHPF—an optimizing High Performance Fortran compiler for distributed memory machines, Scientific Programming, v.6 n.1, p.29-40, Spring 1997
• 3: T. Brandes. Compiling data parallel programs to message passing programs for massively parallel MIMD systems. In Working Conference on Massively Parallel Programming Models, Berlin, 1993.
• 4: R. G. Brickner, W. George, S. L. Johnsson, and A. Ruttenberg. A stencil compiler for the Connection Machine models CM-2/200. In Proceedings of the Fourth Workshop on Compilers for Parallel Computers, Delft, The Netherlands, December 1993.
• 5: R. G. Brickner, K. Holian, B. Thiagarajan, and S. L. Johnsson. A stencil compiler for the Connection Machine model CM-5. Technical Report CRPC-TR94457, Center for Research on Parallel Computation, Rice University, June 1994.
• 6: 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
• 7: Steve Carr , Kathryn S. McKinley , Chau-Wen Tseng, Compiler optimizations for improving data locality, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.252-262, October 05-07, 1994, San Jose, California, United States
• 8: A. Choudhary, G. Fox, S. Hiranandani, K. Kennedy, C. Koelbel, S. Ranka, and C.-W. Tseng. Compiling Fortran 77D and 90D for MIMD distributed-memory machines. In Frontiers '92: The 4th Symposium on the Frontiers of Massively Parallel Computation, McLean, VA, October 1992.
• 9: 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]
• 10: William George , Ralph G. Brickner , S. Lennart Johnsson, POLYSHIFT communications software for the connection machine system CM-200, Scientific Programming, v.3 n.1, p.83-99, Spring 1994
• 11: 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]
• 12: Manish Gupta , Sam Midkiff , Edith Schonberg , Ven Seshadri , David Shields , Ko-Yang Wang , Wai-Mee Ching , Ton Ngo, An HPF compiler for the IBM SP2, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.71-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224422]
• 13: T. Haupt, S. Reddy, and G. Vengurlekar. Low level HPF compiler benchmark suite. Technical Report SCCS-735, Northeast Parallel Architectures Center, Syracuse University, Syracuse, NY, August 1995.
• 14: High Performance Fortran Forum. High Performance Fortran language specification. Scientific Programming, 2(1-2):1-170, 1993.
• 15: Ken Kennedy , John M. Mellor-Crummey , Gerald Roth, Optimizing Fortran 90 Shift Operations on Distributed-Memory Multicomputers, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.161-175, August 10-12, 1995
• 16: K. Kennedy and K. S. McKinley. Typed fusion with applications to parallel and sequential code generation. Technical Report TR93-208, Dept. of Computer Science, Rice University, August 1993.
• 17: K. Kennedy and G. Roth. Context optimization for SIMD execution. In Proceedings of the 1994 Scalable High Performance Computing Conference, Knoxville, TN, May 1994.
• 18: K. Knobe, J. Lukas, and M. Weiss. Optimization techniques for SIMD Fortran compilers. Concurrency: Practice and Experience, 5(7):527-552, October 1993.
• 19: Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
• 20: A. Mohamed, G. Fox, G. v. Laszewski, M. Parashar, T. Haupt, K. Mills, Y. Lu, N. Lin, and N. Yeh. Applications benchmark set for Fortran-D and High Performance Fortran. Technical Report SCCS-327, Northeast Parallel Architectures Center, Syracuse University, Syracuse, NY, June 1992.
• 21: J. R. Rice and J. Jing. Problems to test parallel and vector languages. Technical Report CSD-TR-1016, Dept. of Computer Science, Purdue University, 1990.
• 22: Gerald H. Roth, Optimizing Fortran90D/HPF for distributed-memory computers, Rice University, Houston, TX, 1997
• 23: G. Sabot. A compiler for a massively parallel distributed memory MIMD computer. In Frontiers '92: The 4th Symposium on the Frontiers of Massively Parallel Computation, McLean, VA, October 1992.
• 24: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990

INDEX TERMS

Keywords:
communication unioning, high performance Fortran, shift optimization, statement partitioning, stencil compilation