深入理解DNN加速器中的基本單元——DSP

DNN加速器的設(shè)計一直在兩個方面使力：通用架構(gòu)和高效性能。通用性需要自頂向下的設(shè)計，首先綜合各種神經(jīng)網(wǎng)絡(luò)的算子設(shè)計一套標(biāo)準(zhǔn)的指令集，然后根據(jù)硬件平臺的特點，考察計算資源，存儲資源以及帶寬，進(jìn)行硬件的模塊化設(shè)計，在指令集以及硬件的特殊結(jié)構(gòu)基礎(chǔ)上，再去構(gòu)建工具鏈。

通用性要看的廣，指令集的定義要具有擴展性和靈活性，工具鏈要能夠靈活的對接不同的深度學(xué)習(xí)框架，能夠處理不同類型的網(wǎng)絡(luò)。這是一個很大的工程，需要一個頂級架構(gòu)師以及大批軟件編譯類工程師合力來做。

但是現(xiàn)在出現(xiàn)的很多開源工具鏈框架將這種開發(fā)難度大大降低了，比如TVM，LLVM，MLIR等工具給我們提供了基礎(chǔ)，避免了再造輪子的重負(fù)。很多公司也基于這些開源框架來編寫自己的編譯工具。

高效性能永遠(yuǎn)是各大芯片廠商比拼的焦點，性能的提升需要三個方面共同努力：一個是來自于芯片的廣大的資源，包括計算資源和存儲資源，以及高帶寬，從Xilinx芯片不斷加大尺寸和DSP數(shù)量，以及采用HBM，還有GPU內(nèi)核數(shù)量的提升以及對HBM的采用都說明了這個問題；

另外一個是算法的深度優(yōu)化，神經(jīng)網(wǎng)絡(luò)對噪聲的容納能力讓其有了很多可以利用的空間，比如int類型的量化，稀疏化，剪枝等等，可以在保證精度的前提下，大大降低其運算量以及參數(shù)數(shù)量，同時能夠更好的適配硬件；

第三就是需要編譯器對指令的優(yōu)化，算符融合，無效算子的kill，指令的schedule等等，都會對最后性能造成很深的影響。提升性能需要看的深，追求硬件，算法，編譯的極限，盡最大可能利用硬件有限的資源，盡最大可能優(yōu)化網(wǎng)絡(luò)的結(jié)構(gòu)，盡最大可能尋求指令序列的優(yōu)化解。今天我們談性能追求當(dāng)中的一個很小的部分——DSP。

Xilinx DSP

1 結(jié)構(gòu)和功能

DSP48E2是zynq器件中使用的DSP類型，其主要結(jié)構(gòu)包括一個27bit前加器，27x18bit的乘法器，一個48bit的可以執(zhí)行加減法，累加以及邏輯功能的ALU。如下圖所示：

DSP48E2單元的功能包括：

1） 前加器可以計算D+/-A以及D+/-B的功能，這大大擴展了A和B端口的公用。通過對A和B的選擇，可以增加乘數(shù)的寬度，利用這個可以將神經(jīng)網(wǎng)絡(luò)的算力提高一倍甚至兩倍，后邊我們具體再講。

2） 前加器可以將結(jié)果發(fā)送到乘法器，所以提供了平方操作，比如A*A。

3） A端口的低27bit用于乘法器輸入，30bit完整數(shù)據(jù)可以和B端口數(shù)據(jù)concate實現(xiàn)48bit數(shù)據(jù)的ALU操作，包括與或非等邏輯運算以及加減法計算。

4） 端口CARRYCASCIN和CARRYCASCOUT能夠用于多個DSP級聯(lián)，這對于實現(xiàn)神經(jīng)網(wǎng)絡(luò)中的矩陣乘法或者卷積的累加非常方便。

5） 基于SIMD模式的加減法操作，可以支持2路24bit加減法以及4路12bit加減法。

6） 支持48bit的邏輯操作：and， or， not， nand， nor以及xnor。

7） 支持一些類型檢測：overflow/underflow，rounding等。

8） 支持17bit右移操作。

