向陶然 葉笑春 李文明 馮煜晶 譚 旭 張 浩 范東睿

1(計算機體系結(jié)構(gòu)國家重點實驗室(中國科學院計算技術(shù)研究所) 北京 100190)2(中國科學院大學 北京 100049)

深度神經(jīng)網(wǎng)絡近幾年在飛速發(fā)展，它們在人臉識別、智能監(jiān)控、圖像識別、文字識別等領域有著非常出色的表現(xiàn).特別是在2012年多倫多大學的Alex Krizhevsky團隊憑借他們提出的深度神經(jīng)網(wǎng)絡分類模型AlexNet[1]，獲得了ImageNet挑戰(zhàn)賽冠軍.他們把分類誤差記錄從26%降到了15%.自此之后，大量公司和學者都投入了深度學習的研究中.

目前常用的DNN算法都具有大量的權(quán)重，其中全連接層(fully connected layers, FC layers)的權(quán)重比例非常高.例如，AlexNet有61×106的權(quán)重參數(shù)，而這其中全連接層的參數(shù)數(shù)量有59×106.VGG-16[2]有138×106的權(quán)重參數(shù)，其中全連接層的參數(shù)數(shù)量有124×106.為減少DNN算法的權(quán)重數(shù)量，文獻[3]提出了一種使用剪枝(pruning)、權(quán)值量化與共享(weight quanti-zation and shared)和哈夫曼編碼(Huffman coding)壓縮權(quán)重的方法.如表1所示，經(jīng)過剪枝后AlexNet和VGG-16在全連接層的權(quán)重數(shù)量大量減少.

Table 1Compression Statistics for FC Layers in AlexNetand VGG-16 After Pruning

表1 剪枝后AlexNet與VGG-16中全連接層剩余的有效權(quán)重比率

DNN ModelLayer#WeightsWeights Rate∕%FC638×1069AlexNetFC717×1069FC84×10625FC6103×1064VGG-16FC717×1064FC84×10623

雖然壓縮DNN可以減少存儲權(quán)重的空間，然而目前的DNN加速器并不能很好支持這樣的算法執(zhí)行.

近年來涌現(xiàn)出的許多DNN硬件加速器，例如DianNao[4],TPU[5],Eyeriss[6]等，充分利用了DNN的并行性和數(shù)據(jù)重用的特征，提出了低功耗高性能的DNN硬件加速方法.但是這些專用加速器只能運行稠密的DNN，甚至部分加速器不能支持DNN中一些常見的層，如激活層和局部響應歸一化層.只有少量加速器，如EIE[7]和Cambricon-X[8]，可以運行稀疏的神經(jīng)網(wǎng)絡.但是同樣地在這些不靈活的硬件上很難實現(xiàn)一些新的算法.

細粒度數(shù)據(jù)流加速器已經(jīng)在科學計算領域[9]和大數(shù)據(jù)領域[10]廣泛應用,它在具有高性能的同時也保持著很高的通用性.本文構(gòu)建的一個細粒度數(shù)據(jù)流加速器(fine-grained dataflow processing units, FDPU),它可以加速Stencil、FFT和矩陣乘等高性能應用[11-12]，此外文獻[13]還證明了DNN在細粒度數(shù)據(jù)流結(jié)構(gòu)上的實現(xiàn)可以獲得非常好的效率和能效比.如圖1所示，F(xiàn)DPU(16tiles，8.192Tops)在運行AlexNet各層時，相較于GPU(NVIDIA Tesla K80，8.73TFLOPS)有1.48× ～ 26×的加速.

Fig. 1 Speedup of FDPU over GPU running layers of AlexNet圖1 FDPU相比于GPU在運行AlexNet各層時的加速比

為了更高效地在細粒度數(shù)據(jù)流加速器上實現(xiàn)DNN的加速，我們提出了一種在細粒度數(shù)據(jù)流加速器上加速稀疏的全連接層的方法.這種方法可以減少加速器對內(nèi)存數(shù)據(jù)的訪問量，并且基本不增加硬件設計，同時對加速器的性能影響也較小.

本文的貢獻主要有3個方面：

1) 提出了一種適合細粒度數(shù)據(jù)流加速器的壓縮數(shù)據(jù)格式，并提出了讀取該壓縮數(shù)據(jù)格式的數(shù)據(jù)流圖.

2) 分析了全連接層的特點，為稀疏的神經(jīng)網(wǎng)絡提出了在FDPU上的加速方案.

