### Compile Time Array Partitioning Techniques

#### Eric Hung-Yu Tseng

**
I. Automatic Array Partitioning:**
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.