圖數(shù)據(jù)格式對三角形計(jì)數(shù)算法影響的特性分析

張世茹，鄧軍勇

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

1 引 言

圖因其宜于表征不同實(shí)體間復(fù)雜的依賴關(guān)系而受到廣泛應(yīng)用[1-3]，社交網(wǎng)絡(luò)分析、推薦系統(tǒng)、傳染病防治等都緊密依賴于高性能、高能效的圖計(jì)算系統(tǒng)[4,5].真實(shí)圖的規(guī)模動(dòng)輒有數(shù)十億個(gè)頂點(diǎn)和上萬億條邊，龐大的頂點(diǎn)和邊以及附帶的各類屬性使得遍歷、查找等圖計(jì)算過程中無法預(yù)知相鄰數(shù)據(jù)，造成存儲(chǔ)訪問的隨機(jī)性強(qiáng)、局部性差，而圖計(jì)算操作簡單、實(shí)時(shí)性強(qiáng)的高“訪存計(jì)算比”不僅帶寬需求高，且?guī)捓速M(fèi)嚴(yán)重[6,7].同時(shí)，圖的組織形式包括鄰接矩陣、關(guān)系矩陣、鄰接表等，冪律分布的圖數(shù)據(jù)往往組織成稀疏矩陣的形式[6]，圖應(yīng)用各式各樣、圖結(jié)構(gòu)也千差萬別，相同圖應(yīng)用處理不同圖時(shí)性能差異巨大[8].經(jīng)過不同壓縮格式處理過的圖數(shù)據(jù)，會(huì)對圖計(jì)算加速器的性能造成不同的影響.因此，根據(jù)不同需求的應(yīng)用算法來選擇合適的壓縮格式來提高圖計(jì)算加速器的性能尤為重要.

本文通過對圖計(jì)算中常用的稀疏矩陣存儲(chǔ)方法COO(Coordinate List，按坐標(biāo)表示)[6,9]、CSC(Compressed Sparse Column，壓縮稀疏列)[6,10]、CSR(Compressed Sparse Row，壓縮稀疏行)[6,11]、DCSC(Doubly Compressed Sparse Column，雙壓縮稀疏列)[12]和CSCI(Compressed Sparse Column Independently，獨(dú)立稀疏列壓縮)[13]5種圖數(shù)據(jù)格式分別作為具有代表性的社交類應(yīng)用的三角形計(jì)數(shù)算法TC(Triangle counting)的輸入格式進(jìn)行特性分析，性能參數(shù)包括執(zhí)行時(shí)間(Exec.time)、計(jì)算量(compute)、數(shù)據(jù)移動(dòng)量(Datamv)、每周期指令數(shù)(IPC)、各級cache的缺失率(MPKI)以及功耗(energy)，通過對這些特征數(shù)據(jù)的比較為不同需求的圖計(jì)算加速器設(shè)計(jì)提供依據(jù).

2 算法及圖數(shù)據(jù)格式分析

2.1 三角形計(jì)數(shù)算法

三角形計(jì)數(shù)算法[14](TC，Triangle Counting)是一種統(tǒng)計(jì)算法，用于理解社交網(wǎng)絡(luò)、圖形分析和計(jì)算聚類系數(shù).該算法偽代碼如表1所示.TC算法計(jì)算給定圖形中三角形的數(shù)目，當(dāng)一個(gè)頂點(diǎn)有兩個(gè)相鄰的頂點(diǎn)，并且這兩個(gè)相鄰頂點(diǎn)也是相鄰的，則判定存在三角形，其流程圖如圖1所示.計(jì)算三角形數(shù)目的技術(shù)如下：每個(gè)頂點(diǎn)與其每個(gè)鄰居共享其鄰居列表.然后每個(gè)頂點(diǎn)計(jì)算其鄰居列表與其接收的鄰居列表之間的交集對于給定的無循環(huán)有向圖，交叉口的大小給出了圖中三角形的數(shù)目.當(dāng)圖是無向圖時(shí)，三角形中的每個(gè)頂點(diǎn)都貢獻(xiàn)了計(jì)數(shù)，因此交點(diǎn)的大小正好是三角形數(shù)目的3倍.本文TC算法的基本思想：若k為源頂點(diǎn)，統(tǒng)計(jì)k的鄰結(jié)點(diǎn)q，再按順序統(tǒng)計(jì)q的鄰結(jié)點(diǎn)m，再統(tǒng)計(jì)對兩個(gè)頂點(diǎn)之間邊計(jì)算交集，并找出交集中id大于前兩個(gè)k和q結(jié)點(diǎn)id的結(jié)點(diǎn)v，最后對每個(gè)結(jié)點(diǎn)統(tǒng)計(jì)三角形總數(shù).

