论文标题
两人：平行和确定性的多级超图形分区者
BiPart: A Parallel and Deterministic Multilevel Hypergraph Partitioner
论文作者
论文摘要
HyperGraph分区用于许多问题领域，包括VLSI设计，线性代数，布尔值满意度和数据挖掘。该问题的大多数版本都是NP兼容或NP-HARD，因此，实际的超图形分区者为除最小输入以外的所有人生成了近似分区解决方案。加快超图形分区者的一种方法是利用并行性。但是，现有的平行超图形分区不是确定性的，这在诸如VLSI设计之类的域中被认为是不可接受的，在vlsi设计中，每当给定的超图被分区时，都必须生成相同的分区。 在本文中，我们描述了双党，这是第一个确定性的，平行的超图形分区者。实验结果表明，双党在运行时和分区质量上优于最先进的超图形分区者，同时确定生成分区。
Hypergraph partitioning is used in many problem domains including VLSI design, linear algebra, Boolean satisfiability, and data mining. Most versions of this problem are NP-complete or NP-hard, so practical hypergraph partitioners generate approximate partitioning solutions for all but the smallest inputs. One way to speed up hypergraph partitioners is to exploit parallelism. However, existing parallel hypergraph partitioners are not deterministic, which is considered unacceptable in domains like VLSI design where the same partitions must be produced every time a given hypergraph is partitioned. In this paper, we describe BiPart, the first deterministic, parallel hypergraph partitioner. Experimental results show that BiPart outperforms state-of-the-art hypergraph partitioners in runtime and partition quality while generating partitions deterministically.
