Abstract
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 |
Publisher | Springer Verlag |
Pages | 296-310 |
Number of pages | 15 |
ISBN (Electronic) | 9783540679561 |
DOIs | |
State | Published - 2000 |
Event | 6th International European Conference on Parallel Computing, Euro-Par 2000 - Munich, Germany Duration: Aug 29 2000 → Sep 1 2000 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 1900 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Other
Other | 6th International European Conference on Parallel Computing, Euro-Par 2000 |
---|---|
Country/Territory | Germany |
City | Munich |
Period | 8/29/00 → 9/1/00 |
Bibliographical note
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 2000.