9） DSP單元是單時鐘同步運轉(zhuǎn)的，始終頻率能夠達(dá)到內(nèi)部memory頻率的兩倍，相對內(nèi)部邏輯，DSP可以工作在倍頻下。

DSP支持的操作類型很多，主要用于兩方面：一個是基于大量乘累加的計算，比如conv，gemm，F(xiàn)FT等。另外一種是純加減法和邏輯的運算，這些在神經(jīng)網(wǎng)絡(luò)中也有很多，比如element-wise add。邏輯運算用的不多，更多可能作為一些計算的輔助。

Zynq器件中通常將2個DSP48E2和一個36Kb的block memory以及5個CLB放置在一起，一個36Kb的BRAM可以拆分成2個18Kb的memory使用，每個memory可以獨自被一個DSP占用。

這樣的配置也為DSP以及存儲的高效配合使用提供了模板。后邊我們可以利用這樣的結(jié)構(gòu)構(gòu)建一個conv計算單元。同時多個DSP在FPGA芯片內(nèi)部是垂直擺放的，這有利于多個DSP的cascade。

現(xiàn)在來看一下如何使用DSP陣列來構(gòu)建低功耗的加法樹。在傳統(tǒng)的FIR濾波器中，乘累加的普遍做法是將多個乘法的輸出通過多級加法器累加起來，需要的加法器級數(shù)是計算數(shù)據(jù)量的log2函數(shù)。

這樣的加法樹會消耗更多的資源，代價以及能耗。特別是后幾級的加法器位寬變的越來越寬，對LUT資源消耗很多。如果我們利用DSP的級聯(lián)功能，可以完全實現(xiàn)FIR中的多輸入加法功能。

DSP中提供的post-adder以及CARRYCASCIN和CARRYCASCOUT可以選擇上一級DSP的輸出，同時將本級輸出作為下一級輸入。但是要注意級聯(lián)的長度收到post-adder加法器位寬的限制，對于48bit的post-addr，如果乘法的輸出長度為32bit，那么其級聯(lián)長度可以達(dá)到2^16。

2 conv實現(xiàn)

CNN中一個卷積層的feature map有三個維度：長（H），寬（W），輸入通道（I）。輸出的feature map也同樣有三個維度長（H），寬（W），輸出通道（O）。卷積核的維度就是4個維度：對應(yīng)著feature map的H，W以及I和O。一個輸出通道O的feature map是每個輸入通道feature map的卷積結(jié)果的和。

依據(jù)這樣的運算特點，我們首先利用DSP的垂直結(jié)構(gòu)和cascade特性構(gòu)建一列運算單元，這個計算鏈包括DSP，BRAM以及一些LUT邏輯，每個DSP的輸出作為下一級DSP的輸入。

DSP的端口A和D分別用于kernel和feature map數(shù)據(jù)的輸入，kernel參數(shù)存儲在BRAM中，36Kb BRAM作為2個18Kb BRAM使用，這樣每個DSP都獨自占用一個存儲單元。我們以3x3卷積為例（stride為1，3輸入通道）。

每個BRAM中存儲9個核參數(shù)，按照先H后W的方向讀取送入DSP，feature map相對應(yīng)的按照3x3卷積計算方向讀取，先讀取一個窗的數(shù)據(jù)，計算出一個元素結(jié)果，然后滑窗讀取下一個窗的數(shù)據(jù)。

每個DSP輸出和下一次DSP的結(jié)果進(jìn)行累加得到一個窗卷積的結(jié)果，然后這個結(jié)果再傳遞到下一個DSP用于feature map不同通道之間的求和。這里面有幾個方面要考慮到：第一個是從一個DSP傳遞到下一個DSP有時間延遲，所以下一個DSP再進(jìn)行通道之間數(shù)據(jù)求和的時候要有延時，這個可以通過延時讀取kernel和feature map來處理。

同時需要有使能信號控制DSP輸出用于自身累加還是送入下一個DSP計算。當(dāng)每個36Kb BRAM被拆分為2個18Kb BRAM的時候，18Kb BRAM讀寫公用相同口，所以將kernel寫入bram的時候和從BRAM讀數(shù)不能夠沖突，當(dāng)然這個可以通過使用ping pong buffer來解決。

