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

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

通用性要看的廣，指令集的定義要具有擴(kuò)展性和靈活性，工具鏈要能夠靈活的對(duì)接不同的深度學(xué)習(xí)框架，能夠處理不同類型的網(wǎng)絡(luò)。這是一個(gè)很大的工程，需要一個(gè)頂級(jí)架構(gòu)師以及大批軟件編譯類工程師合力來(lái)做。但是現(xiàn)在出現(xiàn)的很多開源工具鏈框架將這種開發(fā)難度大大降低了，比如TVM，LLVM，MLIR等工具給我們提供了基礎(chǔ)，避免了再造輪子的重負(fù)。很多公司也基于這些開源框架來(lái)編寫自己的編譯工具。

高效性能永遠(yuǎn)是各大芯片廠商比拼的焦點(diǎn)，性能的提升需要三個(gè)方面共同努力：一個(gè)是來(lái)自于芯片的廣大的資源，包括計(jì)算資源和存儲(chǔ)資源，以及高帶寬，從Xilinx芯片不斷加大尺寸和DSP數(shù)量，以及采用HBM，還有GPU內(nèi)核數(shù)量的提升以及對(duì)HBM的采用都說(shuō)明了這個(gè)問題；另外一個(gè)是算法的深度優(yōu)化，神經(jīng)網(wǎng)絡(luò)對(duì)噪聲的容納能力讓其有了很多可以利用的空間，比如int類型的量化，稀疏化，剪枝等等，可以在保證精度的前提下，大大降低其運(yùn)算量以及參數(shù)數(shù)量，同時(shí)能夠更好的適配硬件；第三就是需要編譯器對(duì)指令的優(yōu)化，算符融合，無(wú)效算子的kill，指令的schedule等等，都會(huì)對(duì)最后性能造成很深的影響。提升性能需要看的深，追求硬件，算法，編譯的極限，盡最大可能利用硬件有限的資源，盡最大可能優(yōu)化網(wǎng)絡(luò)的結(jié)構(gòu)，盡最大可能尋求指令序列的優(yōu)化解。今天我們談性能追求當(dāng)中的一個(gè)很小的部分——DSP。

Xilinx DSP

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

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

DSP48E2單元的功能包括：

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

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

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

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

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

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

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

8）支持17bit右移操作。

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

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

Zynq器件中通常將2個(gè)DSP48E2和一個(gè)36Kb的block memory以及5個(gè)CLB放置在一起，一個(gè)36Kb的BRAM可以拆分成2個(gè)18Kb的memory使用，每個(gè)memory可以獨(dú)自被一個(gè)DSP占用。這樣的配置也為DSP以及存儲(chǔ)的高效配合使用提供了模板。后邊我們可以利用這樣的結(jié)構(gòu)構(gòu)建一個(gè)conv計(jì)算單元。同時(shí)多個(gè)DSP在FPGA芯片內(nèi)部是垂直擺放的，這有利于多個(gè)DSP的cascade。

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

使用加法樹會(huì)采用這樣的結(jié)構(gòu)：

這樣的加法樹會(huì)消耗更多的資源，代價(jià)以及能耗。特別是后幾級(jí)的加法器位寬變的越來(lái)越寬，對(duì)LUT資源消耗很多。如果我們利用DSP的級(jí)聯(lián)功能，可以完全實(shí)現(xiàn)FIR中的多輸入加法功能。DSP中提供的post-adder以及CARRYCASCIN和CARRYCASCOUT可以選擇上一級(jí)DSP的輸出，同時(shí)將本級(jí)輸出作為下一級(jí)輸入。但是要注意級(jí)聯(lián)的長(zhǎng)度收到post-adder加法器位寬的限制，對(duì)于48bit的post-addr，如果乘法的輸出長(zhǎng)度為32bit，那么其級(jí)聯(lián)長(zhǎng)度可以達(dá)到2^16。

2 conv實(shí)現(xiàn)

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

依據(jù)這樣的運(yùn)算特點(diǎn)，我們首先利用DSP的垂直結(jié)構(gòu)和cascade特性構(gòu)建一列運(yùn)算單元，這個(gè)計(jì)算鏈包括DSP，BRAM以及一些LUT邏輯，每個(gè)DSP的輸出作為下一級(jí)DSP的輸入。DSP的端口A和D分別用于kernel和feature map數(shù)據(jù)的輸入，kernel參數(shù)存儲(chǔ)在BRAM中，36Kb BRAM作為2個(gè)18Kb BRAM使用，這樣每個(gè)DSP都獨(dú)自占用一個(gè)存儲(chǔ)單元。我們以3x3卷積為例（stride為1，3輸入通道），DSP陣列以及計(jì)算結(jié)構(gòu)如下圖所示：

