Parallel Multilevel Algorithms for Multi-Constraint Graph Partitioning

Abstract

Recently, serial multi-constraint graph partitioning algorithms have been developed that are able to compute high-quality partitionings for emerging multi-phase, multi-mesh, and multi-physics problems. While these results are promising, the fact that these algorithms are serial limits the problem size that can be solved due to both solution time and memory requirements. A parallel multi-constraint graph partitioner will allow the partitioning of larger multi-constraint graphs, and therefore, is key to the efficient execution of large multi-phase, multi-mesh, and multi-physics problems. In this paper, we present a parallel multi-constraint graph partitioning algorithm based on the multilevel graph partitioning paradigm. We describe this algorithm and give experimental results conducted on a 128-processor Cray T3E. We show that our parallel algorithm is able to robustly compute balanced partitionings of similar quality to serial multi-constraint algorithms, while being scalable to very large graphs. We show that the run time of our algorithm is very fast. 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.