我們現(xiàn)在通過一列的DSP可以實現(xiàn)一個輸出通道的卷積計算了，如果我們沿著橫向增加DSP列數(shù)，就可以實現(xiàn)多輸出通道的卷積計算了。Feature map每個輸出通道是共享的，因此數(shù)據(jù)可以沿著橫向廣播到其它列來進(jìn)行計算。

3 乘法器復(fù)用

INT16，INT8和INT4是神經(jīng)網(wǎng)絡(luò)經(jīng)常量化的數(shù)據(jù)類型。DSP48E2的乘法器是27x18的，因此INT16xINT16的只能同時計算一次。但是對INT8和INT4可以利用DSP的前加器實現(xiàn)乘法計算次數(shù)的翻倍。

我們發(fā)現(xiàn)兩個INT8乘法結(jié)果位寬是16bit，因此我們可以利用pre-adder將兩個INT8數(shù)據(jù)打包在一起。使得multiplier的27bit端口包含兩個INT8數(shù)據(jù)。

因為bc數(shù)據(jù)位寬為16bit，所以ac和bc的數(shù)據(jù)區(qū)分開了。我們從結(jié)果中取出低16bit作為bc的結(jié)果，而ac的結(jié)果受到了bc符號位的影響，其值相當(dāng)于減了一個符號位數(shù)值，所以要獲得ac的結(jié)果需要取出偏移18bit結(jié)果加上符號位數(shù)值才是最終結(jié)果。如果符號位為1，則+1，如果符號位為0，則直接提取出來就可以了。

運用同樣的思路，我們能夠?qū)崿F(xiàn)4路INT4的乘法，方法如下：

1） 利用pre-adder打包兩個INT4數(shù)據(jù)，然后再利用B端口拼接兩個正數(shù)數(shù)據(jù)。這種實現(xiàn)可以針對任何符號數(shù)據(jù)的乘法，因為pre-adder打包的數(shù)據(jù)可以有符號，所以我們可以通過轉(zhuǎn)換將B端口數(shù)據(jù)的符號位轉(zhuǎn)換到pre-adder端口上來。

2） 需要對打包的數(shù)據(jù)進(jìn)行偏移，偏移保證4個結(jié)果不會發(fā)生混疊。

這樣低8bit就是A1*W1的結(jié)果，然后依次取出其它結(jié)果，同時加上符號位。

通過以上的處理，可以最大化利用DSP的計算能力，實現(xiàn)1個INT16，2個INT8和4個INT4的乘法。DSP的頻率通常都高于外部邏輯和BRAM的頻率（DSP最高頻率是BRAM頻率的2倍），所以可以讓DSP工作于高頻，而外部邏輯工作于低頻，這樣能夠讓DSP的計算再有所提升。BRAM以2倍的數(shù)據(jù)位寬供數(shù)，而DSP以倍頻方式工作，實現(xiàn)計算的增倍。那么相對于低頻工作時鐘來說，DSP就可以實現(xiàn)2倍INT16，INT8，INT4的乘法了。

Intel Stratix 10 DSP

對Intel的DSP沒有使用過，這里就根據(jù)其官方文檔進(jìn)行一些淺顯的了解吧。相比于DSP48E2，Intel的DSP計算功能更為強大，可以同時支持可變精度的頂點計算以及單精度浮點計算，浮點計算在DSP48E2中是不支持的。其定點計算功能包括：

1） 支持18bit和27bit的位寬。

2） 能夠?qū)崿F(xiàn)兩個18x19和一個27x27的乘法運算。

3） 內(nèi)部有加法器和減法器，能夠?qū)崿F(xiàn)兩個乘法結(jié)果的求和，還有64bit累加器實現(xiàn)歷史結(jié)果累加。

4） 有cascade級聯(lián)，用于多DSP block串聯(lián)，這已經(jīng)是DSP普遍的拓展功能。

5） 內(nèi)部含有寄存器組用于儲存參數(shù)，特別適用于filter操作。

6） 支持rounding。

浮點計算功能包括：

1） 支持通常的浮點乘法，加法，減法，乘加和乘減等。

