Traditional graph partitioning algorithms compute a k-way partitioning of a graph such that the number of edges that are cut by the partitioning is minimized and each partition has an equal number of vertices. The task of minimizing the edge-cut can be considered as the objective and the requirement that the partitions will be of the same size can be considered as the constraint. In this paper we extend the partitioning problem by incorporating an arbitrary number of balancing constraints. In our formulation, a vector of weights is assigned to each vertex, and the goal is to produce a k-way partitioning such that the partitioning satisfies a balancing constraint associated with each weight, while attempting to minimize the edge-cut. Applications of this multi-constraint graph partitioning problem include parallel solution of multi-physics and multi-phase computations, that underlay many existing and emerging large-scale scientific simulations. We present new multi-constraint graph partitioning algorithms that are based on the multilevel graph partitioning paradigm. Our work focuses on developing new types of heuristics for coarsening, initial partitioning, and refinement that are capable of successfully handling multiple constraints. We experimentally evaluate the effectiveness of our multi-constraint partitioners on a variety of synthetically generated problems.
|Original language||English (US)|
|Title of host publication||SC 1998 - Proceedings of the ACM/IEEE Conference on Supercomputing|
|Publisher||Association for Computing Machinery|
|State||Published - 1998|
|Event||1998 ACM/IEEE Conference on Supercomputing, SC 1998 - Orlando, United States|
Duration: Nov 7 1998 → Nov 13 1998
|Name||Proceedings of the International Conference on Supercomputing|
|Conference||1998 ACM/IEEE Conference on Supercomputing, SC 1998|
|Period||11/7/98 → 11/13/98|
Bibliographical noteFunding Information:
The formulation of the multi-objective multi-constraint graph partitioning problem was motivated by discussion with Raju Namburu, Carol Hoover, and David Keys. We also like to thank Bruce Hendrickson for his valuable comments on an early draft of this paper. This work was supported by NSF CCR-9423082 and by Army Research Office contract DA/DAAH04-95-1-0538, and by Army High Performance Computing Research Center under the auspices of the Department of the Army, Army Research Laboratory cooperative agreement number DAAH04-95-2-0003/contract number DAAH04-95-C-0008, the content of which does not necessarily reflect the position or the policy of the government, and no official endorsement should be inferred. Access to computing facilities was provided by AHPCRC, Minnesota Supercomputer Institute, Cray Research Inc, and by the Pittsburgh Supercomputing Center. Related papers are available via WWW at URL: http://www.cs.umn.edu/~karypis
© 1998 IEEE.
- Graph partitioning
- Numerical simulations
- Parallel processing