鄧軍勇，趙一迪

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

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

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

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

1 圖框架及算法介紹

1.1 典型圖計(jì)算框架

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

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

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

1.2 基本遍歷類算法

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

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

(1)

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

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

(2)

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

2 實(shí)驗(yàn)環(huán)境建立與性能指標(biāo)

2.1 硬件平臺(tái)

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

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

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

性能分析數(shù)據(jù)集選自斯坦福大學(xué)的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ù)集頂點(diǎn)個(gè)數(shù)、邊數(shù)如表2所示。本文將對(duì)這些真實(shí)世界圖數(shù)據(jù)進(jìn)行處理。

表2 實(shí)驗(yàn)所選的數(shù)據(jù)集

2.3 性能評(píng)測(cè)工具

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

2.4 性能指標(biāo)

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

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

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

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

(3)

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

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

(4)

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

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

(5)

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

6)計(jì)算量。計(jì)算量是分析圖計(jì)算加速器性能的重要指標(biāo)，通過分析每條邊計(jì)算量來(lái)表示完成圖計(jì)算所需的計(jì)算量。定義計(jì)算量

(6)

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

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

3 特性化結(jié)果與分析

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

3.1 特性化分析概述

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

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

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

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

雷達(dá)圖顯示了每個(gè)性能指標(biāo)的相對(duì)數(shù)據(jù)，下面詳細(xì)給出各指標(biāo)的具體測(cè)量數(shù)據(jù)。

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

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

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

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

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

3)功耗。3種框架實(shí)現(xiàn)SSSP算法和BC算法處理4種數(shù)據(jù)集的每邊功耗如表4所示?？梢钥闯?，GraphBIG框架下實(shí)現(xiàn)算法的功耗較大，這是因?yàn)楦鬟厛?zhí)行的功耗與數(shù)據(jù)移動(dòng)量成正比，數(shù)據(jù)移動(dòng)的次數(shù)越多其功耗就越大，由于GraphBIG框架的數(shù)據(jù)移動(dòng)量遠(yuǎn)大于Ligra框架和Gemini框架，從而導(dǎo)致GraphBIG框架的功耗相對(duì)較高，由于Ligra框架數(shù)據(jù)移動(dòng)量較小，因此功耗較小。

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

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

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

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

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

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

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

6)PCC。不同指標(biāo)性能和能量的PCC相關(guān)性如表9所示。

表9 不同指標(biāo)性能和能量的PCC相關(guān)性

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

4 結(jié)語(yǔ)

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

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

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

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

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

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