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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：539818