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

Design and Experiment on MPI-Based Parallel Network Simplex Algorithm for Network Minimum-Cost Flow

作　　者：吴立新[1,2] 刘纪平[3] 江锦成[4] 

机构地区：[1]东北大学测绘遥感与数字矿山研究所,辽宁沈阳110819 [2]中国矿业大学环境与测绘学院,江苏徐州221116 [3]中国测绘科学研究院,北京100830 [4]北京师范大学减灾与应急管理研究院,北京100875

出　　处：《地理与地理信息科学》2016年第1期1-5,共5页Geography and Geo-Information Science

基　　金：国家863计划项目(2011AA20302);测绘地理信息公益性行业科研专项经费项目(201512032)

摘　　要：网络最小费用流算法常用来解决资源流最优分配问题,传统的串行算法因时间复杂度高而不能满足大规模网络对计算效率的要求。该文用时间复杂度低的网络单纯形算法(NSA)的并行化求解大规模网络的最小费用流问题。通过分析NSA的可并行性,使用MPI分布式并行技术,设计了NSA并行算法;分析了3种常用流网络的拓扑结构特征及其与地理网络的关系;在并行环境下对计算效率进行实验测试,结果表明该算法具有显著的加速效果,峰值可达5.4。NSA并行算法应用面宽,可为区域及全国性大规模网络流资源分配方案的快速制定与政务决策提供有力支持。Network minimum-cost flow algorithms are usually used to solve optimal flow resource allocation problems.However,the traditional sequential algorithm is not efficient enough to satisfy the requirement of computing performance in large-scale network due to its high time-complexity.With the rapid development of computer technology,parallel computing is becoming an effective way of solving the computational bottleneck.This paper utilizes the relatively low time-complexity network simplex algorithm（NSA）to solve the network minimum-cost flow problem,and designs the parallel computing process of NSA.Analyzing to the parallelizability of NSA,distributed parallel NSA using MPI（Message Passing Interface）technology is designed for high-performance computing platform.The topological structures of three types of classical flow networks are discussed and referred to that of geographical networks.Experimental tests on the three classical flow networks demonstrate that the proposed parallel NSA displays notable acceleration effect,and the maximum speedup reaches 5.4.The proposed parallel NSA provides powerful support for rapid solution of large network resource allocation and decision making on national affairs at regional or national scale.

关 键 词：网络最小费用流 并行计算 资源分配 网络单纯形算法(NSA) MPI 

分 类 号：P208[天文地球—地图制图学与地理信息工程] TP301.6[天文地球—测绘科学与技术]