基于BSP模型的網(wǎng)絡(luò)最大流算法的并行化研究與實(shí)現(xiàn).pdf

1、網(wǎng)絡(luò)最大流問(wèn)題是圖論有向圖部分的一個(gè)非常重要的基本問(wèn)題,在圖論研究領(lǐng)域有著非常重要的理論意義。同時(shí)網(wǎng)絡(luò)最大流在快遞企業(yè)中心選址、交通分配、圖像分割、社交網(wǎng)絡(luò)Web社團(tuán)發(fā)現(xiàn)等方面也有非常重要的實(shí)際應(yīng)用?；ヂ?lián)網(wǎng)大數(shù)據(jù)時(shí)代的到來(lái)給很多傳統(tǒng)的計(jì)算問(wèn)題帶來(lái)了新的困難和挑戰(zhàn),傳統(tǒng)的求解網(wǎng)絡(luò)最大流的串行算法目前已經(jīng)難以適應(yīng)當(dāng)前計(jì)算數(shù)據(jù)與應(yīng)用的要求。研究網(wǎng)絡(luò)最大流算法的并行化求解是互聯(lián)網(wǎng)發(fā)展對(duì)我們提出的新要求。
　　BSP并行計(jì)算模型是并行計(jì)算領(lǐng)

2、域的一個(gè)簡(jiǎn)潔,實(shí)用且非常重要的計(jì)算模型。其具有清晰的邏輯組成結(jié)構(gòu),嚴(yán)謹(jǐn)?shù)牟⑿锌刂茩C(jī)制和良好的實(shí)用性,可擴(kuò)展性與可靠性。在云計(jì)算的研究熱潮下,BSP模型在云計(jì)算領(lǐng)域又有了新的應(yīng)用方向。
　　本文對(duì)基于BSP模型實(shí)現(xiàn)并行化求解網(wǎng)絡(luò)最大流問(wèn)題進(jìn)行了深入且卓有成效的研究。主要的研究工作如下:①對(duì)求解網(wǎng)絡(luò)最大流的基礎(chǔ)算法進(jìn)行了廣泛深入的研究,并選取Push-Relabel算法作為并行化實(shí)現(xiàn)的基礎(chǔ)算法,選定BSP并行計(jì)算模型作為并行計(jì)算的基礎(chǔ)

3、模型。②基于BSP并行計(jì)算模型,通過(guò)模塊化編程設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)適用于圖計(jì)算問(wèn)題的并行計(jì)算引擎。③對(duì)Push-Relabel算法,在計(jì)算的數(shù)據(jù)上進(jìn)行了并行化設(shè)計(jì),提出了一種新的兩階段圖數(shù)據(jù)劃分策略和圖分割跨界邊處理策略。④對(duì)Push-Relabel算法,在計(jì)算步驟上進(jìn)行了超步化設(shè)計(jì),優(yōu)化了超步中的算法計(jì)算步驟,并基于BSP并行計(jì)算引擎,編程實(shí)現(xiàn)了并行化求解網(wǎng)絡(luò)最大流。
　　本文最后在實(shí)驗(yàn)室條件下,通過(guò)仿真實(shí)驗(yàn)測(cè)試對(duì)并行化求解網(wǎng)絡(luò)最大