X. Chen
G.M. Megson
University of Newcastle upon Tyne. 1993
Partitioning and mapping algorithms onto a lower dimensional processor array with fixed-shape and fixed-interconnections is a significant challenge which has not yet been dealt with so far. A methodology of partitioning and mapping an arbitrary n-D computation graph onto a given-shape and fixed-mesh (n-k)-D array is proposed (k >1). It begins by transforming the original computational problem to a computational polytope with a canonical dependencies. Two models of unimodular space-time mapping matrix are proposed. The resulting n-D polytope is, then, projected into a k-D time polytope and an (n-k) space polytope. The latter can be allocated within a given (n-k)-D array by scaling supernode partitioning parallelepipeds properly. The former is re-projected along a 1-D time domain by a valid minimum projection vector p which is derived to achieve high efficiency.