A Fast Work-Efficient SSSP Algorithm for GPUs
A Fast Work-Efficient SSSP Algorithm for GPUs
复制标题
一种适用于 GPU 的快速、高效的 SSSP 算法
DOI：
10.1145/3437801.3441605
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Lin, Calvin
中科院分区：
文献类型：
--
作者：
Wang, Kai;Fussell, Don;Lin, Calvin
提出了一种新的GPU单源最短路径算法。我们的主要进步是一个改进的工作调度，这是中央的SSSP算法的性能。以前的SSSP GPU解决方案使用简单的工作调度器，可以在GPU上有效地实现，但产生低质量的调度。这样的解决方案产生较差的工作效率，并且由于缺乏并行性而可能未充分利用硬件。我们的解决方案引入了一个更复杂的工作调度器-基于一个新的高度并行的近似优先级队列-产生高质量的调度，同时在GPU上有效地实现。为了评估我们的解决方案，我们使用了Lonestar 4.0基准套件和SuiteSparse Matrix Collection中的226个图形输入，我们发现我们的解决方案比以前的最先进的解决方案平均高出2.9倍，在不牺牲调度质量的前提下，本文重点研究了SSSP算法，问题，它有更广泛的影响，使用GPU，说明似乎不适合的数据结构，如优先级队列，可以有效地实现GPU，如果我们使用适当的软件结构。
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 yield poor work efficiency and can underutilize the hardware due to a lack of parallelism. Our solution introduces a more sophisticated work scheduler---based on a novel highly parallel approximate priority queue---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×, showing that an efficient work scheduling mechanism can be implemented on GPUs without sacrificing schedule quality.While this paper focuses on the SSSP problem, it has broader implications for the use of GPUs, illustrating that seemingly ill-suited data structures, such as priority queues,canbe efficiently implemented for GPUs if we use the proper software structure.