3) 對比了FDPU與CPU，GPU和專用數(shù)據(jù)流加速器的實驗結(jié)果.從實驗結(jié)果可知，本文提出的加速稀疏的全連接層的方法相較于原有稠密的全連接層運算減少了2.44×～ 6.17×的峰值帶寬需求.在輸入圖像的批次大小(batch size)為64時，F(xiàn)DPU運行稀疏全連接層的計算部件利用率遠超過其他硬件平臺，平均比CPU,GPU和mGPU分別高了43.15%,34.57%和44.24%.

1 相關工作

1.1 通用細粒度數(shù)據(jù)流加速器

細粒度數(shù)據(jù)流架構(gòu)由Dennis[14]提出，其結(jié)構(gòu)與傳統(tǒng)的控制流架構(gòu)完全不同.細粒度數(shù)據(jù)流結(jié)構(gòu)具有較好的指令并行性、數(shù)據(jù)復用性和低功耗等特點.細粒度數(shù)據(jù)流架構(gòu)具有3種特性：

1) 數(shù)據(jù)流結(jié)構(gòu)中的指令只要其操作數(shù)準備好了即可被執(zhí)行，指令的執(zhí)行不受程序計數(shù)器和指令窗口的限制，可以充分挖掘指令級并行和數(shù)據(jù)級并行；

2) 數(shù)據(jù)在執(zhí)行單元(PE)間直接通信，避免了頻繁的數(shù)據(jù)存取，減少訪存開銷；

3) 執(zhí)行單元不需要如亂序執(zhí)行、分支預測、深度流水等復雜的邏輯控制，簡化了執(zhí)行單元的設計.

TRIPS[15]是由德克薩斯大學的Burger等人提出的細粒度數(shù)據(jù)流體系結(jié)構(gòu).TRIPS可以同時支持8個程序塊(frame)并行運行，用以掩蓋指令之間傳輸操作數(shù)的延遲.程序塊的指令被映射到4×4執(zhí)行單元(PE)陣列上，每個PE執(zhí)行被分配到的部分指令，并將執(zhí)行結(jié)果傳遞給目的指令.程序塊執(zhí)行完成后，TRIPS調(diào)度下一個程序塊，將下一個程序塊的指令映射到執(zhí)行陣列上執(zhí)行.WaveScalar[16]是華盛頓大學的Swanson提出的基于簇(cluster)的可擴展數(shù)據(jù)流體系結(jié)構(gòu).每個簇包含4個域(domains)，每個域包含8個PE.數(shù)據(jù)流程序中的每條指令被映射到PE中.在程序執(zhí)行期間，WaveScalar不斷替換無用指令并將新的未執(zhí)行指令加載到PE中，就如同波浪一樣一波一波地執(zhí)行指令.2種數(shù)據(jù)流體系結(jié)構(gòu)都是通用處理器，無法充分利用DNN中的并行性來掩蓋操作數(shù)傳輸?shù)难舆t，導致功能單元的利用率較低.

1.2 基于數(shù)據(jù)流思想的專用DNN加速器

相比于功耗較高的通用計算引擎，例如圖形處理單元(GPU)，越來越多的研究人員提出了在功耗和性能上更具優(yōu)勢的基于ASIC[17-18]或基于FPGA[19-21]的專用DNN加速器.其中基于脈動陣列的DNN加速器或者是簡單的控制數(shù)據(jù)流入流出的DNN專用加速器都可以視為數(shù)據(jù)流思想延伸的產(chǎn)物.

紐約大學的Farabet等人在2011年提出了一款面向卷積神經(jīng)網(wǎng)絡的數(shù)據(jù)流加速器NeuFlow[22]，它是一個運行時可重配置的數(shù)據(jù)流結(jié)構(gòu).DianNao[4]是由中國科學院計算技術(shù)研究所的陳云霽于2014年提出的深度學習專用加速器.它采用了基于分時復用的加速器設計結(jié)構(gòu)，該結(jié)構(gòu)由神經(jīng)功能部件(neural functional unit, NFU)和片上存儲構(gòu)成.DianNao可以說開啟了專用DNN加速芯片研究的風潮.2016年麻省理工大學的Sze提出了卷積神經(jīng)網(wǎng)絡加速器Eyeriss[6].Eyeriss使用了一種最小化數(shù)據(jù)傳輸功耗開銷的數(shù)據(jù)流模型，可以利用DNN具有的所有數(shù)據(jù)重用類型.TPU[5]是谷歌提出的機器學習專用芯片，它使用了256×256的脈動陣列加速矩陣乘和卷積，實現(xiàn)了非常高的吞吐量和極短的響應時間.FlexFlow[23]提出了基于多種并行類型互補的卷積實現(xiàn)，提高了計算資源的利用率.此外，它可以為不同的卷積層提供最優(yōu)的并行混合方案.EIE[7]是2016年斯坦福大學提出的用于加速稀疏的全連接層和RNN等神經(jīng)網(wǎng)絡的專用加速器.Cambricon-X[8]提出了一款既可以加速稠密神經(jīng)網(wǎng)絡，也可以加速稀疏神經(jīng)網(wǎng)絡的硬件加速器.但是這些專用數(shù)據(jù)流加速器為了獲得更高的性能犧牲了硬件的靈活性，有些加速器甚至不能支持DNN的全部層.相較于這些加速器，細粒度數(shù)據(jù)流體系結(jié)構(gòu)可以提供更高的靈活性和更廣的應用范圍，針對不同應用自身的特點挖掘其并行性.如本文提出的架構(gòu)可以用于數(shù)據(jù)中心[24]加速矩陣乘、FFT、Stencil等高性能應用，同時也能用于加速神經(jīng)網(wǎng)絡等應用.