表1 TC算法偽代碼Table 1 TC algorithm pseudo code

圖1 TC算法流程圖Fig.1 TC algorithm flow chart

2.2 圖數(shù)據(jù)格式

在實(shí)際問題中大規(guī)模矩陣基本上都是稀疏矩陣，稀疏矩陣是指矩陣中的元素大部分是0的矩陣.COO按坐標(biāo)表示，每一個(gè)元素需要用一個(gè)三元組來表示，分別是行號、列號和數(shù)值.CSC由3個(gè)數(shù)組表示：指數(shù)、索引和數(shù)值，其中指數(shù)是行索引的數(shù)組，數(shù)值是對應(yīng)非零值的數(shù)組，索引指向列的指數(shù)和數(shù)值.長度為n+1，最后一項(xiàng)是數(shù)據(jù)的總數(shù).CSR與CSC類似，同樣由3個(gè)數(shù)組來表示：列索引、行偏移和數(shù)值.DCSC它是CSC的擴(kuò)展，由4個(gè)數(shù)組表示：列號，行號，列偏移，數(shù)值.CSCI由索引index的最高兩位指示index其余位與數(shù)值value的含義.(ioc，index,value)，ioc為“1”，則表示index為列號，value表示該列非零元素的個(gè)數(shù)；若ioc為“0”，則表示index為當(dāng)前列非零元素所在的行號，value表示該非零元素的值.如圖2所示一個(gè)有向圖以及它的鄰接矩陣和5種圖數(shù)據(jù)格式.

圖2 一個(gè)有向圖以及它的鄰接矩陣和5種圖數(shù)據(jù)格式Fig.2 Directed graph as well as its adjacency matrix and five graph data formats

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

3.1 硬件平臺

本文的實(shí)驗(yàn)平臺是hpe580 Intel(R)Xeon(R)Platinum 8164 CPU@2.00GHZ，該服務(wù)器具有208個(gè)物理核416線程，每個(gè)核心都有一個(gè)32KB的L1級數(shù)據(jù)cache，一個(gè)32KB的L1級指令cache，1024KB的L2級cache以及36608KB的L3級cache，內(nèi)存大小為1TB，運(yùn)行Linux內(nèi)核4.15.0系統(tǒng)，所有代碼均使用gcc5.3.0版本進(jìn)行編譯和運(yùn)行，CPU平臺的規(guī)格如表2表示.

表2 CPU平臺的規(guī)格Table 2 Specifications of the CPU platform

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

本文的實(shí)驗(yàn)數(shù)據(jù)選自斯坦福大學(xué)的SNAP(Stanford Network Analysis Project)數(shù)據(jù)集中internet peer-to-peer networks的p2p-Gnutella04[15]、internet peer-to-peer networks的p2p-Gnutella06[16]以及Social networks的soc-Epinions1[17]，其各自的頂點(diǎn)個(gè)數(shù)、邊數(shù)、類型以及描述如表3所示.

表3 實(shí)驗(yàn)所選的數(shù)據(jù)集Table 3 Data sets selected in the experiment

3.3 分析工具

