鄧軍勇 趙一迪

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

0 引 言

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

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

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

1 算法及壓縮格式分析

1.1 SSSP算法

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

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

算法1SSSP算法偽代碼

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

output 從源頂點(diǎn)s到其他各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度min[n]

a)b)c)d)e)f)g)h)i)j)k)l)m)n)o)p)forn∈Vdo//初始化 dis[n]=INF;//源頂點(diǎn)s到頂點(diǎn)n的當(dāng)前路徑長(zhǎng)度 min[n]=INF; state[n]=0;//頂點(diǎn)n的活動(dòng)狀態(tài)dis[s]=0;state[s]=1;queue←s;//源頂點(diǎn)s入隊(duì)while(P.queue不為空) do forn(n為s的鄰接點(diǎn)) 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)按坐標(biāo)表示，每一個(gè)元素需要用一個(gè)三元組(行號(hào)，列號(hào)，數(shù)值)來(lái)表示。這種壓縮方式比較簡(jiǎn)單，每個(gè)三元組都可以直接定位，但是記錄的信息多，因此占用空間較大[14]。如圖1所示的原始矩陣，其COO壓縮格式為(0,2,3)，(0,3,2)，(1,0,1)，以此類推。

圖1 原始矩陣

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

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

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

表1 原始矩陣的DCSC壓縮

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

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

2.1 硬件平臺(tái)

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

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

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

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

2.3 分析工具perf[23]

perf是內(nèi)置于Linux內(nèi)核源碼樹(shù)中的性能剖析(profiling)工具。它基于事件采樣原理，以性能事件為基礎(chǔ)，對(duì)處理器相關(guān)性能指標(biāo)與操作系統(tǒng)相關(guān)性能指標(biāo)進(jìn)行性能剖析。本文通過(guò)分析器收集性能指標(biāo)數(shù)據(jù)來(lái)計(jì)算不同數(shù)據(jù)集中不同壓縮格式的IPC、數(shù)據(jù)移動(dòng)量、功耗、計(jì)算量、L1、L2以及L3數(shù)據(jù)緩存MPKI。

2.4 性能指標(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í)間。任務(wù)的執(zhí)行時(shí)間即目標(biāo)任務(wù)真正占用處理器的時(shí)間，單位為ms/edgs。根據(jù)下式計(jì)算三種實(shí)現(xiàn)方式在不同壓縮格式中的每條邊的執(zhí)行時(shí)間：

(1)

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

(2)

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

(3)

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

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

(4)

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

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

(5)

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 綜合分析

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

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

4 結(jié) 語(yǔ)

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

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