2 DNN全連接層背景

DNN在各個領域和各種應用中具有不同的形狀和尺寸，比較著名的DNN模型有AlexNet[1],VGG-16[2]等，這些模型獨特的結(jié)構(gòu)決定了它們能達到的精度和效率.DNN是由一系列層(layer)構(gòu)成的，主要有卷積層(convolutional layers, CONV)、池化層(pooling layers, POOL)、全連接層(fully connected layers, FC)、激活層(activation layers, ACT)和局部響應歸一化層(local response normali-zation layers, LRN)等.DNN的輸入是一組需要被網(wǎng)絡分析的信息，這些值可以是圖像的像素、音頻的采樣幅度等數(shù)值表示.這些輸入通過DNN的推斷后，就會得到相應的分析結(jié)果.DNN的精度還與它各個層中權(quán)重的值有關，可以通過訓練對網(wǎng)絡中的權(quán)值進行調(diào)整.

全連接層是DNN的重要組成部分，是DNN所有層中參數(shù)最多的層.全連接層通過使用濾波器權(quán)重從輸入數(shù)據(jù)中提取特征.全連接層的參數(shù)如表2所示.

全連接層的輸入是由從多張輸入圖像提取出的一組2-D輸入特征圖(input feature maps)構(gòu)成.一張輸入圖像提取出的一組輸入特征圖稱為一個通道(channel)，每次輸入網(wǎng)絡的一組圖片稱為一個批次(batch).所以輸入集是一個四維張量，其參數(shù)分別是一個batch內(nèi)的圖像個數(shù)N、每張圖像的輸入特征圖數(shù)量C、輸入特征圖的行數(shù)H、輸入特征圖的列數(shù)W，本文用I∈RNCHW表示.全連接層的權(quán)重(filters)也是一個四維張量，其參數(shù)分別是每張圖像的輸入特征圖數(shù)量C、每張圖像的輸出特征圖(output feature maps)數(shù)量K、權(quán)重的行數(shù)R、權(quán)重的列數(shù)S，本文中用F∈RKCRS表示.在全連接層中，每一個結(jié)點都與上一層的所有結(jié)點相連.因此輸入特征圖與權(quán)重大小相同，即H=R,W=S.多個2-D filters會組成一個filter channel，分別與一個channel內(nèi)對應的2-D輸入特征圖卷積，所得結(jié)果累加獲得一個輸出特征圖.每個輸入channel都會和K個filter channel卷積，從而獲得輸出特征圖的四維張量，本文中用O∈RNKPQ表示(其中P是輸出特征圖的行數(shù)，Q是輸出特征圖的列數(shù)，P=Q=1).

Table 2 Parameters of FC Layers表2 全連接層的參數(shù)

可以得到全連接層的計算為

I[n][c][r][s],

(1)

0≤n

從式(1)可以看出，全連接層可以看作是輸入特征圖與權(quán)重大小相同的特殊卷積層.根據(jù)全連接的運算特點，當N=1時，通常將其轉(zhuǎn)換為矩陣向量乘計算，其形式如圖2所示.N>1時，則可以轉(zhuǎn)化為矩陣乘.

N=1時，得到全連接層的公式為

(2)

0≤n

Fig. 2 Computation of FC layers when N=1圖2 當N=1時全連接層的計算形式

3 FDPU結(jié)構(gòu)

3.1 細粒度數(shù)據(jù)流體系結(jié)構(gòu)概述

Fig. 3 FDPU architecture diagram圖3 FDPU體系結(jié)構(gòu)框圖

