摘要： 针对目前图形处理器(GPU)上的动态数据处理问题，在分析现有并行单源最短路径(SSSP)算法的基础上，对GPU上的Moore SSSP算法进行并行化设计与实现。搜索时，综合应用层次化任务分配、层次化工作队列、层次化Kernel调用等策略。在不同类型图数据上进行实验测试，实验结果表明，该算法能有效减少空线程开销、访存开销以及同步时间。

关键词: 图形处理器, 图论, 动态数据, 单源最短路径, 计算统一设备架构

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)

中图分类号: 

• TP311.52