Parallel Multilevel Algorithms for Multi-Constraint Graph Partitioning

Kirk Schloegel, George Karypis, and Vipin Kumar
Euro-Par, pp: 296-310, 2000
Download Paper
Recently, sequential multi-constraint graph partitioning algorithms have been developed to address the load balancing requirements of emerging multi-phase and multi-physics scientific simulation problems. Effective execution of such 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 quality to 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.
Research topics: Graph partitioning | Parallel processing | ParMETIS