基于磁盤的單機(jī)大規(guī)模圖計(jì)算引擎性能的改進(jìn)方法.pdf

1、本文研究圖計(jì)算引擎性能問題?，F(xiàn)實(shí)世界的許多對(duì)象都能夠被轉(zhuǎn)化成圖格式，并且運(yùn)用各種圖處理工具進(jìn)行高效處理。GraphChi是最先提出能夠在單機(jī)上高效處理十億規(guī)模節(jié)點(diǎn)的基于磁盤的圖計(jì)算引擎，在性能上能夠接近甚至超越那些主流的分布式圖計(jì)算引擎。
　　本文針對(duì)圖計(jì)算引擎其中的兩個(gè)方面進(jìn)行了改進(jìn)，主要包括兩部分：1）圖計(jì)算引擎的內(nèi)存管理制度以及2）圖計(jì)算引擎的算法。
　　在圖計(jì)算引擎的內(nèi)存管理制度的問題上，本文受到TurboGraph

2、的“pin”的概念以及GraphLab中“ghost”的概念的啟發(fā)，提出了一種新的內(nèi)存管理制度來提高GraphChi引擎的性能。這種模式的主要思想是在整個(gè)計(jì)算過程中將一部分?jǐn)?shù)據(jù)固定在內(nèi)存里。此改進(jìn)在原始的GraphChi引擎上僅增添了40行左右的代碼，卻收獲了最高達(dá)60％性能的提高。分別運(yùn)用不同大小的內(nèi)存、點(diǎn)數(shù)據(jù)集、邊數(shù)據(jù)集以及放入內(nèi)存數(shù)據(jù)比例進(jìn)行了相應(yīng)的實(shí)驗(yàn)，證明了這種優(yōu)化模式的通用性及有效性；并且在實(shí)驗(yàn)過程中我們發(fā)現(xiàn)在整個(gè)數(shù)據(jù)集無法

3、完全放入內(nèi)存的情況下，存在一個(gè)最優(yōu)的固定到內(nèi)存的數(shù)據(jù)比例，此時(shí)能夠獲得最優(yōu)的性能。
　　在針對(duì)圖計(jì)算引擎處理的算法進(jìn)行優(yōu)化上，受到著名的六度空間理論的啟發(fā)：當(dāng)某些節(jié)點(diǎn)迭代過程中值的變化滿足一定條件時(shí)，可以停止對(duì)這部分相對(duì)次要的節(jié)點(diǎn)進(jìn)行計(jì)算，這并不會(huì)對(duì)那部分重要節(jié)點(diǎn)造成影響。在大數(shù)據(jù)集上進(jìn)行了相關(guān)實(shí)驗(yàn)，驗(yàn)證了本文提出的優(yōu)化算法的有效性（最高24%性能的提高）以及準(zhǔn)確性；同時(shí)通過對(duì)節(jié)點(diǎn)收斂值以及過濾不同比例的次要節(jié)點(diǎn)進(jìn)行了研究，揭示了