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.