鄧軍勇，趙一迪

(西安郵電大學 電子工程學院，陜西 西安 710121)

大數(shù)據(jù)背景下，真實世界圖數(shù)據(jù)的規(guī)模爆炸式增長，處理圖數(shù)據(jù)的圖計算被認為是新興數(shù)據(jù)驅(qū)動市場的支撐技術[1-3]。與此同時，隨著社交網(wǎng)絡分析、生物信息網(wǎng)絡分析、傳染病防治和自然語言處理等應用領域的發(fā)展，不同領域圖計算應用的實際需求以及大量圖數(shù)據(jù)的獨特特征都對傳統(tǒng)計算架構提出了挑戰(zhàn)，高性能圖計算加速器研發(fā)備受關注[4-7]。

為了高效實現(xiàn)圖計算任務，研究人員開始設計并實現(xiàn)各種框架來促進應用的程序開發(fā)，并通過硬件設計提高圖計算加速器的性能[8-10]。圖框架Ligra[11]可以根據(jù)圖的疏密情況自適應地切換其計算方法，但是其適用于單機計算，計算能力和內(nèi)存空間有限。圖框架Gemini[12]是以計算為中心的圖框架體系，對整體集群圖數(shù)據(jù)處理性能比較顯著。圖框架GraphBIG[13]利用動態(tài)的以頂點為中心的數(shù)據(jù)表示形式，基于當前主流圖框架并涵蓋了所有主要圖計算類型和數(shù)據(jù)源。這些主流的圖框架從不同角度對算法的實現(xiàn)進行了優(yōu)化。遍歷類應用作為圖計算中常見的算法應用非常廣泛，是圖數(shù)據(jù)路徑/流分析、網(wǎng)絡理論以及網(wǎng)絡通信重要性等許多實際問題的處理基礎[14-15]。目前，沒有適用的準則判斷遍歷類算法處理、圖框架的設計和性能之間的關聯(lián)關系，研究并獲得相關特定算法在各種不同實現(xiàn)方式下的性能的詳細信息和數(shù)據(jù)至關重要[16]。

擬通過對當前主流的圖計算框架Ligra、Gemini和GraphBIG中遍歷類應用的單源最短路徑算法(Single Source Shortest Path,SSSP)算法和介數(shù)中心性(Betweenness Centrality,BC)算法的實現(xiàn)進行特性分析，分析各個圖框架在處理不同數(shù)據(jù)集時的每一時鐘周期內(nèi)執(zhí)行的指令數(shù)(Instruction Per Clock,IPC)、數(shù)據(jù)移動量(datamovement)、計算量(compute)功耗(energy)和各級cache每千條指令的平均未命中數(shù)(Misses Per Kilo Instructions,MPKI)等性能指標，并通過Pearson相關系數(shù)分析性能/能耗與各個評估指標之間的關系，據(jù)此對圖計算框架及算法選擇提出建議。

1 圖框架及算法介紹

1.1 典型圖計算框架

1)Ligra框架。Ligra框架是一種經(jīng)典的單機內(nèi)存圖計算系統(tǒng)，其根據(jù)圖的疏密情況自適應地切換其計算模式的方法，并提供了一種基于邊映射、頂點映射以及頂點集映射的并行編程算法，可以通過調(diào)用兩個原語分別對所有活動頂點和所有活動頂點的出邊進行處理，使圖遍歷算法易于編寫。Ligra框架的圖計算單機運行，可以直接將圖數(shù)據(jù)完全加載到內(nèi)存中進行圖計算操作。但是，由于單機的計算能力和內(nèi)存空間有限，所以該框架只能計算和處理一些規(guī)模較小的圖數(shù)據(jù)。

2)Gemini框架。Gemini框架是一種以計算為中心的圖框架體系，其在單機內(nèi)存圖計算系統(tǒng)的高效性和分布式內(nèi)存圖計算系統(tǒng)良好的伸縮性之間找到一種平衡[6]。Gemini框架針對圖框架的稀疏或稠密情況，采用與Ligra圖框架一致的自適應推/拉處理方式，在內(nèi)存中采用基于Chunk的圖劃分操作，進行更細粒度的負載均衡調(diào)節(jié)。Gemini框架對整體集群的圖數(shù)據(jù)處理性能的改善較為顯著。

