On Dynamic Graph Partitioning and Graph Clustering using Diffusion

J. Gehweiler, H. Meyerhenke, in: Dagstuhl Seminar Proceedings 10261: Algorithm Engineering, 2010.

Download
No fulltext has been uploaded.
Conference Paper | English
Author
;
Abstract
Load balancing is an important requirement for the efficient execu-tion of parallel numerical simulations. In particular when the simulation domainchanges over time, the mapping of computational tasks to processors needs tobe modified accordingly. State-of-the-art libraries for this problem are basedon graph repartitioning. They have a number of drawbacks, including the opti-mized metric and the difficulty of parallelizing the popular repartitioning heuris-tic Kernighan-Lin (KL).Here we further explore the very promising diffusion-based graph partitioningalgorithm DIBAP (Meyerhenke et al., JPDC 69(9):750–761, 2009) by adaptingDIBAP to the related problem of load balancing. Experiments with graph se-quences that imitate adaptive numerical simulations demonstrate the applicabilityand high quality of DIBAP for load balancing by repartitioning. Compared to thefaster state-of-the-art repartitioners PARMETIS and parallel JOSTLE, DIBAP’ssolutions have partitions with significantly fewer external edges and boundarynodes and the resulting average migration volume in the important maximumnorm is also the best in most cases.We also prove that one of DIBAP’s key components optimizes a relaxed versionof the minimum edge cut problem. Moreover, we hint at a distributed algorithmbased on ideas used in DIBAP for clustering a virtual P2P supercomputer.
Publishing Year
Proceedings Title
Dagstuhl Seminar Proceedings 10261: Algorithm Engineering
LibreCat-ID

Cite this

Gehweiler J, Meyerhenke H. On Dynamic Graph Partitioning and Graph Clustering using Diffusion. In: Dagstuhl Seminar Proceedings 10261: Algorithm Engineering. ; 2010.
Gehweiler, J., & Meyerhenke, H. (2010). On Dynamic Graph Partitioning and Graph Clustering using Diffusion. In Dagstuhl Seminar Proceedings 10261: Algorithm Engineering.
@inproceedings{Gehweiler_Meyerhenke_2010, title={On Dynamic Graph Partitioning and Graph Clustering using Diffusion}, booktitle={Dagstuhl Seminar Proceedings 10261: Algorithm Engineering}, author={Gehweiler, Joachim and Meyerhenke, Henning}, year={2010} }
Gehweiler, Joachim, and Henning Meyerhenke. “On Dynamic Graph Partitioning and Graph Clustering Using Diffusion.” In Dagstuhl Seminar Proceedings 10261: Algorithm Engineering, 2010.
J. Gehweiler and H. Meyerhenke, “On Dynamic Graph Partitioning and Graph Clustering using Diffusion,” in Dagstuhl Seminar Proceedings 10261: Algorithm Engineering, 2010.
Gehweiler, Joachim, and Henning Meyerhenke. “On Dynamic Graph Partitioning and Graph Clustering Using Diffusion.” Dagstuhl Seminar Proceedings 10261: Algorithm Engineering, 2010.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar