A parallel algorithm for multilevel k-way hypergraph partitioning

In this paper we present a coarse-grained parallel multi-level algorithm for the k-way hypergraph partitioning problem. The algorithm significantly improves on our previous work in terms of run time and scalability behaviour by improving processor utilisation, reducing synchronisation overhead and avoiding disk contention. The new algorithm is also generally applicable and no longer requires a particular structure of the input hypergraph to achieve a good partition quality. We present results which show that the algorithm has good scalability properties on very large hypergraphs with Θ(10⁷) vertices and consistently outperforms the approximate partitions produced by a state-of-the-art parallel graph partitioning tool in terms of partition quality, by up to 27%.