常用的分析工具包括Perf[18]和Intel VTune[19].Perf是一個(gè)分析器工具，可以抽象出CPU硬件性能測量.VTune性能分析器用于基于x86的32位和64位的性能分析，它有助于各種代碼分析，包括堆棧采樣、線程分析和硬件事件采樣.本文使用Perf和VTune來保證數(shù)據(jù)的可靠性.表4列出了與性能特征相關(guān)的可測量事件的子集[20,21].

表4 性能事件列表及描述Table 4 List and description of performance events

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

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

3.4.1 執(zhí)行時(shí)間

執(zhí)行時(shí)間是計(jì)算機(jī)完成目標(biāo)任務(wù)所需的總時(shí)間，包括硬盤訪問、內(nèi)存訪問、I/O活動(dòng)、操作系統(tǒng)開銷和CPU執(zhí)行時(shí)間等，單位為毫秒/邊(ms/edges).根據(jù)下列公式計(jì)算3種圖數(shù)據(jù)在不同壓縮格式中的每條邊的執(zhí)行時(shí)間：

(1)

3.4.2 IPC

IPC(Instruction Per Clock)是CPU每一時(shí)鐘周期內(nèi)所執(zhí)行的指令數(shù)，影響IPC的因素有算法、編程語言、編譯器以及指令系統(tǒng)體系結(jié)構(gòu).根據(jù)下列公式計(jì)算3種圖數(shù)據(jù)作為輸入數(shù)據(jù)的TC算法的IPC：

(2)

3.4.3 數(shù)據(jù)移動(dòng)量

數(shù)據(jù)移動(dòng)量受延遲和帶寬的限制，對于不同壓縮格式的同一個(gè)數(shù)據(jù)集運(yùn)行之后的數(shù)據(jù)移動(dòng)量是遠(yuǎn)遠(yuǎn)不同的.本文統(tǒng)計(jì)了TC算法在每一種圖數(shù)據(jù)格式下的數(shù)據(jù)移動(dòng)次數(shù)，此處的數(shù)字表示數(shù)據(jù)移動(dòng)操作.在等式(3)中所示負(fù)載和存儲(chǔ)指令總數(shù)和表示數(shù)據(jù)移動(dòng)，然后除以邊數(shù)，根據(jù)下列公式計(jì)算每條邊的數(shù)據(jù)移動(dòng)量：

(3)

3.4.4 功 耗

功耗是圖計(jì)算加速器的重要性能指標(biāo)，在評價(jià)分析功耗時(shí)使用焦耳能量單位比瓦特功率單位更合理.本文用VTune性能分析器分別統(tǒng)計(jì)3種圖數(shù)據(jù)在每種圖數(shù)據(jù)格式下TC算法實(shí)現(xiàn)時(shí)所消耗的總功率.根據(jù)公式計(jì)算每條邊的功耗：

(4)

3.4.5 MPKI

MPKI(Misses Per Kilo Instructions)是用來分析cache性能的通用指標(biāo)，表示每千條指令的平均未命中數(shù).cache缺失率越低，則cache性能越好，存儲(chǔ)訪存的速度就越快.根據(jù)下列公式計(jì)算各級cache的MPKI：

(5)

3.4.6 計(jì)算量

在程序執(zhí)行的過程中，不同的圖數(shù)據(jù)輸入格式和使用的算法是影響計(jì)算量的主要原因.同一個(gè)算法處理同一個(gè)數(shù)據(jù)集的不同壓縮格式時(shí)，計(jì)算量也是不盡相同的.根據(jù)下列公式計(jì)算每條邊的計(jì)算量：

(6)

4 圖數(shù)據(jù)格式的內(nèi)存占用及特性分析

本節(jié)介紹了在所選的5種圖數(shù)據(jù)格式的內(nèi)存占用情況以及在TC應(yīng)用下的性能特征，并通過對比不同的性能指標(biāo)列出了一些圖計(jì)算加速器設(shè)計(jì)建議.

4.1 圖數(shù)據(jù)格式內(nèi)存占用情況

