本文選題：網(wǎng)絡(luò)最大流 + 并行計(jì)算��； 參考：《電子科技大學(xué)》2014年碩士論文

【摘要】：網(wǎng)絡(luò)最大流問題是圖論有向圖部分的一個(gè)非常重要的基本問題,在圖論研究領(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í)代的到來給很多傳統(tǒng)的計(jì)算問題帶來了新的困難和挑戰(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ā)展對我們提出的新要求。BSP并行計(jì)算模型是并行計(jì)算領(lǐng)域的一個(gè)簡潔,實(shí)用且非常重要的計(jì)算模型。其具有清晰的邏輯組成結(jié)構(gòu),嚴(yán)謹(jǐn)?shù)牟⑿锌刂茩C(jī)制和良好的實(shí)用性,可擴(kuò)展性與可靠性。在云計(jì)算的研究熱潮下,BSP模型在云計(jì)算領(lǐng)域又有了新的應(yīng)用方向。本文對基于BSP模型實(shí)現(xiàn)并行化求解網(wǎng)絡(luò)最大流問題進(jìn)行了深入且卓有成效的研究。主要的研究工作如下:①對求解網(wǎng)絡(luò)最大流的基礎(chǔ)算法進(jìn)行了廣泛深入的研究,并選取Push-Relabel算法作為并行化實(shí)現(xiàn)的基礎(chǔ)算法,選定BSP并行計(jì)算模型作為并行計(jì)算的基礎(chǔ)模型。②基于BSP并行計(jì)算模型,通過模塊化編程設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)適用于圖計(jì)算問題的并行計(jì)算引擎。③對Push-Relabel算法,在計(jì)算的數(shù)據(jù)上進(jìn)行了并行化設(shè)計(jì),提出了一種新的兩階段圖數(shù)據(jù)劃分策略和圖分割跨界邊處理策略。④對Push-Relabel算法,在計(jì)算步驟上進(jìn)行了超步化設(shè)計(jì),優(yōu)化了超步中的算法計(jì)算步驟,并基于BSP并行計(jì)算引擎,編程實(shí)現(xiàn)了并行化求解網(wǎng)絡(luò)最大流。本文最后在實(shí)驗(yàn)室條件下,通過仿真實(shí)驗(yàn)測試對并行化求解網(wǎng)絡(luò)最大流進(jìn)行了兩個(gè)方面的結(jié)果測試。①對兩階段圖數(shù)據(jù)劃分策略與Hash圖分割的子圖分割效果進(jìn)行了對比測試,測試結(jié)果良好反應(yīng)了兩階段圖數(shù)據(jù)劃分策略在圖分割結(jié)果上的改進(jìn)效果。②對并行計(jì)算實(shí)現(xiàn)在加速比和并行度等方面進(jìn)行了性能測試,通過理論和數(shù)據(jù)兩個(gè)方面對測試數(shù)據(jù)進(jìn)行了分析和論證,驗(yàn)證了該并行化計(jì)算在實(shí)驗(yàn)室環(huán)境下的良好計(jì)算性能。
[Abstract]:The maximum flow problem of network is a very important basic problem in graph theory digraph. It has very important theoretical significance in the field of graph theory research. At the same time, the maximum flow of network has very important practical applications in the location of the express enterprise center, traffic assignment, image segmentation, and the discovery of social network Web community. According to the arrival of the times, new difficulties and challenges have been brought to many traditional computing problems. The traditional serial algorithm for solving the maximum flow of network is difficult to meet the requirements of current computing data and applications. The parallel computing of the maximum flow algorithm of the network is a new.BSP parallel computing model proposed by the Internet development. It is a concise, practical and very important computing model in the field of parallel computing. It has a clear logical structure, strict parallel control mechanism and good practicability, scalability and reliability. In the upsurge of cloud computing, the BSP model has a new application direction in the field of cloud computing. This paper is based on the BSP model. The main research work is as follows: (1) the basic algorithm for solving the maximum flow of the network is studied extensively, and the Push-Relabel algorithm is selected as the basic algorithm of the parallel implementation, and the BSP parallel computing model is selected as the basis of parallel computing. Based on the BSP parallel computing model, a parallel computing engine is designed and implemented by modularized programming. (3) a parallel design for the Push-Relabel algorithm is carried out on the calculated data, and a new two stage graph data partition strategy and a Graph Segmentation cross boundary processing strategy are proposed. (4) to Push-Rel The Abel algorithm has carried out the super step design in the calculation step, optimized the algorithm calculation steps in the super step, and based on the BSP parallel computing engine, the programming realized the parallelization to solve the maximum flow of the network. Finally, in the laboratory conditions, the results of two aspects of the maximum flow of the parallel computing network were tested by the simulation test. (1) the comparison test of the two stage map data partition strategy and the sub graph segmentation effect of the Hash graph segmentation is carried out. The test results well reflect the improvement effect of the two stage map data partition strategy on the image segmentation results. Secondly, the performance test is carried out on the speedup ratio and the parallelism of parallel computing, through two parties of theory and data. The analysis and demonstration of the test data verify the good computing performance of the parallel computing in the laboratory environment.

【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：O157.5;TP338.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前2條

1 厙向陽;;基于棧的網(wǎng)絡(luò)最大流算法[J];計(jì)算機(jī)工程與應(yīng)用;2009年33期

2 趙禮峰;白睿;宋常城;;求解網(wǎng)絡(luò)最大流問題的標(biāo)號算法[J];計(jì)算機(jī)技術(shù)與發(fā)展;2011年12期

，

本文編號：1816231