作者 | 殷慶瑜
責編 | 胡巍巍
本文主要討論了如何在FPGA上實現雙線性插值的計算。Interp和Resize是Yolo_v2,Yolo_v3和Faster R-CNN等目標檢測網絡的關鍵層。主要的作用是使得圖片的放大和縮小過程變得更為平滑。
What？什麼是雙線性插值？
雙線性插值顧名思義是線性插值Pro，為了說明白什麼是雙線性插值，首先得先從線性插值說起。那麼什麼又是線性呢？用數學課本上的話來說，兩個變量之間存在一次方函數關係，就稱它們之間存在線性關係。可能這麼說有些太抽象，下面舉個生活中的例子來形象地說明一下線性插值。
如下圖所示，女朋友每周生氣次數和男生的直男程度是線性相關的。已知A男生直男程度為1，女朋友每周生氣次數為4千次。另外一個B男生，直男程度為5，女朋友每周生氣的次數為6千次。那麼C男生直男程度為3，那麼他女朋友每周的生氣程度是可以根據A和B的情況被計算出來的。
由於他的直男程度是A和B的中間值，所以在A和B中間插值的結果為5千。如果C的直男程度向B的方向移動，則他女朋友生氣的次數會更多。回到本文想討論的雙線性插值的話，計算出一個點數值需要這個點周圍4個點的數值。
將單線性插值升維成雙線性插值後，計算一個點的情況如下圖所示。首先藍色的點是水平方向單線性插值算出來的數，接著在垂直方向上2個藍色的點線性插值出紅色的點，經過兩次單線性插值之後就完成了雙線性插值的整個過程。
Why？為什麼需要雙線性插值？
在計算機圖像的過程中，圖片放大有很多種不同的方法。速度最快的就是最鄰近法（簡單圖像縮放），它的原理就是直接把源圖像距離最近的像素點值填充到放大圖像的像素點。
缺點就是會在放大圖片中出現很多的馬賽克，圖像放大非常不平滑。而雙線性插值的方法則是每個點都通過前文介紹的線性插值的方法計算出來的，圖片的縮放過程會比較平滑。下面的原理示意圖對比了2種過程的不同。
從示意圖中可以看出，簡單圖像縮放並沒有增加任何圖像信息，而雙線性插值則根據原有的圖片算出了原來並不存在的像素點。下面的實際對比圖中也能看出兩者的區別，雙線性插值會使得圖片縮放更加平滑。
How？怎麼實現雙線性插值？
Interp的算法簡單來說就是用源圖的四個點分別與各自的權重相乘然後再相加得到目標圖片的一個值。所以這個算法的關鍵點有兩個：
1. 源圖4個像素點的選擇；
2. 與4個像素點相乘的權重的計算。
實際上，無論是像素點的選擇還是權重的計算都依賴源圖片和目標圖片長和寬像素點的比例關係。根據源圖片和目標圖片的比例關係可以先算出一個基礎係數（Base_Parameter）。但這並不意味著一個2*2的圖片擴大成4*4的圖片，比例係數就由2/4直接得到，因為雙線性插值的的點是指的每個像素點的中心點的值，如下圖所示。
所以實際的比例關係計算應該是中心點距離的總和之間的比例關係，也就是像素點減一之後的比例關係。還是舉例說明的話，2*2的圖片擴大成4*4的圖片應該就是（2-1）/（4-1）這樣來得出比例關係。為了證明這個推導的正確性，下面是caffe裡面interp層的c++代碼，可以從圖中看到的是選擇像素點的代碼，確實是需要進行減一操作的。
關鍵點1 像素點選擇
用3*3擴大成4*4的例子來舉例說明。根據上面推導出的公式可以得到這個過程中的基礎比例係數是（3-1）/（4-1）=0.67。如下圖所示，目標圖片的第二行第二列的點是由1，2，4，5四個點計算的。因為此時，選擇像素點行的參數為0.67*1=0.67沒有超過1且選擇像素點水平方向和垂直方向的參數為0.67*1=0.67沒有超過1。所以，參與計算的源圖片像素點。
是最左最上的2*2矩陣。到計算目標圖片的第二行第三列數時，水平方向的參數為0.67*2=1.34，這個值超過了1，所以源圖片水平2*2的矩陣要向右移動一個像素的位置。而垂直方向的參數還是0.67，故而垂直方向無需移動。參與運算的數就從1、2、4、5變為了2、3、5、6。
關鍵點2 權重計算
還是用3*3擴大成4*4的例子來舉例說明。現在需要計算0Base下（1，1）的數，也就是圖中黃色的像素點。由於它的行坐標和列坐標都為1，所以這層的計算參數需要分別將行和列的基礎係數乘1得到，也就是行為0.67，列為0.67。具體計算過程為1*(1-0.67)*(1-0.67) + 2*0.67(1-0.67) + 4*(1-0.67)*0.67 +5*0.67*0.67。其中紅字的部分就是權重的計算過程。
小結：
1. 根據輸入輸出解析度計算出基礎係數。
2. 根據需要計算的像素點位置計算出計算參數。
3. 計算參數的整數部分作為index去選擇像素點，小數部分作為權重去計算。
Difference？在FPGA上實現Interp有什麼不同？
首先分析C++代碼中，Interp的計算過程，下圖是caffe中Interp的計算過程代碼。
基礎係數的計算需要用到除法，然後每個像素點的計算參數計算需要用基礎係數和像素的index相乘來得到。在FPGA上，乘法是一件非常消耗資源的事，雖然Xilinx和Altera這樣的FPGA廠商會在每塊FPGA板上設計dsp來專門應對乘法、除法等複雜運算。但dsp的數量是十分有限的，dsp的使用水平很大程度上決定了整個FPGA的計算速度。
一個dsp可以當作一個乘法器使用，而一個除法器則需要多個DSP級聯組成。除此以外，除法器消耗的周期也是十分巨大的，這就意味著除了dsp之外，也需要增加很多寄存器來同步數據，這樣又會降低很多計算性能，還使得FPGA的布線更加困難。
FPGA之所以能提高神經網絡的運算速度，很重要的一個原因就是它是一個靈活可變的架構，無數不同的設計最終可以實現同樣的效果。雪湖之所以能在相對低端的板子上跑運算量巨大的網絡，本質的原因也是公司內部有著大量優秀的FPGA開發工程師。
通過對Interp代碼的仔細研究，工程師們發現了其中的計算規律。只要輸入和輸出的解析度固定，基礎係數可以在FPGA外部提前算出，去掉除法器。同時，每個像素點的計算參數也會根據基礎係數提前算出，到時候通過導入二進位文件的方式進入FPGA的計算單元，減少DSP的使用。
升級1 通過查表減少計算量
在caffe的Interp代碼當中，每次計算出插值的時候都需要進行除法運算，來計算出一個基礎係數，然後根據這個插值在目標圖片的具體位置計算出計算參數。
經過雪湖的FPGA工程師的大膽假設，精心設計和仔細驗證等過程，一套通過查表來減少計算量的方法被應用到了Interp層的計算。具體的實現方法如下：
首先，目標圖片的相關參數被輸入地址產生器這個函數，當地址產生器這個函數開始運行時，會輸出相應的地址去到權重BRAM。
權重BRAM中存著提前輸入的的參數，如前文所述，計算參數的整數部分為INDEX用於選數，小數部分為權重用於計算。所以當權重BRAM的數據取出數，這個數據會被截斷。
前半部分是INDEX，會被作為數據BRAM的地址用於取出對應的2x2窗口數據。後半部分則是對應的權重部分，會被放到寄存器中同步周期，等待窗口數據被取出。
當窗口數據和權重數據同步到達計算函數的時候，dsp會對數據進行一步乘法處理，然後進行加法和截斷的操作（具體計算過程見上文）。最後插值的數據會被總線輸出到內存當中。
小結：
1. 由於輸入輸出的解析度在每一層網絡是固定的，所以部分需要計算量可以在FPGA外部做好，然後存進BRAM。通過查表的方式來減少計算量，實現資源最大化利用。
2. INDEX和對應PARA需存在BRAM的同一個地址，方便通過地址發生器來控制參數的取出和調用，一次解決窗口選擇和權重計算兩個問題。
升級2 通過數據鎖存減少取數周期
如前文介紹，計算一個插值需要有4個源圖片像素點。由於BRAM每個周期只能將一個地址位上的數據讀出來。這就意味著如果將一個feature map的所有像素點都存在一個BRAM裡的話，讀出一個2x2窗口數據就需要用4個周期。
這樣做相當於DSP會在3/4的時間上處於空置狀態。所以在這層實現的時候，採用了一個2行緩存BRAM的方案。如下圖所示，一個BRAM存源圖片的一行數據。
這樣在進數的時候，使用雙口BRAM，開啟先讀後寫的功能就可以讓數據做一個整行的位移。也就是第二行BRAM的數據推進到第一行的BRAM裡面，第二行BRAM再寫入新的數據。在取數的時候，從權重BRAM傳來的地址就代表了數據的水平方向的位置。
這樣的設計在取數時，也變得十分方便。在取數的時候，從權重BRAM傳來的地址就代表了數據的水平方向的位置。與此同時，每個BRAM的輸出口接一個鎖存器，鎖存2x2窗口左側的2個數據。
當窗口滑動的時候，前面的函數傳來一個使能信號，讓鎖存器能夠進行換數操作。這裡存在一個問題，正常卷積層的的窗口滑動是存在這一個固定步長的，而在雙線性插值這種非卷積層，滑動的周期是不固定的。所以在卷積層使用的計數器滑動窗口這種常規手段完全失效，那麼下一個小結會討論滑動的信號如何產生。
小結：
1. 2行BRAM緩存的方案降低了進數和取數的複雜程度。
2. BRAM和出數後接的鎖存器使得一個周期取出2x2窗口數據成為可能。
升級3 通過換數信號兼容更多解析度
在一個FPGA晶片當中，DSP和BRAM都是十分關鍵的資源。所有入門的FPGA開發工程師在DSP的使用率上，幾乎不會有太大的差距，而在BRAM的實用設計上差距就很大了。
原因在於，一個完整的feature map被塞入BRAM是一件非常簡單的事。但代價就是這種做法直接對解析度較大或者通道數較多的feature map宣判了死刑。另外一個壞處就是，一個層佔用太多資源的話，對層合併來說也不是個好消息，直接會降低運算速度。
雪湖在這個問題上是採用了切feature map的方式來解決的。在同一個時間段內，只有2行的數據被存進了BRAM，在保證了一行插值計算所需的數據量的基礎上，最少佔用BRAM存儲空間。
在權重BRAM的數據被取出時，INDEX的一個作用就是被用來取數，另外一個作用就是被用來與上一個周期的INDEX作比較。在雙線性插值中，會產生2個維度的INDEX。
當包含行信息的INDEX（垂直方向）發生改變時，比較器會發出一個換數信號，一行新的數據會通過總線輸入進入BRAM。而當包含列信息的INDEX（水平方向）發生改變時，窗口則向右滑動一個步長。
小結：
1. 行INDEX改變進一行數，列INDEX改變窗口滑動一個步長。
眾所周知，Faster R-CNN是一個全球公認的優秀二階網絡，它是擁有最高精度表現的。但是這樣的目標檢測網絡卻沒有被大規模使用，其主要原因就是它算的慢。
那麼為什麼會算的慢呢？因為業界目前普遍使用GPU去跑Faster R-CNN，而這個網絡實際上對GPU是不友好的。Faster R-CNN當中除了常規的卷積層，它還有大量的Proposal，Interp和ROI-Align等非卷積層。
因為GPU原來就是做圖形圖像處理，它對所有能展開的東西都是非常友好的。但是Faster R-CNN中這些特殊操作的層，GPU就無能為力了。然而這些層是真正賦予Faster R-CNN高精度特性的層。
在雪湖工程師不斷地討論和驗證之後，終於摸索出一條能在fpga上將卷積層和非卷積層並行計算的技術道路。
這種辦法的核心原理就是FPGA內部帶寬巨大和資源調配靈活。而在fpga上實現這種非卷積層的加速運算則是解決Faster R-CNN計算速度慢的核心。
雪湖相信當我們的工程師將越來越多類似於Interp層這樣GPU支持不友好的算子在FPGA上實現之後，一些原本很優秀卻又無法在GPU上發揮最大價值的網絡會在FPGA上迎來自己的春天。
作者簡介：殷慶瑜，雪湖科技FPGA應用研發開發工程師，畢業於英國伯明罕大學並取得工學碩士學位。畢業後進入雪湖極客學院學習並取得優異成績，現負責神經網絡加速器產品開發。
【End】
今日七夕！不取標題，只想娶你
TIOBE 8 月程式語言排行榜：Python 奮力追趕 C，Swift 下跌
被罰 50 億後，Google 不再強制綁定 Android 默認引擎！
張一鳴：我用排除法選工作和擇偶
重磅！AI Top 30+案例評選正式啟動
自然語言處理十問！獨家福利
容器快速入門完全指南
媒體巨頭進軍區塊鏈！紐約時報將用區塊鏈技術打擊假新聞
為什麼雷軍說「華為不懂研發」？