A parallel priority queue with fast updates for GPU architectures

The single-source shortest path (SSSP) problem is a well-studied problem that is used in many applications. In the parallel setting, a work-efficient algorithm that additionally attains $o(n)$ parallel depth has been elusive. Alternatively, various approaches have been developed that take advantage of specific properties of a particular class of graphs. On a graphics processing unit (GPU), the current state-of-the-art SSSP algorithms are implementations of the Delta-stepping algorithm, which does not perform well for graphs with large diameters. The main contribution of this work is to provide an algorithm designed for GPUs that runs efficiently for such graphs. We present the parallel bucket heap, a parallel cache-efficient data structure adapted for modern GPU architectures that supports standard priority queue operations, as well as bulk update. We analyze the structure in several well-known computational models and show that it provides both optimal parallelism and is cache-efficient. We implement the parallel bucket heap and use it in a parallel variant of Dijkstra's algorithm to solve the SSSP problem. Experimental results indicate that, for sufficiently large, dense graphs with high diameter, we outperform the current state-of-the-art SSSP implementations on an NVIDIA RTX 2080 Ti and Quadro M4000 by up to a factor of 2.8 and 5.4, respectively.