2） 支持同級聯(lián)累加結(jié)果的乘法。

3） 支持復(fù)數(shù)乘法。

4） 支持一些異常報錯。

5） 支持vector的點乘操作。

前加器能夠選擇性實現(xiàn)加法或者減法，也可以通過internal coeficient模塊控制input和內(nèi)部參數(shù)的選擇，內(nèi)部參數(shù)能夠支持8個不同的常數(shù)參數(shù)。雙18x19的乘法結(jié)果可以通過post-adder實現(xiàn)求和，也可以將結(jié)果獨立輸出。利用這種模式能夠?qū)崿F(xiàn)復(fù)數(shù)計算，僅僅需要兩個DSP就可以實現(xiàn)

在雙乘法模式下，可以支持2個INT16乘法，2個INT8和4個INT4乘法。而在27x27模式下可以支持1個INT16，2個INT8和4個INT4的乘法。

在浮點模式下，DSP可以支持浮點數(shù)乘法，加減法以及MAC。同時還支持浮點數(shù)計算報錯，有助于計算中的debug。在乘法模式下，支持的異常有：mult_invalid（浮點乘法操作過程異常，導(dǎo)致結(jié)果不正確，這個時候結(jié)果會是NaN），mult_inexact（結(jié)果是rounded的，超過極大值或者極小值），mult_underflow（結(jié)果下溢），mult_overflow（結(jié)果發(fā)生上溢）。加法模式下支持的異常也有類似情形：adder_overflow， adder_underflow， adder_inexact， adder_invalid。而MAC模式下支持乘法和加法的所有異常檢測。

前邊梳理了Xilinx和Intel DSP硬核的功能和用法，但是我們還不知道DSP其內(nèi)部的核心模塊乘法器是如何設(shè)計的。加法器我們知道有很多設(shè)計方法：串行加法器，并行加法器，相對邏輯和算法都很簡單。乘法器的設(shè)計相對就復(fù)雜了，接下來來研究一下。

乘法器

1 Baugh-Wooley算法

Baugh-Wooley是很古老很經(jīng)典的一個乘法器算法，最早追溯到1973年，由Charles R.Baugh和Broce A.Wooley提出。1973年的時候大規(guī)模集成電路已經(jīng)發(fā)展起來了，Intel已經(jīng)造了第一個微處理器4004。

中國當(dāng)年集成電路產(chǎn)業(yè)剛剛起步，那個時候才開始自己研制的第一塊PMOS電路，同年引入外國單臺設(shè)備并開始建設(shè)自己的工藝線。這個時候距離FPGA出現(xiàn)還有10年的時間。

其中an和bn是符號表示，1表示負(fù)數(shù)，0表示正數(shù)。ai和bi是A和B中實際數(shù)值的表示。

從上邊方程看出，結(jié)果中有加法也有減法，這是不統(tǒng)一的，不適合硬件的設(shè)計。Baugh-Wooley算法的核心就在于對減法的轉(zhuǎn)換，抓換為加法就可以使用加法器來實現(xiàn)部分結(jié)果的求和了。如果將后兩項的減法作為數(shù)據(jù)的負(fù)數(shù)符號位，用二進(jìn)制補碼表示，就能夠轉(zhuǎn)換為和前兩項一樣的加法，這樣我們就可以設(shè)計出基本的4:2 compressor來作為乘法器的基本單元

灰色單元是用于處理減法項的，這樣我們就能夠用一個二維陣列來構(gòu)建一個乘法器了，比如對于4x4乘法有：

對于部分和邊界需要對數(shù)據(jù)取反，同時還需要附加上上式的最后兩項，對應(yīng)著兩個“1”。對于一個nxn的乘法來說，部分和有n個，所以最長級聯(lián)鏈為n。這種乘法器隨著數(shù)據(jù)寬度的增加級聯(lián)線性增長，這會影響其延時。

2 基于Baugh-Wooley算法的可變位寬DSP設(shè)計

