License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2022.5
URN: urn:nbn:de:0030-drops-165393
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16539/
Go to the corresponding LIPIcs Volume Portal

Gottesbüren, Lars ; Heuer, Tobias ; Sanders, Peter

Parallel Flow-Based Hypergraph Partitioning

pdf-format:
LIPIcs-SEA-2022-5.pdf (4 MB)

Abstract

We present a shared-memory parallelization of flow-based refinement, which is considered the most powerful iterative improvement technique for hypergraph partitioning at the moment. Flow-based refinement works on bipartitions, so current sequential partitioners schedule it on different block pairs to improve k-way partitions. We investigate two different sources of parallelism: a parallel scheduling scheme and a parallel maximum flow algorithm based on the well-known push-relabel algorithm. In addition to thoroughly engineered implementations, we propose several optimizations that substantially accelerate the algorithm in practice, enabling the use on extremely large hypergraphs (up to 1 billion pins). We integrate our approach in the state-of-the-art parallel multilevel framework Mt-KaHyPar and conduct extensive experiments on a benchmark set of more than 500 real-world hypergraphs, to show that the partition quality of our code is on par with the highest quality sequential code (KaHyPar), while being an order of magnitude faster with 10 threads.

BibTeX - Entry

@InProceedings{gottesburen_et_al:LIPIcs.SEA.2022.5,
  author =	{Gottesb\"{u}ren, Lars and Heuer, Tobias and Sanders, Peter},
  title =	{{Parallel Flow-Based Hypergraph Partitioning}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16539},
  URN =		{urn:nbn:de:0030-drops-165393},
  doi =		{10.4230/LIPIcs.SEA.2022.5},
  annote =	{Keywords: multilevel hypergraph partitioning, shared-memory algorithms, maximum flow}
}

Keywords: multilevel hypergraph partitioning, shared-memory algorithms, maximum flow
Collection: 20th International Symposium on Experimental Algorithms (SEA 2022)
Issue Date: 2022
Date of publication: 11.07.2022
Supplementary Material: Software (Multilevel Framework): https://github.com/kahypar/mt-kahypar
Software (Flow-Based Refinement): https://github.com/larsgottesbueren/WHFC/tree/parallel
Dataset (Benchmark Set & Experimental Results): https://algo2.iti.kit.edu/heuer/sea22/

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI