An Algebraic Machinery for Optimizing Data Motion for HPF

Article type: Research Article

Authors: Wu, Jan-Jan | Chen, Marina C.

Affiliations: Institute of Information Science, Academia Sinica, Taipei, Taiwan 11529; E-mail: wuj@iis.sinica.edu.tw | Computer Science Department, Boston University, 111 Cummington Street, Boston, MA 0221, USA; E-mail: mcchen@cs.bu.edu

Abstract: This paper describes a general compiler optimization technique that reduces communica tion over-head for FORTRAN-90 (and High Performance FORTRAN) implementations on massively parallel machines. The main sources of communication, or data motion, for the parallel implementation of a FORTRAN-90 program are array assignments, array operators (e.g., CSHIFT, TRANSPOSE, etc.), and array parameters passing to and from subroutines. Coupled with the variety of ways arrays can be distributed, a FORTRAN-90 implementor faces a rich space of posibilities by which data motion can be organized. We propose a unified framework for optimizing intra- and inter-procedural data motion. The central idea of this framework is algebraic analysis of data motion. We give an algebraic representation for each HPF's array intrinsics and data distribution specifications. An array reference extracted from the source FORTRAN-90 program, given a particular data distribution specification, is represented as a communication expression, which in turn can be simplified according to a communication algebra. Fast communication is uncovered by pattern matching with a set of communication idioms. Experimental results on the Connection Machine CM-5 demonstrating the effectiveness of this approach are reported.

Journal: Scientific Programming, vol. 6, no. 3, pp. 297-325, 1997