基于BSP的大規(guī)模圖處理系統(tǒng)中通信和緩存技術(shù)研究.pdf

1、隨著計算機以及網(wǎng)絡(luò)技術(shù)的發(fā)展，在計算機集群中采用并行的分布式計算方式提高計算處理能力已經(jīng)成為發(fā)展趨勢。云計算(Cloud Computing)的一個最主要的優(yōu)勢就是它的強大的并行計算處理能力，而這種能力是建立在一個簡便高效的并行編程模型的基礎(chǔ)上的。其中，最有代表性的就是Google提出的MapReduce分布式并行編程模型。然而，隨著近年來互聯(lián)網(wǎng)應(yīng)用的迅猛發(fā)展，Web網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等大規(guī)模網(wǎng)絡(luò)圖數(shù)據(jù)的分析處理成為了研究熱點，例如社交網(wǎng)絡(luò)

2、中的最短路徑、網(wǎng)頁搜索的PageRank等。這些圖處理問題通常需要多次迭代，而MapReduce適合于通用的大數(shù)據(jù)集計算問題，在處理具有多次迭代性質(zhì)的圖挖掘問題時會導(dǎo)致次優(yōu)的性能。因而這些圖算法往往更適合于采用基于消息傳遞的并行模型來處理。BSP(Bulk Synchronous Parallel)整體同步并行模型就是一種支持消息傳遞的塊內(nèi)異步并行，塊間顯式同步的并行計算模型。隨著Google基于BSP模型實現(xiàn)的大規(guī)模圖處理系統(tǒng)Preg

3、el的提出，在云環(huán)境中采用BSP模型實現(xiàn)大規(guī)模圖處理系統(tǒng)成為了主要的解決途徑。
　　本文旨在以BSP模型為核心，研究基于BSP模型的大規(guī)模圖處理系統(tǒng)中的消息通信原理和磁盤緩存技術(shù)的設(shè)計方案及其實現(xiàn)等問題。提出了一種基于隊列的消息組織方式和通信方案，并在此基礎(chǔ)上提出了基于消息打包、多發(fā)送者線程池以及支持消息合并的優(yōu)化通信方案。針對基于BSP的大圖處理系統(tǒng)可能存在的內(nèi)存不足以存放計算中所有的圖和消息數(shù)據(jù)的問題，本文建立了數(shù)據(jù)的內(nèi)存管理

4、模型，并基于內(nèi)存優(yōu)先(MemoryFirst)的思想，分別提出了圖數(shù)據(jù)和消息數(shù)據(jù)的磁盤緩存策略及相應(yīng)的算法:MF-GHIC算法、MLF圖數(shù)據(jù)遍歷算法和基于消息隊列優(yōu)先級的消息數(shù)據(jù)磁盤緩存算法等。
　　將本文提出的通信和緩存技術(shù)應(yīng)用于NEU-BSP系統(tǒng)中，我們通過實驗，首先分析了通信方案中各類參數(shù)的較優(yōu)值及其相互的制約關(guān)系;其次證明了在磁盤緩存率低于30％時，系統(tǒng)的時間性能下降并不顯著;最后，我們以PageRank和單源最短路徑為例