Parallel static and dynamic multi-constraint graph partitioning

Kirk Schloegel, George Karypis, and Vipin Kumar
Concurrency and Computation: Practice and Experience. Volume 14, Issue 3, pages 219 - 240, 2002
Download Paper
requirements of multi-phase simulations. These work well when (i) the graph that models the computation
fits into the memory of a single processor, and (ii) the simulation does not require dynamic load
balancing. The efficient execution of very large or dynamically adapting 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 multi-constraint graph-partitioning algorithm, as well
as a new partitioning algorithm for dynamic multi-phase simulations. We describe these algorithms and
give experimental results conducted on a 128-processor Cray T3E. These results show that our parallel
algorithms are able to efficiently compute partitionings of similar edge-cuts as serial multi-constraint
algorithms, and can scale to very large graphs. Our dynamic multi-constraint algorithm is also able to
minimize the data redistribution required to balance the load better than a naive scratch-remap approach.
We have shown that both of our parallel multi-constraint graph partitioners are as scalable as the widely used
parallel graph partitioner implemented in PARMETIS. Both of our parallel multi-constraint graph
partitioners are very fast, as they are able to compute three-constraint 128-way partitionings of a 7.5 million
vertex graph in under 7 s on 128 processors of a Cray T3E.
Research topics: Graph partitioning | Parallel processing | ParMETIS