CPU緩存友好的圖數(shù)據(jù)布局策略研究.pdf

1、對于大規(guī)模圖計(jì)算，內(nèi)存的隨機(jī)讀寫會顯著降低系統(tǒng)整體性能，因此，提高圖計(jì)算過程中內(nèi)存的讀寫性能具有重要意義。在當(dāng)前存儲分級的計(jì)算機(jī)體系結(jié)構(gòu)中，提高CPU緩存的使用效率將能極大提高內(nèi)存的讀寫性能，但是傳統(tǒng)的圖計(jì)算框架在內(nèi)存中組織數(shù)據(jù)時沒有針對CPU緩存進(jìn)行優(yōu)化。
　　為了解決上述問題，提出了針對不同場景的CPU緩存友好的圖數(shù)據(jù)布局策略，來提高圖計(jì)算過程的效率。結(jié)合CPU緩存讀寫數(shù)據(jù)的局部性特點(diǎn)與鄰接表結(jié)構(gòu)，使用sort布局來提高節(jié)點(diǎn)編

2、號的順序性，進(jìn)而提高CPU緩存的使用效率；結(jié)合圖算法的常用操作：遍歷查詢，使用經(jīng)典遍歷算法BFS（Breadth First Search）來提高圖數(shù)據(jù)邏輯上的順序性，進(jìn)而優(yōu)化圖算法的執(zhí)行效率，且對應(yīng)矮胖型BFS樹的圖數(shù)據(jù)，布局使整體順序性更好，對算法適用性更廣。綜合上述分析，設(shè)計(jì)并實(shí)現(xiàn)了圖數(shù)據(jù)預(yù)處理系統(tǒng)CookGraph，按照算法特性與圖類型特征匹配運(yùn)用布局策略。
　　通過在3種圖計(jì)算框架上分別對4種圖算法共6類圖數(shù)據(jù)集進(jìn)行測試

3、分析后可得，對內(nèi)存模式 SNAP（Stanford Network Analysis Platform）下的CC（Connected Components）算法，只有sort布局能優(yōu)化CPU緩存的使用效率，且測試了6類圖數(shù)據(jù)集，其中4類得到優(yōu)化，優(yōu)化比率最少為11％，最高為78.76%；對外存模式的GraphChi，BFS布局能提高對應(yīng)矮胖型BFS樹的圖數(shù)據(jù)執(zhí)行3種算法CC、TC（Triangle Counting）和 Pagerank