吳欣欣 歐 焱 李文明 王 達(dá) 張 浩 范東睿

1(計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院計(jì)算技術(shù)研究所) 北京 100190)

2(中國科學(xué)院計(jì)算技術(shù)研究所 北京 100190)

3(中國科學(xué)院大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 北京 100049)

由于嚴(yán)格的計(jì)算、存儲(chǔ)、能耗等資源的限制，領(lǐng)域?qū)Ｓ眉铀倨鱗1-2]成為CPU和GPU的可替代方案.隨著應(yīng)用的不斷發(fā)展，卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network, CNN)模型也隨之變得龐大和復(fù)雜.例如Alexnet[3]和VGG16[4]中分別包含6 000萬、1.38億個(gè)參數(shù).龐大的參數(shù)對(duì)加速器的計(jì)算、訪存產(chǎn)生沉重的負(fù)擔(dān).為有效緩解這些問題，提出了很多減少模型參數(shù)的方法，如剪枝[5]、低秩分解[6]等.這些方法利用模型參數(shù)的冗余特性[7]將密集網(wǎng)絡(luò)變成稀疏網(wǎng)絡(luò).由于CPU和GPU處理稀疏網(wǎng)絡(luò)效率很低，近年來出現(xiàn)了許多領(lǐng)域?qū)Ｓ玫南∈杈W(wǎng)絡(luò)加速器[8-13]，它們能夠充分發(fā)揮稀疏網(wǎng)絡(luò)計(jì)算和存儲(chǔ)的優(yōu)勢(shì)從而實(shí)現(xiàn)高能效.

