基于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];计算机工程与应用;1997年01期

2 肖曼玉;吕全义;汪保;欧阳洁;;周期块三对角线性方程组的一种并行算法[J];计算机工程与应用;2007年09期

3 杜云飞;唐玉华;杨学军;;容错并行算法的性能分析[J];计算机科学;2009年09期

4 胡峰,胡保生;并行计算技术与并行算法综述[J];电脑与信息技术;1999年05期

5 殷海涛;姜金辉;张方;侯友政;;分布动载荷识别的并行算法研究[J];国外电子测量技术;2012年08期

6 王翔;宋君强;卢风顺;杨锦辉;;快速球谐函数展开的并行算法设计及实现[J];微电子学与计算机;2011年08期

7 刘兴平,莫则尧,雷光耀,张宝琳,张景琳;高效并行算法的设计与实现[J];高技术通讯;1998年08期

8 杜云飞;王攀峰;富弘毅;周海芳;杨学军;;矩阵LU分解的容错并行算法设计与实现[J];微电子学与计算机;2008年10期

9 米国伟;周海芳;杜云飞;;面向星载计算机的容错并行算法设计与实现[J];航空兵器;2010年04期

10 朱政慧,薛纪善;一个有限区格点模式的两种并行算法性能分析比较[J];计算机应用;2002年09期

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

1 杜云飞;王攀峰;富弘毅;周海芳;杨学军;;矩阵LU分解的容错并行算法设计与实现[A];2008年全国开放式分布与并行计算机学术会议论文集(下册)[C];2008年

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

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

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

3 彭滢;基于BSDE的期权定价并行算法研究[D];山东大学;2013年

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

1 刘腾;基于并行算法的随机数生成方法的研究[D];北京工业大学;2013年

2 米国伟;面向星载计算机的容错并行算法研究与实现[D];国防科学技术大学;2010年

3 张衍涛;物质点并行算法研究[D];清华大学;2011年

4 高硕;多处理机上的矩阵运算并行算法的研究与实现[D];湖北大学;2011年

5 刘勃达;基带处理共性技术多核并行算法研究[D];电子科技大学;2012年

6 林子皓;计算机系统的性能参数及速度研究[D];南京邮电大学;2014年

7 彭超;基于Hadoop的数理统计功能集的研究与实现[D];北京邮电大学;2013年

，

本文编号：539818