田 璞 蔣 林 鄧軍勇 趙一迪 劉新闖 樊 萌

1(西安郵電大學(xué)電子工程學(xué)院 陜西 西安 710121) 2(西安科技大學(xué)集成電路設(shè)計(jì)實(shí)驗(yàn)室 陜西 西安 710054)

0 引 言

大數(shù)據(jù)時(shí)代，每天產(chǎn)生的數(shù)據(jù)量呈指數(shù)增長(zhǎng)，預(yù)計(jì)到2020年，全球的數(shù)據(jù)量有望達(dá)到44 ZB[1-2]。這些數(shù)據(jù)很大一部分以圖的形式存儲(chǔ)在各個(gè)領(lǐng)域中，而圖是一種眾所周知的數(shù)據(jù)格式，例如在線(xiàn)零售、社交網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)和生物信息學(xué)中的數(shù)據(jù)以圖的形式存儲(chǔ)[3-4]?，F(xiàn)實(shí)世界中實(shí)體規(guī)模的擴(kuò)張導(dǎo)致相應(yīng)圖數(shù)據(jù)的規(guī)模有數(shù)十億個(gè)頂點(diǎn)和上萬(wàn)億條邊，龐大的頂點(diǎn)和邊構(gòu)成的結(jié)構(gòu)信息，以及頂點(diǎn)與邊附帶的各類(lèi)屬性信息使得遍歷、查找、分析等圖計(jì)算過(guò)程中無(wú)法預(yù)知相鄰頂點(diǎn)，造成存儲(chǔ)訪(fǎng)問(wèn)的隨機(jī)性強(qiáng)、局部性差，圖計(jì)算實(shí)時(shí)性強(qiáng)的高“訪(fǎng)存/計(jì)算比”不僅要求帶寬高，而且?guī)捓速M(fèi)嚴(yán)重[5-6]。真實(shí)世界圖數(shù)據(jù)的平均度數(shù)通常只有幾到幾百，與上千萬(wàn)甚至上億個(gè)頂點(diǎn)的規(guī)模相比顯得極為稀疏，且度數(shù)呈冪律分布。該分布的圖數(shù)據(jù)往往組織成鄰接稀疏矩陣的形式存儲(chǔ)，由于零元素多、規(guī)模大，壓縮以后存儲(chǔ)可以節(jié)約大量的空間[7]，常見(jiàn)的圖數(shù)據(jù)壓縮格式有壓縮稀疏列(Compressed Sparse Column，CSC)、壓縮稀疏行(Compressed Sparse Row，CSR)、坐標(biāo)列表(Coordinate List，COO)，但這些壓縮方式難以精確尋址，且現(xiàn)有的圖計(jì)算加速器需要將壓縮后的圖數(shù)據(jù)重新解壓縮才能執(zhí)行后續(xù)處理。

隨著圖計(jì)算、稀疏線(xiàn)性代數(shù)和機(jī)器學(xué)習(xí)的興起，圖計(jì)算應(yīng)用變得越來(lái)越重要和普遍[8]。對(duì)于常用的圖計(jì)算應(yīng)用，專(zhuān)用的硬件加速器是實(shí)現(xiàn)高性能低功耗的一種途徑[9-12]。根據(jù)圖計(jì)算系統(tǒng)中數(shù)據(jù)處理對(duì)象的局部性差、“訪(fǎng)存/計(jì)算比”高的實(shí)際特性，本文已經(jīng)設(shè)計(jì)了一個(gè)優(yōu)化的圖數(shù)據(jù)組織形式獨(dú)立壓縮稀疏列(Compressed Sparse Column Independently，CSCI)和圖計(jì)算加速器[13]，深入挖掘圖數(shù)據(jù)潛在并行性。

