%A Ioannis T. Christou
%A Robert R. Meyer
%T Optimal and Asymptotically Optimal Equi-partition of Rectangular Domains via Stripe Decomposition
%D November 1995
%R 95-19
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X We present an efficient method for assigning any number of processors
to tasks associated with the cells of a rectangular uniform grid. Load
balancing equi-partition constraints are observed while approximately
minimizing the total perimeter of the
partition, which corresponds to the amount of interprocessor communication.
This method is based upon decomposition of the grid into stripes of ``optimal''
height. We
prove that under some mild assumptions, as the problem size grows large in all
parameters, the error bound associated with this feasible solution
approaches zero. We also present computational results from
a high level parallel Genetic Algorithm that utilizes this method, and make
comparisons with other methods. On a network of workstations, our
algorithm solves within minutes instances of the
problem that would require one billion binary variables in a Quadratic
Assignment formulation.