可變位寬的大規模矩陣乘法方法
引言
本文介紹了一種數據位寬可變的乘法方法，由於避免了DSP的使用，可以充分利用LUT資源，在DSP數量少的晶元上也可以獲得很高的計算量。這種方法更適合大矩陣乘法，矩陣越大，計算效率就會越高。
01
可變位寬乘演算法
方法其實很簡單，就是利用數據的二進位表示方法。一個有符號二進位數，用二進位表示為：
這樣就將矩陣中每個數都分解成1bit數和一個權重數相乘的形式，而這個權重是2的冪次，在FPGA中可以通過簡單移位操作來實現。論文中給出了一個簡單的例子，求兩個2x2矩陣的乘法，數據位寬為2bit。如下圖1.1所示：首先將每個矩陣分解成兩個矩陣之和，然後通過因式分解分別計算4個1bit矩陣乘法，然後根據權重大小進行移位操作，再求和。乘法只是1bit數，僅僅通過與操作就可以完成了，完全不需要乘法器。但是這樣做也有一個缺點，就是延遲變大了。所以對於特大矩陣乘法來說，這些延遲可以通過增加計算量來彌補。以上方式用偽代碼可以表示為圖1.2。將這種方法進行推廣，可以想到用4進位，8進位來進行數據表示，這樣對於較大位寬數據來說可以降低延時。但是這樣的低價就是增加了LUT資源。比如對於4進位表示，乘法數據為2bit，這個就會需要更多LUT來完成了。如果表示進位更高，比如16進位，那麼用乘法器實現就更合適了。但是這無疑給我們提供了一種可變位寬乘法的設計思路。
圖1.1 2x2矩陣乘法分解過程
圖1.2 可變位寬乘法演算法
02
硬體架構
整體框架如圖2.1所示，基本包括三部分：fetch，execute，result。
Fetch包含一個簡單的DMA引擎，以及一個數據讀取調度器，主要用於從DDR中獲得指令和數據。數據被放於片上緩存中，片上緩存和計算單元通過大量走線互聯，走線的帶寬受到了DDR帶寬的限制，而走線帶寬取決於計算單元的算力。論文中參數化了這三個變數，可以根據不同平台來進行適配。
圖2.1 硬體架構
Execute是最核心的計算單元，這部分由基本的DPU構成。DPU是專門處理數據乘法和累加的單元，這些DPU相互連接成二維平面結構，專門用於處理矩陣乘法。DPU結構主要由一個與門，求和，移位寄存器，累加器組成。與門和求和結構用於計算1bit矩陣乘法，移位寄存器用於乘以權重係數，累加器是用於大矩陣求和。一個大矩陣乘法是被分塊的，然後每塊乘法是用矩陣列x行的形式，這樣計算陣列中的每行和每列對應的bufer中的數據都是被多次利用的，並且以廣播形式傳播到各個單元。這種方式增加了矩陣數據利用率，能夠到達緩解搬運帶寬。這方面計算還可以參見文章《在DNN中FPGA做了什麼？》每個計算單元都會出來一個最終結果，這些結果通過並串轉換分別進入result buffer。
圖2.2 計算結構
Result結構和fetch類似，只不過是寫入DDR。也是通過DMA引擎來控制對DDR寫入。
接下來介紹論文中指令架構，指令也是依據三種結構來設計成對應指令：fetch，execute，result。創新點主要在指令的pipeline設計上。其通過引入「鎖」的機制來實現不同指令之間的依賴關係。用wait來阻塞下一條指令的執行，而用signal來接觸wait，觸發下一條指令執行。三種指令主要是fetch和result相對於execute的依賴。如果fetch完成，execute可以執行，在執行的同時，fetch可以讀取下一次要用的數據，通過這樣的流水來減少execute的等待時間。用一個簡單過程來說明，如圖2.3所示：首先execute進入等待，直到fetch了L和R矩陣數據，此時通過signal來觸發execute的執行。當execute執行L*R的同時，fetch不需要等待，可以進一步下載數據。而在沒有生成最終矩陣數據結果之前，result一直處於等待中，直到完成矩陣運算，execute通過signal來觸發result的執行。
圖2.3 指令依賴關係
03
結果
矩陣大小對計算效率影響很大，矩陣越大，那麼矩陣元素的復用率就高，所以計算效率也越高。
圖3.1 計算效率和矩陣大小k以及數據位寬D_k關係
資源利用和峰值算力如圖3.2，最大算力達到了3.2TOPS。主要對片上BRAM使用較多，這也是矩陣計算中受到限制的重要因素，因為通常限制計算的都是片上緩存以及帶寬。
圖3.2 資源利用
還有功耗估計如圖3.3所示。
圖3.3 功耗
總結
論文提出了一種可變位寬的計算矩陣乘法的方法，通過串列計算乘法來實現。這對於大規模矩陣乘計算比較有優勢，但是對於較小矩陣或者數據位寬較大的乘法來說，效率會比較差。所以這種方法就當做是提供了一種可變bit乘法的思路。
文獻
1. Yaman Umuroglu, L.R., Magnus Sjalander, BISMO: A Scalable Bit-Serial Matrix Multiplication Overlay for Reconfigurable Computing. arXiv preprint, 2018. 18
往期回顧
1. 在DNN中FPGA做了什麼？
2. 稀疏LSTM硬體架構
推薦閱讀：
TAG:現場可編輯邏輯門陣列（FPGA） | 矩陣運算 | 深度學習（DeepLearning） |