Deterministic Parallel High-Quality Hypergraph Partitioning
Robert Krause, Lars Gottesbüren, Nikolai Maas · 2025
Read Deterministic Parallel High-Quality Hypergraph Partitioning by Robert Krause, Lars Gottesbüren, Nikolai Maas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-12013.txt.
Introduction
Robert Krause, Lars Gottesbüren, and Nikolai Maas build a hypergraph partitioner that gives the same answer every time. Splitting a hypergraph into balanced parts underpins chip design and scientific computing, and the best parallel tools rely on randomness, so runs differ and results cannot be reproduced. High-quality local search had no good deterministic parallel form.
The team generalizes a recent refinement method called Jet, retunes its rebalancing, and adds a deterministic scheme over flow-based refinement, even though the underlying flow solver is not deterministic. In tests, the Jet version matched or beat the leading non-deterministic solver's default quality while running only about fifteen percent slower, with speedups up to fifty-five-fold on 64 cores. The flow version edged past its random rival on quality for about a third more time. The authors call it the first deterministic parallel partitioner to rival the best solvers.
Catalog record
| CREATOR | Robert Krause, Lars Gottesbüren, Nikolai Maas |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-12013
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Deterministic Parallel High-Quality Hypergraph Partitioning Robert Krause, Lars Gottesbüren, Nikolai Maas Abstract We present a deterministic parallel multilevel algorithm for balanced hypergraph partitioning that matches the state of the art for non-deterministic algorithms. Deterministic parallel algorithms produce the same result in each invocation, which is crucial for reproducibility. Moreover, determinism is highly desirable in application areas such as VLSI design. While there has been tremendous progress in parallel hypergraph partitioning algorithms recently, deterministic counterparts for high-quality local search techniques are missing. Consequently, solution quality is severely lacking in comparison to the non-deterministic algorithms. In this work we close this gap. First, we present a generalization of the recently proposed Jet refinement algorithm. While Jet is naturally amenable to determinism, significant changes are necessary to achieve competitive performance on hypergraphs. We also propose an improved deterministic rebalancing algorithm for Jet. Moreover, we consider the powerful but slower flow-based refinement and introduce a scheme that enables deterministic results while building upon a non-deterministic maximum flow algorithm. As demonstrated in our thorough experimental evaluation, this results in the first deterministic parallel partitioner that is competitive to the highest quality solvers. With Jet refinement, we match or exceed the quality of Mt-KaHyPar’s non-deterministic default configuration while being only 15% slower on average. We observe self-relative speedups of up to 55 on 64 cores with a 22.5 × \times average speedup. Our deterministic flow-based refinement exceeds the quality of the non-deterministic variant by roughly 1% on average but requires 31% more running time. 1 Introduction Figure 1 : The quality gap between non-deterministic solvers (Mt-KaHyPar-{Default, Flows}) and deterministic solvers (BiPart, Mt-KaHyPar-SDet). Higher and to the left is better. Refer to Section 7.1 for details on the plot. Balanced hypergraph partitioning is a fundamental optimization problem with applications in key domains such as VLSI design [ 3 ] , scientific computing [ 54 , 18 ] , distributed database sharding [ 50 ] and more [ 15 ] . The task is to divide the vertices of a hypergraph into roughly equal-sized blocks such that the connectivity metric is minimized, which is defined as the sum of the number of different blocks connected by each hyperedge. As balanced partitioning is NP-hard to approximate within a constant factor [ 5 ] , the prevalent technique for obtaining good solutions in practice is the multilevel method [ 32 ] . The multilevel scheme first constructs a series of increasingly smaller hypergraphs by contracting vertices in the coarsening phase , and then finds a good initial partition on the smallest hypergraph. Subsequently, the contractions are undone in reverse order in the uncoarsening phase . The current partition is projected to the next larger hypergraph and local search algorithms are used to improve the partition. The improvement step is called refinement . A recent line of work [ 29 , 27 , 26 , 25 ] developed multi-core parallel algorithms that match the solution quality of the highest quality sequential methods [ 28 , 1 ] . Yet, these are still largely non-deterministic. Deterministic algorithms always produce the same output in each invocation when the same input is used. Researchers have long advocated the benefits of determinism in parallel algorithms [ 36 , 39 , 10 , 9 ] such as reasoning about performance, ease of debugging and reproducibility. In some applications reproducibility is necessary. For example in VLSI design, hardware engineers perform manual post-processing steps which expect a certain initial solution, and which are expensive to repeat [ 41 ] . Contrary to the sequential setting where using pseudo-random number generation with a fixed random seed suffices, it can be highly non-trivial to make parallel programs deterministic. In particular, changes to the internal workings of the algorithms may be required, which can lead to performance degradation compared to the non-deterministic counterparts [ 9 ] . Partitioning algorithms work with an existing partition and move vertices between blocks based on gains – the improvement in the objective function. Traditionally, parallel vertex moves are performed asynchronously for performance and solution quality reasons [ 29 ] , leading to race conditions in the computed gains, which in turn lead to non-deterministic partitioning results [ 23 ] . There are two existing works on deterministic parallel partitioning: BiPart [ 41 ] and Mt-KaHyPar’s deterministic mode [ 23 ] . However, they achieve worse solution quality than state-of-the-art methods, as shown in Figure 1 . This is due to the lack of high-quality refinement algorithms such as parallel localized FM [ 2 , 29 ] and flow-based refinement [ 47 , 26 , 28 , 24 ] . Instead, both deterministic partitioners use a synchronous label propagation refinement, which only considers moves with positive gain and is thus unable to escape local minima – contrary to FM refinement, which builds a sequence of dependent moves that can include negative gain moves. Flow-based refinement is even more powerful as it takes a more global view of the optimization problem by computing minimum cuts on cut boundary segments. Contributions In this paper, we close the quality gap by presenting two new deterministic versions of Mt-KaHyPar: DetJet and DetFlows. In place of FM refinement, we employ the recently proposed Jet refinement [ 21 ] , an algorithm designed for graph partitioning on GPUs with the goal of matching the solution quality of FM. This is achieved through unconstrained local search, i.e., allowing large temporary imbalances that are then repaired in a rebalancing step. As a GPU algorithm, it is naturally suited for a deterministic implementation. Here our technical contributions are an improved and deterministic rebalancing algorithm, as well as an efficient generalization of Jet from graphs to hypergraphs. Specifically, a naive generalization of Jet’s so-called afterburner component incurs O(\sum_{e\in E}|e|^{2}) work, which is infeasibly slow. We present an implementation with O(\sum_{e\in E}|e|\log|e|)) work. Secondly, we devise a deterministic version of Mt-KaHyPar’s flow-based refinement. Our contributions are a matching-based scheduling scheme of independent block pairs for two-way refinement and low-level adaptations of the two-way refinement scheme. The latter permit using a non-deterministic maximum flow algorithm, which is crucial for performance, while guaranteeing deterministic bipartition results. Finally, we implement two small improvements to Mt-KaHyPar’s deterministic coarsening that further improve solution quality and robustness. Mt-KaHyPar-DetJet uses the improved coarsening and deterministic Jet for refinement. Mt-KaHyPar-DetFlows additionally uses deterministic flow-based refinement. Results Mt-KaHyPar-DetJet matches or exceeds the solution quality of Mt-KaHyPar-Default at a 15% increase in running time. Mt-KaHyPar-DetFlows achieves a 1% improvement in solution quality over Mt-KaHyPar-Flows at a 31% increase in running time. Notably, Mt-KaHyPar-Flows achieves solution quality on the same level as the highest quality sequential solvers [ 49 , 47 ] while being substantially faster through parallelism, e.g., an order of magnitude on 10 cores [ 26 ] . By extension the same applies to our deterministic parallel variant. We perform strong scaling experiments for Mt-KaHyPar-DetJet, showing up to 55 \times self-relative speedup on 64 cores, with an average speedup of 22.5. In an individual comparison with BiPart, Mt-KaHyPar-DetJet outperforms BiPart by a factor of 2.4 in solution quality and 3.5 in running time, computing better partitions on 99.6\% of the instances. 2 Preliminaries Hypergraphs A weighted hypergraph H=(V,E,c,\omega) is a set of vertices V and a