如何用LUT做一個可動態(tài)配置的卷積核呢？

引言

由于卷積核數(shù)據(jù)在計算過程中保持不變，更新較慢。這樣就可以利用LUT來存儲權(quán)重并同時進行乘法運算。LUT乘法器的實現(xiàn)很早就已經(jīng)研究過，本論文正是在此基礎(chǔ)上，提出了用于實現(xiàn)可配置的卷積實現(xiàn)方法。基于LUT的乘法器不會受到FPGA中DSP資源的限制，能夠?qū)?a href="http://www.ttokpm.com/tags/神經(jīng)網(wǎng)絡(luò)/" target="_blank">神經(jīng)網(wǎng)絡(luò)加速應(yīng)用于低端FPGA芯片。

01

LUT乘法器的實現(xiàn)

一個LUT有固定的輸入和輸出管腳，例如在xilinx的zynq系列器件中，LUT有5個輸入1個輸出或者4個輸入兩個輸出。如何用LUT來實現(xiàn)任意大小的乘法運算呢？這里用到了一個基本的數(shù)學(xué)法則：因式分解?？紤]一個補碼數(shù)據(jù)x，其有Bi bit，那么表示為：

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

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

02

Compressor加法樹

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

圖2.1 乘法分解求和

03

可配置LUT

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

04

可配置卷積的硬件架構(gòu)

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

圖4.1 基于LUT的卷積運算結(jié)構(gòu)

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

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

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

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

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

現(xiàn)在來看如何對LUT進行數(shù)據(jù)的更新。由于將LUT用作4輸入2輸出，那么一個LUT可以計算出2bit結(jié)果的乘法。于是計算需要的每個個LUT的一部分用于和weights的偶數(shù)部分進行乘法，而另一部分用于和weights的奇數(shù)部分乘法。而LUT的配置接口只有一個CDI，因此就需要分別對LUT的這兩部分進行配置。論文中先計算對應(yīng)奇數(shù)部分weights的乘法結(jié)果，存儲到LUT中，然后計算對應(yīng)偶數(shù)部分weihts的乘法，存儲到LUT中。

圖4.3 動態(tài)配置LUT電路圖

從上述架構(gòu)中可以看到，當(dāng)進行LUT配置的時候，LUT是無法進行計算的。這個很好解決，可以通過增加雙倍LUT來實現(xiàn)，對沒有計算的LUT來進行動態(tài)配置，而另一部分LUT進行計算。這樣相當(dāng)于進行了ping-pong操作。

圖4.4 雙LUT結(jié)構(gòu)進行計算

05

結(jié)果

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

圖5.1 綜合后資源對比

總結(jié)

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

審核編輯：劉清