GENERATING LOCAL ADDRESSES AND COMMUNICATION SETS FOR DATA-PARALLEL PROGRAMS

Generating local addresses and communication sets is an important issu e in distributed-memory implementations of data-parallel languages suc h as High Performance Fortran. We demonstrate a storage scheme for an array A affinely aligned to a template that is distributed across p pr ocessors with a cyclic(k) distribution that does not waste any storage , and show that, under this storage scheme, the local memory access se quence of any processor for a computation involving the regular sectio n A(l:h:s) is characterized by a finite state machine of at most k sta tes. We present fast algorithms for computing the essential informatio n about these state machines, and we extend the framework to handle mu ltidimensional arrays. We also show how to generate communication sets using the state machine approach. Performance results show that this solution requires very little runtime overhead and acceptable preproce ssing time. (C) 1995 Academic Press, Inc.