本文關(guān)鍵詞：基于MPI的最小費用流網(wǎng)絡單純形并行算法設計與實驗

  更多相關(guān)文章： 網(wǎng)絡最小費用流 并行計算 資源分配 網(wǎng)絡單純形算法(NSA) MPI

【摘要】：網(wǎng)絡最小費用流算法常用來解決資源流最優(yōu)分配問題,傳統(tǒng)的串行算法因時間復雜度高而不能滿足大規(guī)模網(wǎng)絡對計算效率的要求。該文用時間復雜度低的網(wǎng)絡單純形算法(NSA)的并行化求解大規(guī)模網(wǎng)絡的最小費用流問題。通過分析NSA的可并行性,使用MPI分布式并行技術(shù),設計了NSA并行算法;分析了3種常用流網(wǎng)絡的拓撲結(jié)構(gòu)特征及其與地理網(wǎng)絡的關(guān)系;在并行環(huán)境下對計算效率進行實驗測試,結(jié)果表明該算法具有顯著的加速效果,峰值可達5.4。NSA并行算法應用面寬,可為區(qū)域及全國性大規(guī)模網(wǎng)絡流資源分配方案的快速制定與政務決策提供有力支持。
【作者單位】： 東北大學測繪遙感與數(shù)字礦山研究所;中國礦業(yè)大學環(huán)境與測繪學院;中國測繪科學研究院;北京師范大學減災與應急管理研究院;
【關(guān)鍵詞】： 網(wǎng)絡最小費用流 并行計算 資源分配 網(wǎng)絡單純形算法(NSA) MPI
【基金】：國家863計劃項目(2011AA20302) 測繪地理信息公益性行業(yè)科研專項經(jīng)費項目(201512032)
【分類號】：TP338.6
【正文快照】： 3.中國測繪科學研究院,北京100830;4.北京師范大學減災與應急管理研究院,北京100875)0引言網(wǎng)絡最小費用流問題旨在將交通網(wǎng)絡上的資源以最小的總代價從供應點運輸至需求點,已被廣泛應用于工業(yè)生產(chǎn)、通訊及GIS網(wǎng)絡分析領(lǐng)域,在全國性物流規(guī)劃與資源調(diào)配中有著重要意義。目前,針

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 徐云;孫廣中;鄭啟龍;吳俊敏;陳國良;;“并行算法”課程的教學與探討[J];教育與現(xiàn)代化;2008年04期

2 陳國良;孫廣中;徐云;呂敏;;并行算法研究方法學[J];計算機學報;2008年09期

3 羅貴章;陳忠偉;;并行算法綜述[J];計算機光盤軟件與應用;2013年15期

4 謝鐵柱;吳功廣;;多項式幾種并行算法的比較與優(yōu)化[J];計算機工程與科學;1981年01期

5 李曉梅 ,胡慶豐;并行算法的發(fā)展與展望[J];計算機工程與科學;1991年03期

6 童麗,王正明,曾泳泓;自變量選擇及其并行算法[J];數(shù)值計算與計算機應用;2001年03期

7 陳國良;昔日王榭堂前燕,飛入尋常百姓家淺談并行算法[J];新電腦;2002年12期

8 李曉梅;《可擴展并行算法的設計與分析》簡介[J];裝備指揮技術(shù)學院學報;2003年02期

9 吳磊,蘆東昕,方馬;并行算法中的指針轉(zhuǎn)移技術(shù)分析[J];計算機工程;2003年22期

10 雷英杰,霍紅衛(wèi);典型并行算法的實現(xiàn)性能分析[J];空軍工程大學學報(自然科學版);2003年05期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 姚向東;;并行算法到并行結(jié)構(gòu)的映射[A];中國工程物理研究院科技年報（2001）[C];2001年

2 高華;苗世光;;城市小區(qū)尺度模式并行算法研究[A];中國氣象學會2006年年會“中尺度天氣動力學、數(shù)值模擬和預測”分會場論文集[C];2006年

3 王志成;吳頌平;;多塊結(jié)構(gòu)網(wǎng)格并行算法研究[A];北京力學會第20屆學術(shù)年會論文集[C];2014年

4 焦龍;郭亞紅;紀守領(lǐng);李金寶;;基于多核計算機的分子動力學并行算法的實現(xiàn)[A];黑龍江省計算機學會2009年學術(shù)交流年會論文集[C];2010年

