Parallel Multilevel Algorithms for Multi-constraint Graph Partitioning
Kirk Schloegel5 
, George Karypis5 and Vipin Kumar5
| (5) |
Army HPC Research Center Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, 55455 |
Abstract
Sequential multi-constraint graph partitioners have been developed to address the load balancing requirements of multi-phase
simulations. The efficient execution of large multi-phase simulations on high performance parallel computers requires that
the multi-constraint partitionings are computed in parallel. This paper presents a parallel formulation of a recently developed
multi-constraint graph partitioning algorithm. We describe this algorithm and give experimental results conducted on a 128-processor
Cray T3E. We show that our parallel algorithm is able to efficiently compute partitionings of similar edge-cuts as serial
multi-constraint algorithms, and can scale to very large graphs. Our parallel multi-constraint graph partitioner is able to
compute a three-constraint 128-way partitioning of a 7.5 million node graph in about 7 seconds on 128 processors of a Cray
T3E.
This work was supported by DOE contract number LLNL B347881, by NSF grant CCR-9972519, by Army Research Office contracts DA/DAAG55-98-1-0441,
by Army High Performance Computing Research Center 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. Additional support was provided by the IBM Partnership Award, and by the IBM SUR equipment grant. Access
to computing facilities was provided by AHPCRC, Minnesota Supercomputer Institute. Related papers are available via WWW at
URL: http://www-users.cs.umn.edu/karypis
References secured to subscribers.