圖3表示了3種圖數(shù)據(jù)在不同的圖數(shù)據(jù)格式下的內(nèi)存占用情況.由于COO格式與原數(shù)據(jù)格式相似，因此為了更好的對比分析5種圖數(shù)據(jù)格式內(nèi)存占用情況，圖3中將其他4種圖數(shù)據(jù)格式歸一化到COO格式.從圖3可以看出，COO格式占用的內(nèi)存最大，因?yàn)镃OO格式采用三元組的形式來存儲(chǔ)原始數(shù)據(jù)的所有邊和頂點(diǎn)的信息；DCSC格式對數(shù)據(jù)的壓縮程度最大，占用的內(nèi)存最小，這是因?yàn)镈CSC在CSC的基礎(chǔ)上對列偏移量再次進(jìn)行壓縮，只存儲(chǔ)非零元素個(gè)數(shù)大于等于1的列，輸出4個(gè)壓縮數(shù)組，分別是壓縮后的非零列、非零列的偏移值，非零列元素值對應(yīng)的非零行以及非零元素，所以對于足夠稀疏的圖數(shù)據(jù)來說存儲(chǔ)效率最高；CSR與CSC的壓縮結(jié)果二者相差不大，CSC和CSR需要用兩個(gè)數(shù)組來存儲(chǔ)每個(gè)頂點(diǎn)所有邊的個(gè)數(shù)、邊的源頂點(diǎn)(CSC)或者目標(biāo)頂點(diǎn)(CSR)，因此當(dāng)稀疏矩陣的行列數(shù)相近時(shí)，內(nèi)存占用大小也相近，對原始數(shù)據(jù)的壓縮程度相對較大；CSCI格式是將鄰接稀疏矩陣表示的圖數(shù)據(jù)轉(zhuǎn)換成獨(dú)立稀疏列壓縮的圖數(shù)據(jù)，每列單獨(dú)壓縮后的圖數(shù)據(jù)包括列標(biāo)識數(shù)據(jù)對和非零元素?cái)?shù)據(jù)對，每個(gè)數(shù)據(jù)對包括索引和數(shù)值，故與DCSC、CSR和CSC格式相比較內(nèi)存占用較大.

圖3 3種圖數(shù)據(jù)5種圖數(shù)據(jù)格式下的內(nèi)存占用情況(歸一化到COO格式)Fig.3 Memory usage of three graph data and five graph data formats(normalized to COO format)

4.2 5種圖數(shù)據(jù)格式的特性分析

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

圖4 3種圖數(shù)據(jù)下5種圖數(shù)據(jù)格式的性能指標(biāo)Fig.4 Performance indicators of five graph data formats under three graph data

4.2.1 執(zhí)行時(shí)間

3種圖數(shù)據(jù)在5種圖數(shù)據(jù)格式下每條邊的執(zhí)行時(shí)間如表5所示.將每個(gè)圖數(shù)據(jù)下的最大執(zhí)行時(shí)間歸一化，在圖數(shù)據(jù)p2p-Gnutella04下COO占CSCI的35.81%，CSC占CSCI的0.04%，CSR占CSCI的0.15%，DCSC占CSCI的9.69%；在圖數(shù)據(jù)p2p-Gnutella06下COO占CSCI的34.06%，CSC占CSCI的0.05%，CSR占CSCI的0.18%，DCSC占CSCI的9.76%；在圖數(shù)據(jù)soc-Epinions1下COO占CSCI的9.49%，CSC占CSCI的0.92%，CSR占CSCI的0.99%，DCSC占CSCI的9.10%.可以看出，3種圖數(shù)據(jù)下CSC格式邊的執(zhí)行時(shí)間最短，CSR格式相比CSC較短，DCSC的執(zhí)行時(shí)間和COO的執(zhí)行時(shí)間相近居中，CSCI的執(zhí)行時(shí)間最大.因此，在考慮邊的執(zhí)行時(shí)間時(shí)，圖計(jì)算應(yīng)用優(yōu)先選擇CSC格式.

