计算机工程2012，Vol.38Issue(2)：42-44,3.DOI:10.3969/j.issn.1000-3428.2012.02.013
基于GPU的单源最短路径算法设计与实现
Design and Implementation of GPU-based Single Source Shortest Path Algorithm
郭绍忠 1王伟 1周刚 1胡艳2
作者信息
- 1. 解放军信息工程大学信息工程学院,郑州450002
- 2. 卫星导航定位总站,北京100094
- 折叠
摘要
Abstract
Based on analyzing existing parallel Single Source Shortest Path(SSSP) algorithm, aiming at the problem of dynamic data processing on Graphic Processor Unit(GPU), this paper designs and implements parallel Moore SSSP algorithm on GPU. The algorithm applies strategies like hierarchical task arrangement, hierarchical work queue and hierarchical Kernel invokes in key step. Experimental results indicate that the algorithm can reduce idle thread cost, memory access cost and synchronizing cost.关键词
图形处理器/图论/动态数据/单源最短路径/计算统一设备架构Key words
Graphic Processor Unit(GPU)/graphic theory/dynamic data/Single Source Shortest Path(SSSP)/Compute Unified Device Architecture(CUDA)分类
信息技术与安全科学引用本文复制引用
郭绍忠,王伟,周刚,胡艳..基于GPU的单源最短路径算法设计与实现[J].计算机工程,2012,38(2):42-44,3.
