引言

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

01

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內最大可以支持512X1大小的RAM。RAM的讀寫地址和輸入的讀寫數據是共享的，數據通道可以使用x和I介面。LUT還可以配置用於4:1選通器，CLB最大能夠支持到32:1的選通器。CLB中的carry邏輯含有異或門和產生進位的門，用於生成進位數據。

圖1.1 LUT結構

LUT還可以被動態配置成32bit移位寄存器，這個功能在乘法器設計中可以用於改變乘法器的乘數和被乘數。在寫入LUT數據的時候，每個時鐘週期從D介面進入數據，依次寫入32bit數據。讀數據的時候，可以通過地址來定位任何32bit中的數據。這樣就可以配置成任何小於32bit的移位寄存器。移位輸出Q31可以進入下一級LUT用於串聯產生更大移位寄存器。在一個CLB中最大可以串聯產生256bit移位寄存器。

圖1.2 移位寄存器配置

02

LUT乘法器原理

首先假設我們處理整數乘法，小數乘法也可以用這樣的方法。基本思想就是將m bit大小的數據進行分割表示：

其中0<=di<2^q。乘以一個常數K：

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

03

基本結構

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

圖2.1 基本結構

圖2.2 LUT實現乘法和半加，外圍carry邏輯實現進位

04

動態配置LUT內容

Xilinx的LUT結構允許在運行過程中改變LUT中的內容，這樣的乘法器就能改變被乘數據K。這可以實現在神經網路計算中需要更新權重參數。論文中使用的是LUT4，所以一個LUT可以被配置成16bit移位寄存器。通過這16bit寄存器可以來配置LUT中的內容，每個時鐘週期更新1bit數據，16個時鐘週期可以完成一個LUT中數據更新。是否進行LUT內容更新通過CE使能信號控制。

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

圖4.1 LUT中內容更新電路圖

圖4.2 負數乘法結果更新電路

05

結果分析

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

圖5.1 沒有pipeline下頻率MHz

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

圖5.2 slice資源

結論

上述通過LUT來設計乘法器的方法，可以應用於CNN中的卷積運算當中，因為權重可以被當做被乘數，用於LUT內容的配置，在更換權重時，可以對LUT內容更新，這樣就能避免了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

往期回顧

1. 可變位寬的大規模矩陣乘法

2. 脈動陣列

3. 在DNN中FPGA做了什麼？


推薦閱讀：
相關文章