5 張衡;張武;;三維拋物型初邊值問題的塊三對角可擴展并行算法[A];2007年全國開放式分布與并行計算機學術(shù)會議論文集(上冊)[C];2007年

6 王雷章;張愛武;劉曉萌;;三維建模中平面分割并行算法的設計與實現(xiàn)[A];中國系統(tǒng)仿真學會第五次全國會員代表大會暨2006年全國學術(shù)年會論文集[C];2006年

7 毛韶陽;李肯立;;一種基因數(shù)據(jù)的聚類并行算法研究[A];2007年全國開放式分布與并行計算機學術(shù)會議論文集(上冊)[C];2007年

8 左墨;藺小林;;電力系統(tǒng)暫態(tài)穩(wěn)定并行算法的進展[A];第二屆中國水利水電巖土力學與工程學術(shù)討論會論文集（二）[C];2008年

9 樊洪明;李先庭;趙彬;任鴻澤;;有限元分布式并行算法研究[A];全國暖通空調(diào)制冷2002年學術(shù)年會論文集[C];2002年

10 侯有政;張方;;基于CUDA的動載荷頻域識別的并行算法研究[A];第十屆全國振動理論及應用學術(shù)會議論文集（2011）上冊[C];2011年

中國重要報紙全文數(shù)據(jù)庫 前4條

1 ;并行算法研究進展[N];中國計算機報;2004年

2 新華社記者 奚啟新 本報通訊員 李汛 記者 喻國英;精彩人生[N];光明日報;2005年

3 新華社記者　奚啟新　本報記者　廖文根;三次選擇　無怨無悔[N];人民日報;2005年

4 清華大學計算機系 薛巍;電網(wǎng)仿真考驗高性能計算[N];計算機世界;2006年

中國博士學位論文全文數(shù)據(jù)庫 前10條

1 任立波;稠密顆粒兩相流的CFD-DEM耦合并行算法及數(shù)值模擬[D];山東大學;2015年

2 李雪寶;太陽望遠鏡海量數(shù)據(jù)并行處理技術(shù)研究[D];中國科學院研究生院(云南天文臺);2015年

3 張艷;分布并行算法設計、分析與實現(xiàn)[D];電子科技大學;2001年

4 杜云飛;容錯并行算法的研究與分析[D];國防科學技術(shù)大學;2008年

5 潘斌;幾何定理機器證明并行算法研究[D];中國科學院研究生院（成都計算機應用研究所）;2006年

6 駱志剛;典型結(jié)構(gòu)大型線性方程組的分布式并行算法研究[D];中國人民解放軍國防科學技術(shù)大學;2000年

7 何霞輝;基于非穩(wěn)態(tài)不可壓縮流的可擴張并行算法研究[D];湖南大學;2013年

8 戚晶晶;熱物性反問題高效并行算法研究[D];武漢理工大學;2013年

9 張愛清;可擴展數(shù)據(jù)驅(qū)動并行算法研究及應用[D];中國工程物理研究院;2009年

10 李鴻健;并行算法在激光化學反應模擬中的應用研究[D];電子科技大學;2012年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 陳權(quán);基于分布式集群的多攝像頭的目標檢測和跟蹤的并行算法[D];南京理工大學;2015年

2 馬煥煥;一類近場動力學問題的并行算法[D];山東大學;2015年

3 朱曉丹;一種神經(jīng)動力學優(yōu)化系統(tǒng)的并行算法設計[D];大連理工大學;2015年

4 張源;新一代視頻編碼技術(shù)的并行算法設計與實現(xiàn)[D];大連理工大學;2015年

5 董蕾;基于GPU的圖像壓縮感知算法并行化研究[D];電子科技大學;2015年

6 蔣昭炎;基于圖像的大場景三維重建并行算法研究[D];東北大學;2013年

7 廖臣;電磁粒子模擬軟件并行算法的研究[D];電子科技大學;2007年

8 戴波;并行算法及其應用[D];電子科技大學;2002年

9 宋偉;關(guān)聯(lián)規(guī)則并行算法的研究與分析[D];鄭州大學;2006年

10 雷瀾;并行算法在矩陣計算中的應用研究[D];重慶大學;2004年

，

本文編號：539817