Minimum-perimeter tiling in parallel computation
Jonathan Yackel · Minds at UW (University of Wisconsin) · 1993
This thesis is primarily concerned with two combinatorial optimization problems that have applications in parallel computing. In each problem the goal (from an applications point of view) is to partition the cells of a grid (of two or more dimensions) evenly among a number of processors so as to minimize interprocessor communication subject to load balancing constraints. In the perimeter minimization problem the communication is measured by interprocessor boundary, while in the diversity minimization problem communication is measured by summing the number of distinct processors in the slices of the grid. Besides the parallel computing applications, these problems are of intrinsic interest as combinatorial problems. For the two-dimensional versions of both these problems, a single theory based on geometric arguments provides good lower bounds on both objective functions and also characterizes the forms of optimal and nearly optimal solutions. The results include a method for generating provably optimal solutions for a large class of problems by tiling the grids with optimal shapes. This theory generalizes to arbitrary dimensions for the diversity minimization problem. A different theory provides lower bounds for many-dimensional versions of perimeter minimization. A tiling-based heuristic for diversity minimization provides the basis for the empirical results in the thesis. The heuristic, which incorporates a high-level genetic algorithm, is naturally parallel and has been implemented on a Thinking Machines CM-5. The code is efficient (spending less than 3% of the total computing time on interprocessor communication) and produced solutions of better quality than a previous heuristic developed by database researchers for diversity minimization. The code computed solutions within 4.2% of the best known lower bounds on all test problems, and solved a million-variable problem to optimality in 70 seconds.