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

A parallel Dijkstra algorithm based on multi-granularity communication

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

Parallelizing serial algorithm is one of effective methods to improve shortest path al- gorithm efficiency. A new parallel method based on the idea of bidirectional search and overlap- ping network segmentation is approached in this paper. In order to reduce communication time of shortest path algorithm, a multi-granularity communication method among different proces- ses is described. The experiment is done by using of American road network data provided by DIMAS. The result indicates： overlapping network segmentation method is an effective selec- tion for shortest path algorithm; improving communication multi-granularity size reduces com- munication time of different processes in parallelization algorithm; MPI communication time by transferring 50 network nodes each time is one-tenth of that by transferring 1 network node.