卷積占據(jù)了CNN網(wǎng)絡中絕大部分運算，進行乘法運算通常都是使用FPGA中的DSP，這樣算力就受到了器件中DSP資源的限制。比如在zynq7000器件中，DSP資源就較少，神經(jīng)網(wǎng)絡的性能就無法得到提升。利用xilinx器件中LUT的結構特征，設計出的乘法器不但能靈活適應數(shù)據(jù)位寬，而且能最大限度降低LUT資源使用。

Xilinx ultrascale器件LUT結構
在這里簡要介紹一下ultrascale系列器件中的LUT結構，有助于后邊對乘法器設計思路的理解。CLB（configuratble logic block）是主要的資源模塊，其包含了8個LUT，16個寄存器，carry邏輯，以及多路選通器等。其中LUT可以用作6輸入1輸出，或者兩個5輸入LUT，但是這兩個LUT公用輸入，具有不同輸出。每個LUT輸出可以連接到寄存器或者鎖存器，或者從CLB輸出。LUT可以用于64x1和32X2的分布式RAM，一個CLB內(nèi)最大可以支持512X1大小的RAM。RAM的讀寫地址和輸入的讀寫數(shù)據(jù)是共享的，數(shù)據(jù)通道可以使用x和I接口。LUT還可以配置用于4:1選通器，CLB最大能夠支持到32:1的選通器。CLB中的carry邏輯含有異或門和產(chǎn)生進位的門，用于生成進位數(shù)據(jù)。

圖1.1 LUT結構

LUT還可以被動態(tài)配置成32bit移位寄存器，這個功能在乘法器設計中可以用于改變乘法器的乘數(shù)和被乘數(shù)。在寫入LUT數(shù)據(jù)的時候，每個時鐘周期從D接口進入數(shù)據(jù)，依次寫入32bit數(shù)據(jù)。讀數(shù)據(jù)的時候，可以通過地址來定位任何32bit中的數(shù)據(jù)。這樣就可以配置成任何小于32bit的移位寄存器。移位輸出Q31可以進入下一級LUT用于串聯(lián)產(chǎn)生更大移位寄存器。在一個CLB中最大可以串聯(lián)產(chǎn)生256bit移位寄存器。

圖1.2 移位寄存器配置

LUT乘法器原理
首先假設我們處理整數(shù)乘法，小數(shù)乘法也可以用這樣的方法?；舅枷刖褪菍 bit大小的數(shù)據(jù)進行分割表示：

這樣就將兩個數(shù)據(jù)乘法分解成低bit數(shù)據(jù)乘法，結果是一個常數(shù)K和di相乘，然后再進行移位求和。M bit數(shù)據(jù)分解后的低bit數(shù)據(jù)位寬通常都適配LUT輸入寬度，這樣能最大利用LUT資源?，F(xiàn)在乘法只有K*di，由于bit位寬較小，這部分可以用LUT查找表的形式來。預先將0K到（2^q-1）K的數(shù)據(jù)存儲到LUT中，然后通過di來選擇對應的數(shù)據(jù)。如果是負數(shù)乘法，那么數(shù)據(jù)使用補碼表示，那么LUT中存儲的數(shù)據(jù)是從-2^(q-1)K到（2^(q-1)-1）K。針對以上介紹的ultrascale器件的LUT6，q可以選擇為5。但是在本論文中使用的是LUT4器件，其只有4輸入，因此選擇了q=3，為什么沒有選擇4呢？另外1bit是為了用于半加器的實現(xiàn)。