表5 3種圖數(shù)據(jù)5種圖數(shù)據(jù)格式下的執(zhí)行時(shí)間(ms)Table 5 Execution time(ms)of three graph data and five graph data formats

4.2.2 數(shù)據(jù)移動(dòng)量

3種圖數(shù)據(jù)在5種圖數(shù)據(jù)格式下每條邊的數(shù)據(jù)移動(dòng)量如表6所示.將每個(gè)圖數(shù)據(jù)下的最大數(shù)據(jù)移動(dòng)量歸一化，在圖數(shù)據(jù)p2p-Gnutella04下COO占CSCI的74.93%，CSC占CSCI的3.71%，CSR占CSCI的4.49%，DCSC占CSCI的59.12%；在圖數(shù)據(jù)p2p-Gnutella06下CSCI占COO的13.43%，CSC占COO的6.48%，CSR占COO的8.10%，DCSC占COO的27.37%；在圖數(shù)據(jù)soc-Epinions1下COO占CSCI的97.07%，CSC占CSCI的42.93%，CSR占CSCI的42.94%，DCSC占CSCI的86.37%.可以看出，3種圖數(shù)據(jù)下CSC和CSR格式每條邊的數(shù)據(jù)移動(dòng)量相接近，其中CSC格式的數(shù)據(jù)移動(dòng)量最小，DCSC格式相對較小，COO格式相對CSC、CSR較大，CSCI格式的數(shù)據(jù)移動(dòng)量最大.因此，在考慮邊的數(shù)據(jù)移動(dòng)量時(shí)，圖計(jì)算應(yīng)用優(yōu)先選擇CSC格式.

表6 3種圖數(shù)據(jù)5種圖數(shù)據(jù)格式下每條邊的數(shù)據(jù)移動(dòng)量(指令數(shù)/邊)Table 6 Data movement amount of each side in the three graph data five graph data formats(number of instructions/edge)

4.2.3 功耗

3種圖數(shù)據(jù)在5種圖數(shù)據(jù)格式下每條邊的功耗如表7所示.將每個(gè)圖數(shù)據(jù)下的最大功耗歸一化，在圖數(shù)據(jù)p2p-Gnutella04下CSCI占COO的75.28%，CSC占COO的57.39%，CSR占COO的47.73%，DCSC占COO的33.24%；在圖數(shù)據(jù)p2p-Gnutella06下COO占CSCI的37.03%，CSC占CSCI的84.71%，CSR占CSCI的40.79%，DCSC占CSCI的43.44%；在圖數(shù)據(jù)soc-Epinions1下CSCI占COO的86.00%，CSC占COO的34.77%，CSR占COO的29.01%，DCSC占COO的28.39%.可以看出，圖數(shù)據(jù)p2p-Gnutella04和soc-Epinions1下DCSC格式的功耗最小，COO格式的功耗最大；圖數(shù)據(jù)p2p-Gnutella6下COO格式的功耗最小，CSCI格式的功耗最大,對于3種圖數(shù)據(jù)在5種圖數(shù)據(jù)下的功耗，DCSC格式總體偏小.因此，考慮到邊的功耗時(shí)，圖計(jì)算應(yīng)用優(yōu)先選擇DCSC格式.

表7 3種圖數(shù)據(jù)5種圖數(shù)據(jù)格式下每條邊的功耗(J)Table 7 Power consumption of each side of the three graph data and five graph data formats(J)

4.2.4 MPKI

