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

吉林大学学报(工学版) ›› 2011, Vol. 41 ›› Issue (6): 1581-1584.

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

杨庆芳^1,2,刘冬²,杨兆升^1,2

1.吉林大学汽车仿真与控制国家重点实验室|长春 130022；2.吉林大学交通学院|长春 130022

收稿日期:2010-09-09 出版日期:2011-11-01 发布日期:2011-11-01
通讯作者: 刘冬(1985-),男,硕士研究生.研究方向:并行计算,云计算,数字图像处理. E-mail:ld081055@126.com
作者简介:杨庆芳(1966-),女,教授,博士生导师.研究方向:智能交通运输系统.E-mail:yangqf@jlu.edu.cn
基金资助:
“863”国家高技术研究发展计划项目(2009AA11Z218,2009AA11Z208).

Parallel algorithm for urban road network shortest path based on MPI+OpenMP hybrid programming model

YANG Qing-fang^1,2,LIU Dong²,YANG Zhao-sheng^{1, 2}

1.State Key Laboratory of Automotive Simulation and Control, Jilin University, Changchun 130022, China；2.College of Transportation, Jilin University, Changchun 130022, China

Received:2010-09-09 Online:2011-11-01 Published:2011-11-01

摘要/Abstract

摘要：

针对城市路网最短路径求解计算量庞大、实时性要求高的问题,提出了用Floyd算法为核心的MPI+OpenMP混合编程模型来解决这个问题。MPI+OpenMP混合编程提供结点内和结点间的两级并行处理,能充分利用共享存储模型和消息传递模型的优点,有效改善系统性能,提高系统计算速度。经由长春市路网验证可知,混合模型比MPI模型具有更好的加速比和运算效率,并且随着计算节点个数的增加,加速比提高幅度更大,表明MPI+OpenMP混合模型有着更好的可扩展性。

关键词: 交通运输系统工程, 消息传递接口, MPI+OpenMP混合模型, 最短路径, Floyd算法

Abstract:

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.

Key words: engineering of communications and transportation system, message passing interface(MPI), MPI+OpenMP hybrid model, shortest path, Floyd algorithm

中图分类号:

U491.2

杨庆芳^1,2,刘冬²,杨兆升^1,2. 基于MPI+OpenMP混合编程模型的城市路网最短路径并行算法[J]. 吉林大学学报(工学版), 2011, 41(6): 1581-1584.

YANG Qing-fang,LIU Dong,YANG Zhao-sheng. Parallel algorithm for urban road network shortest path based on MPI+OpenMP hybrid programming model[J]. 吉林大学学报(工学版), 2011, 41(6): 1581-1584.

参考文献

相关文章 15

[1]	陈永恒,刘芳宏,曹宁博. 信控交叉口行人与提前右转机动车冲突影响因素[J]. 吉林大学学报(工学版), 2018, 48(6): 1669-1676.
[2]	常山,宋瑞,何世伟,黎浩东,殷玮川. 共享单车故障车辆回收模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1677-1684.
[3]	曲大义,杨晶茹,邴其春,王五林,周警春. 基于干线车流排队特性的相位差优化模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1685-1693.
[4]	宗芳, 齐厚成, 唐明, 吕建宇, 于萍. 基于GPS数据的日出行模式-出行目的识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1374-1379.
[5]	刘翔宇, 杨庆芳, 隗海林. 基于随机游走算法的交通诱导小区划分方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1380-1386.
[6]	钟伟, 隽志才, 孙宝凤. 不完全网络的城乡公交一体化枢纽层级选址模型[J]. 吉林大学学报(工学版), 2018, 48(5): 1387-1397.
[7]	刘兆惠, 王超, 吕文红, 管欣. 基于非线性动力学分析的车辆运行状态参数数据特征辨识[J]. 吉林大学学报(工学版), 2018, 48(5): 1405-1410.
[8]	宗芳, 路峰瑞, 唐明, 吕建宇, 吴挺. 习惯和路况对小汽车出行路径选择的影响[J]. 吉林大学学报(工学版), 2018, 48(4): 1023-1028.
[9]	栾鑫, 邓卫, 程琳, 陈新元. 特大城市居民出行方式选择行为的混合Logit模型[J]. 吉林大学学报(工学版), 2018, 48(4): 1029-1036.
[10]	陈永恒, 刘鑫山, 熊帅, 汪昆维, 谌垚, 杨少辉. 冰雪条件下快速路汇流区可变限速控制[J]. 吉林大学学报(工学版), 2018, 48(3): 677-687.
[11]	王占中, 卢月, 刘晓峰, 赵利英. 基于改进和声搜索算法的越库车辆排序[J]. 吉林大学学报(工学版), 2018, 48(3): 688-693.
[12]	李志慧, 胡永利, 赵永华, 马佳磊, 李海涛, 钟涛, 杨少辉. 基于车载的运动行人区域估计方法[J]. 吉林大学学报(工学版), 2018, 48(3): 694-703.
[13]	陈松, 李显生, 任园园. 公交车钩形转弯交叉口自适应信号控制方法[J]. 吉林大学学报(工学版), 2018, 48(2): 423-429.
[14]	苏书杰, 何露. 步行交通规划交叉路口行人瞬时动态拥塞疏散模型[J]. 吉林大学学报(工学版), 2018, 48(2): 440-447.
[15]	孟品超, 李学源, 贾洪飞, 李延忠. 基于滑动平均法的轨道交通短时客流实时预测[J]. 吉林大学学报(工学版), 2018, 48(2): 448-453.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed