RECTILINEAR PARTITIONING OF IRREGULAR DATA-PARALLEL COMPUTATIONS

This paper describes new mapping algorithms for domain-oriented data-p arallel computations, where the workload is distributed irregularly th roughout the domain, but exhibits localized or rectilinear communicati on patterns. We consider the problem of partitioning the domain for pa rallel processing in such a way that the workload on the most heavily loaded processor is minimized, subject to the constraint that the part ition be perfectly rectilinear. Rectilinear partitions are useful on a rchitectures that have a fast local mesh network and a relatively slow er global network; these partitions heuristically attempt to maximize the fraction of communication carried by the local network. We provide an improved algorithm for finding the optimal partition in one dimens ion, propose new algorithms for partitioning in two dimensions, and sh ow that optimal partitioning in three dimensions is NP-complete. We di scuss our application of these algorithms to real problems. (C) 1994 A cademic Press, Inc.