基于启发信息并行求解无环K最短路径  

Parallel Solving Acyclic K Shortest Paths Based on Heuristic Information

作　　者：刘正平[1] 钟诚[1] 张雄宝 高楠[1] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004

出　　处：《小型微型计算机系统》2017年第7期1506-1511,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61462005)资助;广西自然科学基金项目(2014GXNSFAA118396)资助

摘　　要：引入适用于非负权图的启发函数评估潜在偏离节点的代价,优先产生代价低的节点对应的候选路径;在迭代计算过程中,当候选偏离节点的代价大于候选路径中K条路径长度时,结束本次候选偏离路径计算,从而避免产生大量无用的候选路径;采用压缩邻接链表、组合数组优化图和路径在GPU储存器中的存储,采取顶点并行和边并行方法将比较耗时的删除和恢复节点操作并行化,以及并行化Dijkstra算法,在CUDA平台上设计实现GPU并行求解无环K最短路径算法P_AStart Yen.实验结果表明,P_AStart Yen比同类的GPU并行算法P_Yen平均加速7.30倍、最高加速14.38倍,比串行算法NIYA平均加速349.19倍、最高加速615.03倍.The cost of potential deviation nodes is evaluated by heuristic function that is suitable for all non-negative weight networks, and the candidate paths with nodes of low cost are generated. In the iteration process, when the cost of the deviation node is greater than the length of all K paths in candidate paths j the computing candidate deviation paths is completed at this round, and generating a lot of useless candidate paths is avoided. The compression adjacency list and combination of arrays are used to optimize the storage of graph and paths in GPU memory, the time-consuming operations for removing and recovering nodes are parallelized by node-edge parallel processing, and the algorithm Dijkstra is parallelized. A GPU parallel algorithm called P_AStartYen for solving acyclic K shortest paths is designed and implemented on CUDA platform. Experiments show that P_AStartYen is faster 7.30 times on average and maximal 14.38 times than parallel algorithm P_Yen,and P_AStartYen is faster 349.19 times on average and maximal 615.03 times than serial algorithm NIYA.

关 键 词：K最短路径 并行算法 启发式函数 GPU计算 CUDA 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]