基于GPU加速的全源对最短路径并行算法

作者：肖汉; 肖诗洋; 李焕勤^*; 周清雷

来源：云南大学学报(自然科学版), 2023, 45(05): 1022-1032.

• 最短路径
• 重复平方法
• 图形处理器
• 开放式计算语言
• 并行算法

针对最短路径算法处理大规模数据集低效的问题，提出了基于图形处理器（Graphics Processing Unit,GPU）加速的全源对最短路径并行算法.首先通过优化矩阵乘法算法实现了在工作组内和组间进行并行运算数据，然后减少了非规则行造成的工作项分支，最后降低了工作项对邻接矩阵计算条带存储资源的访问延时.实验结果表明，与基于AMD Ryzen5 1600X CPU的串行算法、基于开放多处理（Open Multi-Processing, OpenMP）并行算法和基于统一计算设备架构（Compute Unified Device Architecture, CUDA）并行算法相比，最短路径并行算法在开放式计算语言（Open Computing Language, OpenCL）架构下NVIDIA GeForce GTX 1 070计算平台上分别获得了196.35、36.76和2.25倍的加速比，验证了提出的并行优化方法的有效性和性能可移植性.

• 单位
  土木工程学院; 郑州师范学院; 东南大学