FDPU是面向計算密集型的、具有簡單的訪存模式和數(shù)據(jù)重用特征應用的細粒度數(shù)據(jù)流加速芯片.FDPU是基于ASIC實現(xiàn)的，它支持細粒度數(shù)據(jù)流指令集，通過最大化數(shù)據(jù)流指令級并行性提高其性能.FDPU的總體結(jié)構(gòu)如圖3所示.FDPU是由執(zhí)行單元(processing element, PE)、數(shù)據(jù)緩存(data buffer, Dbuf)、指令緩存(command buffer, Cbuf)、一個微控制器(micro controller, MicC)和一個直接存儲器存取(direct memory access, DMA)組成.PE陣列呈二維結(jié)構(gòu)排列.Dbuf和Cbuf是用便簽式存儲(scratch pad memory, SPM)的存儲訪問形式實現(xiàn)的.Dbuf分布在PE陣列的周圍，Cbuf則位于PE陣列的左側(cè).MicC用于控制指令在PE上的執(zhí)行.PE，Dbuf，Cbuf，MicC通過2-D mesh網(wǎng)絡相互通信.

1) PE.PE的內(nèi)部結(jié)構(gòu)如圖3的下半部分所示.每個PE包含可流水的執(zhí)行單元、指令緩沖、操作數(shù)緩沖、指令發(fā)射控制器和本地寄存器單元.

2) Dbuf.用于存儲數(shù)據(jù)，被所有PE共享.

3) Cbuf.用于存儲要映射到PE中的指令和PE的本地寄存器值.

4) MicC.負責控制加速器的運行過程.執(zhí)行開始時，CPU會向MicC發(fā)送請求啟動加速器.然后MicC會通過Mesh網(wǎng)絡把Cbuf中存儲的指令和本地寄存器的值送到PE內(nèi).PE初始化完成后，MicC會向PE陣列流水地發(fā)送上下文啟動指令和上下文ID，并收集PE發(fā)來的上下文結(jié)束消息.當PE陣列將所有上下文都執(zhí)行完后，MicC會向CPU發(fā)送結(jié)束消息.

5) NoC.Router之間采用靜態(tài)XY(X方向優(yōu)先)的確定性路由策略.

6) DMA.負責Cbuf、Dbuf和內(nèi)存的數(shù)據(jù)交換.

3.2 并行模式

傳統(tǒng)細粒度數(shù)據(jù)流架構(gòu)(如TRIPS[15])，將應用的程序劃分為多個塊，程序塊之間必須串行執(zhí)行.只有前一個程序塊執(zhí)行完后，才會載入和運行新的程序塊，這造成計算部件的利用率不高.因此，F(xiàn)DPU不只是簡單地采用了數(shù)據(jù)流模式，還采用了循環(huán)流水[25]的優(yōu)化方法提高計算部件的利用率.

Fig. 4 Process of dataflow executing圖4 數(shù)據(jù)流執(zhí)行過程

1) 數(shù)據(jù)流模式

數(shù)據(jù)流模式是一種與傳統(tǒng)控制流完全不同的計算模式.在傳統(tǒng)控制流處理器中，指令按照程序計數(shù)器(program counter, PC)的順序執(zhí)行.但是，在數(shù)據(jù)流模式中，只要指令的操作數(shù)準備好了，那么這條指令即可被執(zhí)行.

在數(shù)據(jù)流計算中，程序是以數(shù)據(jù)流圖表示的，每條指令的執(zhí)行結(jié)果直接傳遞到另外一條指令，指令與指令之間通過依賴邊來建立依賴關系，從而形成數(shù)據(jù)流圖.數(shù)據(jù)流圖中的每個節(jié)點表示一條指令，每條邊表示一條指令與另一條指令之間的依賴關系.如圖4(a)所示，把數(shù)送入數(shù)據(jù)流圖，指令就會依據(jù)依賴關系依次被發(fā)射.例如當Inst3收到Inst0和Inst1輸出的結(jié)果后，Inst3就可以執(zhí)行了.

在PE中，操作數(shù)緩沖中的每一個條目是被一條指令私有的，存儲屬于這條指令的所有操作數(shù).指令發(fā)射控制器會監(jiān)視指令所需的所有操作數(shù)是否都已就位.當指令滿足發(fā)射條件，指令發(fā)射控制器會將指令和其操作數(shù)送入譯碼器中.譯碼完成后，opcode和操作數(shù)被送入可流水的計算部件中.最終，指令的計算結(jié)果會通過Mesh網(wǎng)絡傳輸?shù)紻buf中或依賴于這條指令的其他指令的數(shù)據(jù)緩沖條目中.

數(shù)據(jù)流圖的指令會被映射到PE中，圖4(b)給出了圖4(a)中的一種可能的映射結(jié)果.文獻[26]提出了一種在細粒度數(shù)據(jù)流體系結(jié)構(gòu)中使用的指令映射算法——基于負載均衡(load balance centric, LBC)的指令映射算法.LBC算法按照深度的優(yōu)先順序依次映射數(shù)據(jù)流圖中的所有指令，對每條指令分別計算執(zhí)行單元陣列中所有位置的代價，取最小代價的位置作為最佳映射位置.在本文中，為了獲得盡可能更優(yōu)的性能，數(shù)據(jù)流圖的映射則是采用了手動映射的方法.

