BC算法性能與圖數(shù)據(jù)格式的關(guān)系特性分析

蔣 林，馮 茹，鄧軍勇，李遠(yuǎn)成

(1.西安科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，陜西 西安 710600；2.西安郵電大學(xué) 電子工程學(xué)院，陜西 西安 710121)

圖因其宜于表征不同實體間復(fù)雜的依賴關(guān)系而受到廣泛應(yīng)用[1-3]。社交網(wǎng)絡(luò)分析[4]、推薦系統(tǒng)、交通網(wǎng)絡(luò)等都緊密依賴于高性能、高能效的圖計算系統(tǒng)[5-6]。然而，由于真實圖規(guī)模的不斷增加和圖結(jié)構(gòu)數(shù)據(jù)的復(fù)雜多變性，圖算法變得越來越重要[7]，使得其在遍歷、查找等圖計算過程中面臨巨大的挑戰(zhàn)。因此，學(xué)術(shù)界和工業(yè)界非常重視圖數(shù)據(jù)的分析和預(yù)處理[8-9]，其中設(shè)計數(shù)據(jù)的壓縮格式是常用的重要手段之一。但是，不同的壓縮格式對圖算法會產(chǎn)生不同的影響，針對特定的圖算法，如何根據(jù)其性能需求選擇合適的壓縮格式是一個待研究的問題。

目前，圖數(shù)據(jù)基本表示格式主要有邊陣列(Edge Array)和鄰接表(Adjacent List)兩種。以邊陣列的方式存儲，可以順序地讀取圖數(shù)據(jù)中邊的屬性，能有效提高其訪存效率。很多系統(tǒng)[10-13]都采用此表示格式來存儲數(shù)據(jù)。鄰接表存儲方式將源頂點和目標(biāo)頂點之間的有向邊編碼為非零項，可線性順序地訪問每一個頂點的所有邊信息，有效減少了隨機訪問，從而提高內(nèi)存訪問速度，目前鄰接表是大多數(shù)圖計算系統(tǒng)[14-16]存儲數(shù)據(jù)的選擇方式。然而，對于大規(guī)模圖進(jìn)行計算時，傳統(tǒng)的圖數(shù)據(jù)存儲格式限制了內(nèi)存訪問的速率。同時，因為真實圖數(shù)據(jù)的稀疏性和冪律性等特征，大多數(shù)的圖計算系統(tǒng)和加速器都會根據(jù)系統(tǒng)的特性以及存儲的特性，重新設(shè)計數(shù)據(jù)的存儲格式，以滿足圖計算系統(tǒng)的訪存、特性，提高內(nèi)存訪問效率。

設(shè)計的存儲格式表現(xiàn)多樣化，不同的壓縮格式需要能夠支持對邊的查詢、循環(huán)遍歷所有頂點的鄰接點以及遍歷所有的邊。常見的壓縮格式有壓縮稀疏列(Compressed Sparse Column，CSC)[17-18]、壓縮稀疏行(Compressed Sparse Row，CSR)[19]以及雙壓縮稀疏列(Doubly Compressed Sparse Column，DCSC)[18，20]等。它們共同的特點是以最小的開銷緊湊地存儲圖數(shù)據(jù)，空間效率高，且允許快速遍歷、查找[20]。但是，每種壓縮格式都有其獨特的優(yōu)點和缺點，在算法的執(zhí)行過程中，程序的性能不僅與輸入圖的大小以及算法的時間復(fù)雜度息息相關(guān)，更重要的是圖數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)對算法產(chǎn)生的影響[21-22]。此外，由于各種圖計算框架的引入導(dǎo)致許多應(yīng)用程序具有不同的實現(xiàn)，框架的數(shù)據(jù)預(yù)處理方式的不同，使單個圖算法的不同實現(xiàn)在可擴展性、計算操作、數(shù)據(jù)移動、能耗等方面可能會產(chǎn)生很大的差異。因此，研究人員了解圖應(yīng)用程序的各種實現(xiàn)特征非常重要。所以，針對不同的圖應(yīng)用程序選擇合適的預(yù)處理方式，使得圖應(yīng)用性能最優(yōu)是一個迫切需要解決的問題。筆者嘗試分析了圖應(yīng)用中心性(Betweenness Centrality，BC)算法的性能與圖數(shù)據(jù)格式之間的關(guān)系，選擇5種圖數(shù)據(jù)壓縮格式，分別為按坐標(biāo)表示(COOrdinate，COO)[23]、CSC、CSR、DCSC以及獨立稀疏列壓縮(Compressed Sparse Column Independently，CSCI)[24]。針對中心性算法，對不同輸入格式數(shù)據(jù)的性能指標(biāo)進(jìn)行特性分析。性能指標(biāo)參數(shù)包括數(shù)據(jù)移動量(Datamv)、計算量(Compute)、每周期指令數(shù)(IPC)、功耗(Energy)、各級cache缺失率(cache MPKI)等。通過性能事件統(tǒng)計結(jié)果，為遍歷類應(yīng)用中心性算法選擇不同壓縮格式的圖數(shù)據(jù)提供了依據(jù)。

