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 language | English (US) |
|---|---|
| Title of host publication | Proceedings of the 1996 ACM/IEEE Conference on Supercomputing, SC 1996 |
| Publisher | Association for Computing Machinery |
| ISBN (Electronic) | 0897918541 |
| DOIs | |
| State | Published - 1996 |
| Event | 1996 ACM/IEEE Conference on Supercomputing, SC 1996 - Pittsburgh, United States Duration: Nov 17 1996 → Nov 22 1996 |
Publication series
| Name | Proceedings of the International Conference on Supercomputing |
|---|---|
| Volume | 1996-November |
Conference
| Conference | 1996 ACM/IEEE Conference on Supercomputing, SC 1996 |
|---|---|
| Country/Territory | United States |
| City | Pittsburgh |
| Period | 11/17/96 → 11/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