圖計算中壓縮格式對單源最短路徑算法影響的特性化分析

鄧軍勇 趙一迪

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

0 引 言

在大數(shù)據(jù)背景下，物理世界中圖數(shù)據(jù)的規(guī)模呈爆炸式增長[1]，社交網(wǎng)絡(luò)分析、網(wǎng)頁搜索、推薦系統(tǒng)、生物信息學(xué)和網(wǎng)絡(luò)安全等大量實際應(yīng)用都緊密依賴于圖計算系統(tǒng)[2,4]。當前，面向不同圖算法的圖計算加速器正蓬勃發(fā)展發(fā)展，為了使大規(guī)模圖數(shù)據(jù)得到更高效的處理，高性能圖計算加速器受到了廣泛關(guān)注。

真實圖數(shù)據(jù)的稀疏性以及分布冪律性導(dǎo)致圖計算負載失衡[5]，選擇合適的圖數(shù)據(jù)表示方式有助于提升圖計算性能[6]。圖數(shù)據(jù)格式主要分為Edge Array(邊陣列)和Adjacent List(鄰接表)兩種。以Edge Array的方式存儲，可以順序地讀取圖數(shù)據(jù)中邊的屬性，能有效提高其訪存效率[7,9]；以Adjacent List方式存儲可有效減少隨機訪問從而提高內(nèi)存訪問速度[10,13]。目前，圖計算加速器的設(shè)計只考慮了從硬件角度對圖數(shù)據(jù)的優(yōu)化處理，無法根據(jù)具體應(yīng)用需求來選擇最適合的壓縮格式，從而無法發(fā)揮圖計算加速器的最優(yōu)性能。因此，根據(jù)不同的環(huán)境及圖算法需求選擇相應(yīng)的數(shù)據(jù)格式使圖計算加速器性能最優(yōu)化顯得尤為重要。但是在不同的環(huán)境要求下，目前沒有適用的標準來決定哪種壓縮格式的圖數(shù)據(jù)在什么時候更適合于哪個算法。因此，對于圖計算加速器的設(shè)計，建立一個性能評價模型來提供相關(guān)的性能數(shù)據(jù)，決定在不同條件應(yīng)選擇的圖數(shù)據(jù)格式成為一種必然趨勢。

本文通過對圖計算中COO[14]、CSC[15]、CSR[16]、DCSC[17]和CSCI[18]五種圖壓縮格式分別作為遍歷類應(yīng)用單源最短路徑SSSP算法的輸入格式進行特性化分析，分析不同數(shù)據(jù)集下不同壓縮格式的性能指標，如 IPC、數(shù)據(jù)移動量(datamv)、功耗(energy)、各級cacheMPKI、執(zhí)行時間(exec.time)等，通過對這些特征數(shù)據(jù)的比較為不同需求圖計算加速器的設(shè)計提供依據(jù)。

1 算法及壓縮格式分析

1.1 SSSP算法

單源最短路徑算法[20]是計算從源點到所有其余頂點的路徑上邊權(quán)值之和的最小值的算法，在實際生產(chǎn)和生活中的應(yīng)用非常廣泛，是網(wǎng)絡(luò)理論、地圖路徑查詢和線路安排等許多實際問題選擇最優(yōu)解決方案的基礎(chǔ)。

SSSP算法的基本思想為：若s為源頂點，u為某次迭代的活動頂點，那么則在與u相連的頂點中依次選擇未訪問頂點vi(state[vi]=0)入列以便作為活動頂點順序訪問，同時計算其當前路徑長度為源頂點到當前活動頂點的路徑長度dis(u)加該頂點的權(quán)值weight(vi)得到temp(vi)；若某一頂點被多次作為相連頂點訪問(state[vi]=1)，則每次都計算其當前路徑長度temp(vi)并與dis(vi)進行比較，選擇兩者最小值作為dis(vi)進行下次迭代，直至隊列為空。其偽代碼如表1所示。

算法1SSSP算法偽代碼

inputGraphG(V,E)；源頂點s；(u,v)邊的權(quán)值weight(u,v)

output 從源頂點s到其他各個頂點的最短路徑長度min[n]