1 算法及壓縮格式分析

1.1 中心性算法

中心性算法[25]是一種檢測節(jié)點對圖中信息或資源流的影響程度的算法。通過計算經(jīng)過該節(jié)點并連接這兩點的最短路徑和這兩點之間的最短路徑數(shù)目，其比值越大，中心性越高[26]。在現(xiàn)實圖網(wǎng)絡(luò)中可以解決各種問題，比如優(yōu)化通信網(wǎng)絡(luò)和計算機網(wǎng)絡(luò)的行為[27]、資源定位和分配[28-29]、發(fā)現(xiàn)電網(wǎng)等網(wǎng)絡(luò)中的關(guān)鍵轉(zhuǎn)移點[30]等。

中心性算法的基本思想為：圖G=(V，E)是由節(jié)點集合V和連接各個節(jié)點之間的邊E?V×V構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。為了方便計算，假設(shè)圖G是無向連接圖，權(quán)重值默認(rèn)為1。圖中節(jié)點v的中心性值CG[v]是圖G中任意兩個節(jié)點經(jīng)過節(jié)點v的最短路徑條數(shù)與圖G中任意兩個節(jié)點之間的最短路徑條數(shù)的比值：

(1)

其中，σst表示圖中節(jié)點s到節(jié)點t之間最短路徑的條數(shù)，σst(v)表示圖中從節(jié)點s到節(jié)點v之間經(jīng)過節(jié)點v的最短路徑條數(shù)?，F(xiàn)已知求圖中節(jié)點的中心性值的最快的算法是由文獻(xiàn)[25]提出的算法，計算未加權(quán)圖的時間復(fù)雜度是O(mn)，其中m表示邊數(shù)，n表示頂點數(shù)。對于在集合V中的任意3個節(jié)點s、t和v，定義pair dependencyδst(v)和source dependencyδs?(v)，分別表示如下：

(2)

(3)

根據(jù)上面的定義，式(1)可以寫為

(4)

BRANDS提出的source dependencyδs?(v)計算公式如下：

(5)

其中，σij是節(jié)點i到節(jié)點j的最短路徑條數(shù)，Ps(w)是從節(jié)點s廣度優(yōu)先搜索的無向圖中節(jié)點w的父節(jié)點組成的列表。BRANDES提出的算法主要分為兩個步驟：第1步執(zhí)行從節(jié)點s開始，使用廣度優(yōu)選擇遍歷(Breadth Fist Search，BFS)算法計算到節(jié)點t的最短路徑條數(shù)σst和Ps(w)，節(jié)點t∈V且s≠t；第2步執(zhí)行從葉子節(jié)點到根節(jié)點的反向BFS算法和利用式(5)計算δs?(v)。

算法1Betweenness Centrality(BC)。

輸入：GraphG(V，E)，頂點V和邊E，且E?V×V。

輸出：中介中心性值CB(v)。

① for everyv∈VdoBC(v)←0

② for everys∈Vdo

③ run Dijkstra SSSP(G是有向圖)fromsor run BFS(G是無向圖)

④ ?t∈V{s}.計算σst和Ps(t)

⑤ store vertices in StackSin non-increasing distance froms

⑥ for everyv∈Vdoδs?(v)←0

⑦ whileS≠0 do

⑧w←pop(S)

⑩ ifw≠sthenCB(w)←CB(w)+δs?(w)。

圖1 BC算法示例以及計算δ1?(v)的過程

1.2 圖數(shù)據(jù)壓縮格式分析

(1)COO壓縮格式按坐標(biāo)表示，是圖數(shù)據(jù)壓縮格式中最基本的壓縮方式。每一個元素需要用一個三元組來表示，包含行索引、列索引以及數(shù)值。COO壓縮格式中的三元組都可以直接定位，實現(xiàn)起來較為簡單，但是記錄的信息多，因此占用空間較大。COO格式的時間復(fù)雜度是O(V+E)，如圖2所示為圖的基本表示方法。

