Generating Local Addresses and Communication Sets for Data-Parallel Programs
✍ Scribed by S. Chatterjee; J.R. Gilbert; F.J.E. Long; R. Schreiber; S.H. Teng
- Publisher
- Elsevier Science
- Year
- 1995
- Tongue
- English
- Weight
- 988 KB
- Volume
- 26
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
Generating local addresses and communication sets is an important issue in distributed-memory implementations of data-parallel languages such as High Performance Fortran. We demonstrate a storage scheme for an array (A) affinely aligned to a template that is distributed across (p) processors with a cyclic ((k)) distribution that does not waste any storage, and show that, under this storage scheme, the local memory access sequence of any processor for a computation involving the regular section (A(\ell: h: s)) is characterized by a finite state machine of at most (k) states. We present fast algorithms for computing the essential information about these state machines, and we extend the framework to handle multidimensional 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 preprocessing time. O 1995 Academic Press, Inc.