Automatic Array Partitioning Based on the Smith Normal Form |
| |
Authors: | Eric Hung-Yu?Tseng Email author" target="_blank">Jean-Luc?GaudiotEmail author |
| |
Affiliation: | (1) Service Assurance, Spirent Communications, Morgan Hill, CA 95037, USA;(2) Department of EECS, University of California, Irvine, CA 92697, USA |
| |
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. |
| |
Keywords: | Data partitioning communication optimization parallel loop Smith-normal-form |
本文献已被 SpringerLink 等数据库收录! |
|