圖2 圖的基本表示方法

(2)CSR壓縮格式按行進(jìn)行壓縮，需要使用row offset(行偏移量)、column indices(列索引)和values(權(quán)值)3個數(shù)組存儲。row offset表示某一非零行的第1個元素在values里面的起始偏移位置(即該元素所在當(dāng)前行之前的非零元素個數(shù))，column indices表示非零元素的列索引，values表示列索引對應(yīng)的權(quán)值。CSR將數(shù)據(jù)進(jìn)行打包存儲，因此添加和刪除數(shù)據(jù)的時間與圖數(shù)據(jù)的大小呈線性關(guān)系，CSR格式的空間復(fù)雜度為O(V+E)。鄰接矩陣圖2(c)的CSR壓縮格式如圖3所示。

圖3 鄰接矩陣的CSR壓縮

(3)CSC壓縮格式按列進(jìn)行壓縮，與CSR類似，節(jié)省了內(nèi)存大小，簡化了圖構(gòu)建、復(fù)制以及傳輸?shù)膹?fù)雜性。需要3個數(shù)組表達(dá)：column offsets(列偏移量)、行索引(row indices)和權(quán)值(values)。column offsets表示某一非零列的第1個元素在values里面的起始偏移位置(即該元素所在當(dāng)前列之前的非零元素個數(shù))，row indices表示非零元素的行索引，values表示行索引對應(yīng)的權(quán)值。鄰接矩陣圖2(c)的CSC壓縮格式如圖4所示。

圖4 鄰接矩陣的CSC壓縮

(4)DCSC是一種雙重壓縮稀疏列的壓縮格式，是CSC的一種擴展格式。該壓縮格式可以有效存儲大規(guī)模稀疏矩陣。主要是使用column offsets、row indices、column indices以及values來存儲圖數(shù)據(jù)，其中，column indices是對column offsets二次壓縮，表示至少有一個非零元素的列索引，其他數(shù)據(jù)與CSC壓縮格式類似。鄰接矩陣圖2(c)的DCSC壓縮格式如圖5所示。

圖5 鄰接矩陣的DCSC壓縮

(5)CSCI是一種獨立稀疏列壓縮格式，每列圖數(shù)據(jù)包括列標(biāo)識數(shù)據(jù)對和非零元素數(shù)據(jù)對，需要使用ioc(標(biāo)識符)、column(row)indices以及values(權(quán)值)3個數(shù)組存儲。將圖數(shù)據(jù)獨立地壓縮成多個數(shù)據(jù)對(ioc，indices，values)，ioc為“1”，則indices指向column，values表示該列非零元素的個數(shù)；若ioc為“0”，則indices指向row，values表示該非零元素的值。鄰接矩陣圖2(c)的CSCI壓縮格式如圖6所示。

圖6 鄰接矩陣的CSCI壓縮

2 硬件環(huán)境建立與性能模型

2.1 硬件平臺搭建

本次實驗是在HPE580高性能服務(wù)器上進(jìn)行的，該服務(wù)器配備了Inter(R)Xeon(R)Platinum 8164 CPU。該服務(wù)器具有208個物理核416線程，每個核心都有一個32 kB的L1級數(shù)據(jù)cache，一個32 kB的L1級指令cache，1 024 kB 的L2級cache以及36 608 KB的L3級cache，內(nèi)存大小為1 TB，運行Linux內(nèi)核4.15.0系統(tǒng)。表1總結(jié)了測試平臺的具體信息。采用評測工具Perf[31]對影響計算性能能耗的性能事件基于真實圖進(jìn)行不同圖計算應(yīng)用下的參數(shù)統(tǒng)計。Perf是內(nèi)置于Linux內(nèi)核源碼樹中的性能剖析(profiling)工具。它基于事件采樣原理，以性能事件為基礎(chǔ)，對處理器相關(guān)性能指標(biāo)與操作系統(tǒng)相關(guān)性能指標(biāo)進(jìn)行性能剖析。性能指標(biāo)參數(shù)主要包括：數(shù)據(jù)移動量(datamv)、計算量(compute)、能耗(energy)和執(zhí)行時間(exec.time)等。

表1 實驗平臺信息性能參數(shù)

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