3)GraphBIG框架。GraphBIG框架是一組CPU/GPU基準測試，其利用動態(tài)的以頂點為中心的數(shù)據(jù)表示形式，采用當前主流圖框架并涵蓋所有主要圖計算類型和數(shù)據(jù)源，以確保數(shù)據(jù)表示和圖計算負載的代表性，改善之前基準測試工作的不足，并實現(xiàn)通用的基準測試解決方案。

1.2 基本遍歷類算法

1)SSSP算法。SSSP算法是一種計算從源頂點到所有其余頂點的路徑上邊權值之和的最小值的算法[17-18]，廣泛應用于網(wǎng)絡理論、地圖路徑查詢和線路安排等實際生產(chǎn)和生活中[19]。SSSP算法使用松弛算子函數(shù)尋找最短路徑，直到找不到更短的路徑為止。松弛算子函數(shù)的表示式為

D(v)=min[D(v),D(u)+w(u,v)]

(1)

其中：u表示源頂點；v表示頂點u的鄰居頂點；w(u,v)表示頂點u到頂點v的邊緣的權重。

2)BC算法。BC算法中的介數(shù)中心性指的是一個頂點擔任其他兩個頂點之間最短路徑的橋梁的次數(shù)[20-21]，一個頂點充當“中介”的次數(shù)越高，該頂點的中介中心度就越大[21]。BC算法能夠揭示網(wǎng)絡結構中具有橋連接作用的頂點，從而控制整個網(wǎng)絡結構的連接以及通信能力，找到網(wǎng)絡傳播過程中的最關鍵點或者最脆弱點。BC算法在網(wǎng)絡研究以及傳染病防治等領域得到廣泛應用。BC算法計算網(wǎng)絡中任意兩個頂點的所有最短路徑，如果這些最短路徑中有多條都經(jīng)過了某個頂點，那么這個頂點介數(shù)中心性較高，頂點x的BC值計算表達式為

(2)

其中：σst表示頂點s和t之間的所有最短路徑數(shù)；σst(x)表示經(jīng)過頂點x的最短路徑數(shù)。

2 實驗環(huán)境建立與性能指標

2.1 硬件平臺

性能分析在基于Skylake架構的4核8線程Intel(R) Core(TM) i5-8250U CPU上運行，其中，CPU具有6 MB的3級緩存，以1.6 GHz的時鐘頻率運行，平臺具有8 GB內(nèi)存和1 TB外存，運行系統(tǒng)為4.15.0的linux內(nèi)核，Ligra、Gemini和GraphBIG等3種圖計算框架的編譯配置如表1所示。

表1 3種圖框架的編譯配置

2.2 數(shù)據(jù)集選取

性能分析數(shù)據(jù)集選自斯坦福大學的Stanford Network Analysis Project (SNAP)中Internet peer to peer networks的p2p-Gnutella31(p2p)、Networks with ground-truth communities的com-DBLP(com)、Signed networks的 soc-Epinions1(soc)以及Road networks的 roadNet-PA(PA) 4種數(shù)據(jù)集，4種數(shù)據(jù)集頂點個數(shù)、邊數(shù)如表2所示。本文將對這些真實世界圖數(shù)據(jù)進行處理。

表2 實驗所選的數(shù)據(jù)集

2.3 性能評測工具

為了對處理器和操作系統(tǒng)相關性能指標進行性能分析，采用內(nèi)置于Linux內(nèi)核源碼樹中，基于事件采樣原理，以性能事件為基礎的perf[22]作為分析工具。采用perf 4.15.18版本，通過分析器收集性能指標數(shù)據(jù)來計算不同圖框架處理SSSP算法及BC算法時的IPC、數(shù)據(jù)移動量、功耗、計算量、L1、L2以及L3數(shù)據(jù)緩存MPKI。

2.4 性能指標

根據(jù)統(tǒng)計的硬件性能事件，分析的性能包括IPC、數(shù)據(jù)移動量、功耗、計算量、L1、L2以及L3數(shù)據(jù)緩存MPKI等。由于輸入圖數(shù)據(jù)規(guī)模差別較大，將性能指標統(tǒng)一到每一條邊的處理上。

1)執(zhí)行時間。任務的執(zhí)行時間是指目標任務真正占用處理器的時間，可直接顯示圖計算的性能。使用C++系統(tǒng)庫記錄任務的執(zhí)行時間。

