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

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

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

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

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

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

1 算法及壓縮格式分析

1.1 中心性算法

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

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

(1)

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

(2)

(3)

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

(4)

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

(5)

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

算法1Betweenness Centrality(BC)。

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

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

① for everyv∈VdoBC(v)←0

② for everys∈Vdo

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

④ ?t∈V{s}.計(jì)算σ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算法示例以及計(jì)算δ1?(v)的過(guò)程

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

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

圖2 圖的基本表示方法

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

圖3 鄰接矩陣的CSR壓縮

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

圖4 鄰接矩陣的CSC壓縮

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

圖5 鄰接矩陣的DCSC壓縮

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

圖6 鄰接矩陣的CSCI壓縮

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

2.1 硬件平臺(tái)搭建

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

表1 實(shí)驗(yàn)平臺(tái)信息性能參數(shù)

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

中心性算法在社交網(wǎng)絡(luò)結(jié)構(gòu)上有廣泛的應(yīng)用，可以捕獲網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)的相對(duì)重要性。實(shí)驗(yàn)數(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ù)倉(cāng)庫(kù)(The Network Data Repository with Interactive Graph Analytics and Visualization)數(shù)據(jù)集中Social networks的Soc-brightkite、Soc_gemsec_HU和Soc_gemsec_HR[33]，具體頂點(diǎn)個(gè)數(shù)、邊數(shù)以及內(nèi)存占用情況如表2所示。

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

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

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

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

E=Tt/Ne。

(6)

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

I=i/c，

(7)

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

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

D=(Nload+Nstore)/Nedges。

(8)

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

E=Rpower_all/Nedges，

(9)

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

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

M=1 000m/i，

(10)

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

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

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

(11)

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

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

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

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

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

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

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

對(duì)不同壓縮格式處理中心性算法的性能特征進(jìn)行系統(tǒng)分析，通過(guò)雷達(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í)行時(shí)間(exec.Time)、IPC、數(shù)據(jù)移動(dòng)量(data.move)、三級(jí)cache MPKI以及功耗(energy)。其中，每個(gè)度量指標(biāo)的最大值視為100%，其他數(shù)據(jù)以此作為標(biāo)準(zhǔn)。另外，采用Pearson相關(guān)系數(shù)分析方法，將參數(shù)實(shí)測(cè)結(jié)果與性能指標(biāo)進(jìn)行相關(guān)性分析，具體分析結(jié)果如下。

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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