基于MPI＋OpenMP混合编程模型的城市路网最短路径并行算法

摘要

An MPI＋OpenMP hybrid programming model was proposed based on the Floyd algorithm as its core to solve the shortest path problem which needs huge computation and high real-timeness.The proposed model provides the intra-and inter-node hierarchical parallel processing,takes full advantage of shared memory model and message passing model,improves the system performance,and enhances the calculation speed.The model was validated by the road network in Changchun city,and the results showed that the proposed model is characterized by better speedup ratio and operation efficiency than the MPI model.With the increase of the node,the speedup ratio of the model improves more significantly,indicating the model has a better expansibility.%针对城市路网最短路径求解计算量庞大、实时性要求高的问题,提出了用Floyd算法为核心的MPI＋OpenMP混合编程模型来解决这个问题。MPI＋OpenMP混合编程提供结点内和结点间的两级并行处理,能充分利用共享存储模型和消息传递模型的优点,有效改善系统性能,提高系统计算速度。经由长春市路网验证可知,混合模型比MPI模型具有更好的加速比和运算效率,并且随着计算节点个数的增加,加速比提高幅度更大,表明MPI＋OpenMP混合模型有着更好的可扩展性。