BiPart: A Parallel and Deterministic Hypergraph Partitioner
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.
Mon 1 MarDisplayed time zone: Eastern Time (US & Canada) change
12:30 - 13:30
Session 3. GraphsMain Conference
Chair(s): Ang Li Pacific Northwest National Laboratory
|Understanding and Bridging the Gaps in Current GNN Performance Optimizations|
Kezhao Huang Tsinghua University, Jidong Zhai Tsinghua University, Zhen Zheng Alibaba Group, Youngmin Yi University of Seoul, Xipeng Shen North Carolina State UniversityLink to publication
|A Fast Work-Efficient SSSP Algorithm for GPUs|
Kai Wang University of Texas at Austin, Donald Fussell University of Texas at Austin, Calvin Lin University of Texas at AustinLink to publication
|ShadowVM: Accelerating Data Plane for Data Analytics with Bare Metal CPUs and GPUs|
Zhifang Li East China Normal University, Mingcong Han East China Normal University, Shangwei Wu East China Normal University, Chuliang Weng East China Normal UniversityLink to publication
|BiPart: A Parallel and Deterministic Hypergraph Partitioner|
Sepideh Maleki The University of Texas at Austin, Udit Agarwal UT Austin, Martin Burtscher Texas State University, Keshav Pingali The University of Texas at AustinLink to publication