a)b)c)d)e)f)g)h)i)j)k)l)m)n)o)p)forn∈Vdo//初始化 dis[n]=INF;//源頂點s到頂點n的當前路徑長度 min[n]=INF; state[n]=0;//頂點n的活動狀態(tài)dis[s]=0;state[s]=1;queue←s;//源頂點s入隊while(P.queue不為空) do forn(n為s的鄰接點) do ifstate[n]=0 P.queue←n; state[n]=1; dis[n]=dis[s]+weight(s,n); ifdis[n]

1.2 五種壓縮格式分析

(1) COO壓縮格式。在COO(Coordinate)按坐標表示，每一個元素需要用一個三元組(行號，列號，數(shù)值)來表示。這種壓縮方式比較簡單，每個三元組都可以直接定位，但是記錄的信息多，因此占用空間較大[14]。如圖1所示的原始矩陣，其COO壓縮格式為(0,2,3)，(0,3,2)，(1,0,1)，以此類推。

圖1 原始矩陣

(2) CSC壓縮格式。CSC(Compressed Sparse Column)按列壓縮，需要三個數(shù)組表達：列偏移、列號和數(shù)值。其中數(shù)值和行號與COO一致，表示一個元素以及其行號，列偏移表示某一列的第一個元素在values里面的起始偏移位置(即該元素所在當前列之前的非零元素個數(shù))[15]。圖1中，第一列元素1是0偏移，第二列元素3是2偏移，第三列元素3是3偏移，以此類推，在列偏移的最后補上矩陣總的元素個數(shù)。

(3) CSR壓縮格式。CSR(Compressed Sparse Row)按行壓縮，與CSC相似，也需要三個數(shù)組來表達：行偏移、列號和數(shù)值。數(shù)值和列號與COO一致，表示一個元素以及其列號，行偏移表示某一行的第一個元素在values里面的起始偏移位置(即該元素所在當前行之前的非零元素個數(shù))[16]。圖1中，第一行元素3是0偏移，第二行元素1是2偏移，第三行元素1是3偏移，以此類推，在行偏移的最后補上矩陣總的元素個數(shù)，本例中是9。

(4) DCSC壓縮格式。如表1所示，DCSC(Doubly Compressed Sparse Column)雙壓縮稀疏列主要使用四個數(shù)組來存儲給定的矩陣，一個數(shù)組用于存儲至少具有一個非零元素的列的列索引，以及指向與該列索引相對應(yīng)的行索引在上述數(shù)組中開始的位置，以及非零元素所在行索引和數(shù)值[17-18]。

表1 原始矩陣的DCSC壓縮

(5) CSCI壓縮格式。CSCI(Compressed Sparse Column Independently)獨立稀疏列壓縮，對稀疏鄰接矩陣按列獨立壓縮成一個個的數(shù)據(jù)對(ioc，index, value)，ioc為“1”，則表示index為列號，value表示該列非零元素的個數(shù)；若ioc為“0”，則表示index為當前列非零元素所在的行號，value表示該非零元素的值[19]。圖1中，壓縮結(jié)果為(1,0,2)，(0,1,1)，(0,4,2)，(1,1,1)，以此類推。

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

2.1 硬件平臺

本次實驗是在4核8線程Intel(R) Core(TM) i5- 8250U CPU上運行的，其中CPU具有6 MB的三級緩存，該CPU以1.6 GHz的時鐘頻率運行，平臺具有8 GB內(nèi)存和1 TB外存，并運行Linux內(nèi)核4.15.0系統(tǒng)，所有代碼均使用gcc 5.4.0版本進行編譯和運行。

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

實驗數(shù)據(jù)選自斯坦福大學(xué)的SNAP(Stanford Network Analysis Project)數(shù)據(jù)集中road network的road net-TX[21]以及social network的Wiki-Vote[22]，其頂點個數(shù)、邊數(shù)以及內(nèi)存占用情況如表2所示。

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

2.3 分析工具perf[23]

perf是內(nèi)置于Linux內(nèi)核源碼樹中的性能剖析(profiling)工具。它基于事件采樣原理，以性能事件為基礎(chǔ)，對處理器相關(guān)性能指標與操作系統(tǒng)相關(guān)性能指標進行性能剖析。本文通過分析器收集性能指標數(shù)據(jù)來計算不同數(shù)據(jù)集中不同壓縮格式的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í)行時間。任務(wù)的執(zhí)行時間即目標任務(wù)真正占用處理器的時間，單位為ms/edgs。根據(jù)下式計算三種實現(xiàn)方式在不同壓縮格式中的每條邊的執(zhí)行時間：

