作　　者： ; ;

机构地区： 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室

出　　处： 《计算机工程》 2012年第3期1-3,共3页

摘　　要： 提出一种多核平台并行单源最短路径算法。采用与Δ-Stepping算法相似的并行策略,通过多个子线程对同一个桶中的弧段进行并行松弛,利用主线程控制串行搜索中桶的序列。实验结果表明,该算法求解全美单源最短路径的时间约为4 s,与使用相同代码实现的串行算法相比,加速比更高。 A multi-thread parallel Single-source Shortest Path（SSSP） algorithm is proposed in multi-cores platform. It employs buckets to sort and uses the similar parallel strategy of A-Stepping algorithm. It does edge relaxations of the same bucket in parallel by slave threads, and searches all buckets in sequence by master thread. Experimental results show that this algorithm performs 4 seconds in the USA road network, achieving a higher speedup compared with serial parallel algorithm using same code.

关 键 词： 并行算法 最短路径 网络分析 多核平台

领　　域： [自动化与计算机技术] [自动化与计算机技术]