絕大多數(shù)圖計(jì)算應(yīng)用都可以映射為稀疏矩陣向量乘法運(yùn)算[14]。根據(jù)大多數(shù)流行的圖計(jì)算應(yīng)用的運(yùn)算功能，比如廣度優(yōu)先搜索算法(Breadth First Search，BFS)之類(lèi)的圖算法將比較最大/最小運(yùn)算作為核心運(yùn)算。相比之下，其他圖計(jì)算應(yīng)用(比如Page Rank)則利用算術(shù)運(yùn)算(比如求和)來(lái)迭代累加相鄰的值，直到最終收斂，所以可以將圖計(jì)算應(yīng)用分為兩類(lèi)：算術(shù)運(yùn)算和最小/最大比較[15]，各種圖計(jì)算應(yīng)用程序的核心運(yùn)算總結(jié)如表1所示[16]。經(jīng)CSCI數(shù)據(jù)存儲(chǔ)格式存儲(chǔ)的圖數(shù)據(jù)在進(jìn)行以上兩種圖應(yīng)用時(shí)，不論核心運(yùn)算是算術(shù)運(yùn)算還是比較運(yùn)算，都需要比較確定兩個(gè)矩陣列向量中的元素在同一列。由于圖數(shù)據(jù)規(guī)模大、稀疏性強(qiáng)，如何高效地實(shí)現(xiàn)兩個(gè)稀疏列向量的比較運(yùn)算就是一個(gè)值得考慮的問(wèn)題，針對(duì)這一問(wèn)題，本文提出兩個(gè)稀疏矩陣向量的比較方法。

表1 圖計(jì)算應(yīng)用的核心運(yùn)算總結(jié)

1 CSCI圖數(shù)據(jù)格式的稀疏向量比較

1.1 圖計(jì)算加速器和圖數(shù)據(jù)壓縮方法

圖計(jì)算加速器的電路結(jié)構(gòu)如圖1所示，包括預(yù)處理電路、存儲(chǔ)器、控制器、數(shù)據(jù)訪(fǎng)問(wèn)單元、調(diào)度器、混合粒度處理單元和結(jié)果產(chǎn)生單元。預(yù)處理電路根據(jù)CSCI數(shù)據(jù)壓縮方法[13]對(duì)鄰接稀疏矩陣數(shù)據(jù)進(jìn)行轉(zhuǎn)換處理。控制電路用于接收預(yù)處理電路中存儲(chǔ)完畢之后發(fā)送的轉(zhuǎn)換就緒指示信號(hào)，根據(jù)主機(jī)發(fā)送的圖計(jì)算應(yīng)用類(lèi)型控制所述數(shù)據(jù)訪(fǎng)問(wèn)單元、混合粒度處理單元、結(jié)果產(chǎn)生單元的操作。數(shù)據(jù)訪(fǎng)問(wèn)單元從所述存儲(chǔ)器中讀取CSCI的圖數(shù)據(jù)和列標(biāo)識(shí)，并根據(jù)所述根頂點(diǎn)索引、源頂點(diǎn)索引或結(jié)果產(chǎn)生單元傳送的活躍頂點(diǎn)索引計(jì)算指定頂點(diǎn)在存儲(chǔ)器中的物理地址以進(jìn)行數(shù)據(jù)訪(fǎng)問(wèn)，以及將讀取的數(shù)據(jù)傳輸?shù)秸{(diào)度器；調(diào)度器用于將CISI中列標(biāo)識(shí)指示的非零元素個(gè)數(shù)暫存，并根據(jù)所述混合粒度處理單元內(nèi)處理元的狀態(tài)信號(hào)，將暫存的數(shù)據(jù)分配到混合粒度處理單元內(nèi)的處理元進(jìn)行處理?；旌狭６忍幚韱卧鶕?jù)控制電路內(nèi)的應(yīng)用類(lèi)型和結(jié)果產(chǎn)生單元的活躍頂點(diǎn)數(shù)據(jù)對(duì)調(diào)度器內(nèi)暫存的數(shù)據(jù)進(jìn)行并行處理，并將處理后的中間數(shù)據(jù)傳輸至結(jié)果產(chǎn)生單元。結(jié)果產(chǎn)生單元根據(jù)控制電路內(nèi)的圖計(jì)算應(yīng)用類(lèi)型對(duì)中間數(shù)據(jù)進(jìn)行處理，以及將處理過(guò)程的活躍頂點(diǎn)索引發(fā)送數(shù)據(jù)訪(fǎng)問(wèn)單元，將處理后的最終結(jié)果存儲(chǔ)。

