双重并行环境下最短路径的研究

Research on Shortest Path in Dual Parallel Environment

摘要:

并行问题和最短路径问题已成为一个热点研究课题,传统的最短路径算法已不能满足数据爆炸式增长的处理需求,尤其当网络规模很大时,所需的计算时间和存储空间也大大的增加;MapReduce模型的出现,带来了一种新的解决方法来解决最短路径;GPU具有强大的并行计算能力和存储带宽,与CPU相比具有明显的优势;通过研究MapReduce模型和GPU执行过程的分析,指出单独基于MapReduce模型的最短路径并行方法存在的问题,降低了系统的性能;论文的创新点是结合MapReduce和GPU形成双并行模型,并行预处理数据,针对最短路径中的数据传输和同步开销,增加数据动态处理器;最后实验从并行算法的性能评价指标平均加速比进行比较,结果表明,双重并行环境下的最短路径的计算,提高了加速比。

Abstract:

Parallel problem and shortest path problem has become a hot research topic, traditional shortest path algorithm cannot meet the demand of the explosive growth of the data processing, especially when the network size is large, the computation time and storage space required is greatly increased.The emergence of MapReduce model, brings a new solution to solve the shortest path. GPU has powerful parallel computing capability and storage bandwidth, and CPU has obvious advantages.By studying MapReduce model and GPU implementation process analysis, pointed out the shortest path parallel method based on MapReduce model alone existing problems, and reduce the performance of the system.The innovation of this paper is combine MapReduce and GPU to form double parallel model, parallel preprocessing data, the data transfer and synchronization overhead for the shortest patht,increase data dynamic processor. Compared with the average speedup of performance evaluation index of parallel algorithm, the results show that the computation of the shortest path in double parallel environment improves the speedup.