(1)

(2) IPC。IPC(Instruction Per Clock)是一個基本性能指標，表示平均每一時鐘周期所執(zhí)行的指令數(shù)。一般而言IPC越大越好，說明程序充分利用了處理器的特征。可根據(jù)下式計算算法設(shè)計的IPC：

(2)

(3) 數(shù)據(jù)移動量。數(shù)據(jù)移動量受延遲和帶寬的限制，在高性能計算程序中往往屬于不可并行或者很難并行的部分。為了描述數(shù)據(jù)移動問題，本文在每種SSSP算法實現(xiàn)中記錄每條邊的數(shù)據(jù)移動量。通過統(tǒng)計的性能事件，根據(jù)下式可計算出在不同壓縮格式中的每條邊的數(shù)據(jù)移動量：

(3)

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

(4) 功耗。功耗是圖計算加速器的重要性能指標?？筛鶕?jù)下式計算每條邊的功耗：

(4)

式中：Rpower_all為消耗的總能量。

(5) MPKI。MPK(Misses Per Kilo Instructions)是一個用來分析cache性能的通用指標，表示每千條指令的平均未命中數(shù)?？筛鶕?jù)下式計算各級cache的MPKI：

(5)

(6) 計算量。分析運行時間對于算法分析也極為重要。在影響程序運行時間的因素中，除了某些超出所有理論模型范疇的因素諸如所使用的編譯器和計算器之外，主要的影響因素是所使用的算法和對該算法的輸入?？筛鶕?jù)下式來計算每條邊的執(zhí)行時間：

(6)

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

本節(jié)介紹了在所選的五種壓縮格式的內(nèi)存占用情況以及在SSSP應(yīng)用下性能特征，并通過性能比較列出了一些圖計算加速器設(shè)計建議。

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

圖2表示了兩種數(shù)據(jù)集在不同壓縮格式下的內(nèi)存占用情況?？梢钥闯?，除COO外的四種壓縮格式都對原始數(shù)據(jù)進行了不同程度的壓縮，其中DCSC壓縮格式對數(shù)據(jù)的壓縮程度最大，CSCI壓縮程度較小，CSR與CSC的壓縮結(jié)果最明顯且二者相差不大。這是因為DCSC在CSC的基礎(chǔ)上對列偏移量再次進行壓縮，只存儲非零元素個數(shù)大于等于1的列，所以對于足夠稀疏的圖數(shù)據(jù)來說存儲效率最高；CSC和CSR兩種壓縮格式需要每個頂點所有邊的個數(shù)、邊的源頂點(CSC)或者目標頂點(CSR)以及邊的權(quán)值三個數(shù)組來存儲圖數(shù)據(jù)，當稀疏矩陣的行列數(shù)趨近于相同時，內(nèi)存占用大小也相近；CSCI壓縮格式將稀疏矩陣中列號及該列的非零元素個數(shù)、非零元素所在的行號以及屬性值都對應(yīng)存儲，而不是只存儲非零元素個數(shù)、行號及屬性值，即會占用更大的內(nèi)存空間；COO壓縮格式是將所有邊的信息以最直接的方式存儲成三元組的形式，即與數(shù)據(jù)的原始存儲格式相同，內(nèi)存占用最大。

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

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

為了對不同壓縮格式的相同算法處理的性能特征進行系統(tǒng)性的分析，本文通過雷達圖的形式顯示了COO、CSC、CSR、DCSC以及CSCI五種壓縮格式在SSSP應(yīng)用算法中的性能，如圖3所示，在每一幅圖中，包括每個壓縮格式實現(xiàn)的IPC、數(shù)據(jù)移動量、執(zhí)行時間、功耗以及L1、L2和L3三級數(shù)據(jù)緩存MPKI。其中，每個度量標準的最大值視為100%，其他數(shù)據(jù)以它作為標準。

(a) 數(shù)據(jù)集Wiki-vote

(b) 數(shù)據(jù)集road net-TX圖3 兩種數(shù)據(jù)集下五種壓縮格式的性能指標

