10.3969/j.issn.1001-3695.2014.05.029
两种GPU上改进的最短路径算法
针对图论中的最短路径问题,提出了两种在GPU上改进的最短路径搜索算法,即针对单源最短路径问题的基于迭代方式且采用原子锁优化的Advanced_Atomics_SSSP算法以及针对所有顶点间最短路径问题的采用二叉堆优化的Heap_APSP算法。将两种算法应用到美国公路网图和节点的度均为6的普通图中,通过对算法的测试表明,Advanced_Atomics_SSSP算法的性能依赖于节点的度数,当节点的度数大于6时加速效果明显,当节点度数为1~3时加速效果不明显;而Heap_APSP可以达到46~56倍的加速比,
Dijkstra算法、单源最短路径、所有顶点间最短路径、GPU、原子锁、二叉堆
31
TP301.6(计算技术、计算机技术)
2014-05-06(万方平台首次上网日期,不代表论文的发表时间)
共4页
1407-1409,1413