We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Automatic Array Partitioning Based on the Smith Normal Form.
- Authors
Tseng, Eric Hung-Yu; Gaudiot, Jean-Luc
- Abstract
We investigate the lattice-based array partitioning based on the theory of the Smith Normal Form and we present two elegant techniques for partitioning arrays in parallel DoAll loops for message-passing parallel machines: (1) DoAll loops with constant dependencies for communication-free partitioning: a general solution of all possible communication-free partitioning is derived where the dependencies among array references are described in constant distance vectors. (2) DoAll loops with non-constant dependencies for block-communication partitioning: the dependencies among array references are described in non-constant distance vectors. We derive the partitioning equations which allocate all remote data to a unique processor such that only one block-communication can obtain all the remote data for the computation. By using the Smith Normal Form decomposition, we are also able to verify our partitioning results.
- Subjects
LATTICE theory; NORMAL forms (Mathematics); VECTOR analysis; ARRAY processors; DECOMPOSITION method; OPERATIONS research
- Publication
International Journal of Parallel Programming, 2005, Vol 33, Issue 1, p35
- ISSN
0885-7458
- Publication type
Article
- DOI
10.1007/s10766-004-1460-2