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

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

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

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