2) 循環(huán)流水模式

數(shù)據(jù)流程序可以在加速器上被多次執(zhí)行，一個數(shù)據(jù)流程序的一次完整執(zhí)行稱為一個上下文.循環(huán)流水的優(yōu)化方法面向具有可分塊和并行性特征的應用，進一步利用上下文間的并行處理特征修改數(shù)據(jù)流結(jié)構(gòu)中上下文切換邏輯，使每一個上下文的開始不需要等待上一個上下文的結(jié)束.這樣循環(huán)流水化結(jié)構(gòu)上的多個上下文以流水線的方式進入執(zhí)行陣列，數(shù)據(jù)流圖中的每一條指令在執(zhí)行一次后會立刻接收到下一個上下文的操作數(shù)，使執(zhí)行單元的利用率得到極大的提高.

如圖4(c)所示，多個上下文以流水線的方式流過整個數(shù)據(jù)圖，結(jié)果以流的方式從數(shù)據(jù)流圖中流出.Inst5執(zhí)行完上下文1的數(shù)據(jù)操作后，立刻接收到上下文2的操作數(shù)，可以再次執(zhí)行運算.用戶只需要配置MicC，設置好需要計算的上下文數(shù)量.FDPU開始計算后，MicC將上下文流水送入執(zhí)行陣列，并統(tǒng)計已經(jīng)完成的上下文數(shù)量，確定當前計算是否完成.在上下文之間完全沒有數(shù)據(jù)依賴時，所有上下文可以在加速器上充分流水；若上下文間有數(shù)據(jù)依賴，可通過MicC中的上下文控制邏輯控制上下文進入執(zhí)行陣列的時間，維持有數(shù)據(jù)依賴的上下文之間的順序.

3.3 數(shù)據(jù)流指令集

FDPU的指令格式如圖5所示.每個指令由指令碼、指令依賴的源操作數(shù)個數(shù)、立即數(shù)、結(jié)果的目的地址組成.目的地址指向某個PE中的操作數(shù)緩沖的地址.FDPU的指令集包含了基礎的運算指令、訪存指令和循環(huán)指令[27]等.表3列出了本文中用到的數(shù)據(jù)流指令和指令對應的功能.

Fig. 5 Instruction format of FDPU
圖5 FDPU的指令格式

Fig. 6 A dataflow diagram with SWITCH instruction圖6 使用SWITCH指令的數(shù)據(jù)流圖例子

Table 3 Descriptions of Dataflow Instructions表3 數(shù)據(jù)流指令描述

4 基于稀疏的全連接層加速方案

4.1 細粒度數(shù)據(jù)流分支指令設計

為了增加數(shù)據(jù)流程序的控制能力、更好地支持稀疏的全連接層，本文設計了用于細粒度數(shù)據(jù)流結(jié)構(gòu)的分支指令——SWITCH指令.SWITCH語句會根據(jù)上游給它的第2個操作數(shù)的值與0比大小的結(jié)果判斷將數(shù)據(jù)發(fā)送給哪些下游指令.圖6是一個使用SWITCH指令的數(shù)據(jù)流程序例子.圖6(a)是這個數(shù)據(jù)流程序?qū)崿F(xiàn)功能的偽代碼.如果EQ發(fā)送給SWITCH0的值大于0，則SWITCH0會沿著點劃線發(fā)送從LD0接收來的數(shù)據(jù)，接著會執(zhí)行IMM1,MUL0指令；如果EQ發(fā)送給SWITCH0的值等于0，則SWITCH0會沿著粗實線發(fā)送從LD0接收來數(shù)據(jù)，接著會執(zhí)行IMM3指令.點劃線和粗實線最終都會將數(shù)據(jù)傳輸?shù)酵粋€指令的相同操作數(shù)位置，保證不論走哪個分支下游指令均可以發(fā)射.

可以看到圖6中ADD0指令有一條虛線指向SWITCH0，這條依賴邊是為了保證在循環(huán)流水模式下，上下文流過SWITCH0的數(shù)據(jù)順序與流過ADD0的數(shù)據(jù)順序是一致的.如圖7(a)所示，在沒有ADD0指向SWITCH0的數(shù)據(jù)依賴邊時，當2個上下文的數(shù)據(jù)在不同的分支流動，后運行的上下文的數(shù)據(jù)有可能會先于前面的上下文到達后續(xù)的指令.這是因為指令執(zhí)行(數(shù)據(jù)流指令的發(fā)射沒有固定的順序)和數(shù)據(jù)在片上網(wǎng)絡傳輸?shù)难舆t是不確定的，這種情況會造成運算結(jié)果的錯誤.

