Write a Blog >>
PPoPP 2021
Sat 27 February - Wed 3 March 2021
Mon 1 Mar 2021 12:45 - 13:00 - Session 3. Graphs Chair(s): Ang Li

This paper presents a new Single Source Shortest Path (SSSP) algorithm for GPUs. Our key advancement is an improved work scheduler, which is central to the performance of SSSP algorithms. Previous GPU solutions for SSSP use simple work schedulers that can be implemented efficiently on GPUs but that produce low quality schedules. Such solutions underutilize the hardware and yield poor work efficiency. Our solution introduces a more sophisticated work scheduler that produces high quality schedules while being efficiently implementable on GPUs.
To evaluate our solution, we use 226 graph inputs from the Lonestar 4.0 benchmark suite and the SuiteSparse Matrix Collection, and we find that our solution outperforms the previous state-of-the-art solution by an average of 2.9$\times$, showing that an efficient work scheduling mechanism can be implemented on GPUs without sacrificing schedule quality.

Mon 1 Mar

Displayed time zone: Eastern Time (US & Canada) change

12:30 - 13:30
Session 3. GraphsMain Conference
Chair(s): Ang Li Pacific Northwest National Laboratory
12:30
15m
Talk
Understanding and Bridging the Gaps in Current GNN Performance Optimizations
Main Conference
Kezhao Huang Tsinghua University, Jidong Zhai Tsinghua University, Zhen Zheng Alibaba Group, Youngmin Yi University of Seoul, Xipeng Shen North Carolina State University
Link to publication
12:45
15m
Talk
A Fast Work-Efficient SSSP Algorithm for GPUs
Main Conference
Kai Wang University of Texas at Austin, Donald Fussell University of Texas at Austin, Calvin Lin University of Texas at Austin
Link to publication
13:00
15m
Talk
ShadowVM: Accelerating Data Plane for Data Analytics with Bare Metal CPUs and GPUs
Main Conference
Zhifang Li East China Normal University, Mingcong Han East China Normal University, Shangwei Wu East China Normal University, Chuliang Weng East China Normal University
Link to publication
13:15
15m
Talk
BiPart: A Parallel and Deterministic Hypergraph Partitioner
Main Conference
Sepideh Maleki The University of Texas at Austin, Udit Agarwal UT Austin, Martin Burtscher Texas State University, Keshav Pingali The University of Texas at Austin
Link to publication