Parallel static and dynamic multi‐constraint graph partitioning

Abstract

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 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.