KIT | KIT-Bibliothek | Impressum | Datenschutz

Deterministic Parallel Hypergraph Partitioning

Gottesbüren, Lars 1; Hamann, Michael 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)


Balanced hypergraph partitioning is a classical NP-hard optimization problem with applications in various domains such as VLSI design, simulating quantum circuits, optimizing data placement in distributed databases or minimizing communication volume in high-performance computing. Engineering parallel heuristics for this problem is a topic of recent research. Most of them are non-deterministic though. In this work, we design and implement a highly scalable deterministic algorithm in the state-of-the-art parallel partitioning framework Mt-KaHyPar. On our extensive set of benchmark instances, it achieves similar partition quality and performance as a comparable but non-deterministic configuration of Mt-KaHyPar and outperforms the only other existing parallel deterministic algorithm BiPart regarding partition quality, running time and parallel speedups.

Volltext §
DOI: 10.5445/IR/1000150458
Veröffentlicht am 07.09.2022
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsdatum 23.12.2021
Sprache Englisch
Identifikator KITopen-ID: 1000150458
Nachgewiesen in arXiv
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page