Parallel static and dynamic multi-constraint graph partitioning

Kirk Schloegel, George Karypis, Vipin Kumar

Research output: Contribution to journalArticlepeer-review

116 Scopus citations

Abstract

Sequential multi-constraint graph partitioners have been developed to address the static load balancing 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.

Original languageEnglish (US)
Pages (from-to)219-240
Number of pages22
JournalConcurrency Computation
Volume14
Issue number3
DOIs
StatePublished - Mar 2002

Keywords

  • Multi-constraint graph partitioning
  • Multi-phase scientific simulation
  • Multilevel graph partitioning
  • Parallel graph partitioning

Fingerprint

Dive into the research topics of 'Parallel static and dynamic multi-constraint graph partitioning'. Together they form a unique fingerprint.

Cite this