每個(gè)BRAM中存儲(chǔ)9個(gè)核參數(shù)，按照先H后W的方向讀取送入DSP，feature map相對(duì)應(yīng)的按照3x3卷積計(jì)算方向讀取，先讀取一個(gè)窗的數(shù)據(jù)，計(jì)算出一個(gè)元素結(jié)果，然后滑窗讀取下一個(gè)窗的數(shù)據(jù)。每個(gè)DSP輸出和下一次DSP的結(jié)果進(jìn)行累加得到一個(gè)窗卷積的結(jié)果，然后這個(gè)結(jié)果再傳遞到下一個(gè)DSP用于feature map不同通道之間的求和。這里面有幾個(gè)方面要考慮到：第一個(gè)是從一個(gè)DSP傳遞到下一個(gè)DSP有時(shí)間延遲，所以下一個(gè)DSP再進(jìn)行通道之間數(shù)據(jù)求和的時(shí)候要有延時(shí)，這個(gè)可以通過(guò)延時(shí)讀取kernel和feature map來(lái)處理。同時(shí)需要有使能信號(hào)控制DSP輸出用于自身累加還是送入下一個(gè)DSP計(jì)算。當(dāng)每個(gè)36Kb BRAM被拆分為2個(gè)18Kb BRAM的時(shí)候，18Kb BRAM讀寫公用相同口，所以將kernel寫入bram的時(shí)候和從BRAM讀數(shù)不能夠沖突，當(dāng)然這個(gè)可以通過(guò)使用ping pong buffer來(lái)解決。

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

3 乘法器復(fù)用

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

我們發(fā)現(xiàn)兩個(gè)INT8乘法結(jié)果位寬是16bit，因此我們可以利用pre-adder將兩個(gè)INT8數(shù)據(jù)打包在一起。使得multiplier的27bit端口包含兩個(gè)INT8數(shù)據(jù)。如下公式表達(dá)了計(jì)算過(guò)程：

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

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

1）利用pre-adder打包兩個(gè)INT4數(shù)據(jù)，然后再利用B端口拼接兩個(gè)正數(shù)數(shù)據(jù)。這種實(shí)現(xiàn)可以針對(duì)任何符號(hào)數(shù)據(jù)的乘法，因?yàn)閜re-adder打包的數(shù)據(jù)可以有符號(hào)，所以我們可以通過(guò)轉(zhuǎn)換將B端口數(shù)據(jù)的符號(hào)位轉(zhuǎn)換到pre-adder端口上來(lái)。

2）需要對(duì)打包的數(shù)據(jù)進(jìn)行偏移，偏移保證4個(gè)結(jié)果不會(huì)發(fā)生混疊?？梢赃M(jìn)行如下偏移：

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

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

Intel Stratix 10 DSP

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

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

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

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

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

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

6）支持rounding。

浮點(diǎn)計(jì)算功能包括：

1）支持通常的浮點(diǎn)乘法，加法，減法，乘加和乘減等。

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

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

4）支持一些異常報(bào)錯(cuò)。

5）支持vector的點(diǎn)乘操作。

在雙18x19乘法模式下，結(jié)夠如下圖：

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

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

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

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

乘法器

1 Baugh-Wooley算法

Baugh-Wooley是很古老很經(jīng)典的一個(gè)乘法器算法，最早追溯到1973年，由Charles R.Baugh和Broce A.Wooley提出。1973年的時(shí)候大規(guī)模集成電路已經(jīng)發(fā)展起來(lái)了，Intel已經(jīng)造了第一個(gè)微處理器4004。中國(guó)當(dāng)年集成電路產(chǎn)業(yè)剛剛起步，那個(gè)時(shí)候才開始自己研制的第一塊PMOS電路，同年引入外國(guó)單臺(tái)設(shè)備并開始建設(shè)自己的工藝線。這個(gè)時(shí)候距離FPGA出現(xiàn)還有10年的時(shí)間。

乘數(shù)和被乘數(shù)使用二進(jìn)制補(bǔ)碼表示如下：

其中an和bn是符號(hào)表示，1表示負(fù)數(shù)，0表示正數(shù)。ai和bi是A和B中實(shí)際數(shù)值的表示。A*B在二進(jìn)制補(bǔ)碼表示下結(jié)果為：

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

這樣我們就可以設(shè)計(jì)出基本的4:2 compressor來(lái)作為乘法器的基本單元，這個(gè)compressor如下：

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

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

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

