| 基于GPU加速的全源对最短路径并行算法 |
| |
| 引用本文： | 肖汉,肖诗洋,李焕勤,周清雷.基于GPU加速的全源对最短路径并行算法[J].云南大学学报(自然科学版),2023(5):1022-1032. |
| |
| 作者姓名： | 肖汉 肖诗洋 李焕勤 周清雷 |
| |
| 作者单位： | 1. 郑州师范学院信息科学与技术学院;2. 郑州大学计算机与人工智能学院;3. 东南大学土木工程学院 |
| |
| 基金项目： | 国家自然科学基金（61572444）；;河南省高等学校重点科研项目（22A520049）； |
| |
| 摘 要： | 针对最短路径算法处理大规模数据集低效的问题，提出了基于图形处理器（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倍的加速比，验证了提出的并行优化方法的有效性和性能可移植性.
|
| 关 键 词： | 最短路径 重复平方法 图形处理器 开放式计算语言 并行算法 |
|
|
