  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.
