Optimal and Asymptotically Optimal Equi-partition of Rectangular Domains via Stripe Decomposition

Abstract

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 problem size grows large in all parameters, he 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.