| 基于GPU的单源最短路径算法设计与实现 |
| |
| 引用本文： | 郭绍忠,王伟,周刚,胡艳.基于GPU的单源最短路径算法设计与实现[J].计算机工程,2012,38(2):42-44. |
| |
| 作者姓名： | 郭绍忠 王伟 周刚 胡艳 |
| |
| 作者单位： | 1. 解放军信息工程大学信息工程学院,郑州,450002
2. 卫星导航定位总站,北京,100094 |
| |
| 摘 要： | 针对目前图形处理器(GPU)上的动态数据处理问题，在分析现有并行单源最短路径(SSSP)算法的基础上，对GPU上的Moore SSSP算法进行并行化设计与实现。搜索时，综合应用层次化任务分配、层次化工作队列、层次化Kernel调用等策略。在不同类型图数据上进行实验测试，实验结果表明，该算法能有效减少空线程开销、访存开销以及同步时间。
|
| 关 键 词： | 图形处理器 图论 动态数据 单源最短路径 计算统一设备架构 |
| 收稿时间： | 2011-07-13 |
Design and Implementation of GPU-based Single Source Shortest Path Algorithm |
| |
| GUO Shao-zhong
,
WANG Wei
,
ZHOU Gang
,
HU Yan.Design and Implementation of GPU-based Single Source Shortest Path Algorithm[J].Computer Engineering,2012,38(2):42-44. |
| |
| Authors: | GUO Shao-zhong WANG Wei ZHOU Gang HU Yan |
| |
| Affiliation: | 1.Institute of Information Engineering,PLA Information Engineering University,Zhengzhou 450002,China;2.Satellite Tracking and Locating Terminal Station,Beijing 100094,China) |
| |
| 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. |
| |
| Keywords: | Graphic Processor Unit（GPU） graphic theory dynamic data Single Source Shortest Path（SSSP） Compute Unified Device Architecture（CUDA） |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
