BiPart
| Autor: | Udit Agarwal, Keshav Pingali, Sepideh Maleki, Martin Burtscher |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Very-large-scale integration
020203 distributed computing Hypergraph Mathematics::Combinatorics Speedup Theoretical computer science Computer science Computer Science::Neural and Evolutionary Computation 020207 software engineering 02 engineering and technology Partition (database) Computer Science::Discrete Mathematics Linear algebra 0202 electrical engineering electronic engineering information engineering Parallelism (grammar) Boolean satisfiability problem MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | PPoPP |
| DOI: | 10.1145/3437801.3441611 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|