Compile-time and run-time strategies for array statement execution on distributed-memory machines
S. D. Kaushik · OhioLink ETD Center (Ohio Library and Information Network) · 1995
Distributed-memory machines have been recognized as a cost effective avenue to high performance computing. Although several commercial distributed-memory machines have been introduced in recent years, use of these machines has not been widespread, in large part due to the difficulty of programming them. To address this problem, languages such as high performance Fortran (HPF) have been defined to be portable parallel programming platforms for these machines. An HPF program is a single address space program annotated with specifications for mapping arrays to processors of the distributed-memory machine. In HPF, array statements are used to express data-parallelism. In this thesis, we develop methods for the efficient execution of array statements on distributed-memory machines. In compiling array statements for a distributed-memory machine, efficient generation of communication sets and local index sets is important. We show that for arrays distributed block-cyclically on multiple processors, the local memory access sequence and communication sets can be efficiently enumerated as closed forms using regular sections. First, closed form solutions are developed for arrays that are distributed using block or cyclic distributions. These closed forms are then used with a virtual processor approach to give an efficient solution for arrays with block-cyclic distributions. Performance results on a Cray T3D system demonstrate the efficacy of the virtual processor approach. To efficiently perform array redistribution, precise closed forms for enumerating the communication sets are developed for two special cases of array redistribution involving block-cyclically distributed arrays. The general case for array redistribution involving block-cyclically distributed arrays can be expressed in terms of these special cases. Using the closed forms, a distributed algorithm for scheduling the communication for redistribution to eliminate node contention is developed. The algorithm has a lower communication and scheduling overhead than those presented in the literature. Based on the closed forms, a cost model for estimating the communication overhead for array redistribution is developed. Using this model, a multi-phase approach for reducing the communication cost of array redistribution is presented. Experimental results on the IBM SP2 and Cray T3D validate the proposed cost model and demonstrate the efficacy of the multi-phase approach.