Parallel multilevel algorithms for multi-constraint graph partitioning

Kirk Schloegel, George Karypis, Vipin Kumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

61 Scopus citations

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 languageEnglish (US)
Title of host publicationEuro-Par 2000 Parallel Processing - 6th International Euro-Par Conference, Proceedings
EditorsArndt Bode, Thomas Ludwig, Wolfgang Karl, Roland Wismüller
PublisherSpringer Verlag
Pages296-310
Number of pages15
ISBN (Electronic)9783540679561
DOIs
StatePublished - 2000
Event6th International European Conference on Parallel Computing, Euro-Par 2000 - Munich, Germany
Duration: Aug 29 2000Sep 1 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1900
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th International European Conference on Parallel Computing, Euro-Par 2000
CountryGermany
CityMunich
Period8/29/009/1/00

Fingerprint Dive into the research topics of 'Parallel multilevel algorithms for multi-constraint graph partitioning'. Together they form a unique fingerprint.

Cite this