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.
Kumar, Vipin; Karypis, George; Schloegel, Kirk.
Parallel Multilevel Algorithms for Multi-Constraint Graph Partitioning.
Retrieved from the University of Minnesota Digital Conservancy,
Content distributed via the University of Minnesota's Digital Conservancy may be subject to additional license and use restrictions applied by the depositor.