圖計算中遍歷類圖框架的特性

鄧軍勇，趙一迪

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

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

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

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

1 圖框架及算法介紹

1.1 典型圖計算框架

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

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

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

1.2 基本遍歷類算法

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

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

(1)

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

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

(2)

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

2 實驗環境建立與性能指標

2.1 硬件平臺

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

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

2.2 數據集選取

性能分析數據集選自斯坦福大學的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種數據集，4種數據集頂點個數、邊數如表2所示。本文將對這些真實世界圖數據進行處理。

表2 實驗所選的數據集

2.3 性能評測工具

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

2.4 性能指標

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

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

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

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

(3)

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

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

(4)

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

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

(5)

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

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

(6)

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

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

3 特性化結果與分析

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

3.1 特性化分析概述

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

圖1 3種框架實現SSSP算法和BC算法的性能指標

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

3.2 具體測量數據

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

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

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

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

圖2 3種框架實現算法處理p2p-Gnutella31

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

3)功耗。3種框架實現SSSP算法和BC算法處理4種數據集的每邊功耗如表4所示?？梢钥闯觯珿raphBIG框架下實現算法的功耗較大，這是因為各邊執行的功耗與數據移動量成正比，數據移動的次數越多其功耗就越大，由于GraphBIG框架的數據移動量遠大于Ligra框架和Gemini框架，從而導致GraphBIG框架的功耗相對較高，由于Ligra框架數據移動量較小，因此功耗較小。

表3 3種框架實現SSSP算法和BC算法每條邊的數據移動量

表4 3種框架實現SSSP算法和BC算法的每邊功耗

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

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

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

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

表8 3種框架實現SSSP算法和BC算法的每邊計算量

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

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

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

4 結語

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

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

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

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

4)在處理較稀疏的圖數據時，單機內存系統具有較低的計算量，選擇Ligra框架能夠減少計算量。

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