Proceedings - International Workshops on Parallel Processing 2023Dynamic graphs Chinese Academy of Sciences Institute of Computing Technolog U Chinese Academy of Sciences

A Bucket-aware Asynchronous Single-Source Shortest Path Algorithm on GPU

Proposed bucket-aware asynchronous SSSP algorithm on GPU uses property-driven reordering, adaptive load balancing, and bucket-aware execution to accelerate convergence and boost performance.

Yuan Zhang, Huawei Cao, Jie Zhang, Yiming Sun, Ming Dun, Junying Huang, Xuejun An, Xiaochun Ye

Published Aug 7, 202310 citationsPaper ↗

55%

OverallWorth a look

OverallWorth a lookVote to see the score

Readers

–

Only vote on papers you've read. Sign in to vote.

AI panel1/20reviewers recommend it

lenient 0/5

medium 1/10

strict 0/5

AI panel?Vote to see what the 20 AI reviewers said

Abstract

Single-Source Shortest Path (SSSP) algorithm is a common routine in graph processing and has been extensively studied on Graphics Processing Unit (GPU). Despite the powerful parallelism resources and high memory bandwidth provided by GPU, the performance of the SSSP algorithm is hindered by several bottlenecks, such as irregular memory access, load imbalance, and redundant operations. In this paper, three optimizations are proposed to boost the performance of the SSSP algorithm on GPU, including property-driven reordering, adaptive load balancing, and bucket-aware asynchronous execution. Property-driven reordering is employed to improve the data locality and work efficiency. Adaptive load balancing brings a higher utilization of software and hardware GPU resources. Bucket-aware asynchronous execution presents a bucket-based approach for asynchronous implementation to accelerate the convergence of SSSP search.