-
题名基于GPU的全源最短路径算法
被引量:3
- 1
-
-
作者
邢星星
赵国兴
骆祖莹
方浩
-
机构
北京师范大学信息科学与技术学院
-
出处
《计算机科学》
CSCD
北大核心
2012年第3期299-303,共5页
-
基金
国家"863"高技术研究发展计划(2009AA01Z126)
国家自然科学基金(60876025)资助
-
文摘
针对有向图中每对顶点之间的最短路径问题,基于CPU集群并行算法,根据GPU并行计算加速机制,提出了基于棋盘划分方式的GPU并行算法,以增加算法的并行性与数据的局部性。当有向图规模超过GPU显存限制时,进一步提出了异步并行处理的GPU最短路径算法。实验结果表明,与CPU上单核算法相比,本算法具有如下加速效果:(1)对于节点数少于10000的小规模有向图,可以实现约155倍的加速;(2)对于节点数超过10000的大规模有向图,可实现约25倍的加速。
-
关键词
全源最短路径
GPU
棋盘划分
FLOYD算法
-
Keywords
Shortest-path,GPU,Chessboard division, Floyd
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
-
题名基于GPU的混合式全源对最短路径算法研究
被引量:3
- 2
-
-
作者
李寅
邓仰东
-
机构
清华大学微电子所
清华大学软件学院
-
出处
《微电子学与计算机》
CSCD
北大核心
2016年第2期77-82,共6页
-
文摘
全源对最短路径问题在生物信息学、地理信息系统、社交网络、复杂网络分析、集成电路计算机辅助设计和交通规划等领域都有重要应用.为了克服具体应用中因图结构差异对计算性能产生的影响,提出一种基于GPU架构的采样混合式全源对最短路径并行算法.在GPU上通过点处理顺序预设,粗细粒度任务分解等手段优化点并行算法,并引入采样方式预估图直径,有针对性地对每个遍历层选择高效的并行策略.与目前性能最好的GPU边并行算法相比,处理交通网络图等大直径图的加速比可达7.2倍,处理亚马逊产品联合采购网络图等小直径图的加速比可达1.9倍,同时采样混合式算法具备较好的伸缩性能,消除了因图结构不同而对算法性能产生的影响.
-
关键词
全源对最短路径
GPU
广度优先搜索
混合式算法
采样混合式算法
-
Keywords
all-pairs shortest paths
GPU
breath first search
hybrid algorithm
sampling hybrid algorithm
-
分类号
TP391.41
[自动化与计算机技术—计算机应用技术]
-
-
题名一种基于路径阻断的求解最短路径算法
- 3
-
-
作者
林家祺
卢罡
许南山
-
机构
北京化工大学信息科学与技术学院
-
出处
《计算机与现代化》
2017年第12期6-11,共6页
-
基金
国家自然科学基金资助项目(61602026)
-
文摘
全源最短路径的求解是计算机科学、交通工程、地理信息系统等学科中的一个研究热点。随着网络规模不断增大,求解全源最短路径的时间复杂度急剧上升,这制约了复杂网络相关研究与应用的快速发展,因此最短路径算法的效率问题是普遍关注并且在实际应用中迫切需要解决的问题。本文在BFS的基础上,引入路径阻断策略,利用已求得的单源最短路径节点的结果,加速全源最短路径的求解。实验结果表明该方法对大规模网络全源最短路径实现了加速计算。
-
关键词
复杂网络
全源最短路径
广度优先遍历
路径阻断
-
Keywords
complex network
APSP
BFS
poths block
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-