圖1 圖計(jì)算加速器的結(jié)構(gòu)

圖計(jì)算加速器的預(yù)處理電路將待處理的以鄰接矩陣表示的圖數(shù)據(jù)轉(zhuǎn)換成獨(dú)立的稀疏列壓縮CSCI格式的圖數(shù)據(jù)，每列獨(dú)立壓縮后的圖數(shù)據(jù)包括列標(biāo)識(shí)數(shù)據(jù)對(duì)和非零元素?cái)?shù)據(jù)對(duì)，每個(gè)數(shù)據(jù)對(duì)都包括索引(index)和數(shù)值(value)，索引的最高兩位指示索引其余位和數(shù)值的含義。

表2是CSCI格式中數(shù)據(jù)對(duì)的具體含義，當(dāng)index最高兩位為“01”時(shí)，index其余位表示列索引，value表示鄰接稀疏矩陣中該列的非零元素?cái)?shù)目；當(dāng)index最高兩位為“10”時(shí)，index其余位表示列索引，且該列為鄰接稀疏矩陣的最后一列，value表示鄰接矩陣中該列的非零元素?cái)?shù)目；當(dāng)index最高位為“00”時(shí)，index其余位表示行索引，value表示稀疏鄰接矩陣中對(duì)應(yīng)的非零元素值。

表2 CSCI格式中數(shù)據(jù)對(duì)含義

1.2 比較設(shè)計(jì)

經(jīng)過(guò)CSCI[13]格式壓縮過(guò)的圖數(shù)據(jù)，對(duì)于多種圖計(jì)算應(yīng)用，都會(huì)涉及到兩個(gè)稀疏矩陣列向量的比較運(yùn)算操作，為高效地實(shí)現(xiàn)兩個(gè)CSCI格式表示對(duì)的稀疏向量的比較，本文設(shè)計(jì)一種基于圖計(jì)算加速器的稀疏矩陣列向量比較電路。

(1) 整體結(jié)構(gòu)。稀疏矩陣列向量比較電路如圖2所示，假設(shè)兩個(gè)稀疏向量一個(gè)是目標(biāo)向量，一個(gè)是比較向量，該設(shè)計(jì)包括64個(gè)比較運(yùn)算電路，比較向量的所有非零元素輸入至第一個(gè)比較運(yùn)算電路，目標(biāo)向量的所有非零元素分別輸入至64個(gè)比較運(yùn)算電路。第一個(gè)比較運(yùn)算電路的輸入是所有比較向量元素和目標(biāo)向量的第一個(gè)非零元素，經(jīng)過(guò)比較運(yùn)算后可以直接輸出的元素不再輸出至第二個(gè)比較運(yùn)算電路與目標(biāo)向量的第二個(gè)非零元素進(jìn)行比較運(yùn)算，需要與目標(biāo)向量的第二個(gè)非零元素做比較運(yùn)算的元素只是比較向量非零元素的一部分，以此類(lèi)推，越后面的比較運(yùn)算電路的比較運(yùn)算操作越少，計(jì)算量越少。

(2) 比較運(yùn)算電路。每個(gè)比較運(yùn)算電路包括了操作電路、直接輸出模塊和中間輸出模塊，具體的電路設(shè)計(jì)如圖2右上部分所示。比較向量的非零元素?cái)?shù)目是64，正如操作電路(Operate Circuit，OC)中包含了8個(gè)比較單元(Compare Unit，CU)，比較運(yùn)算的結(jié)果需要傳輸至下一個(gè)比較運(yùn)算電路的非零元素通過(guò)中間輸出電路輸出，可以直接輸出的非零元素通過(guò)直接輸出電路輸出。中間輸出電路輸出的元素是運(yùn)算元素，需要在下一個(gè)比較運(yùn)算單元與下一個(gè)目標(biāo)向量的非零元素進(jìn)行比較運(yùn)算。直接輸出電路輸出的元素是輸出元素，為保證最后一級(jí)比較運(yùn)算電路輸出最終的比較運(yùn)算結(jié)果，輸出元素在每一級(jí)的比較運(yùn)算電路都是透?jìng)鳌?/p>

