基于多粒度通讯的Dijkstra并行算法优化

作     者：孙文彬 谭正龙 王江 赵帅阳 SUN Wenbin;TAN Zhenglong;WANG Jiang;ZHAO Shuaiyang

作者机构：中国矿业大学(北京)地球科学与测绘工程学院北京100083 

出 版 物：《中国矿业大学学报》 (Journal of China University of Mining & Technology)

年 卷 期：2014年第43卷第5期

页      面：938-943页

核心收录：

学科分类：081603[工学-地图制图学与地理信息工程] 081802[工学-地球探测与信息技术] 0709[理学-地质学] 0819[工学-矿业工程] 07[理学] 08[工学] 070503[理学-地图学与地理信息系统] 0818[工学-地质资源与地质工程] 0708[理学-地球物理学] 0815[工学-水利工程] 0705[理学-地理学] 0816[工学-测绘科学与技术] 0813[工学-建筑学] 0802[工学-机械工程] 0814[工学-土木工程] 0801[工学-力学（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(41201416) 国家高技术研究发展计划(863)项目(2011AA120302) 

主　　题：最短路径算法 MPI通讯 带重叠区的网路分割 

摘      要：串行算法的并行化是提高算法效率的一种有效途径,在分析最短路径算法特点的基础上,采用带重叠区的网络分割策略,提出了基于双向搜索的并行Dijkstra最短路径搜索算法.采用多粒度通讯方式进行进程间消息传递,能降低算法的通讯时间,并应用离散数学与理论计算研究中心(DIMAS)提供的美国路网数据进行试验.结果表明:采用带重叠区的数据分割策略适用于并行最短路径算法的求解;应用大粒度的多点接口(MPI)通讯方式能减少并行算法进程间的通讯时间;当通讯粒度为50时,MPI通讯所需时间是单粒度通讯模式的1/10左右.