3種圖數(shù)據(jù)在5種圖數(shù)據(jù)格式的L1、L2和L3級cache MPKI分別如表8、表9和表10所示.將每個(gè)圖數(shù)據(jù)下的最大的各級cache缺失率歸一化，在圖數(shù)據(jù)p2p-Gnutella 04下L1級cache缺失率CSCI占COO的90.44%，CSC占COO的58.13%，CSR占COO的60.36%，DCSC占COO的16.46%，L2級cache缺失率CSCI占COO的35.48%，CSC占COO的3.71%，CSR占COO的0.10%，DCSC占COO的0.68%，L3級cache缺失率COO占CSC的2.41%，CSR占CSC的1.19%，CSCI占CSC的3.22%，DCSC占CSC的3.47%；在圖數(shù)據(jù)p2p-Gnutella06下L1級cache缺失率CSCI占COO的95.84%，CSC占COO的58.86%，CSR占COO的64.77%，DCSC占COO的12.47%，L2級cache缺失率CSCI占COO的52.14%，CSC占COO的12.78%，CSR占COO的4.22%，DCSC占COO的0.14%，L3級cache缺失率COO占CSC的2.22%，CSR占CSC的17.99%，CSCI占CSC的3.33%，DCSC占CSC的1.92%；在圖數(shù)據(jù)soc-Epinions1下L1級cache缺失率CSCI占COO的54.38%，CSC占COO的10.56%，CSR占COO的10.22%，DCSC占COO的9.89%，L2級cache缺失率CSCI占COO的64.68%，CSC占COO的7.02%，CSR占COO的4.68%，DCSC占COO的0.05%，L3級cache缺失率CSC占COO的2.07%，CSR占COO的2.57%，CSCI占COO的47.56%，DCSC占CSC的1.05%.可以看出，在所有圖數(shù)據(jù)格式下，L1級cache MPKI都小于5，L1級cache MPKI與L2級cache MPKI和L3級cache MPKI相比普遍偏高，綜合各級cache MPKI對比可以發(fā)現(xiàn)DCSC格式具有更小的各級cache MPKI，COO格式具有較高的cache缺失率，較低的缺失率可有效減少時(shí)間損耗.因此，考慮各級cache缺失率時(shí)，圖計(jì)算應(yīng)用優(yōu)先選擇DCSC格式.

表8 3種圖數(shù)據(jù)5種圖數(shù)據(jù)格式下L1級cache MPKI(misses/kilo_instructions)Table 8 L1 level cache MPKI(misses/kilo_instructions)under three typesof graph data and five types of graph data formats

表9 3種數(shù)據(jù)集5種圖數(shù)據(jù)格式下L2級cache MPKI(misses/kilo_instructions)Table 9 L2 level cache MPKI(misses/kilo_instructions)in three data sets and five image data formats

表10 3種數(shù)據(jù)集5種圖數(shù)據(jù)格式下L3級cache MPKI(misses/kilo_instructions)Table 10 L3 level cache MPKI(misses/kilo_instructions)in three data sets and five image data formats

4.2.5 計(jì)算量

3種圖數(shù)據(jù)在5種圖數(shù)據(jù)格式下每條邊的計(jì)算量如表11所示.將每個(gè)圖數(shù)據(jù)下的最大計(jì)算量歸一化，在圖數(shù)據(jù)p2p-Gnutella04下COO占CSCI的39.36%，CSC占CSCI的6.50%，CSR占CSCI的8.62%，DCSC占CSCI的10.68%；在圖數(shù)據(jù)p2p-Gnutella06下COO占CSCI的31.64%，CSC占CSCI的6.97%，CSR占CSCI的8.64%，DCSC占CSCI的8.67%；在圖數(shù)據(jù)soc-Epinions1下CSCI占COO的33.07%，CSC占COO的8.95%，CSR占COO的8.94%，DCSC占COO的28.09%.可以看出，3種圖數(shù)據(jù)下CSC格式的計(jì)算量最少，CSR格式相對較少，DCSC格式的計(jì)算操作量居中，COO格式的計(jì)算操作相對較多，CSCI格式的計(jì)算量最多.因此在計(jì)算量受限制的情況下，圖計(jì)算應(yīng)用優(yōu)先選擇CSC格式.

