基于鄰接表垂直劃分的NEu-BSP圖處理系統(tǒng)優(yōu)化技術(shù)的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、近年來(lái)互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，使得Web網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等大規(guī)模網(wǎng)絡(luò)圖數(shù)據(jù)的分析處理成為了研究熱點(diǎn)，例如社交網(wǎng)絡(luò)中的最短路徑、網(wǎng)頁(yè)搜索的PageRank等。云計(jì)算(Cloud Computing)提供強(qiáng)大的并行計(jì)算處理能力。其中，最有代表性的就是MapReduce分布式并行編程模型。然而大多圖算法具有多次迭代的性質(zhì)，這并非MapReduce所擅長(zhǎng)。隨著Google基于BSP模型實(shí)現(xiàn)的大規(guī)模圖處理系統(tǒng)Pregel的提出，在云環(huán)境中采用BSP模

2、型實(shí)現(xiàn)大規(guī)模圖處理系統(tǒng)成為了一個(gè)可選的解決途徑?！霸朴?jì)算平臺(tái)NEU-BSP大規(guī)模圖處理系統(tǒng)的研究與研發(fā)”項(xiàng)目提出了一種均衡劃分算法來(lái)保證子任務(wù)的頂點(diǎn)數(shù)量大致平衡，但是沒(méi)能夠有效降低任務(wù)間的通信量。因此，如何將一張大規(guī)模的圖劃分到各個(gè)計(jì)算結(jié)點(diǎn)上時(shí)，減少這些結(jié)點(diǎn)之間的通信量，是一個(gè)具有挑戰(zhàn)性的工作。
　　為了解決上述問(wèn)題，本文使用了一種新的分布式環(huán)境下圖數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，在原有NEU-BSP系統(tǒng)的基礎(chǔ)上，開(kāi)發(fā)了NEU-BSP+系統(tǒng)，提升了

3、整體計(jì)算性能。本文的主要貢獻(xiàn)如下：第一，對(duì)原系統(tǒng)進(jìn)行了一系列的基礎(chǔ)優(yōu)化:用并行的任務(wù)調(diào)度代替原系統(tǒng)中的串行執(zhí)行、改進(jìn)消息通信中的序列化方法等，使系統(tǒng)性能提升1倍，為進(jìn)一步工作提供了方便;第二，類(lèi)似PageRank和單源最短路徑的算法應(yīng)用在原系統(tǒng)中會(huì)產(chǎn)生大量重復(fù)的消息，針對(duì)這個(gè)問(wèn)題，本文提出了一種基于鄰接表垂直劃分的數(shù)據(jù)結(jié)構(gòu)，和在這種數(shù)據(jù)結(jié)構(gòu)之上的數(shù)據(jù)放置算法，并為用戶(hù)提供了新的計(jì)算模型:頂點(diǎn)-邊計(jì)算模型;第三，本文研究并實(shí)現(xiàn)了在頂點(diǎn)-邊

4、計(jì)算模型下PageRank算法和單元最短路徑算法的實(shí)現(xiàn)。
　　本文通過(guò)與原NEU-BSP系統(tǒng)對(duì)比實(shí)驗(yàn)評(píng)價(jià)了NEU-BSP+系統(tǒng)的各方面性能:在數(shù)據(jù)加載時(shí)間增長(zhǎng)不多的情況下，大大減少了任務(wù)間的通信量，使得應(yīng)用在迭代計(jì)算中的平均超步時(shí)間加快25％-30％。同時(shí)與現(xiàn)有的可處理圖的系統(tǒng)Hadoop、Giraph、Hama多組數(shù)據(jù)上進(jìn)行了整體性能對(duì)比，證明NEU-BSP+系統(tǒng)在各個(gè)系統(tǒng)中最快，其運(yùn)行速度是Hadoop系統(tǒng)的3-7倍，Gira