论文标题
基于平行流量的超图形分区
Parallel Flow-Based Hypergraph Partitioning
论文作者
论文摘要
我们提出了基于流的改进的共享记忆并行化，这被认为是目前用于超图形分配的最强大的迭代改进技术。基于流的精炼作品可在两部分中起作用，因此当前的顺序分区者将其安排在不同的块对上，以改善$ k $ - 道路分区。我们研究了两个不同的并行源：基于众所周知的推送标记算法的平行调度方案和平行最大流量算法。除了彻底设计的实施外，我们还提出了几种优化，这些优化在实践中实质上加速了算法，从而可以对极大的超图（高达10亿针）进行使用。我们将方法整合到最新的平行多级框架MT-KAHYPAR中，并在500多个现实世界中的基准集上进行了广泛的实验，以表明我们代码的分区质量与最高质量的顺序代码（KAHYPAR）相当，同时是10个线程的级级级级级。
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.
