基于BSP的高性能大圖迭代計算的研究與實現(xiàn).pdf

1、隨著信息技術(shù)的快速發(fā)展與廣泛應(yīng)用，如何有效管理、高效處理大量的信息數(shù)據(jù)已經(jīng)成為學術(shù)界與工業(yè)界面臨的重要挑戰(zhàn)。如社交網(wǎng)絡(luò)、傳感器網(wǎng)絡(luò)及電商交易等應(yīng)用中的數(shù)據(jù)具有圖的結(jié)構(gòu)，并且在科學研究中具有巨大的價值，因此成為了“大數(shù)據(jù)”研究的熱點。Google公司提出的MapReduce分布式計算框架，能夠支持各種類型的大數(shù)據(jù)應(yīng)用處理，但是對于圖應(yīng)用的算法，如單源最短路徑、子圖挖掘等，通常需要多次迭代并交換中間結(jié)果數(shù)據(jù)，迭代過程中數(shù)據(jù)處理并行化的缺失導

2、致MapReduce不適合處理大圖計算。以Google提出的Pregel為代表的基于BSP模型的大圖處理系統(tǒng)，已經(jīng)成為目前大圖處理的重要手段，但是在消息通信與圖迭代磁盤處理等方面仍存在不足。
　　本文以BSP模型為基礎(chǔ)，圍繞消息通信與磁盤迭代處理兩個方面研究如何提高圖處理系統(tǒng)的效率。首先，建立一個簡單有效的消息傳遞通信結(jié)構(gòu)，通過控制相關(guān)參數(shù)保證基本通信性能。其次，在其基礎(chǔ)上，結(jié)合廣播消息類圖算法，提出一種基于邊聚簇的邊界點備份策略

3、(ECBVR)，并建立代價估計模型分析消息通信的優(yōu)化對系統(tǒng)處理性能的作用效果，同時，圍繞ECBVR，提出點-邊計算模型，并優(yōu)化邊計算過程，設(shè)計Hash索引和多隊列并行順序索引兩種機制進一步提高系統(tǒng)的處理效率。再次，在圖迭代磁盤處理方面，建立內(nèi)存分配模型以提高數(shù)據(jù)內(nèi)存駐留率，提出數(shù)據(jù)分組迭代(DGI)與消息有序迭代(MSI)兩種迭代處理機制避免磁盤隨機訪問。對于DGI方式，討論了兩種分組算法:隨機Hash分組與均衡分組;對于MSI方式，設(shè)

4、計了新的數(shù)據(jù)存儲模型OERSV以保證消息的接收有序，同時為避免對頂點有序表的隨機磁盤訪問建立分頁機制。
　　本文的相關(guān)技術(shù)在BC-BSP大規(guī)模圖處理系統(tǒng)的框架下實現(xiàn)，并在合成數(shù)據(jù)集與真實數(shù)據(jù)集上完成相關(guān)實驗。對于ECBVR技術(shù)，通過分析邊聚簇劃分閾值對通信規(guī)模、處理速度及數(shù)據(jù)加載時間的影響，可以確定ECBVR的有效性，通過對三種不同的實現(xiàn)方式的對比，驗證了索引的有效性，并發(fā)現(xiàn)該技術(shù)對高出度圖數(shù)據(jù)較為有效。對于磁盤處理技術(shù)，驗證內(nèi)存