在匯合指令ADD0增加一條指向SWITCH0的依賴邊可以解決這樣的問題，這條邊被稱為反饋依賴邊.SWITCH指令被增加了一個源操作數(shù)用于接收反饋信號，在執(zhí)行初始狀態(tài)下，這個操作數(shù)被初始化為已經(jīng)收到；運行過程中，每次SWITCH執(zhí)行后都需要等到分支后的某個匯合指令給它發(fā)送的操作數(shù)，才能進行下一次運算.如圖7(b)中，ADD0擔任了匯合指令的作用.匯合指令可以是任意種類的指令，但它必須是SWITCH指令的2個分支匯合后的數(shù)據(jù)流指令.這樣的方式可以在不增加硬件開銷的情況下保證SWITCH和其后的指令的數(shù)據(jù)流動順序一致.

Fig. 7 Function description of the feedback data dependence edge of SWITCH圖7 SWITCH指令的反饋依賴邊的功能說明

4.2 面向細粒度數(shù)據(jù)流的稀疏存儲格式

常用的稀疏矩陣存儲格式有很多，比如坐標格式(coordinate format, COO)、壓縮稀疏行格式(compressed sparse row, CSR)等.但是由于數(shù)據(jù)流程序的控制性較弱，無法靈活地控制循環(huán)次數(shù)等，在這些格式很難用數(shù)據(jù)流程序高效解析.比如COO，它用一個三元組表示，分別是(行號，列號，數(shù)值).讀取到當前數(shù)據(jù)的行號與列號后，才能知道數(shù)據(jù)的位置，很難將數(shù)據(jù)劃分為多個上下文并行處理.而CSR格式，雖然其格式可以方便地推算得到每行數(shù)據(jù)的數(shù)量和數(shù)據(jù)的起始位置，便于劃分數(shù)據(jù)，但是由于每行數(shù)據(jù)的數(shù)量不確定，數(shù)據(jù)流圖無法確定.對于細粒度數(shù)據(jù)流加速器，需要一種更具有“確定性”的稀疏矩陣存儲格式.

本文提出了一種類似于CSR的存儲格式，稱為面向細粒度數(shù)據(jù)流的壓縮稀疏行格式(fine-grained dataflow CSR, FD-CSR).FD-CSR與CSR相同，也由3部分組成：數(shù)值(values)、列號(column indices)以及行偏移(row offsets).數(shù)值用于存儲數(shù)組中所有的非零元素；列號的每一個比特標志了一行數(shù)據(jù)中每個元素是否為0；行偏移則表示每行的第1個非零元素在value中的偏移位置.通過這樣的設計，可以使列號和行偏移都成為固定長度的數(shù)組，方便數(shù)據(jù)流程序進行讀取.

Fig. 9 Basic operation of FC layers圖9 全連接層的基本操作

如圖8所示，一個任意長度的一維數(shù)組會被重新排列為每行16個元素的二維數(shù)組.這是因為每個列號的數(shù)據(jù)位寬是16 bit，只能表示最多16個元素的有效位.列號的每一個比特代表其對應的數(shù)據(jù)是否為0，如第1個列號為6339，其二進制數(shù)值為0001100011000011(最低位對應第1行的第1個數(shù)據(jù)，最高位對應第1行的最后一個數(shù)據(jù)).該數(shù)組壓縮后的列號和行偏移的數(shù)據(jù)個數(shù)均為二維數(shù)組的行數(shù)，數(shù)值的數(shù)據(jù)個數(shù)則為數(shù)組中非零元素的個數(shù).

Fig. 8 Format of FD-CSR圖8 FD-CSR稀疏矩陣存儲格式

這樣的稀疏矩陣存儲格式的設計可以將列號和行偏移的個數(shù)固定.本文設計的數(shù)據(jù)流圖會通過對列號和行偏移的分析，同時使用SWITCH語句，實現(xiàn)對不定個數(shù)的數(shù)值的解析訪問.

4.3 讀取稀疏存儲格式的數(shù)據(jù)流圖設計

全連接層的計算通常被轉(zhuǎn)化為矩陣向量乘.矩陣向量乘是由大量的向量點積組成的，其操作如圖9(a)所示，其中A代表權(quán)重的一行，B代表輸入特征圖，C代表輸出特征圖的一個元素.A的每個元素與對應的B元素相乘，其結(jié)果進行累加，最終得到C.在稠密的矩陣向量乘中，數(shù)據(jù)流圖被寫為圖9(b)的形式.在稀疏的全連接層中，權(quán)重使用了稀疏矩陣存儲格式進行存儲.為了讀取稀疏的權(quán)重，本文提出了如圖9(c)所示的數(shù)據(jù)流圖.

