發(fā)布時間：2017-07-14 05:19

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

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

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

【相似文獻(xiàn)】

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

1 喬長閣;利用一個隨機(jī)并行算法實現(xiàn)最佳電路劃分[J];計算機(jī)工程與應(yīng)用;1997年01期

2 肖曼玉;呂全義;汪保;歐陽潔;;周期塊三對角線性方程組的一種并行算法[J];計算機(jī)工程與應(yīng)用;2007年09期

3 杜云飛;唐玉華;楊學(xué)軍;;容錯并行算法的性能分析[J];計算機(jī)科學(xué);2009年09期

4 胡峰,胡保生;并行計算技術(shù)與并行算法綜述[J];電腦與信息技術(shù);1999年05期

5 殷海濤;姜金輝;張方;侯友政;;分布動載荷識別的并行算法研究[J];國外電子測量技術(shù);2012年08期

6 王翔;宋君強(qiáng);盧風(fēng)順;楊錦輝;;快速球諧函數(shù)展開的并行算法設(shè)計及實現(xiàn)[J];微電子學(xué)與計算機(jī);2011年08期

7 劉興平,莫則堯,雷光耀,張寶琳,張景琳;高效并行算法的設(shè)計與實現(xiàn)[J];高技術(shù)通訊;1998年08期

8 杜云飛;王攀峰;富弘毅;周海芳;楊學(xué)軍;;矩陣LU分解的容錯并行算法設(shè)計與實現(xiàn)[J];微電子學(xué)與計算機(jī);2008年10期

9 米國偉;周海芳;杜云飛;;面向星載計算機(jī)的容錯并行算法設(shè)計與實現(xiàn)[J];航空兵器;2010年04期

10 朱政慧,薛紀(jì)善;一個有限區(qū)格點模式的兩種并行算法性能分析比較[J];計算機(jī)應(yīng)用;2002年09期

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

1 杜云飛;王攀峰;富弘毅;周海芳;楊學(xué)軍;;矩陣LU分解的容錯并行算法設(shè)計與實現(xiàn)[A];2008年全國開放式分布與并行計算機(jī)學(xué)術(shù)會議論文集(下冊)[C];2008年

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

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

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

3 彭瀅;基于BSDE的期權(quán)定價并行算法研究[D];山東大學(xué);2013年

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

1 劉騰;基于并行算法的隨機(jī)數(shù)生成方法的研究[D];北京工業(yè)大學(xué);2013年

2 米國偉;面向星載計算機(jī)的容錯并行算法研究與實現(xiàn)[D];國防科學(xué)技術(shù)大學(xué);2010年

3 張衍濤;物質(zhì)點并行算法研究[D];清華大學(xué);2011年

4 高碩;多處理機(jī)上的矩陣運算并行算法的研究與實現(xiàn)[D];湖北大學(xué);2011年

5 劉勃達(dá);基帶處理共性技術(shù)多核并行算法研究[D];電子科技大學(xué);2012年

6 林子皓;計算機(jī)系統(tǒng)的性能參數(shù)及速度研究[D];南京郵電大學(xué);2014年

7 彭超;基于Hadoop的數(shù)理統(tǒng)計功能集的研究與實現(xiàn)[D];北京郵電大學(xué);2013年

，

本文編號：539818