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

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

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

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