We have developed two elegant techniques for partitioning arrays in parallel DoAll loops for message-passing parallel machines.
(i) Communication-free array partitioning: A general solution of communication-free partitioning is derived for arrays in a DoAll loop. The derivation is based on the Smith Normal Form decomposition of the matrix that characterizes the array references in a DoAll loop.
(ii) One block-communication partitioning: When communication-free partitioning is not possible, we derive the partitioning equations which allocate all remote data to a unique processor. Thus, at most one block-communication is required for each processor to obtain the remote data it needs during computation.
II. Distributed Array Compilation for Data-Parallel Programs:
We have developed an methodology which provides closed-form solution for (1) Local array enumeration, (2) Local iteration set enumeration, and communication sets, and (3) Compact storage scheme for local arrays. The derivation is based on the Smith Normal Form decomposition of the matrix which characterizes the data distribution information and the array references.