操作電路OC包括了8個(gè)比較單元，分別為CU0-CU7，比較向量的非零元素順序分組后，每個(gè)CU都有8個(gè)比較向量的非零元素，每個(gè)CU的具體比較過(guò)程如圖3所示，實(shí)現(xiàn)一個(gè)目標(biāo)向量非零元素和比較向量中的8個(gè)非零元素進(jìn)行比較的過(guò)程。其中：target表示目標(biāo)向量元素；com表示目標(biāo)向量的元素；“00”表示目標(biāo)向量元素的索引等于比較向量元素索引；“01”表示小于；“10”表示大于。

目標(biāo)向量元素首先與比較向量的首個(gè)元素索引進(jìn)行比較，小于或相等就可以結(jié)束比較，直接輸出相應(yīng)結(jié)果，比較向量的其他元素可以輸出至下一級(jí)進(jìn)行比較。若大于，接著與比較向量的最后一個(gè)元素索引進(jìn)行比較。若相等輸出相應(yīng)結(jié)果，本級(jí)的比較結(jié)束，小于該元素索引的比較向量元素都可以送至直接輸出模塊；若大于比較向量的最后一個(gè)元素索引，則要與下一組比較向量繼續(xù)進(jìn)行比較；若小于比較向量的最后一個(gè)元素索引，繼續(xù)按照二分法進(jìn)行比較，得到本級(jí)比較的結(jié)果。最后將可以直接輸出的向量元素送至直接輸出模塊，將需要輸出下一級(jí)比較的比較向量元素送至中間輸出模塊。

圖4是目標(biāo)向量元素和比較向量元素的行索引三種比較情況，每個(gè)CU中目標(biāo)向量的第一個(gè)非零元素與比較向量分組后的第一組8個(gè)非零元素進(jìn)行行索引比較。

若比較向量的第一組中的非零元素的最小行索引(compare0_index)都大于目標(biāo)向量第一個(gè)非零元素的行索引(target0_index)，則目標(biāo)向量的第一個(gè)非零元素可以直接輸出至直接輸出電路，分組比較單元CU0-CU7不再運(yùn)行，將不再進(jìn)行比較的比較向量的非零元素輸出至操作電路連接的中間輸出模塊，之后作為第二個(gè)比較運(yùn)算電路的輸入比較向量，繼續(xù)與目標(biāo)向量的第二個(gè)非零元素比較，如圖4中①所示。

若比較向量的第一組中的非零元素中存在與目標(biāo)向量的第一個(gè)非零元素行索引相同，則將兩個(gè)非零元素的數(shù)值進(jìn)行相應(yīng)的運(yùn)算，該結(jié)果傳輸至直接輸出電路，比較向量中其他索引小于目標(biāo)向量的第一個(gè)非零元素的索引的非零元素傳輸?shù)街苯虞敵鲭娐?，剩余大于目?biāo)向量的第一個(gè)非零元素的索引的非零元素傳輸?shù)街虚g輸出電路。剩余分組比較單元CU1-CU7不再運(yùn)行，將不再進(jìn)行比較的比較向量的非零元素輸出至操作電路連接的中間輸出模塊，之后作為第二個(gè)比較運(yùn)算電路的輸入比較向量，繼續(xù)與目標(biāo)向量的第二個(gè)非零元素比較，如圖4中②所示。

若比較向量的第一組中的非零元素的行索引均小于目標(biāo)向量第一個(gè)非零元素的行索引，將比較向量非零元素的第一組輸出至直接輸出模塊，目標(biāo)向量第一個(gè)非零元素的行索引繼續(xù)與比較向量的第二組CU2的8個(gè)非零元素的索引比較，比較方法以此類(lèi)推，如圖4中③所示。

