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

鄧軍勇 趙一迪

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

0 引 言

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

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

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

1 算法及壓縮格式分析

1.1 SSSP算法

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

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

算法1SSSP算法偽代碼

inputGraphG(V,E)；源頂點s；(u,v)邊的權值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的活動狀態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)按坐標表示，每一個元素需要用一個三元組(行號，列號，數值)來表示。這種壓縮方式比較簡單，每個三元組都可以直接定位，但是記錄的信息多，因此占用空間較大[14]。如圖1所示的原始矩陣，其COO壓縮格式為(0,2,3)，(0,3,2)，(1,0,1)，以此類推。

圖1 原始矩陣

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

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

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

表1 原始矩陣的DCSC壓縮

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

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

2.1 硬件平臺

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

2.2 數據集選取

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

表2 實驗所選的數據集

2.3 分析工具perf[23]

perf是內置于Linux內核源碼樹中的性能剖析(profiling)工具。它基于事件采樣原理，以性能事件為基礎，對處理器相關性能指標與操作系統相關性能指標進行性能剖析。本文通過分析器收集性能指標數據來計算不同數據集中不同壓縮格式的IPC、數據移動量、功耗、計算量、L1、L2以及L3數據緩存MPKI。

2.4 性能指標定義

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

(1) 執行時間。任務的執行時間即目標任務真正占用處理器的時間，單位為ms/edgs。根據下式計算三種實現方式在不同壓縮格式中的每條邊的執行時間：

(1)

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

(2)

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

(3)

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

(4) 功耗。功耗是圖計算加速器的重要性能指標。可根據下式計算每條邊的功耗：

(4)

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

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

(5)

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

(6)

3 不同壓縮格式的內存占用及特性化

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

3.1 不同壓縮格式內存占用情況

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

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

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

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

(a) 數據集Wiki-vote

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

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

(1) 執行時間。兩種數據集在不同壓縮格式下每條邊的執行時間如表3所示。可以看出CSCI格式邊的執行最長而CSR壓縮格式邊的執行時間最短，幾乎為CSCI格式的一半，當數據量足夠大時甚至相差更多，CSC與DCSC格式執行時間接近，COO格式的執行時間居中。因此對于遍歷類應用而言，在考慮邊的執行時間時，優先選擇CSR壓縮格式作為數據集的輸入格式。

表3 兩種數據集五種壓縮格式下的執行時間 單位：ms

(2) 數據移動量。表4列出了兩種數據集在不同壓縮格式下每條邊的數據移動量。可以看出，對于頂點與邊相對較小的Wiki_Vote數據集而言，每條邊的需要成千上萬的數據移動量，而對于road net-TX數據集，每條邊所需的數據移動量甚至可達上千萬。對比五種壓縮格式，可以發現CSR壓縮格式的數據移動量遠小于其他四種格式，CSC和DCSC的數據移動量接近且居中，COO和CSCI的數據移動量相對較大。因此對于遍歷類應用而言，在考慮邊的數據移動量時，應選擇CSR壓縮格式作為數據集的輸入格式。

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

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

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

(4) MPKI。兩種數據集在五種壓縮格式的L1、L2和L3級cache MPKI分別如表6、表7和表8所示。可以看出，在所有壓縮格式下，L1級cache MPKI都小于3，L2級cache MPKI幾乎小于L1級cache MPKI的一半甚至更多，L3級cache MPKI更小，因此我們只關注各個壓縮格式的L1級cache MPKI。對比結果可以發現CSC壓縮格式具有更小的L1級cache MPKI，因此選擇CSC壓縮格式可以有效提高遍歷類應用的緩存命中率。

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

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

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

(5) 計算量。表9列出了兩種數據集在不同壓縮格式下每條邊計算量。可以看出CSR壓縮格式具有更少的計算量，而COO與CSCI壓縮格式的計算操作相對較多，高達CSR壓縮格式的數倍。因此在計算量受限制的情況下，遍歷類應用應優先選擇CSR壓縮格式作為數據集的輸入結構。

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

3.3 綜合分析

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

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

4 結 語

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

綜上所述，在面對不同的應用環境、不同的性能要求時，根據實際需求以上述結論為依據進行調整可有效提高圖計算加速器的性能。