Premium
Parallel static and dynamic multi‐constraint graph partitioning
Author(s) -
Schloegel Kirk,
Karypis George,
Kumar Vipin
Publication year - 2002
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.605
Subject(s) - computer science , parallel computing , scalability , computation , graph , constraint graph , constraint (computer aided design) , load balancing (electrical power) , constraint satisfaction problem , graph partition , vertex (graph theory) , theoretical computer science , algorithm , local consistency , mathematics , geometry , database , artificial intelligence , probabilistic logic , grid
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 P AR M E T I S. 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. Copyright © 2002 John Wiley & Sons, Ltd.