(3) 共享存儲(chǔ)。共享存儲(chǔ)是用來(lái)存儲(chǔ)每一個(gè)比較運(yùn)算電路中可以直接輸出的向量元素，如圖5所示，共享存儲(chǔ)包括一個(gè)初始地址寄存器和一個(gè)數(shù)據(jù)存儲(chǔ)。當(dāng)一個(gè)比較運(yùn)算電路運(yùn)算結(jié)束后，根據(jù)初始存儲(chǔ)地址將數(shù)據(jù)依次存儲(chǔ)在數(shù)據(jù)存儲(chǔ)RAM中，當(dāng)把本級(jí)比較運(yùn)算電路直接輸出的向量元素存儲(chǔ)完畢會(huì)產(chǎn)生一個(gè)停止存儲(chǔ)的地址，該地址作為下一個(gè)比較運(yùn)算電路的直接輸出向量元素在共享存儲(chǔ)中的初始地址。共享存儲(chǔ)的輸出是兩個(gè)稀疏向量比較運(yùn)算的結(jié)果，當(dāng)兩個(gè)稀疏向量的所有比較運(yùn)算結(jié)束后，共享存儲(chǔ)的輸出將作為整個(gè)稀疏向量的比較運(yùn)算結(jié)果輸出，此時(shí)，兩個(gè)稀疏向量的比較運(yùn)算結(jié)束。

2 實(shí)驗(yàn)結(jié)果及分析

本文所設(shè)計(jì)的圖計(jì)算中稀疏向量的比較運(yùn)算電路，基于Verilog HDL語(yǔ)言在ModelSim SE-64 10.1c上完成設(shè)計(jì)和功能驗(yàn)證，并且采用Xilinx公司的ISE14.7開(kāi)發(fā)環(huán)境進(jìn)行綜合，使用Xilinx公司ZYNQ系列的zc706 FPGA開(kāi)發(fā)板對(duì)硬件電路進(jìn)行測(cè)試。圖數(shù)據(jù)選自斯坦福大學(xué)SNAP(Stanford Network Analysis Project)的數(shù)據(jù)集Flickr[17]。

2.1 仿真設(shè)計(jì)結(jié)果

在對(duì)本文所設(shè)計(jì)的稀疏向量比較運(yùn)算電路進(jìn)行驗(yàn)證時(shí)，首先將數(shù)據(jù)集中的非零元素轉(zhuǎn)換為CSCI格式，然后將這些壓縮過(guò)的數(shù)據(jù)作為整個(gè)設(shè)計(jì)的輸入。根據(jù)每個(gè)向量中非零元素的數(shù)目不同，分別對(duì)整個(gè)設(shè)計(jì)進(jìn)行驗(yàn)證。圖6是仿真的部分波形圖，圖6(a)是第一級(jí)比較運(yùn)算電路的波形圖，第一級(jí)比較運(yùn)算的實(shí)現(xiàn)周期是23，圖6(b)是第36級(jí)比較運(yùn)算電路的波形圖，該級(jí)比較運(yùn)算的實(shí)現(xiàn)周期是16?？梢钥闯霰容^運(yùn)算電路的實(shí)現(xiàn)周期數(shù)減少了。

(a) 第1級(jí)比較運(yùn)算電路

(b) 第36級(jí)比較運(yùn)算電路圖6 比較運(yùn)算電路仿真結(jié)果

如圖7所示，根據(jù)稀疏向量中非零元素?cái)?shù)目的不同，每一級(jí)比較運(yùn)算電路實(shí)現(xiàn)的周期數(shù)也不同，前幾級(jí)的比較運(yùn)算電路實(shí)現(xiàn)的周期數(shù)比較多，但是越往后，比較運(yùn)算電路所做的計(jì)算量越少，實(shí)現(xiàn)的周期數(shù)也越少。圖7中的比較向量/目標(biāo)向量中的非零元素?cái)?shù)目分別是：64/64、55/50、40/42、32/40、23/20，雖然非零元素的數(shù)目不同，但所呈現(xiàn)的趨勢(shì)一樣。橫坐標(biāo)表示比較運(yùn)算電路的第一級(jí)至最后一級(jí)，每八個(gè)比較運(yùn)算電路為一組，第一級(jí)的比較運(yùn)算電路實(shí)現(xiàn)的周期數(shù)目在19～26個(gè)，第二級(jí)電路的實(shí)現(xiàn)也在20～24個(gè)周期，第三級(jí)至第四級(jí)的比較運(yùn)算電路所實(shí)現(xiàn)的周期個(gè)數(shù)比前兩級(jí)明顯減少，且周期數(shù)基本保持在11～15個(gè)，后面三級(jí)的比較運(yùn)算電路實(shí)現(xiàn)的周期數(shù)也明顯的減少，甚至有的運(yùn)算電路由于非零元素?cái)?shù)目的個(gè)數(shù)太少，導(dǎo)致最后三級(jí)的比較運(yùn)算電路不執(zhí)行，直接輸出最終的比較結(jié)果。

