  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.
