• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      ?

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

      2023-01-31 12:42:06張世茹鄧軍勇
      關(guān)鍵詞:條邊數(shù)據(jù)格式功耗

      張世茹,鄧軍勇

      (西安郵電大學(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ì)算加速器的性能.

      猜你喜歡
      條邊數(shù)據(jù)格式功耗
      圖的Biharmonic指數(shù)的研究
      在智能交通系統(tǒng)中PLC數(shù)據(jù)格式轉(zhuǎn)換方法的研究
      電子測試(2018年1期)2018-04-18 11:52:49
      2018年第2期答案
      揭開GPU功耗的面紗
      數(shù)字電路功耗的分析及優(yōu)化
      電子制作(2016年19期)2016-08-24 07:49:54
      “功耗”說了算 MCU Cortex-M系列占優(yōu)
      電子世界(2015年22期)2015-12-29 02:49:44
      IGBT模型優(yōu)化及其在Buck變換器中的功耗分析
      認(rèn)識平面圖形
      論子函數(shù)在C語言數(shù)據(jù)格式輸出中的應(yīng)用
      DWG與SHP數(shù)據(jù)格式互轉(zhuǎn)換方法研究——以龍巖規(guī)劃測繪數(shù)據(jù)為例
      子洲县| 河池市| 冷水江市| 海盐县| 历史| 托里县| 万全县| 贵溪市| 临清市| 龙江县| 额尔古纳市| 富阳市| 罗田县| 聂拉木县| 报价| 满洲里市| 乳源| 南充市| 额济纳旗| 烟台市| 凤城市| 温州市| 忻州市| 青浦区| 台东县| 昌宁县| 绿春县| 桐梓县| 马关县| 永平县| 磴口县| 东乌珠穆沁旗| 德庆县| 平阴县| 乐亭县| 屯门区| 偃师市| 清苑县| 平罗县| 来宾市| 景洪市|