降低深度學(xué)習(xí)推理階段的精度表示不僅僅可以改善加速器性能，而且可以降低模型存儲(chǔ)以及DDR帶寬需求。對(duì)于量化精度更寬的深度學(xué)習(xí)模型來(lái)說(shuō)，F(xiàn)PGA的可編程性提供了更為靈活的bit寬度適配，這相比于其它硬件平臺(tái)有更大優(yōu)勢(shì)。但是目前Xilinx和Intel中嵌入式硬核DSP的bit位寬固定（只支持18bit以下數(shù)據(jù)乘法），不能夠有效的利用DSP資源來(lái)打包低bit數(shù)據(jù)乘法。于是有人從這一點(diǎn)出發(fā)來(lái)設(shè)計(jì)可變位寬乘法的DSP結(jié)構(gòu)。本篇就介紹一篇基于Baugh-Wooley算法的改進(jìn)的DSP結(jié)構(gòu)。我們重點(diǎn)關(guān)注其實(shí)現(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個(gè)乘法器M1（18x18），M2（9x9），M3（9x18），M4（9x18）。乘法器M1以及M4輸出有shift模塊，這塊可以用于實(shí)現(xiàn)乘法結(jié)果的分離。同時(shí)還添加了基于4:2compressor的加法器，可以支持多種計(jì)算模式（比如不同路乘法的求和等）。在雙路18x18模式下，M1可以執(zhí)行一個(gè)18x18的乘法計(jì)算，另外一個(gè)18x18的計(jì)算需要M3和M4乘法器進(jìn)行配合，Y（其中一個(gè)乘數(shù)）可以被拆分為兩部分（各9bit）用M3和M4執(zhí)行乘法，然后在C1處完成求和。如果兩路乘法結(jié)果要求和，可以通過(guò)C2實(shí)現(xiàn)，如果要輸出兩路結(jié)果，那么可以bypass C2。在27x27模式下，四個(gè)乘法器都被用到，依然采用類似的辦法“分而治之”，將數(shù)據(jù)拆分為18bit和9bit，利用組合和移位實(shí)現(xiàn)。這里就不細(xì)說(shuō)了。

2 DSP加強(qiáng)版。

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

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

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

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

先看9x9bit計(jì)算支持，根據(jù)72bit的輸出端口，最大可以支持4個(gè)9x9計(jì)算（每個(gè)9x9輸出18bit位寬，所以最高是4個(gè)乘法）。M1的輸入最高位可以放有效的9bit數(shù)據(jù)，可以執(zhí)行一個(gè)9x9乘法，M2也可以執(zhí)行一個(gè)9x9乘法，因?yàn)镸1有效結(jié)果向左偏移了18bit，不會(huì)和M2的重合，所以這樣就實(shí)現(xiàn)了兩個(gè)9x9乘法。關(guān)鍵在于M3和M4，其是18x9的乘法器，M3使用高9bit，M4使用低9bit，兩個(gè)乘法結(jié)果還是會(huì)存在數(shù)據(jù)交疊。一種辦法就是該進(jìn)M4乘法器，使得其可以支持9x9乘法。改進(jìn)的辦法就是修改乘法器中基本Baugh-Wooley計(jì)算單元。需要將9x9乘法部分和的邊界的cell修改為灰色（見Baugh-Wooley算法介紹）的cell。為了還能夠兼容18x9的乘法，就需要有一個(gè)配置開關(guān)，來(lái)控制邊界cell的模式。這回增加一些邏輯。

對(duì)于4x4的乘法，作者增加了4給4x4乘法器，同時(shí)修改M2和M3乘法器，使得其可以支持兩路的4bit乘法，這根據(jù)Baugh-Wooley的結(jié)構(gòu)去修改是可行的。我們可以選擇去將一些無(wú)效的結(jié)果屏蔽掉來(lái)滿足這種要求。這加強(qiáng)版DSP就可以執(zhí)行8個(gè)4x4乘法了。雖然M1和M4是空閑的，同時(shí)增加了4個(gè)4x4乘法器，但是能夠以最小的面積和邏輯代價(jià)換來(lái)計(jì)算性能的以倍提升也是值得的（可以看幾種模式的芯片面積和邏輯）。

3 Booth算法

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

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

2）從右至左依次遍歷每?jī)蓚€(gè)bit位；

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

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

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

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

選擇radix-4作為乘法器基本單元有一個(gè)巨大的優(yōu)勢(shì)是：在保持乘法計(jì)算簡(jiǎn)潔的同時(shí)，將部分和數(shù)目降低了一半。一個(gè)基本的Booth乘法器結(jié)構(gòu)如下：

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

看看作者如何通過(guò)對(duì)部分和生成模塊（PPG）的一個(gè)簡(jiǎn)單修改來(lái)實(shí)現(xiàn)可變數(shù)據(jù)位寬乘法的。PPG的基本結(jié)構(gòu)如下圖所示：

其中當(dāng)encode值為負(fù)數(shù)的時(shí)候，符號(hào)位需要參與到部分和求和（PPR）中，作者將這個(gè)correction term傳遞到PPR中進(jìn)行計(jì)算。由于Booth算法需要對(duì)每一個(gè)bit乘數(shù)進(jìn)行encode，因此當(dāng)位寬發(fā)生改變了的時(shí)候，就需要在符號(hào)位和encoded位進(jìn)行選擇，這樣對(duì)于不同乘數(shù)位寬的配置來(lái)說(shuō)，就需要很多multiplexer。一個(gè)簡(jiǎn)單有效的辦法是先清除部分結(jié)果中的符號(hào)位擴(kuò)展。我們可以給符號(hào)擴(kuò)展位加1，加1之后符號(hào)擴(kuò)展位就變成了一個(gè)inverted數(shù)。這樣部分和中的符號(hào)位就可以用0和一個(gè)inverted的符號(hào)位替代。而在部分和求和后面在通過(guò)-1來(lái)實(shí)現(xiàn)。所有部分和擴(kuò)展位-1可以綜合起來(lái)用一個(gè)常數(shù)替代。