2)IPC。IPC表示平均每一時鐘周期所執(zhí)行的指令數(shù)，能夠直觀的表示指令級的并行性。IPC越大，說明程序充分利用了處理器的特征。

3)數(shù)據(jù)移動量。數(shù)據(jù)移動量衡量移動操作的次數(shù)而不是移動操作的數(shù)據(jù)量。實際測量中，記錄不同圖框架在SSSP算法及BC算法實現(xiàn)過程中每條邊的數(shù)據(jù)移動量。其定義為

(3)

式中：Nload和Nstore分別為加載和存儲指令總數(shù)，用來表示數(shù)據(jù)移動；Nedges表示邊的總數(shù)。

4)功耗。功耗是衡量圖計算加速器性能的重要指標。功耗與所分析圖的大小成比例。使用每條邊的能量消耗來表示功耗，將功耗定義為

(4)

式中，Rpower_all表示消耗的總能量。

5)MPKI。MPKI指每千條指令的平均未命中數(shù)，即緩存cache缺失率。各級cache的MPKI為

(5)

式中：Cm表示緩存缺失數(shù)；Iinstructions表示指令數(shù)。

6)計算量。計算量是分析圖計算加速器性能的重要指標，通過分析每條邊計算量來表示完成圖計算所需的計算量。定義計算量

(6)

式中：Dload表示加載指令數(shù)；Dstore表示存儲指令數(shù)；Dbranch表示分支指令數(shù)。

7)皮爾遜相關系數(shù)。為了分析各指標參數(shù)對性能及能耗的影響，采用皮爾遜相關系數(shù)(Pearson Correlation Coefficient,PCC)方法計算參數(shù)實測結果與性能/能耗指標之間的影響系數(shù)，其參數(shù)范圍介于+1和-1之間，正值表示正相關，負值表示負相關，0表示不相關。

3 特性化結果與分析

通過對4種數(shù)據(jù)集采用不同的圖框架進行處理，根據(jù)其處理結果以及性能參數(shù)進行分析比較。

3.1 特性化分析概述

在3種圖框架中實現(xiàn)SSSP和BC算法處理4種數(shù)據(jù)集的性能指標如圖1所示。圖1以雷達圖的形式顯示了分別在Ligra、GraphBIG和Gemini等3種圖框架下實現(xiàn)的SSSP和BC算法處理4種不同數(shù)據(jù)集的性能指標值。雷達圖以對數(shù)刻度表示的歸一化值按順時針方向從頂部開始顯示每條邊的執(zhí)行時間(exec.time)、IPC、數(shù)據(jù)移動量(MV)、L1、L2和L3三級數(shù)據(jù)緩存的MPKI(L1_MPKI、L2_MPKI和L3_MPKI)、計算量(compute)以及每單位的功耗(energy)等8個指標值。其中，每個度量標準的最大值視為100%，其他數(shù)據(jù)以最大值作為標準進行歸一化處理。

圖1 3種框架實現(xiàn)SSSP算法和BC算法的性能指標

由圖1可以看出，當圖框架在進行算法處理時，若高速緩存MPKI越大且IPC越小，則會增加其邊的執(zhí)行時間；若數(shù)據(jù)移動量較小，則會在減少其執(zhí)行時間的同時減少功耗。這是由于MPKI越大則緩存缺失率越高，IPC越小則每時鐘周期內(nèi)處理的指令數(shù)越少，從而導致執(zhí)行時間越長。在SSSP算法和BC算法的3種實現(xiàn)框架中，Ligra框架表現(xiàn)出的性能最佳，具有較低的執(zhí)行時間和數(shù)據(jù)移動量，這是由于Ligra框架的單機內(nèi)存系統(tǒng)把圖數(shù)據(jù)直接加載到內(nèi)存中進行計算，在處理過程中沒有外部輸入/輸出延時，從而減少了數(shù)據(jù)的讀取時間；而在BC算法的3種實現(xiàn)框架中，GraphBIG框架的功耗最大，是Ligra框架的6.07倍，這是由于GraphBIG框架的數(shù)據(jù)移動量為Ligra框架的數(shù)據(jù)移動量的近100倍。Gemini框架采用了塊式劃分的策略，能夠進行更細粒度的負載均衡調(diào)節(jié)，相比于其他圖框架，Gemini框架的執(zhí)行時間較短，這種方式讓每臺機器負責一段連續(xù)區(qū)間的頂點，從而盡可能減少分布式的相關開銷，從而在每條邊的計算方面也節(jié)省了大量資源。同時，圖計算加速器可以從減少數(shù)據(jù)移動次數(shù)的硬件技術(例如存內(nèi)計算)中受益。