中心性算法在社交網(wǎng)絡(luò)結(jié)構(gòu)上有廣泛的應(yīng)用，可以捕獲網(wǎng)絡(luò)中單個節(jié)點的相對重要性。實驗數(shù)據(jù)選自斯坦福大學(xué)的SNAP(Stanford Network Analysis Project)數(shù)據(jù)集中Social networks的feather-deezer-social、Wiki-Vote和ca-AstroPh[32]以及網(wǎng)絡(luò)數(shù)據(jù)倉庫(The Network Data Repository with Interactive Graph Analytics and Visualization)數(shù)據(jù)集中Social networks的Soc-brightkite、Soc_gemsec_HU和Soc_gemsec_HR[33]，具體頂點個數(shù)、邊數(shù)以及內(nèi)存占用情況如表2所示。

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

2.3 性能指標(biāo)定義

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

(1)執(zhí)行時間。執(zhí)行時間(Exec.Time)直接決定了圖處理性能。任務(wù)的執(zhí)行時間即目標(biāo)任務(wù)真正占用處理器的時間。根據(jù)下式可計算不同壓縮格式中每條邊的執(zhí)行時間(單位為ms)：

E=Tt/Ne。

(6)

(2)IPC。IPC(Instruction Per Clock)是衡量處理器性能的一個基本指標(biāo)，表示平均每一時鐘周期所執(zhí)行的指令數(shù)。一般IPC越大越好，說明程序充分利用了處理器的特征。首先，通過運行算法代碼，計算運行所需要的機器級指令的數(shù)量；其次，使用高性能計時器計算在實際硬件上完成運行代碼所需要的時鐘周期數(shù)，即根據(jù)下式計算算法設(shè)計的IPC：

I=i/c，

(7)

其中，i表示執(zhí)行的指令數(shù)，c表示時令中數(shù)。

(3)數(shù)據(jù)移動量。數(shù)據(jù)移動量(datamv)受延遲和帶寬的限制，在高性能計算程序中往往屬于不可并行或者很難并行的部分。據(jù)觀察，移動數(shù)據(jù)的成本高于計算操作的成本。在大數(shù)據(jù)時代，很多應(yīng)用越來越受到數(shù)據(jù)移動成本的影響。在圖計算中，這個問題是一個突出的問題。為了顯示數(shù)據(jù)移動問題的強度，應(yīng)測量每個圖中的數(shù)據(jù)移動的數(shù)量。注意，這是移動操作的次數(shù)，而不是移動的數(shù)據(jù)量。數(shù)據(jù)移動量D表示記錄加載(load)和存儲指令(store)之和的計數(shù)與邊(edges)數(shù)量的商，即

D=(Nload+Nstore)/Nedges。

(8)

(4)功耗。在大圖分析中，功耗E(Energy)是一個必不可少的考慮因素，尤其是對于移動設(shè)備。由于能耗應(yīng)該隨著圖的大小而伸縮，用每條邊的功耗來代替功耗效率，如下所示：

E=Rpower_all/Nedges，

(9)

其中，Rpower_all表示執(zhí)行期間的功耗(單位為J)。

(5)MPKI。MPKI(Misses Per Kilo Instructions)是一個用來分析cache性能的通用指標(biāo)，表示每千條指令的平均未命中數(shù)。MPKI通常優(yōu)于cache Miss，因為MPKI還傳達(dá)了關(guān)于內(nèi)存訪問指令在整個指令流中的比例的信息?？筛鶕?jù)下式計算各級cache的M(MPKI)：

M=1 000m/i，

(10)

其中，m表示cache未命中數(shù)，i為指數(shù)。

(6)計算量。計算量性能指標(biāo)對于算法分析也極為重要。使用每條邊上的計算量表示不同壓縮格式處理數(shù)據(jù)集的計算量效率C：

C=(i-l-s-b)/Ne，

(11)

其中，i表示當(dāng)前執(zhí)行的指令總數(shù)，l表示加載指令數(shù)，s表示存儲指令數(shù)，b表示分支指令總數(shù)。

3 不同壓縮格式的內(nèi)存占用情況及特性分析

針對中心性算法，通過對6種不同的輸入圖數(shù)據(jù)集進(jìn)行5種壓縮格式的比較分析。本節(jié)從多個角度提供了比較結(jié)果與相應(yīng)分析。

3.1 不同壓縮格式內(nèi)存占用情況

