Sequential multi-constraint graph partitioners have been developed to address the load balancing requirements of multi-phase simulations. The efficient execution of large 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 recently developed multi-constraint graph partitioning algorithm. We describe this algorithm and give experimental results conducted on a 128-processor Cray T3E. We show that our parallel algorithm is able to efficiently compute partitionings of similar edge-cuts as serial multi-constraint algorithms, and can scale to very large graphs. Our parallel multi-constraint graph partitioner is able to compute a threeconstraint 128-way partitioning of a 7.5million node graph in about 7 seconds on 128 processors of a Cray T3E.
|Original language||English (US)|
|Title of host publication||Euro-Par 2000 Parallel Processing - 6th International Euro-Par Conference, Proceedings|
|Editors||Arndt Bode, Thomas Ludwig, Wolfgang Karl, Roland Wismüller|
|Number of pages||15|
|State||Published - 2000|
|Event||6th International European Conference on Parallel Computing, Euro-Par 2000 - Munich, Germany|
Duration: Aug 29 2000 → Sep 1 2000
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||6th International European Conference on Parallel Computing, Euro-Par 2000|
|Period||8/29/00 → 9/1/00|
Bibliographical notePublisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.