降低深度學(xué)習(xí)推理階段的精度表示不僅僅可以改善加速器性能，而且可以降低模型存儲以及DDR帶寬需求。對于量化精度更寬的深度學(xué)習(xí)模型來說，F(xiàn)PGA的可編程性提供了更為靈活的bit寬度適配，這相比于其它硬件平臺有更大優(yōu)勢。但是目前Xilinx和Intel中嵌入式硬核DSP的bit位寬固定（只支持18bit以下數(shù)據(jù)乘法），不能夠有效的利用DSP資源來打包低bit數(shù)據(jù)乘法。于是有人從這一點出發(fā)來設(shè)計可變位寬乘法的DSP結(jié)構(gòu)。本篇就介紹一篇基于Baugh-Wooley算法的改進(jìn)的DSP結(jié)構(gòu)。我們重點關(guān)注其實現(xiàn)27x27，18x18，9x9以及4x4乘法的方式和結(jié)構(gòu)。

1 DSP基礎(chǔ)版。

基礎(chǔ)版結(jié)構(gòu)類似于Arria-10器件中的DSP結(jié)構(gòu)，其可以支持雙18x18以及單路27x27乘法和累加（見下圖）。它包含4個乘法器M1（18x18），M2（9x9），M3（9x18），M4（9x18）。

乘法器M1以及M4輸出有shift模塊，這塊可以用于實現(xiàn)乘法結(jié)果的分離。同時還添加了基于4:2compressor的加法器，可以支持多種計算模式（比如不同路乘法的求和等）。

在雙路18x18模式下，M1可以執(zhí)行一個18x18的乘法計算，另外一個18x18的計算需要M3和M4乘法器進(jìn)行配合，Y（其中一個乘數(shù)）可以被拆分為兩部分（各9bit）用M3和M4執(zhí)行乘法，然后在C1處完成求和。

如果兩路乘法結(jié)果要求和，可以通過C2實現(xiàn)，如果要輸出兩路結(jié)果，那么可以bypass C2。在27x27模式下，四個乘法器都被用到，依然采用類似的辦法“分而治之”，將數(shù)據(jù)拆分為18bit和9bit，利用組合和移位實現(xiàn)。這里就不細(xì)說了。

2 DSP加強版。

對于比18bit更低的乘法計算，基礎(chǔ)版本只能將數(shù)據(jù)拓展為18bit來進(jìn)行計算，這樣不能夠有效利用DSP資源。這對于功率消耗很高的DSP來說存在巨大的功耗浪費，代價巨大。為了支持低bit乘法，需要對基礎(chǔ)版進(jìn)行改進(jìn)。改進(jìn)有以下幾個挑戰(zhàn)：

1） 改進(jìn)版也必須兼容27x27和雙18x18模式。

2） 保證輸入輸出接口不會增加，避免模塊面積增大以及布線壓力。

3） 改進(jìn)版工作時鐘不能低于600MHz（這是28nm器件DSP的普遍頻率）。

先看9x9bit計算支持，根據(jù)72bit的輸出端口，最大可以支持4個9x9計算（每個9x9輸出18bit位寬，所以最高是4個乘法）。M1的輸入最高位可以放有效的9bit數(shù)據(jù)，可以執(zhí)行一個9x9乘法，M2也可以執(zhí)行一個9x9乘法，因為M1有效結(jié)果向左偏移了18bit，不會和M2的重合，所以這樣就實現(xiàn)了兩個9x9乘法。

關(guān)鍵在于M3和M4，其是18x9的乘法器，M3使用高9bit，M4使用低9bit，兩個乘法結(jié)果還是會存在數(shù)據(jù)交疊。一種辦法就是該進(jìn)M4乘法器，使得其可以支持9x9乘法。改進(jìn)的辦法就是修改乘法器中基本Baugh-Wooley計算單元。

需要將9x9乘法部分和的邊界的cell修改為灰色（見Baugh-Wooley算法介紹）的cell。為了還能夠兼容18x9的乘法，就需要有一個配置開關(guān)，來控制邊界cell的模式。這回增加一些邏輯。

對于4x4的乘法，作者增加了4給4x4乘法器，同時修改M2和M3乘法器，使得其可以支持兩路的4bit乘法，這根據(jù)Baugh-Wooley的結(jié)構(gòu)去修改是可行的。我們可以選擇去將一些無效的結(jié)果屏蔽掉來滿足這種要求。