6種輸入圖數(shù)據(jù)集經(jīng)過5種壓縮格式后的內(nèi)存占用情況如圖7所示。圖中顯示，將其他壓縮格式的數(shù)據(jù)歸一化到COO格式，且其余格式都對數(shù)據(jù)進(jìn)行不同程度的壓縮，其中DCSC對數(shù)據(jù)壓縮最明顯，CSCI的壓縮結(jié)果最不理想，CSC以及CSR的結(jié)果比較好且相差不大。稀疏矩陣通過壓縮數(shù)據(jù)的方式更新成本來節(jié)省這些空間存儲。CSC和CSR壓縮格式輸出結(jié)果主要包含行(列)偏移量、行(列)索引以及權(quán)值，所以，壓縮效果比較好且占用的內(nèi)存的大小較小。若稀疏矩陣的行數(shù)和列數(shù)接近或是對稱矩陣，壓縮格式的結(jié)果則會趨于相近，甚至相同。DCSC為雙壓縮稀疏列格式，在CSC的基礎(chǔ)上對列偏移量進(jìn)行壓縮，主要包含非零列的列偏移量、非零列的行(列)索引以及權(quán)值。因此，DCSC的壓縮效果最好，占用內(nèi)存最小，存儲效率最高。CSCI是獨立壓縮稀疏列，需要將非零元素在該列的個數(shù)以及索引全部輸出，占用內(nèi)存空間非常大，存儲效率最慢。

圖7 6種數(shù)據(jù)集5種壓縮格式下的內(nèi)存占用情況(歸一化到COO格式)

3.2 不同壓縮格式的特性分析

對不同壓縮格式處理中心性算法的性能特征進(jìn)行系統(tǒng)分析，通過雷達(dá)圖形式形象地展示了6種數(shù)據(jù)集的COO、CSR、CSC、DCSC以及CSCI 5種壓縮格式處理BC算法的性能，如圖8所示。

(a)feather-deezer-social

圖8(a)～(f)分別表示6種數(shù)據(jù)集feather-deezer-social、Soc-brightkite、Wiki-Vote、ca-AstroPh、Soc_gemsec_HU 以及 Soc_gemsec_HR下的性能雷達(dá)圖。雷達(dá)圖中性能指標(biāo)包括執(zhí)行時間(exec.Time)、IPC、數(shù)據(jù)移動量(data.move)、三級cache MPKI以及功耗(energy)。其中，每個度量指標(biāo)的最大值視為100%，其他數(shù)據(jù)以此作為標(biāo)準(zhǔn)。另外，采用Pearson相關(guān)系數(shù)分析方法，將參數(shù)實測結(jié)果與性能指標(biāo)進(jìn)行相關(guān)性分析，具體分析結(jié)果如下。

(1)執(zhí)行時間。圖9給出了6種數(shù)據(jù)集在不同的壓縮格式下每條邊的執(zhí)行時間。圖9顯示，COO和CSCI執(zhí)行邊的時間最長，且隨著數(shù)據(jù)集邊數(shù)的增大，CSCI的執(zhí)行時間也在呈正相關(guān)增長。DCSC壓縮格式次之，同時發(fā)現(xiàn)隨著數(shù)據(jù)的稀疏性越來越明顯，DCSC壓縮格式的執(zhí)行時間越來越短，這是因為DCSC在CSC的基礎(chǔ)上對列偏移量進(jìn)行壓縮，使得數(shù)據(jù)更加具有相關(guān)性。CSC和CSR壓縮格式的結(jié)果最接近，且執(zhí)行時間最短，原因在于，這兩種壓縮格式只記錄當(dāng)前活動頂點的偏移量、索引值和權(quán)值，占用內(nèi)存小且存儲速率高，可快速定位頂點信息。因此對于以遍歷為中心的算法，在考慮邊的執(zhí)行時間的情況下，優(yōu)先選擇CSR和CSC壓縮格式作為參考。

圖9 5種壓縮格式下每條邊的執(zhí)行時間

(2)數(shù)據(jù)移動量。6種數(shù)據(jù)集在不同的壓縮格式下每條邊的數(shù)據(jù)移動量如圖10所示。數(shù)據(jù)移動量主要是由于CPU與內(nèi)存交互這個過程影響的，若CPU減少Load和Store次數(shù)，則可有效提高運算效率。圖10顯示，數(shù)據(jù)移動量會隨著數(shù)據(jù)集的增大而增加。CSR壓縮格式相對于其他壓縮格式具有較好的邊的數(shù)據(jù)移動量，COO和CSCI壓縮格式的數(shù)據(jù)移動量最差，原因在于這兩種壓縮格式壓縮的效果不理想，導(dǎo)致存取數(shù)據(jù)操作復(fù)雜。DCSC相較于CSC和CSR次之。因此對于以遍歷為中心的算法，在考慮邊的數(shù)據(jù)移動量的情況下，應(yīng)選擇CSR或者壓縮格式。

