KIT | KIT-Bibliothek | Impressum | Datenschutz

Parallel Flow-Based Hypergraph Partitioning

Gottesbüren, Lars 1; Heuer, Tobias ORCID iD icon 1; Sanders, Peter ORCID iD icon 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)


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.

Verlagsausgabe §
DOI: 10.5445/IR/1000152817
Veröffentlicht am 18.11.2022
DOI: 10.4230/LIPIcs.SEA.2022.5
Zitationen: 5
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsdatum 11.07.2022
Sprache Englisch
Identifikator ISBN: 978-3-95977-251-8
KITopen-ID: 1000152817
HGF-Programm 46.21.02 (POF IV, LK 01) Cross-Domain ATMLs and Research Groups
Erschienen in 20th International Symposium on Experimental Algorithms (SEA 2022)
Veranstaltung 20th International Symposium on Experimental Algorithms (SEA 2022), Heidelberg, Deutschland, 25.07.2022 – 27.07.2022
Auflage 233
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten 5:1-5:21
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page