這加強版DSP就可以執(zhí)行8個4x4乘法了。雖然M1和M4是空閑的，同時增加了4個4x4乘法器，但是能夠以最小的面積和邏輯代價換來計算性能的以倍提升也是值得的（可以看幾種模式的芯片面積和邏輯）。

3 Booth算法

Baugh-Wooley算法中部分和進(jìn)位鏈較長（等于乘數(shù)的位寬），這會限制乘法器的大小。A.D.Booth通過一種巧妙的辦法可以減少部分和結(jié)果，大大降低了部分和求和的鏈路長度。其基本思想是對乘數(shù)（multiplier）重新編碼，而被乘數(shù)（multiplicant）不變，以此降低乘數(shù)的位數(shù)。比如radix-2模式下，每2bit數(shù)據(jù)會被encode為0，1，-1三種數(shù)據(jù)類型，經(jīng)過encode，乘數(shù)中連續(xù)為1的部分就會被0替代，而其它部分則不變，經(jīng)過這樣就大大降低了部分和數(shù)目。具體過程如下：

1） 在乘數(shù)最后一位添加0，然后觀察乘數(shù)位數(shù)是否為2的倍數(shù)，如果不是最高位擴充符號位；

2） 從右至左依次遍歷每兩個bit位；

3） 進(jìn)行如下encoder：00，11 -》 0，01 -》 1， 10 -》 -1。

4） 然后使用encode的乘數(shù)和被乘數(shù)進(jìn)行乘法計算。0和被乘數(shù)結(jié)果為0，這樣就節(jié)省了一個部分和，因此對于連續(xù)111的數(shù)據(jù)，就可以節(jié)省了部分和的計算。1和被乘數(shù)y結(jié)果y，-1和y結(jié)果為-y，-y可以轉(zhuǎn)變?yōu)槎M(jìn)制補碼形式，這樣就將減法轉(zhuǎn)化為加法。之后使用加法樹將這些結(jié)果加起來就可以了。

用的最多的是radix-4算法，其將連續(xù)的3bit數(shù)據(jù)encode為0，1，-1，-2，2表示。因為2的乘法只需要將數(shù)據(jù)左移一位就可以實現(xiàn)了，所以實現(xiàn)起來簡單。而-2是結(jié)果移位后取補碼結(jié)果，也容易實現(xiàn)。因此radix-4算法用途很廣。Booth算法減少了加法進(jìn)位鏈，能夠?qū)崿F(xiàn)更快速的乘法運算。

4 基于Booth算法的可變位寬DSP設(shè)計

選擇radix-4作為乘法器基本單元有一個巨大的優(yōu)勢是：在保持乘法計算簡潔的同時，將部分和數(shù)目降低了一半。

Booth encode的具體操作是：將最低bit后邊補0，然后每三個數(shù)據(jù)遍歷，按照表格encode為（0，1，-1，-2，2）中的數(shù)據(jù)，然后向左移動2bit，再進(jìn)行3bit數(shù)據(jù)encode。然后計算encode后的multiplier和multiplicant的乘法。

看看作者如何通過對部分和生成模塊（PPG）的一個簡單修改來實現(xiàn)可變數(shù)據(jù)位寬乘法的。

其中當(dāng)encode值為負(fù)數(shù)的時候，符號位需要參與到部分和求和（PPR）中，作者將這個correction term傳遞到PPR中進(jìn)行計算。由于Booth算法需要對每一個bit乘數(shù)進(jìn)行encode。

因此當(dāng)位寬發(fā)生改變了的時候，就需要在符號位和encoded位進(jìn)行選擇，這樣對于不同乘數(shù)位寬的配置來說，就需要很多multiplexer。一個簡單有效的辦法是先清除部分結(jié)果中的符號位擴展。

我們可以給符號擴展位加1，加1之后符號擴展位就變成了一個inverted數(shù)。這樣部分和中的符號位就可以用0和一個inverted的符號位替代。而在部分和求和后面在通過-1來實現(xiàn)。所有部分和擴展位-1可以綜合起來用一個常數(shù)替代。

編輯：jq