3.2 具體測量數(shù)據(jù)

雷達圖顯示了每個性能指標的相對數(shù)據(jù)，下面詳細給出各指標的具體測量數(shù)據(jù)。

1)執(zhí)行時間。執(zhí)行時間的大小與圖計算加速器的性能好壞直接相關。為了更好地表示可擴展性，分別對3種圖框架進行多線程處理。

3種框架實現(xiàn)算法處理p2p-Gnutella31數(shù)據(jù)集的各邊執(zhí)行時間如圖2所示?？梢钥闯?，隨著線程數(shù)的增加，SSSP算法和BC算法各邊的執(zhí)行時間均呈下降趨勢，這是由于多線程執(zhí)行任務時，系統(tǒng)對可以同時執(zhí)行的部分進行并行處理的原因。在硬件設計中，可通過增加處理單元使算法并行執(zhí)行的方法減少執(zhí)行時間，從而提高加速器性能。

另外，從圖2中還可以看出，GraphBIG框架由于IPC較低導致執(zhí)行時間偏高。當線程數(shù)小于4時，Gemini框架的執(zhí)行時間小于Ligra框架的執(zhí)行時間；當并行處理線程數(shù)大于4時，隨著線程數(shù)的增加，Ligra框架的執(zhí)行時間下降較快，且逐漸優(yōu)于Gemini框架。當硬件條件受限制時，應該優(yōu)先考慮在Gemini框架中實現(xiàn)算法。

圖2 3種框架實現(xiàn)算法處理p2p-Gnutella31

2)數(shù)據(jù)移動量。數(shù)據(jù)移動量受延遲和帶寬的限制，在高性能計算程序中很難實現(xiàn)并行處理。分別對在3種框架實現(xiàn)SSSP算法和BC算法每條邊的數(shù)據(jù)移動量進行測量，其結果如表3所示?？梢钥闯?，Ligra框架下實現(xiàn)算法的邊數(shù)據(jù)移動量較少，然而GraphBIG框架的相對偏大甚至達到Ligra框架的數(shù)十倍，這是由于Ligra框架是基于單機內(nèi)存的圖計算系統(tǒng)，其在運行時可以直接將圖數(shù)據(jù)完全加載到內(nèi)存中進行計算，從而減少了訪存計算比。然而真實圖數(shù)據(jù)符合冪律分布，GraphBIG框架遵循以頂點為中心的數(shù)據(jù)表示方式，在進行數(shù)據(jù)處理時的局部性較差。因此，對于規(guī)模較小的圖數(shù)據(jù)，可以將其全部存儲到內(nèi)存以減少數(shù)據(jù)移動量，以減少帶寬浪費。

3)功耗。3種框架實現(xiàn)SSSP算法和BC算法處理4種數(shù)據(jù)集的每邊功耗如表4所示。可以看出，GraphBIG框架下實現(xiàn)算法的功耗較大，這是因為各邊執(zhí)行的功耗與數(shù)據(jù)移動量成正比，數(shù)據(jù)移動的次數(shù)越多其功耗就越大，由于GraphBIG框架的數(shù)據(jù)移動量遠大于Ligra框架和Gemini框架，從而導致GraphBIG框架的功耗相對較高，由于Ligra框架數(shù)據(jù)移動量較小，因此功耗較小。

表3 3種框架實現(xiàn)SSSP算法和BC算法每條邊的數(shù)據(jù)移動量

表4 3種框架實現(xiàn)SSSP算法和BC算法的每邊功耗

4)MPKI。3種框架實現(xiàn)SSSP算法和BC算法的每邊L1、L2和L3級cache 的MPKI如表5、表6和表7所示?？梢钥闯?，由于緩存技術的進步，使得所有圖應用程序的緩存性能都較好。另外，除了GraphBIG框架外，Ligra框架和Gemini框架的L1級cache的MPKI都小于11，L2級cache的MPKI和L3級cache的MPKI均遠小于L1級cache的MPKI，因此，在分析各級緩存缺失與命中率時，應該將注意力集中在不同圖框架算法實現(xiàn)的L1級cache MPKI上。

