基于多粒度通讯的Dijkstra并行算法优化
A parallel Dijkstra algorithm based on multi-granularity communication作者机构:中国矿业大学(北京)地球科学与测绘工程学院北京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)
摘 要:串行算法的并行化是提高算法效率的一种有效途径,在分析最短路径算法特点的基础上,采用带重叠区的网络分割策略,提出了基于双向搜索的并行Dijkstra最短路径搜索算法.采用多粒度通讯方式进行进程间消息传递,能降低算法的通讯时间,并应用离散数学与理论计算研究中心(DIMAS)提供的美国路网数据进行试验.结果表明:采用带重叠区的数据分割策略适用于并行最短路径算法的求解;应用大粒度的多点接口(MPI)通讯方式能减少并行算法进程间的通讯时间;当通讯粒度为50时,MPI通讯所需时间是单粒度通讯模式的1/10左右.