Parallel multilevel k-way partitioning scheme for irregular graphs

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

94 Scopus citations

Abstract

In this paper we present a parallel formulation of a multilevel k-way graph partitioning algorithm. The multilevel k-way partitioning algorithm reduces the size of the graph by collapsing vertices and edges (coarsening phase), finds a k-way partition of the smaller graph, and then it constructs a k-way partition for the original graph by projecting and refining the partition to successively finer graphs (uncoarsening phase). A key innovative feature of our parallel formulation is that it utilizes graph coloring to effectively parallelize both the coarsening and the refinement during the uncoarsening phase. Our algorithm is able to achieve a high degree of concurrency, while maintaining the high quality partitions produced by the serial algorithm. We test our scheme on a large number of graphs from finite element methods, and transportation domains. Our parallel formulation on Cray T3D, produces high quality 128-way partitions on 128 processors in a little over two seconds, for graphs with a million vertices. Thus our parallel algorithm makes it possible to perform dynamic graph partition in adaptive computations without compromising quality.

Original languageEnglish (US)
Title of host publicationProceedings of the 1996 ACM/IEEE Conference on Supercomputing, SC 1996
PublisherAssociation for Computing Machinery
ISBN (Electronic)0897918541
DOIs
StatePublished - 1996
Externally publishedYes
Event1996 ACM/IEEE Conference on Supercomputing, SC 1996 - Pittsburgh, United States
Duration: Nov 17 1996Nov 22 1996

Publication series

NameProceedings of the International Conference on Supercomputing
Volume1996-November

Conference

Conference1996 ACM/IEEE Conference on Supercomputing, SC 1996
Country/TerritoryUnited States
CityPittsburgh
Period11/17/9611/22/96

Bibliographical note

Funding Information:
This work was supported by NSF CCR-9423082 and by Army Research Office contract DA/DAAH04-95-1-0538, and by Army High Performance Computing Research Center under the auspices of the Department of the Army, Army Research Laboratory cooperative agreement number DAAH04-95-2-0003/contract number DAAH04-95-C-0008, the content of which does not necessarily reflect the position or the policy of the government, and no official endorsement should be inferred. Access to computing facilities was provided by Minnesota Supercomputer Institute, Cray Research Inc, and by the Pittsburgh Supercomputing Center. Related papers are available via WWW at URL: http://www.cs.umn.edu/~karypis

Funding Information:
∗This work was supported by NSF CCR-9423082 and by Army Research Office contract DA/DAAH04-95-1-0538, and by Army High Performance Computing Research Center under the auspices of the Department of the Army, Army Research Laboratory cooperative agreement number DAAH04-95-2-0003/contract number DAAH04-95-C-0008, the content of which does not necessarily reflect the position or the policy of the government, and no official endorsement should be inferred. Access to computing facilities was provided by Minnesota Supercomputer Institute, Cray Research Inc, and by the Pittsburgh Supercomputing Center. Related papers are available via WWW at URL:

Publisher Copyright:
© 1996 IEEE.

Keywords

  • Kernighan-Lin Heuristic
  • Multilevel Partitioning Methods
  • Parallel Graph Partitioning
  • Parallel Sparse Matrix Algorithms
  • Spectral Partitioning Methods

Fingerprint

Dive into the research topics of 'Parallel multilevel k-way partitioning scheme for irregular graphs'. Together they form a unique fingerprint.

Cite this