圖7 不同非零元素?cái)?shù)目每個(gè)比較運(yùn)算電路實(shí)現(xiàn)的周期數(shù)

2.2 綜合結(jié)果

由于圖計(jì)算加速器的主要瓶頸就是在兩個(gè)稀疏向量的比較運(yùn)算上，所以本文所設(shè)計(jì)的兩個(gè)稀疏向量比較單元的性能在一定程度上可以代表整個(gè)圖計(jì)算加速器的性能。表3是與文獻(xiàn)[9]的資源利用的對(duì)比結(jié)果，可以看出，本文所設(shè)計(jì)的硬件電路LUTs資源使用減少了80 k，F(xiàn)Fs資源使用減少了281 k。

表3 本文與文獻(xiàn)[9]的資源使用對(duì)比

圖的大小是圖計(jì)算的一個(gè)關(guān)鍵性能參數(shù)，表4是各圖計(jì)算加速器所用的數(shù)據(jù)集和數(shù)據(jù)集中的頂點(diǎn)V及邊E的大小。文獻(xiàn)[9]的數(shù)據(jù)集為SpMV，文獻(xiàn)[11]和文獻(xiàn)[12]均來(lái)自社交網(wǎng)絡(luò)和合成圖Kronecker，由表4可以看出，本文所采用的數(shù)據(jù)集Flickr比文獻(xiàn)[9]的數(shù)據(jù)集規(guī)模大，最大的頂點(diǎn)數(shù)目和最大的邊數(shù)目分別是GraphSOC[9]的58倍和7.9倍，但均小于文獻(xiàn)[11]和文獻(xiàn)[12]圖的規(guī)模。GraphOps[11]和GraFBoost[12]采用的圖的大小均大于Flickr，特別是GraFBoost[12]的數(shù)據(jù)集大小遠(yuǎn)遠(yuǎn)大于Flickr。

表4 數(shù)據(jù)集和數(shù)據(jù)集中的頂點(diǎn)及邊的大小

與圖計(jì)算加速器GraphSOC[9]、GraphOps[11]和GraFBoost[12]的數(shù)據(jù)集、圖數(shù)據(jù)壓縮格式和頻率進(jìn)行了比較，結(jié)果如表5所示。GraphOps[11]采用的圖數(shù)據(jù)壓縮格式是自定義的，GraFBoost[12]采用的圖數(shù)據(jù)壓縮格式是CSR，本文采用的圖數(shù)據(jù)壓縮格式是CSCI[13]。本文硬件電路綜合的頻率均高于以上三個(gè)圖計(jì)算加速器，分別提高了5.6%、76%和111%。

在數(shù)據(jù)集大小相差不多的情況下，本文所設(shè)計(jì)的硬件電路比GraphSOC的資源使用低，且具有更高的綜合頻率。雖然綜合頻率高于GraphOps[11]和GraFBoost[12]，但是本文用于驗(yàn)證的數(shù)據(jù)集均小于這兩個(gè)加速器，并且本文設(shè)計(jì)的硬件電路是圖計(jì)算加速器的一部分。

3 結(jié) 語(yǔ)

為了高效地實(shí)現(xiàn)圖計(jì)算加速器中的稀疏矩陣列向量的比較運(yùn)算，本文設(shè)計(jì)一種稀疏矩陣列向量的比較運(yùn)算電路。本文提出的電路由64個(gè)比較運(yùn)算電路和一個(gè)共享存儲(chǔ)模塊組成，經(jīng)實(shí)驗(yàn)分析，與其他的圖計(jì)算加速器相比，具有更高的工作頻率和更少的資源利用率。通過(guò)在Xilinx公司的ZC706開(kāi)發(fā)板上進(jìn)行驗(yàn)證，表明可實(shí)現(xiàn)稀疏向量比較的功能。