圖10 5種壓縮格式下每條邊的數(shù)據(jù)移動量

(3)功耗。圖11給出了6種數(shù)據(jù)集在不同的壓縮格式下每條邊的功耗。可以看出，CSR和CSC壓縮格式的每條邊的功耗最小，原因在于這兩種壓縮格式記錄了每一個頂點的行(列)偏移量，可以快速地遍歷查詢當(dāng)下頂點的鄰接點，可以很大程度上降低能耗。COO和CSCI壓縮格式完整地記錄了從源頂點到鄰接點的信息，對于較大的稀疏矩陣，消耗能量較大。DCSC在圖數(shù)據(jù)的稀疏性比較明顯時，才能發(fā)揮特長。因此，對于以遍歷為中心的算法，在考慮邊的能耗的情況下，應(yīng)選擇CSR(CSC)壓縮格式，當(dāng)數(shù)據(jù)量足夠大時，應(yīng)考慮DCSC格式。

圖11 5種壓縮格式下每條邊的功耗

(4)cache MPKI。6種數(shù)據(jù)集在不同的壓縮格式下的L1、L2、L3級的cahe MPKI如圖12所示。圖12顯示，L1級的cache MPKI平均大于L2級的cache MPKI，L3級的cache MPKI更是微乎其微，主要考慮對L1級的cache MPKI的影響程度。影響各級cache缺失的因素主要與數(shù)據(jù)集的規(guī)模、程序訪問的局部性規(guī)律以及映射方式等相關(guān)。可以發(fā)現(xiàn)，CSC壓縮格式的cache缺失率最低，因此對于以遍歷為中心的算法，在考慮cache性能的情況下，應(yīng)選擇CSC壓縮格式。

圖12 5種壓縮格式下L1、L2、L3級的cache MPKI

(5)計算量。6種數(shù)據(jù)集在不同的壓縮格式下每條邊的計算量如圖13所示。CSR壓縮格式的計算量最小，COO和CSCI壓縮格式的計算量最高，原因在于程序需要全部遍歷當(dāng)前頂點的鄰接點，數(shù)據(jù)信息復(fù)雜，因此平均到每條邊的計算量便會增大。并且，隨著數(shù)據(jù)規(guī)模的增大，COO和CSCI處理數(shù)據(jù)的計算量將會是CSR的數(shù)倍。因此，在考慮數(shù)據(jù)計算量受限的情況下，優(yōu)先選擇CSR壓縮格式。

圖13 5種壓縮格式下每條邊的計算量

4 結(jié)束語

筆者針對以遍歷為中心的中心性算法，通過分析6種數(shù)據(jù)集下的5種壓縮格式(COO、CSR、CSC、DCSC、CSCI)的性能數(shù)據(jù)，根據(jù)其特征得出以下結(jié)論：對于BC算法，考慮到數(shù)據(jù)規(guī)模復(fù)雜影響內(nèi)存存儲效率，應(yīng)優(yōu)先選擇DCSC壓縮格式，可有效提高圖數(shù)據(jù)的訪存速度；在硬件環(huán)境有限的情況下，應(yīng)優(yōu)先選擇CSR壓縮格式，可有效減少程序執(zhí)行時間、數(shù)據(jù)移動量以及降低能耗；在有效提升cache的性能，降低cache缺失率的情況下，優(yōu)先選擇CSC壓縮格式；當(dāng)程序的計算量受限時，優(yōu)先選擇CSR壓縮格式；CSCI壓縮格式是結(jié)合線性代數(shù)中矩陣向量乘積可以看作矩陣列向量的線性組合提出的，在硬件加速器的數(shù)據(jù)并行性方面有一定的優(yōu)勢，但在通用處理器上的圖應(yīng)用方面并不理想；COO壓縮格式在提升圖計算應(yīng)用性能方面相對較差。綜上所述，針對以遍歷為中心的BC算法，研究者可以針對不同的應(yīng)用環(huán)境、不同的性能需求和軟硬件條件，基于上述結(jié)論進(jìn)行實際需求的調(diào)整，可有效提升圖計算系統(tǒng)的性能。同時，筆者預(yù)估在其他的遍歷類應(yīng)用，結(jié)果具有相似性，在后續(xù)的工作將逐步驗證。