數(shù)據(jù)流圖首先獲取了本行的列號和行偏移.列號被共享給了多條指令，AND0將列號與0x1按位與，獲得了本行第1個數(shù)是否為非零數(shù)的結(jié)果.同樣AND1,AND2,AND3分別將右移了1位、2位、3位的值與0x1按位與，分別獲得了對應的數(shù)據(jù)是否為非零數(shù)的結(jié)果.行偏移首先被減一，然后與AND0輸出的結(jié)果相加.如果AND0輸出1，那么ADD0算出的就是本行第1個數(shù)在數(shù)值向量中的偏移.ADD0的結(jié)果會傳給下一個ADD，只有AND輸出的值為1時，即對應數(shù)據(jù)是非零數(shù)，ADD的輸出結(jié)果才是對應數(shù)據(jù)在數(shù)值向量中的地址偏移.AND與ADD的結(jié)果均會被傳給SWITCH指令.當AND輸出1時，SWITCH會把ADD算出的偏移傳給LD指令，LD指令從對應的存儲地址取數(shù)并把獲取到的數(shù)發(fā)送給FMUL或FMADD.當AND輸出0時，SWITCH則會傳輸數(shù)據(jù)給FIMM，F(xiàn)IMM則將0值發(fā)送給下游.FMUL指令和FMADD指令會從2條分支中的一條獲得向量A中的一個元素，并與從LD指令傳輸來的向量B的元素相乘.FMADD指令將乘積與上游送來的C的部分和進行累加，最終得到C.

5 實驗與結(jié)果

在本節(jié)中，我們使用本文提出的方法，在FDPU上加速運算了經(jīng)過剪枝后的AlexNet和VGG-16中的稀疏全連接層.

5.1 度量標準

本文使用了計算部件利用率(computing resource utilization)來評估稀疏神經(jīng)網(wǎng)絡在不同峰值性能的硬件加速器的優(yōu)化效果.

(3)

Fig. 10 Computing resource utilization of dense FC layers and sparse FC layers for FDPU圖10 FDPU運行稠密全連接層和稀疏全連接層時的計算部件利用率

5.2 實驗平臺

我們以中國科學院計算技術(shù)研究所自主研發(fā)的大規(guī)模并行模擬框架SimICT[28]為平臺，實現(xiàn)了一個C語言的精確于時鐘的模擬器.實驗環(huán)境具體配置如表1所示.FDPU模擬器的結(jié)構(gòu)如圖3所示，主要包含ARM處理器、DMA控制器、內(nèi)存和FDPU等模擬組件.

FDPU加速器由8×8個PE、32個Dbuf、8個Cbuf、1個微控制器(MicC)和1個DMA控制器組成.所有Dbuf的大小均為2 MB，每個PE內(nèi)的操作數(shù)緩沖為6 KB.浮點數(shù)據(jù)均使用16-bit表示.每個PE有2個32-bit的定點乘加器、用于計算loadstore的地址索引以及16-bit的SIMD4的乘加器.FDPU運行時的頻率為1 GHz，其峰值性能為512 Gops.

我們用verilog對FDPU設計進行了實現(xiàn)和rtl級仿真，并對模擬器進行了時鐘級的校準.然后用45 nm的工藝進行了綜合，最終得到的面積約為44 mm2，功耗約為3.27 W.

實驗中的對比基準我們使用了CPU(Intel Core i-7 5930k)，GPU(NVIDIA GeForce GTX Titan X)和Mobile GPU(NVIDIA Tegra K1).其性能數(shù)據(jù)均來自文獻[7].

5.3 數(shù)據(jù)集

我們選擇了AlexNet和VGG-16中稀疏程度差異較大的3個層進行性能對比，這3個層分別是AlexNet-FC6，AlexNet-FC8和VGG16-FC7，它們的稀疏性分別為9%，25%，4%.我們對比了運行稠密的全連接層和稀疏的全連接層的性能.其中稠密的全連接層來自Caffe model zone，稀疏的全連接層使用了文獻[3]中剪枝的算法生成.

5.4 實驗和結(jié)果