表5 3種框架實現(xiàn)SSSP算法和BC算法的每邊L1級cache 的MPKI

表7 3種框架實現(xiàn)SSSP算法和BC算法的每邊L3級cache 的MPKI

5)計算量。3種框架實現(xiàn)SSSP算法和BC算法的每邊計算量如表8所示?？梢钥闯觯谔幚磔^密集的圖數(shù)據(jù)集p2p和PA時，Gemini框架每邊的計算量明顯小于基于單機式圖計算加速器Ligra框架每邊的計算量，而處理較稀疏的圖數(shù)據(jù)集com和soc時，單機式圖計算加速器的平均計算量是Gemini框架的25%。這是由于Gemini框架采用圖劃分操作進行更細粒度的負載均衡調(diào)節(jié)，在圖數(shù)據(jù)相對密集時通過圖劃分操作減少其計算量，同時也降低了內(nèi)存訪問延遲。因此，當處理稀疏數(shù)據(jù)時，選擇Ligra框架實現(xiàn)算法實現(xiàn)能夠有效地減少計算量，提高處理性能。

表8 3種框架實現(xiàn)SSSP算法和BC算法的每邊計算量

6)PCC。不同指標性能和能量的PCC相關性如表9所示。

表9 不同指標性能和能量的PCC相關性

可以看出，每邊的數(shù)據(jù)移動量和功耗之間的相關度高達0.97，表現(xiàn)出二者直接具有很強的相關性；另外，計算量和功耗在某種程度上與性能/能耗相關，相關度大于0.8。因此，在對圖框架及圖計算加速器進行優(yōu)化時，應重點從數(shù)據(jù)移動量和功耗著手，減少數(shù)據(jù)的移動次數(shù)以提高圖計算效率。

4 結語

通過對當前主流的圖計算框架Ligra、Gemini和GraphBIG中SSSP及BC算法的不同實現(xiàn)進行特性化分析，得到如下4個結論。

1)在算法處理過程中，如果緩存MPKI較大且IPC較小會增加其執(zhí)行時間，若數(shù)據(jù)移動量較小則會在減少其執(zhí)行時間的同時減少功耗。

2)隨著系統(tǒng)處理任務的線程數(shù)增加，圖數(shù)據(jù)邊的執(zhí)行時間明顯減少，可以通過增加處理單元個數(shù)的方式提高硬件加速器的性能。另外，當硬件環(huán)境受限時，如處理器內(nèi)核數(shù)小于4，則優(yōu)先選擇框架Gemini實現(xiàn)算法；而當內(nèi)核數(shù)大于4時，選擇圖框架Ligra能夠有效減少執(zhí)行時間。

3)數(shù)據(jù)移動量和功耗與性能/能耗表現(xiàn)出極強的相關性，將圖數(shù)據(jù)全部加載到內(nèi)存中進行計算可有效減少數(shù)據(jù)移動的次數(shù)，但其計算能力有限。除此之外，可以通過建立計算容量可伸縮的處理單元或者對圖數(shù)據(jù)進行劃分的方法緩解冪律分布所導致的“水桶效應”。

4)在處理較稀疏的圖數(shù)據(jù)時，單機內(nèi)存系統(tǒng)具有較低的計算量，選擇Ligra框架能夠減少計算量。

當對硬件設計進行優(yōu)化時，一方面，可以通過增加容量可伸縮的計算處理單元，對算法能夠同時執(zhí)行的部分進行并行處理；另一方面，可以對圖數(shù)據(jù)進行圖劃分操作，從而減少功耗。對于較小的圖數(shù)據(jù)，可以直接將其存儲到內(nèi)存中處理以減少數(shù)據(jù)移動的次數(shù)；對于較大的圖數(shù)據(jù)，則可以借助外部存儲器對數(shù)據(jù)進行存儲，從而更高效地進行圖計算處理。當執(zhí)行時間為優(yōu)先考慮因素時，若硬件環(huán)境受限制，處理器內(nèi)核數(shù)小于4時，選擇Gemini框架實現(xiàn)算法；當并行處理內(nèi)核數(shù)大于4時，可以選擇Ligra框架實現(xiàn)算法。當以數(shù)據(jù)移動量或計算量為優(yōu)先參考考慮因素時，應選擇基于單機內(nèi)存系統(tǒng)的Ligra框架實現(xiàn)算法。