引言

由於卷積核數據在計算過程中保持不變，更新較慢。這樣就可以利用LUT來存儲權重並同時進行乘法運算。LUT乘法器的實現很早就已經研究過，本論文正是在此基礎上，提出了用於實現可配置的卷積實現方法。基於LUT的乘法器不會受到FPGA中DSP資源的限制，能夠將神經網路加速應用於低端FPGA晶元。

01 LUT乘法器的實現

一個LUT有固定的輸入和輸出管腳，例如在xilinx的zynq系列器件中，LUT有5個輸入1個輸出或者4個輸入兩個輸出。如何用LUT來實現任意大小的乘法運算呢？這裡用到了一個基本的數學法則：因式分解。考慮一個補碼數據x，其有Bi bit，那麼表示為：

如果這個數被一個常數c乘，這個乘法可以被分解為更小bit的乘法，然後對這些小份乘法進行位移和求和。

這樣就將一個BcxBi bit的乘法分解成多個BcxL的乘法，而這個小的乘法就可以去利用LUT來實現。將L設置為LUT的輸入引腳數量，可以直接將乘法映射到LUT上，並且對LUT資源利用效率最高。

02 Compressor加法樹

上述乘法的分解造成了大量的加法，因此需要較大的加法樹來完成各個乘法結果移位後的累加。基於Generalized parallel counters（GPC）充分利用了FPGA中的LUT資源以及進位鏈，可以更好的映射到LUT上，減少LUT使用的浪費。其主要特點就是在一個LUT中實現最多個全加器的運算，這樣能保證進位鏈最短，LUT資源利用率最高。

圖2.1 乘法分解求和

03 可配置LUT

LUT是一個查找表，FPGA中對代碼邏輯的映射都是映射到查找表中。現代的LUT有個特點就是可以進行動態配置，意味著可以在運行中去更新查找表的值。比如在xilinx的virtex，spartan和zynq器件中LUT就可以通過移位寄存器的方式來更新內部數據，32個時鐘週期完成。這樣就可以將卷積核數據存放在LUT中，然後在需要更新的時候進行更新。

04 可配置卷積的硬體架構

卷積運算的結構如圖4.1所示，N個輸入數據（x1, x2, .., xN）每個和c的乘法都被分解為K個乘法，然後將所有的部分乘法結果移位送入加法樹。每個BcXL的乘法需要的LUT數量大致為Bc+L個。加法樹輸出的Bo位寬會遠遠大於輸入位寬，因此需要進行rouding或者截位。

圖4.1 基於LUT的卷積運算結構

論文中使用了LUT4輸入2輸出，使用4輸入LUT而不是5輸入是因為乘法分解的特點，4bit位寬對於16bit，8bit整型乘法來說更能充分利用LUT資源。這樣N個輸入數據的每個部分乘法總共花費的LUT數量就是：

乘法和加法導致輸出Bo位寬變大，需要減小位寬。論文採用了faithful rouding的辦法。比如輸入是12bit的數據，要求輸出也要截位成12bit，如果在最後求和之後再進行截位，加法樹中就因為計算多餘位數求和而浪費LUT。如果每個乘法結果都截位為12，那麼會造成最後結果精度較大丟失。如果先對每個乘法結果截位大於12bit的數據，根據總共求和的個數可以計算出需要保留的bit位數。這樣就能夠保證最後加法結果精度等於或者小於直接截位加法結果的精度。比如開始對每個乘法截位2^(-q-g)，因為總共有N*Bi/L個部分積結果。所以總共的精度損失為：

通過限制總精度損失在需要範圍：

這樣就可以得到g的數據。這樣就能最大程度減少LUT的使用同時能保證良好精度。

圖4.2 3個輸入x，bit位寬12bit，分解為4個乘法，輸出要求12bit

現在來看如何對LUT進行數據的更新。由於將LUT用作4輸入2輸出，那麼一個LUT可以計算出2bit結果的乘法。於是計算需要的每個個LUT的一部分用於和weights的偶數部分進行乘法，而另一部分用於和weights的奇數部分乘法。而LUT的配置介面只有一個CDI，因此就需要分別對LUT的這兩部分進行配置。論文中先計算對應奇數部分weights的乘法結果，存儲到LUT中，然後計算對應偶數部分weihts的乘法，存儲到LUT中。

圖4.3 動態配置LUT電路圖

從上述架構中可以看到，當進行LUT配置的時候，LUT是無法進行計算的。這個很好解決，可以通過增加雙倍LUT來實現，對沒有計算的LUT來進行動態配置，而另一部分LUT進行計算。這樣相當於進行了ping-pong操作。

圖4.4 雙LUT結構進行計算

05 結果

下圖給出了不同卷積核大小以及不同位寬所需要的資源對比。相比於其他使用LUT來進行乘法和加法操作的方式來說，這樣更能最大化利用LUT資源。

圖5.1 綜合後資源對比

總結

論文中提出的可配置卷積運算架構，可以改善CNN在FPGA的應用。充分利用了LUT資源，可以更好的改善時序性能。

文獻

1 Hardieck, M., et al., Reconfigurable Convolutional Kernels for Neural Networks on FPGAs, in Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays - FPGA 19. 2019.

往期回顧

1 用LUT來搭建乘法器

2 在FPGA中實現高效的compressor加法樹

3 可變位寬的大規模矩陣乘法方法


推薦閱讀：
相關文章