1 Search Results for "Gehweiler, Joachim"

Document

On Dynamic Graph Partitioning and Graph Clustering using Diffusion

Authors: Henning Meyerhenke and Joachim Gehweiler

Published in: Dagstuhl Seminar Proceedings, Volume 10261, Algorithm Engineering (2010)

Abstract

Load balancing is an important requirement for the efficient execution of parallel numerical simulations. In particular when the simulation domain changes over time, the mapping of computational tasks to processors needs to be modified accordingly. State-of-the-art libraries for this problem are based on graph repartitioning. They have a number of drawbacks, including the optimized metric and the difficulty of parallelizing the popular repartitioning heuristic Kernighan-Lin (KL). Here we further explore the very promising diffusion-based graph partitioning algorithm DIBAP (Meyerhenke et al., JPDC 69(9):750–761, 2009) by adapting DIBAP to the related problem of load balancing. The presented experiments with graph sequences that imitate adaptive numerical simulations demonstrate the applicability and high quality of DIBAP for load balancing by repartitioning. Compared to the faster state-of-the-art repartitioners PARMETIS and parallel JOSTLE, DIBAP’s solutions have partitions with significantly fewer external edges and boundary nodes and the resulting average migration volume in the important maximum norm is also the best in most cases. We also prove that one of DIBAP's key components optimizes a relaxed version of the minimum edge cut problem. Moreover, we hint at a distributed algorithm based on ideas used in DIBAP for clustering a virtual P2P supercomputer.

Cite as

Henning Meyerhenke and Joachim Gehweiler. On Dynamic Graph Partitioning and Graph Clustering using Diffusion. In Algorithm Engineering. Dagstuhl Seminar Proceedings, Volume 10261, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{meyerhenke_et_al:DagSemProc.10261.4,
  author =	{Meyerhenke, Henning and Gehweiler, Joachim},
  title =	{{On Dynamic Graph Partitioning and Graph Clustering using Diffusion}},
  booktitle =	{Algorithm Engineering},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10261},
  editor =	{Giuseppe F. Italiano and David S. Johnson and Petra Mutzel and Peter Sanders},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10261.4},
  URN =		{urn:nbn:de:0030-drops-27980},
  doi =		{10.4230/DagSemProc.10261.4},
  annote =	{Keywords: Dynamic graph partitioning/clustering, disturbed diffusion, load balancing, relaxed cut optimization}
}

Refine by Author
1 Gehweiler, Joachim
1 Meyerhenke, Henning

Refine by Classification

Refine by Keyword
1 Dynamic graph partitioning/clustering
1 disturbed diffusion
1 load balancing
1 relaxed cut optimization

Refine by Type
1 document

Refine by Publication Year
1 2010

1 Search Results for "Gehweiler, Joachim"

On Dynamic Graph Partitioning and Graph Clustering using Diffusion

Abstract

Cite as

Thanks for your feedback!

Could not send message