基于MPI的最小费用流网络单纯形并行算法设计与实验

发布时间：2017-07-14 05:19

  本文关键词：基于MPI的最小费用流网络单纯形并行算法设计与实验

  更多相关文章： 网络最小费用流 并行计算 资源分配 网络单纯形算法(NSA) MPI

【摘要】：网络最小费用流算法常用来解决资源流最优分配问题,传统的串行算法因时间复杂度高而不能满足大规模网络对计算效率的要求。该文用时间复杂度低的网络单纯形算法(NSA)的并行化求解大规模网络的最小费用流问题。通过分析NSA的可并行性,使用MPI分布式并行技术,设计了NSA并行算法;分析了3种常用流网络的拓扑结构特征及其与地理网络的关系;在并行环境下对计算效率进行实验测试,结果表明该算法具有显著的加速效果,峰值可达5.4。NSA并行算法应用面宽,可为区域及全国性大规模网络流资源分配方案的快速制定与政务决策提供有力支持。
【作者单位】： 东北大学测绘遥感与数字矿山研究所;中国矿业大学环境与测绘学院;中国测绘科学研究院;北京师范大学减灾与应急管理研究院;
【关键词】： 网络最小费用流 并行计算 资源分配 网络单纯形算法(NSA) MPI
【基金】：国家863计划项目(2011AA20302) 测绘地理信息公益性行业科研专项经费项目(201512032)
【分类号】：TP338.6
【正文快照】： 3.中国测绘科学研究院,北京100830;4.北京师范大学减灾与应急管理研究院,北京100875)0引言网络最小费用流问题旨在将交通网络上的资源以最小的总代价从供应点运输至需求点,已被广泛应用于工业生产、通讯及GIS网络分析领域,在全国性物流规划与资源调配中有着重要意义。目前,针

【相似文献】

中国期刊全文数据库 前10条

1 徐云;孙广中;郑启龙;吴俊敏;陈国良;;“并行算法”课程的教学与探讨[J];教育与现代化;2008年04期

2 陈国良;孙广中;徐云;吕敏;;并行算法研究方法学[J];计算机学报;2008年09期

3 罗贵章;陈忠伟;;并行算法综述[J];计算机光盘软件与应用;2013年15期

4 谢铁柱;吴功广;;多项式几种并行算法的比较与优化[J];计算机工程与科学;1981年01期

5 李晓梅 ,胡庆丰;并行算法的发展与展望[J];计算机工程与科学;1991年03期

6 童丽,王正明,曾泳泓;自变量选择及其并行算法[J];数值计算与计算机应用;2001年03期

7 陈国良;昔日王榭堂前燕,飞入寻常百姓家浅谈并行算法[J];新电脑;2002年12期

8 李晓梅;《可扩展并行算法的设计与分析》简介[J];装备指挥技术学院学报;2003年02期

9 吴磊,芦东昕,方马;并行算法中的指针转移技术分析[J];计算机工程;2003年22期

10 雷英杰,霍红卫;典型并行算法的实现性能分析[J];空军工程大学学报(自然科学版);2003年05期

中国重要会议论文全文数据库 前10条

1 姚向东;;并行算法到并行结构的映射[A];中国工程物理研究院科技年报（2001）[C];2001年

2 高华;苗世光;;城市小区尺度模式并行算法研究[A];中国气象学会2006年年会“中尺度天气动力学、数值模拟和预测”分会场论文集[C];2006年

3 王志成;吴颂平;;多块结构网格并行算法研究[A];北京力学会第20届学术年会论文集[C];2014年

4 焦龙;郭亚红;纪守领;李金宝;;基于多核计算机的分子动力学并行算法的实现[A];黑龙江省计算机学会2009年学术交流年会论文集[C];2010年

5 张衡;张武;;三维抛物型初边值问题的块三对角可扩展并行算法[A];2007年全国开放式分布与并行计算机学术会议论文集(上册)[C];2007年

6 王雷章;张爱武;刘晓萌;;三维建模中平面分割并行算法的设计与实现[A];中国系统仿真学会第五次全国会员代表大会暨2006年全国学术年会论文集[C];2006年

7 毛韶阳;李肯立;;一种基因数据的聚类并行算法研究[A];2007年全国开放式分布与并行计算机学术会议论文集(上册)[C];2007年

8 左墨;蔺小林;;电力系统暂态稳定并行算法的进展[A];第二届中国水利水电岩土力学与工程学术讨论会论文集（二）[C];2008年

9 樊洪明;李先庭;赵彬;任鸿泽;;有限元分布式并行算法研究[A];全国暖通空调制冷2002年学术年会论文集[C];2002年

10 侯有政;张方;;基于CUDA的动载荷频域识别的并行算法研究[A];第十届全国振动理论及应用学术会议论文集（2011）上册[C];2011年

中国重要报纸全文数据库 前4条

1 ;并行算法研究进展[N];中国计算机报;2004年

2 新华社记者 奚启新 本报通讯员 李汛 记者 喻国英;精彩人生[N];光明日报;2005年

3 新华社记者　奚启新　本报记者　廖文根;三次选择　无怨无悔[N];人民日报;2005年

4 清华大学计算机系 薛巍;电网仿真考验高性能计算[N];计算机世界;2006年

中国博士学位论文全文数据库 前10条

1 任立波;稠密颗粒两相流的CFD-DEM耦合并行算法及数值模拟[D];山东大学;2015年

2 李雪宝;太阳望远镜海量数据并行处理技术研究[D];中国科学院研究生院(云南天文台);2015年

3 张艳;分布并行算法设计、分析与实现[D];电子科技大学;2001年

4 杜云飞;容错并行算法的研究与分析[D];国防科学技术大学;2008年

5 潘斌;几何定理机器证明并行算法研究[D];中国科学院研究生院（成都计算机应用研究所）;2006年

6 骆志刚;典型结构大型线性方程组的分布式并行算法研究[D];中国人民解放军国防科学技术大学;2000年

7 何霞辉;基于非稳态不可压缩流的可扩张并行算法研究[D];湖南大学;2013年

8 戚晶晶;热物性反问题高效并行算法研究[D];武汉理工大学;2013年

9 张爱清;可扩展数据驱动并行算法研究及应用[D];中国工程物理研究院;2009年

10 李鸿健;并行算法在激光化学反应模拟中的应用研究[D];电子科技大学;2012年

中国硕士学位论文全文数据库 前10条

1 陈权;基于分布式集群的多摄像头的目标检测和跟踪的并行算法[D];南京理工大学;2015年

2 马焕焕;一类近场动力学问题的并行算法[D];山东大学;2015年

3 朱晓丹;一种神经动力学优化系统的并行算法设计[D];大连理工大学;2015年

4 张源;新一代视频编码技术的并行算法设计与实现[D];大连理工大学;2015年

5 董蕾;基于GPU的图像压缩感知算法并行化研究[D];电子科技大学;2015年

6 蒋昭炎;基于图像的大场景三维重建并行算法研究[D];东北大学;2013年

7 廖臣;电磁粒子模拟软件并行算法的研究[D];电子科技大学;2007年

8 戴波;并行算法及其应用[D];电子科技大学;2002年

9 宋伟;关联规则并行算法的研究与分析[D];郑州大学;2006年

10 雷澜;并行算法在矩阵计算中的应用研究[D];重庆大学;2004年

，

本文编号：539817