然而由于算法和結(jié)構(gòu)的強(qiáng)耦合性，這些領(lǐng)域?qū)Ｓ眉铀倨鳡奚遂`活的結(jié)構(gòu)特性，這使它們很難應(yīng)用新的算法.例如Dadiannao[14]加速器由于沒有稀疏支持所以不能加速稀疏網(wǎng)絡(luò).Cnvlution[8]則是完全修改Dadiannao的結(jié)構(gòu)以實(shí)現(xiàn)對(duì)稀疏網(wǎng)絡(luò)的支持.SCNN[9]，EIE[10]，ESE[11]等加速器在很好地支持了稀疏網(wǎng)絡(luò)后卻不支持密集網(wǎng)絡(luò).

粗粒度數(shù)據(jù)流架構(gòu)通過靈活的指令調(diào)度實(shí)現(xiàn)不同的應(yīng)用.其在大數(shù)據(jù)、科學(xué)計(jì)算[15]、神經(jīng)網(wǎng)絡(luò)[16]等領(lǐng)域的應(yīng)用中表現(xiàn)出良好的靈活性、性能和能效優(yōu)勢(shì).粗粒度數(shù)據(jù)流架構(gòu)由相對(duì)簡單的控制電路組成處理單元陣列，陣列之間可以直接通信，從而避免了對(duì)內(nèi)存的頻繁訪問.基于一種類數(shù)據(jù)流執(zhí)行模型——Codelet執(zhí)行模型[17]，應(yīng)用程序被編譯器編譯為Codelet有向圖(Codelet directed graph, CDG)映射在處理單元陣列中.在CDG中，Codelet由指令組成，有向邊則表示Codelet之間的數(shù)據(jù)依賴性.當(dāng)Codelet中所需的數(shù)據(jù)和資源都滿足時(shí)，Codelet就會(huì)被觸發(fā)執(zhí)行，這種執(zhí)行模式最大程度地提高了Codelet指令級(jí)并行性和數(shù)據(jù)級(jí)并行性.本文基于粗粒度數(shù)據(jù)流架構(gòu)，通過研究稀疏網(wǎng)絡(luò)中權(quán)值的數(shù)據(jù)特征及指令特征，優(yōu)化網(wǎng)絡(luò)映射和執(zhí)行方式，最大程度地提高結(jié)構(gòu)效益.

在粗粒度數(shù)據(jù)流架構(gòu)中，處理單元陣列運(yùn)行時(shí)首先經(jīng)過初始化將CDG中的Codelet指令從內(nèi)存加載至處理單元陣列的指令緩存區(qū)中.當(dāng)某個(gè)Codelet所需的條件滿足后，內(nèi)部的指令逐條被發(fā)射執(zhí)行.對(duì)于CNN的密集卷積層，每個(gè)通道的卷積操作以CDG圖的形式映射到處理單元陣列上.由于規(guī)則的計(jì)算特性，不同通道形成的CDG圖內(nèi)的Codelet指令是相同的，所以Codelet指令只需加載一次即可在所有通道中實(shí)現(xiàn)卷積運(yùn)算.

然而，當(dāng)處理單元陣列執(zhí)行使用剪枝方法如文獻(xiàn)[5]獲得的稀疏網(wǎng)絡(luò)時(shí)，會(huì)產(chǎn)生2個(gè)問題：1)現(xiàn)有的逐條執(zhí)行指令方式使得權(quán)值中存在的0值相關(guān)指令無法自動(dòng)跳過，從而產(chǎn)生了無效的計(jì)算，浪費(fèi)了計(jì)算資源.2)當(dāng)稀疏網(wǎng)絡(luò)被映射在處理單元陣列上時(shí)，由于不規(guī)則的結(jié)構(gòu)特性，造成非0權(quán)值相關(guān)指令分布不均衡的現(xiàn)象.它們都增加了網(wǎng)絡(luò)的執(zhí)行時(shí)間，阻礙了網(wǎng)絡(luò)性能的提升.

基于這2個(gè)問題，本文基于粗粒度數(shù)據(jù)流架構(gòu)分別使用2種策略解決它們并實(shí)現(xiàn)稀疏網(wǎng)絡(luò)的加速.本文的貢獻(xiàn)有3個(gè)方面：

1) 通過分析稀疏網(wǎng)絡(luò)中卷積層權(quán)值的數(shù)據(jù)特征和指令特征，根據(jù)數(shù)據(jù)特征生成相應(yīng)指令的控制信息，然后在每個(gè)處理單元內(nèi)增加指令控制單元并根據(jù)指令的控制信息檢測(cè)并跳過0值相關(guān)的無效指令，從而去除無效數(shù)據(jù)運(yùn)算.

2) 通過分析現(xiàn)有的指令映射和執(zhí)行方式，并根據(jù)稀疏權(quán)值的數(shù)據(jù)特征，設(shè)計(jì)了適用于稀疏卷積網(wǎng)絡(luò)的負(fù)載均衡的指令映射算法，從而保證了處理單元陣列的負(fù)載均衡.

3) 通過對(duì)這些方法實(shí)施Benchmark，本文實(shí)現(xiàn)的稀疏卷積層比密集卷積層具有平均1.55倍的性能提升以及63.77%的能耗減少.同時(shí)與GPU(cuSparse)相比，Alexnet和VGG16網(wǎng)絡(luò)分別獲得2.39倍和2.28倍的性能提升.與Cambricon-X相比，分別獲得1.14倍和1.23倍的性能提升.

1 相關(guān)研究

稀疏卷積神經(jīng)網(wǎng)絡(luò)的出現(xiàn)有效地緩解了硬件資源的需求.為了充分利用稀疏網(wǎng)絡(luò)在存儲(chǔ)、計(jì)算方面的優(yōu)勢(shì)，出現(xiàn)了很多加速稀疏網(wǎng)絡(luò)的專用加速器.這些專用神經(jīng)網(wǎng)絡(luò)加速器利用稀疏網(wǎng)絡(luò)中激活和/或權(quán)值數(shù)據(jù)的稀疏特征，通過不傳輸0值數(shù)據(jù)或使用數(shù)據(jù)選擇模塊以跳過0值數(shù)據(jù)從而消除0值計(jì)算，最終實(shí)現(xiàn)稀疏網(wǎng)絡(luò)的加速.

EIE[10]利用稀疏網(wǎng)絡(luò)中權(quán)值稀疏和激活稀疏，結(jié)合權(quán)值共享的壓縮方法設(shè)計(jì)了稀疏矩陣向量乘單元，僅將非0操作數(shù)傳給運(yùn)算單元.然而它只加速了全連接層，未對(duì)卷積層實(shí)現(xiàn)加速.Eyeriss[18]基于最小化數(shù)據(jù)移動(dòng)功耗的數(shù)據(jù)流模型，實(shí)現(xiàn)了卷積運(yùn)算中的所有數(shù)據(jù)的復(fù)用，同時(shí)還通過門控邏輯檢測(cè)激活數(shù)據(jù)中的0值并跳過它實(shí)現(xiàn)了加速器的節(jié)能效果.然而它僅具有節(jié)能效果而沒有加速效果，同時(shí)也不能對(duì)權(quán)值稀疏的網(wǎng)絡(luò)進(jìn)行加速.為了實(shí)現(xiàn)稀疏加速，Cnvlutin[8]完全修改Dadiannao[14]的微結(jié)構(gòu)，解耦了Dadiannao的多運(yùn)算通道，并利用激活稀疏，僅傳遞非0激活值給運(yùn)算單元，實(shí)現(xiàn)了卷積層的加速.但是它卻沒有利用權(quán)值的稀疏.這些加速器或者加速了全連接層(如EIE)，或者利用了激活的稀疏性實(shí)現(xiàn)了節(jié)能(Eyeriss)和卷積層的加速(Cnvlutin)，而沒有實(shí)現(xiàn)卷積層加速或者利用權(quán)值稀疏性實(shí)現(xiàn)卷積層的加速.

Cambricon-X[12]利用權(quán)值的稀疏性，設(shè)計(jì)了數(shù)據(jù)選擇硬件模塊實(shí)現(xiàn)了非0數(shù)據(jù)的篩選，加速了卷積層和全連接層.Cambricon-S[13]使用軟硬件協(xié)同設(shè)計(jì)，在軟件層面實(shí)現(xiàn)粗粒度的剪枝方法消除網(wǎng)絡(luò)的不規(guī)則性，在硬件層面設(shè)計(jì)神經(jīng)元和突觸的選擇單元，實(shí)現(xiàn)卷積層和全連接層的加速.SCNN[9]基于笛卡兒乘積，對(duì)卷積層和全連接層的稀疏權(quán)值和激活進(jìn)行加速.雖然這些專用加速器都取得了很好的性能和功耗，但是由于算法和結(jié)構(gòu)的強(qiáng)耦合特性，它們喪失了靈活性而無法適用新的算法.與這些加速器對(duì)比，數(shù)據(jù)流體系結(jié)構(gòu)提供了更高的靈活性和更廣的應(yīng)用范圍.針對(duì)不同的應(yīng)用特點(diǎn)，它可以用于數(shù)據(jù)中心實(shí)現(xiàn)FFT，Stencil等高性能應(yīng)用[19]，也可以用于實(shí)現(xiàn)神經(jīng)網(wǎng)絡(luò)的加速[20].

文本基于粗粒度數(shù)據(jù)流架構(gòu)，其通過靈活的指令調(diào)度可以有效支持不同的應(yīng)用，同時(shí)依據(jù)應(yīng)用的特點(diǎn)充分利用其指令和數(shù)據(jù)的并行性.

2 背 景

2.1 粗粒度數(shù)據(jù)流架構(gòu)

數(shù)據(jù)流架構(gòu)分為細(xì)粒度數(shù)據(jù)流架構(gòu)和粗粒度數(shù)據(jù)流架構(gòu).在處理單元陣列之間2種數(shù)據(jù)流架構(gòu)都使用由操作數(shù)驅(qū)動(dòng)的數(shù)據(jù)流執(zhí)行模式，即一旦指令所需的操作數(shù)可用，則指令被允許執(zhí)行[21].而在處理單元內(nèi)部，細(xì)粒度數(shù)據(jù)流仍使用數(shù)據(jù)流執(zhí)行模式，如TRIPS[22]，WaveScalar[23].粗粒度數(shù)據(jù)流則使用控制流執(zhí)行模式，即使用程序控制器(program counter, PC)執(zhí)行指令，例如TERAFLUX[24]，Runnemede[25].與細(xì)粒度數(shù)據(jù)流相比，粗粒度數(shù)據(jù)流具有控制流易編譯和數(shù)據(jù)流并行性的優(yōu)點(diǎn)，所以本文的研究基于粗粒度數(shù)據(jù)流架構(gòu).

圖1是一個(gè)實(shí)例化的粗粒度數(shù)據(jù)流加速器(dataflow processing unit, DPU)，它由微控制器(micro controller, MicC)、處理單元(processing element, PE)陣列和片上網(wǎng)絡(luò)(network on chip, NoC)組成.微控制器MicC和PE陣列通過2D Mesh網(wǎng)絡(luò)相互通信.而在PE內(nèi)部，主要由流水執(zhí)行單元(pipeline execution unit)、Codelet選擇控制器(codelet choosing controller)、指令緩沖(instruction buffer)、數(shù)據(jù)緩沖(operand buffer)以及Codelet狀態(tài)寄存器(codelet status register)組成.

Fig. 1 Structure of the coarse-grained dataflow accelerator圖1 粗粒度數(shù)據(jù)流加速器的結(jié)構(gòu)

MicC管理PE陣列的執(zhí)行過程，并且還負(fù)責(zé)與主機(jī)(host)進(jìn)行通信.當(dāng)主機(jī)向MicC發(fā)送啟動(dòng)信號(hào)時(shí)，MicC啟動(dòng)PE陣列，PE陣列完成初始化工作，即將內(nèi)存(memory)中的Codelet指令加載至PE的指令緩沖區(qū)中，PE陣列執(zhí)行時(shí)根據(jù)Codelet狀態(tài)寄存器選擇就緒的Codelet，并從指令緩沖區(qū)中獲取所選的Codelet指令，送入流水執(zhí)行單元逐條執(zhí)行指令.當(dāng)PE陣列執(zhí)行結(jié)束后，MicC還會(huì)收集PE的執(zhí)行信息，并向主機(jī)發(fā)送結(jié)束信息.

為了實(shí)現(xiàn)PE內(nèi)計(jì)算單元的高利用率，應(yīng)用被編譯成Codelet模型.Codelet模型是一種類數(shù)據(jù)流并行執(zhí)行模型[17].基于該模型，所有程序被編譯成多個(gè)Codelet，每個(gè)Codelet內(nèi)部由一系列指令組成，所有的Codelet根據(jù)數(shù)據(jù)依賴性被連接成Codelet圖，然后被映射在PE陣列中，如圖2所示.當(dāng)1個(gè)Codelet所需的數(shù)據(jù)和資源滿足后，就可以被發(fā)射和執(zhí)行.基于Codelet的執(zhí)行模式最大化Codelet級(jí)指令并行和數(shù)據(jù)級(jí)并行.

Fig. 2 Codelet graph and mapping圖2 Codelet圖和映射

DPU的指令格式如圖3所示，每條指令由指令碼、源操作數(shù)索引、目的操作數(shù)索引組成.DPU指令包含了基本的運(yùn)算指令(Add，Sub，Mul，Madd)、訪存指令(Load，Store)以及PE之間直接通信指令(Copy).

Fig. 3 Instruction format圖3 指令格式

2.2 卷積神經(jīng)網(wǎng)絡(luò)

CNN主要由多個(gè)卷積層組成，它們占據(jù)整個(gè)網(wǎng)絡(luò)處理的約85%的計(jì)算時(shí)間[26]，這些卷積層執(zhí)行高維的卷積計(jì)算.卷積層在輸入特征圖(input feature map, Ifmap)上應(yīng)用濾波器(Filter)以生成輸出特征圖(onput feature map, Ofmap).卷積層的輸入數(shù)據(jù)由1組2D輸入特征圖組成，每個(gè)特征圖稱為1個(gè)通道(channel)，多個(gè)通道的輸入組成1個(gè)輸入批次(batch)，每個(gè)通道的特征值都與1個(gè)不同的2D濾波器進(jìn)行卷積運(yùn)算，所有通道上的每個(gè)點(diǎn)的卷積結(jié)果相加得到1個(gè)通道的Ofmap.表1顯示了卷積層運(yùn)算的參數(shù)描述，卷積層的計(jì)算：

(1)

Table 1 Network for Different Pruning Methods表1 卷積層參數(shù)描述

基于Codelet模型，卷積層的每個(gè)通道運(yùn)算以CDG圖的形式被映射到PE陣列中順序執(zhí)行.每個(gè)通道相同的執(zhí)行方式使得它們共用1套Codelet指令，如圖4展示了2個(gè)通道執(zhí)行1次卷積操作需要的指令.

Fig. 4 Convolution instructions for two channels圖4 2個(gè)通道的卷積運(yùn)算指令

結(jié)合圖3的指令格式和卷積的計(jì)算式(1)，在通道1中，Ifmap需要4個(gè)Load指令(Inst1到Inst4)，它們具有相同的基地址(0x0)，不同的地址偏移量(分別為0，1，3，4)和不同的操作數(shù)索引index0(分別用I0，I1，I2，I3表示).濾波器Filter也需要4個(gè)Load指令(Inst5到Inst8)，它們也具有相同的基址(0x3000)，不同的地址偏移量(分別為0，1，2，3)和不同的操作數(shù)索引index0(分別用W0，W1，W2，W3表示).執(zhí)行乘法累加運(yùn)算需要4個(gè)Madd指令(Inst9到Inst12)，它們具有相同的操作數(shù)索引index2(O0)，不同的操作數(shù)索引index0(分別為I0，I1，I2，I3)和不同的操作數(shù)索引index1(分別為W0，W1，W2，W3).卷積計(jì)算完成后，需要Store指令(Inst13)來存儲(chǔ)Ofmap值.與通道1相比，通道2通過使用不同的數(shù)據(jù)執(zhí)行相同的卷積運(yùn)算，該數(shù)據(jù)由通道偏移量、指令中的地址偏移量和基址索引index0獲得.對(duì)于每個(gè)通道相同位置的數(shù)據(jù)，其通道偏移量不同(Ifmap分別為0x0，0x400，濾波器Filter分別為0x0，0x100)，但是由于操作數(shù)索引index0，地址偏移量以及基地址索引是相同的，所以它們的指令也是相同的.例如，2個(gè)通道的Inst1指令的基地址、地址偏移和操作數(shù)index0分別為0x0，0，I0.因此，只需要從內(nèi)存加載1次指令，卷積操作就可以持續(xù)執(zhí)行，從而確保了PE陣列計(jì)算資源的充分利用.

于此同時(shí)，為了減少內(nèi)存訪問，節(jié)省數(shù)據(jù)移動(dòng)能耗，需要充分利用數(shù)據(jù)復(fù)用的特性[18].在PE陣列中，每個(gè)PE內(nèi)可實(shí)現(xiàn)卷積復(fù)用，PE之間可通過Copy指令實(shí)現(xiàn)Ifmap和Filter復(fù)用.圖5顯示了在6個(gè)PE中實(shí)現(xiàn)1個(gè)Ifmap與2個(gè)Filter的卷積操作，在圖5中，PE1，PE3，PE5使用相同的濾波器Filter1與Ifmap的不同行執(zhí)行卷積操作得到Ofmap1的不同行.同樣地，PE2，PE4，PE6使用相同的濾波器Filter2與Ifmap的不同行執(zhí)行卷積操作得到Ofmap2的不同行.由于它們使用了同一個(gè)Ifmap，所以在PE之間還可以復(fù)用Ifmap.在每個(gè)PE內(nèi)部濾波器以滑動(dòng)窗口形式應(yīng)用在Ifmap上計(jì)算Ofmap一行的所有值.不同數(shù)據(jù)的復(fù)用減少了內(nèi)存訪問，節(jié)省了數(shù)據(jù)移動(dòng)能耗.

Fig. 5 Data reuse opportunities in PE arrays圖5 PE陣列中存在的數(shù)據(jù)復(fù)用機(jī)會(huì)

由于大模型CNN對(duì)硬件資源的挑戰(zhàn)，研究人員提出許多壓縮CNN模型的方法(例如，剪枝[5]、低秩[6]、短位寬[27])，這些方法極大地減小了模型大小，且對(duì)結(jié)果精度不產(chǎn)損失或者僅有輕微的損失.這其中，使用修剪方法生成的稀疏網(wǎng)絡(luò)是有效的方法之一.先進(jìn)的剪枝方法[5]通過訓(xùn)練—剪枝—再訓(xùn)練的步驟分別將Alexnet和VGG16的網(wǎng)絡(luò)參數(shù)減少到原來的11%和7%.

3 稀疏卷積神經(jīng)網(wǎng)絡(luò)指令執(zhí)行分析

3.1 存在無效指令

在稀疏卷積神經(jīng)網(wǎng)絡(luò)中，剪枝操作將網(wǎng)絡(luò)中的一些權(quán)值置為0.基于Codelet模型，DPU編譯器將每個(gè)卷積層應(yīng)用編譯為CDG圖映射在PE陣列中，于是在Codelet中存在與0值相關(guān)的指令.由于卷積神經(jīng)網(wǎng)絡(luò)主要為乘加運(yùn)算，而0乘任何數(shù)都為0，所以稀疏卷積的運(yùn)算中存在0值相關(guān)指令的加載和執(zhí)行以及0值數(shù)據(jù)的加載和計(jì)算，這些可以被認(rèn)為是無效數(shù)據(jù)的指令和數(shù)據(jù).執(zhí)行無效的指令和數(shù)據(jù)不僅占用了加速器的硬件資源，造成資源浪費(fèi)的同時(shí)還造成加速器的功耗的增加以及PE陣列執(zhí)行時(shí)間延長.

圖6展示的是1個(gè)PE內(nèi)執(zhí)行1次卷積運(yùn)算所需的指令，可以看到為了得到Ofmap的1個(gè)值，Ifmap的I0到I8以及Filter的W0到W8需要Load指令(Inst1到Inst18)將數(shù)據(jù)從內(nèi)存加載至PE中，接著還需要Madd指令(Inst19到Inst27)執(zhí)行卷積運(yùn)算.在這些指令中，由于W2，W3，W5，W7的值均為0，所以Inst12，Inst13，Inst15，Inst17為無效的Load指令，相應(yīng)的Madd指令I(lǐng)nst21，Inst22，Inst24，Inst26也為無效的指令.為了去除0值數(shù)據(jù)的加載和計(jì)算，需要消除與0值有關(guān)的指令.然而在PE陣列中，Codelet內(nèi)指令逐條執(zhí)行的方式無法跳過這些無效指令，從而使它們占用了PE陣列的計(jì)算資源，造成計(jì)算資源的浪費(fèi)，也不能加速稀疏網(wǎng)絡(luò)的執(zhí)行過程.

Fig. 6 Instructions for calculating an output value圖6 計(jì)算一個(gè)輸出值需要的指令

如果在編譯階段只生成有效指令，則可以去除無效指令的執(zhí)行.然而，由于剪枝操作造成稀疏網(wǎng)絡(luò)不規(guī)則的運(yùn)算特性，使得每個(gè)通道的Codelet指令不再相同，從而使它們無法使用同一套指令，于是PE陣列在執(zhí)行不同通道的運(yùn)算時(shí)需要重新從內(nèi)存加載指令，而指令的加載會(huì)造成PE陣列空閑，極大地延長了卷積的執(zhí)行時(shí)間.圖7展示了Alexnet(Conv 2到Conv 5)和VGG16(Conv 1_2到Conv 5_3)兩個(gè)網(wǎng)絡(luò)密集卷積和稀疏卷積的初始化時(shí)間和執(zhí)行時(shí)間占比.從圖7可以看到，對(duì)于密集網(wǎng)絡(luò)，初始化時(shí)間即指令加載時(shí)間僅占總時(shí)間的1%，基本可以忽略不計(jì).而對(duì)于稀疏網(wǎng)絡(luò)，可以看到PE陣列的執(zhí)行時(shí)間明顯減少了，但是由于指令加載時(shí)間很長導(dǎo)致稀疏網(wǎng)絡(luò)的總時(shí)間比密集網(wǎng)絡(luò)還長，所以這種策略無法加速稀疏卷積網(wǎng)絡(luò).

Fig. 7 Comparison of time between dense convolution and sparse convolution圖7 密集卷積和稀疏卷積的時(shí)間對(duì)比

由于在粗粒度數(shù)據(jù)流架構(gòu)中，每個(gè)PE內(nèi)是控制流的執(zhí)行模式，即通過PC方式獲取Codelet內(nèi)的每條指令，因此可以增加指令控制結(jié)構(gòu)以使PE陣列在運(yùn)行過程中檢測(cè)0值相關(guān)指令并跳過它們，從而消除0值相關(guān)的操作.

3.2 指令執(zhí)行不均衡

在消除0值相關(guān)指令后，使用Han等人[5]的剪枝方法獲得的稀疏網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)映射在PE陣列上時(shí)存在非0值相關(guān)指令分布不均衡的問題.負(fù)載的不均衡導(dǎo)致硬件資源利用率降低和性能下降.如圖8所示，2個(gè)PE分別被映射2個(gè)剪枝后的濾波器Filter.由于剪枝操作，每個(gè)Filter中的非0權(quán)值個(gè)數(shù)不同，導(dǎo)致它們有效指令數(shù)不再相同.圖8中PE1和PE2分別有10個(gè)，7個(gè)非0值，由于一個(gè)權(quán)值相關(guān)的指令有Load，Madd，Copy指令，如果只執(zhí)行1次卷積運(yùn)算(如圖6所示)，PE1和PE2中與Filter相關(guān)的有效指令分別為30條(10條Load指令，10條Madd指令和10條Copy指令)和21條(7條Load指令，7條Madd指令和7條Copy指令).假設(shè)一條Load，一條Madd和一條Copy指令分別需要1個(gè)cycle，2個(gè)cycle，1個(gè)cycle的執(zhí)行時(shí)間，則PE1和PE2分別需要40個(gè)cycle和28個(gè)cycle.顯然PE1比PE2的計(jì)算忙碌，阻礙了整體性能的提升.為了利用稀疏網(wǎng)絡(luò)的計(jì)算和存儲(chǔ)優(yōu)勢(shì)，稀疏網(wǎng)絡(luò)需要被有效的處理.

Fig. 8 Filters with different numbers of non-zero values mapped in PE圖8 PE中映射的非0值個(gè)數(shù)不同的Filter

4 稀疏卷積網(wǎng)絡(luò)加速策略

為維持指令只初始化1次，即只從內(nèi)存加載1次Codelet指令，同時(shí)也要消除Codelet中的無效指令，即0值相關(guān)的指令.本文在每個(gè)PE內(nèi)部增加了指令控制器用于對(duì)即將執(zhí)行的Codelet指令進(jìn)行指令篩選，僅把有效指令傳輸給PE內(nèi)的流水執(zhí)行單元，免去無效指令的執(zhí)行從而消除無效數(shù)據(jù)的加載和運(yùn)算.然而控制單元對(duì)指令的篩選需要依賴指令標(biāo)記信息，根據(jù)指令標(biāo)記信息表征指令是否有效，從而實(shí)現(xiàn)篩選的目標(biāo).

4.1 指令標(biāo)記信息的生成

基于卷積神經(jīng)網(wǎng)絡(luò)中濾波器Filter的靜態(tài)特性，即每個(gè)卷積層的權(quán)值不隨輸入的變化而變化，所以在每個(gè)卷積層被編譯器編譯成CDG圖時(shí)，可以根據(jù)指令所需的數(shù)據(jù)特征生成指令標(biāo)記信息以標(biāo)記指令是否有效，這些標(biāo)記信息使用1和0分別表示指令的有效和無效.在PE陣列執(zhí)行Codelet的指令時(shí)，MicC會(huì)將該Codelet內(nèi)的指令標(biāo)記信息通過2D Mesh網(wǎng)絡(luò)傳輸給PE，PE內(nèi)部的PC根據(jù)該標(biāo)記信息跳過無效指令.圖9(a)為1個(gè)PE內(nèi)5×5的Ifmap與3×3的Filter生成1個(gè)Ofmap結(jié)果的卷積執(zhí)行過程.在圖中，這些相應(yīng)的指令被加載至PE中，在此次卷積運(yùn)算中，參與運(yùn)算的Ifmap的指令標(biāo)記信息全為1，參與運(yùn)算的Filter值分別為1，1，0，0，2，0，1，0，4，則其對(duì)應(yīng)的Load指令和Copy指令的標(biāo)記信息(Filter_flag)為1，1，0，0，1，0，1，0，1.當(dāng)執(zhí)行乘加運(yùn)算時(shí)，乘加運(yùn)算的指令標(biāo)記信息為Ifmap與Filter對(duì)應(yīng)位置的標(biāo)記信息的與操作，而由于Ifmap的指令標(biāo)記信息全為1，所以乘加運(yùn)算的指令標(biāo)記信息與Filter的相同，即為1，1，0，0，1，0，1，0，1.最后PE根據(jù)這些指令標(biāo)記信息選擇執(zhí)行或者不執(zhí)行指令，實(shí)現(xiàn)無效指令的跳過.

Fig. 9 Execution flow chart of instruction control unit圖9 指令控制單元的執(zhí)行流程圖

4.2 指令控制單元

圖9(b)為指令控制單元對(duì)Codelet中指令的篩選過程，它通過計(jì)算指令標(biāo)記信息Flag中的2個(gè)1之間的距離，得到2條有效指令的間隔，當(dāng)前PC與該間隔相加獲取下一條有效指令的PC值，以使PC自動(dòng)跳轉(zhuǎn)至有效指令位置，從而跳過無效指令.在流程圖中，參數(shù)i記錄待檢測(cè)的指令與當(dāng)前PC所指的指令之間的間隔，F(xiàn)lag_id表示Codelet中的指令對(duì)應(yīng)的標(biāo)記信息的索引，指令控制單元對(duì)指令標(biāo)記信息逐條檢測(cè)，直到檢測(cè)到某條指令標(biāo)記信息為1或者所有的指令標(biāo)記信息檢測(cè)結(jié)束，則流程結(jié)束.

圖9(c)為Codelet指令(對(duì)應(yīng)圖9(a)的Codelet指令)經(jīng)過指令控制單元后最終執(zhí)行的有效指令，其中Flag為Codelet的指令標(biāo)記信息，它與Codelet指令一一對(duì)應(yīng).剛開始，Inst1的Flag值為1，所以PC指向Inst1以執(zhí)行Inst1指令，執(zhí)行結(jié)束后，PC自動(dòng)加1指向Inst2，由于Inst2的Flag也為1，所以PC仍指向Inst2并執(zhí)行.如此執(zhí)行，直到Inst11執(zhí)行結(jié)束，PC自動(dòng)加1指向Inst12，因?yàn)镮nst12的Flag為0，所以指令控制單元中的i和Flag_id均加1以檢測(cè)Inst13指令的有效性，而Inst13的Flag仍為0，i和Flag_id繼續(xù)加1，此時(shí)Inst14的Flag為1，所以PC更新為PC+2，檢測(cè)結(jié)束，PC跳轉(zhuǎn)到Inst14處執(zhí)行.之后指令控制單元繼續(xù)執(zhí)行直到Codelet中的指令檢測(cè)完.所以最終PE執(zhí)行的有效指令為Inst1到Inst11，Inst14，Inst16，Inst18到Inst20，Inst23，Inst25，Inst27.

4.3 負(fù)載均衡的指令映射

基于稀疏網(wǎng)絡(luò)中計(jì)算的不規(guī)則性，映射在每個(gè)PE的Codelet中的有效指令數(shù)不再完全相同.為了保證PE陣列有效指令均勻分布和硬件資源的高利用率，需要使用負(fù)載均衡的指令映射算法.先前的工作[19]已經(jīng)提出了基于數(shù)據(jù)流的負(fù)載均衡的指令映射算法(LBC)，它基于每條指令在計(jì)算單元陣列中的位置為代價(jià)，以最小代價(jià)位置為最佳映射位置以保證負(fù)載均衡.但是對(duì)于Codelet執(zhí)行模式，Codelet內(nèi)的指令不能跨多個(gè)PE映射，使用該算法只能保證Codelet在PE陣列的均勻分布，而不能保證每個(gè)PE中Codelet內(nèi)的有效指令數(shù)相同，所以本文使用新負(fù)載均衡的指令映射算法.

根據(jù)神經(jīng)網(wǎng)絡(luò)的執(zhí)行方式，水平方向的PE使用了相同的輸入特征圖Ifmap和不同的濾波器，垂直方向上的PE使用了相同的濾波器，所以在現(xiàn)有的執(zhí)行方式中，PE中有效指令數(shù)的分布不均衡來源于濾波器中非0權(quán)值數(shù)的不同.本文基于濾波器中的非0權(quán)值個(gè)數(shù)實(shí)現(xiàn)負(fù)載均衡的有效指令映射.

由于垂直方向的PE復(fù)用了相同的濾波器，所以它們之間的有效指令數(shù)是相同的，基于此本文將PE陣列按列劃分為組.對(duì)于每個(gè)PE組，它們被映射新的濾波器的優(yōu)先級(jí)依賴于已經(jīng)存在的濾波器中的非0權(quán)值個(gè)數(shù)，擁有的非0權(quán)值數(shù)越多，其優(yōu)先級(jí)越低.

圖10為3×3的PE陣列上映射6個(gè)Filter的結(jié)果.根據(jù)算法要求，PE陣列按列分為3組，分別為G1，G2，G3.組內(nèi)PE復(fù)用相同的濾波器，初始化階段，每個(gè)PE組的優(yōu)先級(jí)設(shè)置為0，F(xiàn)ilter1首先被映射到G1后，由于Filter1中非0權(quán)值個(gè)數(shù)為5，所以G1的優(yōu)先級(jí)更新為-5，之后Filter2，F(xiàn)ilter3分別被映射在G2和G3中，G2和G3的優(yōu)先級(jí)分別更新為-4，-3.對(duì)于Filter4，由于當(dāng)前所有組中G3具有最高優(yōu)先級(jí)，所以F4被映射在G3中，同時(shí)G3的優(yōu)先級(jí)更新為-8，同理，F(xiàn)ilter5被映射在G2，F(xiàn)ilter6被映射在G1中.直到所有濾波器都被映射，算法結(jié)束.通過使用負(fù)載均衡的指令映射算法，可以看到每組PE內(nèi)非0權(quán)值數(shù)分別為7，8，8.它們對(duì)應(yīng)的有效指令條數(shù)基本一致，保證了PE陣列的負(fù)載均衡.

Fig. 10 Load balancing instruction mapping圖10 負(fù)載均衡的指令映射

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

本節(jié)在實(shí)例化的DPU上實(shí)施上述提出的方法，實(shí)現(xiàn)對(duì)稀疏的Alenet和VGG16卷積層的加速.

5.1 實(shí)驗(yàn)平臺(tái)

本文使用中國科學(xué)院計(jì)算技術(shù)研究所自主研發(fā)的大規(guī)模并行模擬框架SimICT[28]平臺(tái)，實(shí)現(xiàn)時(shí)鐘精確型的模擬器DPU，它的結(jié)構(gòu)如圖1所示，配置信息如表2所示.同時(shí)，還使用Verilog實(shí)現(xiàn)DPU的設(shè)計(jì)以及RTL級(jí)仿真，并使用12 nm的工藝進(jìn)行綜合.

Table 2 DPU Structure Configuration Information表2 DPU結(jié)構(gòu)的配置信息

整個(gè)加速器的面積為13.82 mm2，單個(gè)PE面積為0.14 mm2，在每個(gè)PE增加指令控制單元后，PE面積僅增加了6.64%，整個(gè)面積增加了4.33%.在執(zhí)行稀疏網(wǎng)絡(luò)時(shí)，指令控制單元的能耗為總能耗的0.87%，基本可以忽略不計(jì).

在本實(shí)驗(yàn)中，DPU由8×8的PE陣列組成，PE之間通過2D Mesh網(wǎng)絡(luò)連接.每個(gè)PE內(nèi)部含有1個(gè)SIMD8模式的16 b乘累加(multiply-accumulate， MAC)單元.同時(shí)還配置了8 KB的指令緩存和32 KB的數(shù)據(jù)緩存.為了提供高的網(wǎng)絡(luò)帶寬，片上網(wǎng)絡(luò)由多個(gè)獨(dú)立的2D Mesh網(wǎng)絡(luò)組成.同時(shí)在片外還使用了1 MB的Cache提供快速的內(nèi)存訪問.

5.2 基準(zhǔn)測(cè)試

本文選取了Alexnet和VGG16網(wǎng)絡(luò)模型中的卷積層作為實(shí)驗(yàn)的基準(zhǔn)測(cè)試(Benchmark)，這些卷積層具有不同的參數(shù)規(guī)模.每層中剩余權(quán)值數(shù)據(jù)的占比如表3所示.基于LLVM平臺(tái)設(shè)計(jì)的編譯器，每個(gè)卷積層被編譯為CDG圖被映射在PE陣列中.

Table 3 Benchmark Configuration Information表3 Benchmark配置信息

5.3 評(píng)估標(biāo)準(zhǔn)

通過應(yīng)用5.2節(jié)的Benchmark，本文從不同方面評(píng)估了提出的稀疏加速策略.通過與密集網(wǎng)絡(luò)對(duì)比，分別從指令執(zhí)行次數(shù)、性能和能耗方面評(píng)估并驗(yàn)證本文提出方法的有效性.同時(shí)，本文使用4片DPU實(shí)現(xiàn)的稀疏網(wǎng)絡(luò)與NVIDIA Titan XP GPU和Cambricon-X[12]加速器進(jìn)行對(duì)比，對(duì)于GPU分別使用GPU-cuBlas和GPU-cuSparse[29](基于CSR索引)實(shí)現(xiàn)密集網(wǎng)絡(luò)和稀疏網(wǎng)絡(luò).而對(duì)于負(fù)載均衡的指令調(diào)度算法，本文使用MAC部件利用率(MAC com-ponent utilization)評(píng)估負(fù)載均衡映射算法的有效性.

(2)

5.4 結(jié)果分析

1) MAC部件利用率

通過使用負(fù)載均衡的指令映射算法，保證了PE陣列的負(fù)載均衡，圖11所示為執(zhí)行VGG16 Conv 5_1卷積層水平方向的8個(gè)PE的MAC部件利用率，由于PE陣列在垂直方向上復(fù)用相同的濾波器，所以每列PE具有相同的MAC部件利用率.通過該算法，PE陣列的MAC部件利用率基本保持一致.后續(xù)也都是基于該算法實(shí)現(xiàn)所有實(shí)驗(yàn).

Fig. 11 MAC resource utilization of Conv 5_1 layer圖11 Conv 5_1層的MAC資源利用率

2) 指令執(zhí)行次數(shù)

本文對(duì)比了密集卷積層和稀疏卷積層的指令執(zhí)行次數(shù)，從圖12中可以看到，由于權(quán)值的稀疏性，通過指令控制單元，PE陣列執(zhí)行時(shí)跳過了0值相關(guān)指令，使得稀疏卷積層的指令執(zhí)行次數(shù)比密集卷積層平均減少了54.78%，其中Load，Madd，Copy指令執(zhí)行次數(shù)分別減少了3.59%，69.21%，33.74%.在圖中，Madd指令的執(zhí)行次數(shù)遠(yuǎn)遠(yuǎn)多于Load指令，表明卷積層是計(jì)算密集型的運(yùn)算.Load指令執(zhí)行次數(shù)僅減少3.59%，這因?yàn)長oad指令的執(zhí)行包含Ifmap，F(xiàn)ilter，Ofmap數(shù)據(jù)的加載，而Filter數(shù)據(jù)的占比較小，所以其Load指令的執(zhí)行次數(shù)相比于所有的Load指令的執(zhí)行，減少的少.

Fig. 12 Comparison of instruction execution times between dense and sparse layers圖12 密集層和稀疏層指令執(zhí)行次數(shù)的對(duì)比

3) 性能

圖13顯示了稀疏卷積層的性能，由于神經(jīng)網(wǎng)絡(luò)卷積層屬于計(jì)算密集型層，利用網(wǎng)絡(luò)的稀疏性去除了無效指令的執(zhí)行，使總指令執(zhí)行次數(shù)減少，提高了卷積運(yùn)算的有效性，卷積層平均性能提升了1.55倍.在圖中Alexnet的Conv 2層性能提升最多為1.92倍，VGG16的Conv 1_2層的性能提升最少為1.23倍.雖然Conv 1_2層的權(quán)值稀疏度最高為78%，但是性能提升卻最少，這是因?yàn)镃onv 1_2層與其他層相比，通道數(shù)較少，當(dāng)通道數(shù)越多時(shí)，加速器發(fā)揮的并行性也會(huì)越高.

Fig. 13 Performance comparison between dense and sparse layers圖13 密集層與稀疏層的性能對(duì)比

4) 能耗

圖14為執(zhí)行密集和稀疏卷積層的能耗分解圖，可以看到稀疏卷積層能耗平均減少了63.77%，其中乘加部件(MAC)、數(shù)據(jù)緩存(operand buffer)、指令緩存(instruction buffer)、片上數(shù)據(jù)傳輸網(wǎng)絡(luò)(NoC data transfer)的能耗分別減少了76.38%，68.06%，55.95%，8.68%.相似地，由于Filter數(shù)據(jù)占比較小，所以對(duì)于片上數(shù)據(jù)的傳輸能耗也減少的少.

Fig. 14 Energy comparison between dense and sparse layers圖14 密集層與稀疏層的能耗對(duì)比

5) 與其他加速器比較

圖15展示了使用DPU和Cambricon-X實(shí)現(xiàn)的稀疏卷積分別相對(duì)于GPU基準(zhǔn)(cuBLAS和cuSparse)在Alexnet和VGG16網(wǎng)絡(luò)上獲得的平均性能.從中可以看到，對(duì)于密集卷積(cuBLAS實(shí)現(xiàn))，DPU的性能分別是GPU的1.76倍和1.35倍，Cambricon-X的性能分別是GPU的1.47倍和1.31倍，所以DPU比Cambricon-X的性能分別提高1.19倍和1.03倍.對(duì)于稀疏卷積(cuSparse實(shí)現(xiàn))，DPU的性能分別是GPU的2.39倍和2.28倍，Cambricon-X的性能分別是GPU的2.08倍和1.85倍，所以DPU的性能比Cambricon-X分別提高1.14倍和1.23倍.實(shí)驗(yàn)結(jié)果展現(xiàn)了粗粒度數(shù)據(jù)流架構(gòu)執(zhí)行稀疏網(wǎng)絡(luò)的高性能.

Fig. 15 Speedup of DPU and Cambricon-X over GPU (cuBLAS and Sparse BLAS) baseline圖15 DPU和Cambricon-X在GPU(cuBLAS和Sparse BLAS)基準(zhǔn)上的加速比

表4列出了DPU，Cambricon-X和GPU的能效對(duì)比，可以看到DPU的能效低于Cambricon-X，而DPU的能效是GPU的12.7倍.

Table 4 Parameter Comparison of DPU, GPU and Cambricon-X表4 DPU，GPU，Cambricon-X的參數(shù)對(duì)比

7 總 結(jié)

本文基于粗粒度數(shù)據(jù)流架構(gòu)中指令映射和執(zhí)行方式，結(jié)合卷積神經(jīng)網(wǎng)絡(luò)權(quán)值數(shù)據(jù)的特征，設(shè)計(jì)了指令控制單元去除了卷積運(yùn)算中無效指令的執(zhí)行，極大地減少了指令的執(zhí)行次數(shù)，而硬件面積和能耗分別只增加4.3%和0.87%，占比很小.同時(shí)還根據(jù)卷積中稀疏權(quán)值的數(shù)據(jù)特征設(shè)計(jì)了負(fù)載均衡的指令映射算法，保證了PE陣列有效指令執(zhí)行的均衡.實(shí)驗(yàn)表明，與密集網(wǎng)絡(luò)相比，本文的方法將稀疏卷積的性能平均提升1.55倍，能耗減少63.77%.與GPU(cuSparse)相比，Alexnet和VGG16網(wǎng)絡(luò)分別獲得2.39倍和2.28倍的性能提升.與Cambricon-X相比，Alexnet和VGG16網(wǎng)絡(luò)分別獲得1.14倍和1.23倍的性能提升.

由于卷積層在整個(gè)網(wǎng)絡(luò)的執(zhí)行中占據(jù)大部分執(zhí)行時(shí)間，所以本文只實(shí)現(xiàn)了該層的加速，并沒有實(shí)現(xiàn)全連接層的加速.雖然全連接的計(jì)算可以轉(zhuǎn)化為卷積計(jì)算模式，但是現(xiàn)有方法實(shí)現(xiàn)對(duì)全連接層加速的效果有待驗(yàn)證.未來工作中，將會(huì)繼續(xù)研究稀疏網(wǎng)絡(luò)的全連接層，對(duì)其驗(yàn)證本文的方法，同時(shí)利用它的數(shù)據(jù)和指令特征設(shè)計(jì)新的指令映射和執(zhí)行方式實(shí)現(xiàn)該層的加速.