可以看出，MPKI高，IPC低時會增加其執(zhí)行時間，同時CSR壓縮格式表現(xiàn)出了更少的執(zhí)行時間、數(shù)據(jù)移動量以及計算量，DCSC壓縮格式的計算量和功耗相對較?。籆SCI壓縮格式的執(zhí)行時間和數(shù)據(jù)移動量相對較長，COO壓縮格式的計算量較大而CSC壓縮格式的各項指標均居中。這是因為CSR壓縮格式記錄了各個頂點作為活動頂點時的行偏移量，減少了頂點遍歷的時間和計算量。當CSCI和COO兩種壓縮格式作為輸入時，每個活動頂點的訪問都需要遍歷所有頂點從而找到與當前活動頂點相連的目標頂點。CSC和DCSC壓縮格式記錄的是圖數(shù)據(jù)中邊的源點，無法直接對其進行單源最短路徑算法處理，需要在實現(xiàn)過程中對數(shù)據(jù)進行預(yù)處理操作，所以其性能相比CSR壓縮格式較差。綜上所述，當執(zhí)行時間作為主要參考指標時應(yīng)優(yōu)先選擇CSR壓縮格式；在計算操作量受限制的情況下，則選擇CSR壓縮格式作為數(shù)據(jù)集的輸入格式；在硬件環(huán)境受限時并且需要盡可能減少功耗時，也可選擇CSR壓縮格式，它具有更少的數(shù)據(jù)移動，可提升圖計算加速器的性能；在考慮內(nèi)存占用情況時，選擇使用DCSC壓縮格式；而在需要提高緩存命中率的情況下，應(yīng)選擇CSC壓縮格式。

(1) 執(zhí)行時間。兩種數(shù)據(jù)集在不同壓縮格式下每條邊的執(zhí)行時間如表3所示?？梢钥闯鯟SCI格式邊的執(zhí)行最長而CSR壓縮格式邊的執(zhí)行時間最短，幾乎為CSCI格式的一半，當數(shù)據(jù)量足夠大時甚至相差更多，CSC與DCSC格式執(zhí)行時間接近，COO格式的執(zhí)行時間居中。因此對于遍歷類應(yīng)用而言，在考慮邊的執(zhí)行時間時，優(yōu)先選擇CSR壓縮格式作為數(shù)據(jù)集的輸入格式。

表3 兩種數(shù)據(jù)集五種壓縮格式下的執(zhí)行時間 單位：ms

(2) 數(shù)據(jù)移動量。表4列出了兩種數(shù)據(jù)集在不同壓縮格式下每條邊的數(shù)據(jù)移動量?？梢钥闯觯瑢τ陧旤c與邊相對較小的Wiki_Vote數(shù)據(jù)集而言，每條邊的需要成千上萬的數(shù)據(jù)移動量，而對于road net-TX數(shù)據(jù)集，每條邊所需的數(shù)據(jù)移動量甚至可達上千萬。對比五種壓縮格式，可以發(fā)現(xiàn)CSR壓縮格式的數(shù)據(jù)移動量遠小于其他四種格式，CSC和DCSC的數(shù)據(jù)移動量接近且居中，COO和CSCI的數(shù)據(jù)移動量相對較大。因此對于遍歷類應(yīng)用而言，在考慮邊的數(shù)據(jù)移動量時，應(yīng)選擇CSR壓縮格式作為數(shù)據(jù)集的輸入格式。

表4 兩種數(shù)據(jù)集五種壓縮格式下每條邊的 數(shù)據(jù)移動量(指令數(shù)/邊數(shù))

(3) 功耗。兩種數(shù)據(jù)集在五種壓縮格式下每條邊的功耗如表5所示?？梢钥闯鯟SR壓縮格式的消耗的能量最少，這是因為CSR壓縮格式記錄了當前活動頂點的行偏移量，無須遍歷所有頂點便可以準確定位到目標頂點，這大大地減少了功耗，所以其他四種格式消耗的能量相對較多。因此對于遍歷類應(yīng)用而言，選擇CSR壓縮格式能夠有效地減少功耗。

表5 兩種數(shù)據(jù)集五種壓縮格式下每條邊的功耗 單位：J