基本結構
實現(xiàn)上述累加的方法有很多種，論文中采用了進位鏈加法器。圖2.1中是m bit和n bit數(shù)據(jù)乘法，每個E結構計算di*K，并且和上一個結構求和，輸出的低3bit直接作為最終結果，而n bit傳輸?shù)较乱患夁M行計算。q=3的計算單元E有[m/3]個。K*di是有n+3bit的查找表實現(xiàn)的。查找表的結果由di選擇，然后再通過一個求和器和之前數(shù)據(jù)求和。這是一個最基本的結構，論文又針對這個結構做了優(yōu)化，用一個LUT同時實現(xiàn)了一個查找表和半加器。具體來講，其中3bit輸入用于di，還有1bit用于上一次輸出，LUT中存放數(shù)據(jù)是di*K和上一次結果第j bit的半加結果，實際上是第j bit數(shù)據(jù)LUT中結果的異或。而進位數(shù)據(jù)由CLB中相應的carry邏輯來計算。相比于粗暴的進行數(shù)據(jù)求和，這樣精確的來控制LUT能夠大大節(jié)省資源。

圖2.1 基本結構

圖2.2 LUT實現(xiàn)乘法和半加，外圍carry邏輯實現(xiàn)進位

動態(tài)配置LUT內(nèi)容
Xilinx的LUT結構允許在運行過程中改變LUT中的內(nèi)容，這樣的乘法器就能改變被乘數(shù)據(jù)K。這可以實現(xiàn)在神經(jīng)網(wǎng)絡計算中需要更新權重參數(shù)。論文中使用的是LUT4，所以一個LUT可以被配置成16bit移位寄存器。通過這16bit寄存器可以來配置LUT中的內(nèi)容，每個時鐘周期更新1bit數(shù)據(jù)，16個時鐘周期可以完成一個LUT中數(shù)據(jù)更新。是否進行LUT內(nèi)容更新通過CE使能信號控制。

如何產(chǎn)生LUT中數(shù)據(jù)的值呢？如果上一次輸出數(shù)據(jù)對應bit為0，那么LUT中就存放0*K到7*K的值，如果上一次對應bit為1，那么存放值為對以上數(shù)據(jù)取反。圖4.1表示了獲得LUT中內(nèi)容的電路圖。首先數(shù)據(jù)被初始化為0*K，下一次對應著求和進位為1的情況，取反，然后再加K得到1*K的值，這樣每隔兩個時鐘周期就得到下一個乘法的數(shù)據(jù)值，依次對LUT進行更新。上述中針對的是正整數(shù)，如果對于負數(shù)乘法更新，可以在上述求整數(shù)乘法的電路基礎上做一下改進，如圖4.2。當最高位為0的時候，輸出結果就是之前求得的乘法結果。如果最高位是1，那么負數(shù)的補碼表示是乘法的原碼結果減去最高位數(shù)值。

圖4.1 LUT中內(nèi)容更新電路圖

圖4.2 負數(shù)乘法結果更新電路

結果分析
最后我們來看看這種乘法器的實現(xiàn)效果，圖5.1表示對多級進位不適用pipeline結構的時鐘頻率隨著被乘數(shù)K位寬變化，可以看到隨著級數(shù)E的增加，頻率降低很多，這主要是進位鏈邊長導致。而隨著K位寬增加，頻率也有降低，這主要是因為實現(xiàn)di*K乘法的LUT資源增加導致。

圖5.1 沒有pipeline下頻率MHz

圖5.2是不同乘法位寬下的使用slice數(shù)量。論文中考慮了兩種極端情況，一種是完全pipeline下，即每級計算單元都經(jīng)過寄存器，另外一種是完全沒有pipeline，所有級E都是串聯(lián)。

圖5.2 slice資源

結論
上述通過LUT來設計乘法器的方法，可以應用于CNN中的卷積運算當中，因為權重可以被當做被乘數(shù)，用于LUT內(nèi)容的配置，在更換權重時，可以對LUT內(nèi)容更新，這樣就能避免了DSP資源的限制，不失為一種增加算力的方法。

文獻
1. Hormigo, J.C., Gabriel Oliver, Juan P.Boemo, Eduardo, Self-Reconfigurable Constant Multiplier for FPGA. ACM Transactions on Reconfigurable Technology and Systems, 2013. 6

編輯：hfy