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

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

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

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