(4) MPKI。兩種數(shù)據(jù)集在五種壓縮格式的L1、L2和L3級cache MPKI分別如表6、表7和表8所示?？梢钥闯?，在所有壓縮格式下，L1級cache MPKI都小于3，L2級cache MPKI幾乎小于L1級cache MPKI的一半甚至更多，L3級cache MPKI更小，因此我們只關(guān)注各個壓縮格式的L1級cache MPKI。對比結(jié)果可以發(fā)現(xiàn)CSC壓縮格式具有更小的L1級cache MPKI，因此選擇CSC壓縮格式可以有效提高遍歷類應(yīng)用的緩存命中率。

表6 兩種數(shù)據(jù)集五種壓縮格式下L1級cache MPKI (misses/kilo_instructions)

表7 兩種數(shù)據(jù)集五種壓縮格式下L2級cache MPKI (misses/kilo_instructions)

表8 兩種數(shù)據(jù)集五種壓縮格式下L3級cache MPKI (misses/kilo_instructions)

(5) 計算量。表9列出了兩種數(shù)據(jù)集在不同壓縮格式下每條邊計算量?？梢钥闯鯟SR壓縮格式具有更少的計算量，而COO與CSCI壓縮格式的計算操作相對較多，高達CSR壓縮格式的數(shù)倍。因此在計算量受限制的情況下，遍歷類應(yīng)用應(yīng)優(yōu)先選擇CSR壓縮格式作為數(shù)據(jù)集的輸入結(jié)構(gòu)。

表9 兩種數(shù)據(jù)集五種壓縮格式下每條邊的計算量 (指令數(shù)/邊數(shù))

3.3 綜合分析

分析結(jié)果可以看出五種壓縮格式在不同的需求下有著各自的特點。COO壓縮格式在存儲圖數(shù)據(jù)時簡潔明了，但對于頂點的鄰接邊和頂點的查詢及訪問效率較低。CSC和CSR壓縮格式占用內(nèi)存較小，存儲效率高，其中CSC可以高效地查詢頂點的入邊信息，CSR可以高效查詢頂點的出邊信息。DCSC壓縮格式對CSC中源頂點再次進行壓縮，對于稀疏圖數(shù)據(jù)來說存儲效率最高。CSCI壓縮格式可以根據(jù)列標識相關(guān)數(shù)據(jù)，計算活躍頂點在存儲中的物理地址，實現(xiàn)“精確”訪問，但內(nèi)存占用較大。

同時，對于SSSP算法而言，CSR是適合單源最短路徑算法的數(shù)據(jù)結(jié)構(gòu)。因為CSR壓縮格式頂點的鄰接點信息遞增順序存儲，其處理時間最短而且能有效縮短執(zhí)行時間，減少計算操作量和數(shù)據(jù)移動量，同時降低功耗。選擇DCSC壓縮格式能減少圖數(shù)據(jù)的內(nèi)存占用。選擇CSC壓縮格式能提高其緩存命中率。

4 結(jié) 語

本文通過分析兩種數(shù)據(jù)集的五種壓縮格式(COO、CSC、CSR、DCSC以及CSCI)在SSSP算法的性能數(shù)據(jù)，發(fā)現(xiàn)：對于SSSP算法，當硬件環(huán)境受限時，應(yīng)當優(yōu)先選擇CSR壓縮格式，能有效減少功耗、計算量和數(shù)據(jù)移動量；當考慮圖應(yīng)用的緩存命中率時，選擇CSC壓縮格式作為其圖數(shù)據(jù)輸入格式；當內(nèi)存受限時，選擇DCSC壓縮格式作為數(shù)據(jù)輸入格式。具體原因如下：CSR壓縮格式記錄了當前活動頂點的行偏移量，在算法處理時無須遍歷所有頂點便可準確定位目標頂點，有效減少了算法的執(zhí)行時間、計算操作量、數(shù)據(jù)移動量以及功耗。而考慮其cache MPKI時，選擇CSC壓縮格式可以有效提高遍歷類應(yīng)用的緩存命中率?？紤]內(nèi)存占用情況時，選擇DCSC壓縮格式可提高圖數(shù)據(jù)的存儲效率。

綜上所述，在面對不同的應(yīng)用環(huán)境、不同的性能要求時，根據(jù)實際需求以上述結(jié)論為依據(jù)進行調(diào)整可有效提高圖計算加速器的性能。