表11 3種圖數(shù)據(jù)5種圖數(shù)據(jù)格式下每條邊的計(jì)算量(指令數(shù)/邊)Table 11 Calculation amount of each side of the three graph data and five graph data formats(number of instructions/edge)

4.3 實(shí)驗(yàn)結(jié)果

分析結(jié)果可以看出5種圖數(shù)據(jù)格式在不同的圖數(shù)據(jù)下有著各自的特點(diǎn).TC算法在相同圖數(shù)據(jù)不同圖數(shù)據(jù)格式下，性能指標(biāo)執(zhí)行時(shí)間、計(jì)算量和數(shù)據(jù)移動(dòng)量在CSC格式下表現(xiàn)最好，性能指標(biāo)功耗和各級cache缺失率在DCSC格式下表現(xiàn)最好；TC算法在不同圖數(shù)據(jù)相同圖數(shù)據(jù)格式下，具有較多的邊和頂點(diǎn)的圖數(shù)據(jù)性能指標(biāo)數(shù)據(jù)偏大.相同的圖數(shù)據(jù)不同的圖數(shù)據(jù)格式對TC算法性能的影響是因?yàn)椴煌膱D數(shù)據(jù)格式對圖數(shù)據(jù)存儲(chǔ)的方式不同.COO格式采用三元組的形式直觀的存儲(chǔ)圖數(shù)據(jù)中非零元素的信息，訪問全部的頂點(diǎn)和頂點(diǎn)的的鄰接邊，故而COO格式對圖數(shù)據(jù)的查詢及訪問效率較低；CSC和CSR格式占用內(nèi)存相比于CSCI和COO較小，其中CSC格式是按列壓縮存儲(chǔ)圖數(shù)據(jù)，CSR格式是按行壓縮存儲(chǔ)圖數(shù)據(jù)的，它們存儲(chǔ)的信息是當(dāng)前活動(dòng)頂點(diǎn)的偏移量，和偏移值對應(yīng)的行列索引值，占用內(nèi)存較小，存儲(chǔ)率較高；DCSC格式是CSC的擴(kuò)展，它通過刪除零(空)列來進(jìn)一步壓縮矩陣，從而避免數(shù)組中重復(fù)的元素，因?yàn)閯h除了零列，所以需要間接指向以索引保留的非零列，對于稀疏圖數(shù)據(jù)來說存儲(chǔ)效率最高；CSCI格式是將鄰接稀疏矩陣表示的圖數(shù)據(jù)轉(zhuǎn)換成獨(dú)立稀疏列壓縮的圖數(shù)據(jù)，每列單獨(dú)壓縮后的圖數(shù)據(jù)包括列標(biāo)識數(shù)據(jù)對和非零元素?cái)?shù)據(jù)對，每個(gè)數(shù)據(jù)對包括索引和數(shù)值，由索引的最高兩位指示其余位與數(shù)值的含義，可以精確的找到頂點(diǎn)，但占用內(nèi)存相比較其他的壓縮格式較大，而具有較大邊和頂點(diǎn)的圖數(shù)據(jù)會(huì)增加算法訪問難度.

5 結(jié)束語

本文通過分析3種圖數(shù)據(jù)的5種圖數(shù)據(jù)格式(COO、CSC、CSR、DCSC和CSCI)在TC算法的性能數(shù)據(jù)，發(fā)現(xiàn)：對于TC算法，同一種圖數(shù)據(jù)下考慮執(zhí)行時(shí)間、數(shù)據(jù)移動(dòng)量和計(jì)算量時(shí)，優(yōu)先選擇CSC格式；當(dāng)考慮緩存命中率和功耗時(shí)，優(yōu)先選擇DCSC格式作；當(dāng)內(nèi)存受限時(shí)，優(yōu)先選擇DCSC格式.因此，在面對不同的應(yīng)用環(huán)境和不同的性能要求時(shí)，根據(jù)實(shí)際需求以上述結(jié)論為依據(jù)進(jìn)行調(diào)整可有效提高圖計(jì)算加速器的性能.