圖10展示了FDPU在加速稀疏全連接層與稠密全連接層所實現(xiàn)的計算部件利用率.我們可以看出，本文提出的稀疏全連接層的加速方法雖然相較于稠密的全連接層增加了大量的指令，但是僅有少量的性能損失.其中在batch size為1和4時，兩者的性能差距最高為1.4%；在batch size為64時，稀疏全連接層的計算部件利用率平均比稠密的低11.7%.其主要原因在于batch size較小時，全連接層的數(shù)據(jù)復用程度很低，此時不論是稠密的還是稀疏的全連接層數(shù)據(jù)流圖中計算指令的比例較低，訪存和計算訪存地址的指令比例較高.這使得因讀取稀疏矩陣數(shù)據(jù)所增加的指令在訪存指令的占比很低，導致稀疏與稠密的全連接層運行時計算部件的利用率相近.而batch size為64時，因數(shù)據(jù)在全連接層的復用程度增高，全連接層數(shù)據(jù)流圖中計算指令的比例增加，使得因讀取稀疏矩陣數(shù)據(jù)所增加的指令在訪存指令的占比增高，導致了稀疏全連接層的性能較稠密的全連接層有較大的性能下降.

從圖10中我們還可以發(fā)現(xiàn)本文提出的稀疏全連接層的加速方法在不同的稀疏比例的全連接層中計算部件利用率基本相等.這是因為我們提出的方案為了適應細粒度數(shù)據(jù)流結(jié)構(gòu)，采取了比較穩(wěn)定的數(shù)據(jù)流圖設計.對于不同的全連接層，其數(shù)據(jù)流圖的流動方式、執(zhí)行的指令條數(shù)相差不大.對于每個權(quán)重，不論其是否為非零值，我們都會計算出其對應的地址索引.因此在不同的稀疏比例的全連接層中，F(xiàn)DPU獲得的計算部件利用率非常接近.

圖11展示了FDPU運行稀疏全連接層相較于稠密全連接層對帶寬需求的減少比.稀疏全連接層相較于稠密全連接層可以減少2.44×～ 6.17×的峰值帶寬需求.

Fig. 11 Bandwidtion requirement reduction of sparse FC layers over dense FC layers圖11 稀疏FC層相較于稠密FC層對帶寬需求的減少比

表4列出了FDPU與CPU，GPU和mGPU在運行batch size為64的稀疏全連接層時的計算部件利用率對比.可以看到，F(xiàn)DPU的計算部件利用率遠超過其他硬件平臺，平均比CPU，GPU和mGPU分別高了43.15%，34.57%和44.24%.

表5列出了FDPU與CPU,GPU和mGPU在運行稀疏全連接層時的峰值性能、面積效率和能效等的對比.其中FDPU的面積效率是CPU和GPU的17.9倍和2.7倍，能效是CPU,GPU和mGPU的50倍、9.7倍和7.9倍.

Table 4Computing Resource Utilization Comparison of FDPUand Other Platforms for Running Sparse FC Layers

表4 FDPU與其他平臺運行稀疏FC層時的計算部件利用率對比%

Table 5 Area Efficiency and Energy Efficiency Comparison of CPU, GPU, mGPU, and FDPU表5 FDPU與CPU,GPU和mGPU的面積效率和能效對比

6 關于卷積層的討論

本文提出的方法主要利用了權(quán)重的稀疏性.卷積層在FDPU上實現(xiàn)是通過循環(huán)展開成矩陣乘的方式實現(xiàn).因此，卷積層也可以利用這種方法減少存儲空間和訪存帶寬需求.但是在卷積層中權(quán)重占輸入數(shù)據(jù)的比重相較于全連接層較小，例如在batch size為64時，AlexNet中的5個卷積層中權(quán)重分別占輸入數(shù)據(jù)的0.35%,9.43%,19.35%,19.35%和13.79%.本文提出的方法對于卷積層的存儲空間和帶寬需求的改善很小，但是會造成一定的性能下降.因此在FDPU上目前卷積層還是用稠密的方式存儲權(quán)重和計算.未來我們會進一步研究如何避免零值權(quán)重的計算，從而提高FDPU加速卷積層和全連接層的性能.

7 總 結(jié)

為了更高效地在細粒度數(shù)據(jù)流加速器上實現(xiàn)DNN的加速，我們提出了一種在細粒度數(shù)據(jù)流加速器上加速稀疏的全連接層的方法.這種方法可以減少加速器對內(nèi)存數(shù)據(jù)的訪問量，并且基本不增加硬件設計，同時對加速器的性能影響也較小.本文提出的加速稀疏的全連接層的方法相較于原有稠密的全連接層運算減少了2.44×～ 6.17×的峰值帶寬需求.在batch size為64時，F(xiàn)DPU運行稀疏全連接層的計算部件利用率遠超過其他硬件平臺，平均比CPU,GPU和mGPU分別高了43.15%,34.57%和44.24%.但是本文中提出的方法無法利用全連接層的稀疏性減少運行的指令條數(shù).未來工作中，我們會繼續(xù)研究稀疏全連接層的加速，目標是設計出可以利用權(quán)重的稀疏性減少計算的數(shù)據(jù)流圖.