針對LSTM實現(xiàn)硬件加速的稀疏化案例分析

本文介紹稀疏LSTM的硬件架構，一種是細粒度稀疏化，權重參數(shù)分布隨機，另外一種是bank-balance稀疏化。

1. 文章結構

Long-short term memory，簡稱LSTM，被廣泛的應用于語音識別、機器翻譯、手寫識別等。LSTM涉及到大量的矩陣乘法和向量乘法運算，會消耗大量的FPGA計算資源和帶寬。為了實現(xiàn)硬件加速，提出了稀疏LSTM。核心是通過剪枝算法去除影響較小的權重，不斷迭代訓練以達到目標函數(shù)收斂。參與實際運算的權重數(shù)量大大縮減，這可以有效降低FPGA計算資源和緩解帶寬以及存儲。本博文結構如下：

1） Fine-grained稀疏壓縮的硬件架構。權重稀疏化后，數(shù)據(jù)被大大壓縮，但是也增加了有效數(shù)據(jù)分布不規(guī)律性，這些增加了硬件實現(xiàn)復雜性。

2） Bank-balanced稀疏化方法以及硬件架構。為了能夠提高權重數(shù)據(jù)規(guī)律性，提出了bank-balanced稀疏化方式。

2. fine-grained稀疏化

首先要講的是細粒度壓縮架構。當對一個已經(jīng)訓練好的網(wǎng)絡進行剪枝后，你會發(fā)現(xiàn)權重分布會變得十分隨機。這不利于硬件加速的實現(xiàn)，因為FPGA更喜歡整齊劃一的結構，這樣便于并行化處理。比如對于下邊左圖，每一行有效權重數(shù)據(jù)個數(shù)不同，而我們在硬件中按照行（這是最容易的并行化方式）并行運算的時候，每一行計算的時間就不會相等，用時少的會等待用時長的，最終用時長的決定了計算的總時間。這樣就產(chǎn)生了計算間歇，降低了計算利用率。左圖的計算效率就只有60%（(5+2+4+1)/20=60%）。、

為了提升計算效率，降低等待時間，最理想情況是每行的有效權重數(shù)據(jù)相同，這樣就不需要進行等待了。如右圖，僅僅每行計算都需要三個時鐘周期。計算效率100%。在進行訓練的時候，就需要添加約束條件使得每行具有相同的有效權重數(shù)。從結果看出，這樣處理在能夠加速硬件的同時，還可以保持不變的精度。

模型數(shù)據(jù)訓練是基于浮點數(shù)的，浮點運算非常消耗硬件資源，最好的辦法就是進行量化，即將浮點轉化為定點。量化基本觀點就是將相互接近的數(shù)用一個數(shù)來表示，可以看做是一種聚類。假設參數(shù)集W，將其分成h類C。使用k-means聚類，就是最小化：

量化之后不僅減小了權重數(shù)據(jù)量，這對FPGA上緩存需求以及帶寬都能有效緩解，而且還會降低浮點運算帶來的巨大邏輯資源消耗。

LSTM中包含了矩陣乘向量，矩陣點乘等操作。進行了剪枝和量化后的權重數(shù)據(jù)大大減少，為了只傳遞有效權重，需要對權重數(shù)據(jù)進行稀疏編碼。論文中采用這樣的方式：一個有效數(shù)據(jù)外加兩個指數(shù)，用于標識數(shù)據(jù)所在矩陣中的位置。一個指數(shù)是相對行號，相對行號表示下一個數(shù)據(jù)相對于前一個數(shù)據(jù)的行號距離。另外一個是列號，表示數(shù)據(jù)所在列坐標。這樣在FPGA中就可以根據(jù)這兩個指數(shù)回復權重的位置，并且取出向量中對應的數(shù)據(jù)?？梢栽诰仃囆械幕A上進行并行化設計，比如設計N個并行乘法陣列，每個陣列有3個乘法器，乘法器之間可以進行累加。假設矩陣每行3個有效數(shù)據(jù)，這樣每個陣列就可以進行3次并行乘法運算，并能前向累加。

再來看整體架構，F(xiàn)PGA進行矩陣乘法，矩陣點乘，激活等加速操作，CPU進行指令、權重、輸入數(shù)據(jù)調度。CPU通過PCIE和FPGA進行通信，將權重、指令、輸入等數(shù)據(jù)發(fā)送到FPGA端，并且接收來自FPGA的處理結果。由于權重等數(shù)據(jù)很大，所以FPGA板卡上也配備了自己的DDR，用于存儲這些數(shù)據(jù)。并且在FPGA芯片中也需要一定緩存用于存儲權重數(shù)據(jù)（這部分數(shù)據(jù)很大，最好是片上可以放得下）、臨時數(shù)據(jù)、結果等。通常都是FPGA計算量很大，而FPGA和DDR的帶寬受到限制，所以一個有較大片上存儲資源的FPGA更有利于深度學習的加速。

FPGA上的結構主要有：和CPU通信的PCIE控制，讀寫DDR的控制接口，輸入輸出緩存，加速計算單元，指令控制和調度。其中加速單元是核心模塊，其中包括了稀疏矩陣乘法，累加，激活函數(shù)等操作模塊。

稀疏矩陣乘法和點乘操作是最耗費計算資源和數(shù)據(jù)資源的，為了提高計算效率。論文中根據(jù)數(shù)據(jù)之間依賴關系建立了整個控制流程。設計的目標是盡量提高并行化，減少等待時間，使得計算和加載數(shù)據(jù)時間可以重疊。比如是相互獨立的，就可以同時計算。而有些雖然相互獨立，但是存儲相互沖突，就只能順序計算。比如

即使經(jīng)過了剪枝和量化，權重參數(shù)也很多，片上有限的資源遠遠承受不了，所以這些數(shù)據(jù)都存放在DDR中。在需要的時候加載到片上，如果能夠做好流水以及有較大帶寬，是能夠有較高計算效率的。

Activation vector queue：ActQueue包含很多FIFO，每個FIFO存儲了向量數(shù)據(jù)，每個ActQueue被同一個通道的PE共享。每個FIFO對應一個PE。ActQueue用于提供給各個PE用的數(shù)據(jù)，這些數(shù)據(jù)在向量中并不是對齊的。如果某一行中有效權重數(shù)據(jù)少，那么其就需要等待其他PE完成。

3. bank-balance架構

提出bank-balanced結構是為了解決fine-grained結構中數(shù)據(jù)隨機不對齊的問題。將權重矩陣每行分割成bank單元，讓每個單元中的有效權重數(shù)據(jù)數(shù)量相等。對比fine-grained和coarse-grained稀疏化，fine-grained可以將參數(shù)壓縮的很高，但是導致權重分布不均勻，而coarse-grained能夠獲得均勻的權重結構，但是精度下降很大。Bank-balanced結構既有分布均勻的權重，同時又能夠保持精度。

BBS結構有利于硬件加速，以為不僅僅可以增加行間并行度，還可以按照每行相同的bank數(shù)進行bank并行計算。而且每個bank數(shù)據(jù)量相同，那么計算的時候可以同時進行，沒有等待時間。比如我們有一個矩陣按行分為4個bank，那么對應的向量也分成4個bank，bank間是并行計算的。Bank內會依次次取出有效的權重和對應的向量，進行乘法之后再累加。這種方式可以避免無規(guī)則的計算以及訪問存儲。

稀疏化后的矩陣是需要經(jīng)過編碼的，這樣才能確定其在矩陣中位置。編碼方式比較流行的有CSR，COO以及CSC等。但是他們一般都是用兩個指數(shù)（比如行號和列號）來表示數(shù)據(jù)位置，這會額外增加數(shù)據(jù)負重。本論文中針對BBS結構設計了一種靈活簡潔的編碼：CBS。其由兩行組成。第一行將數(shù)據(jù)重新排列，取出每個bank中第一個非零數(shù)據(jù)一次排列，然后再取出第二個bank中非零數(shù)據(jù)。第二行由數(shù)據(jù)所在的bank內位置決定。這個位置指標可以用于后邊取得向量數(shù)據(jù)的bram地址。

整個硬件架構如下圖：主要包括PCIE控制，DDR控制接口，指令控制，PE陣列，矩陣存儲，向量存儲，之后的點乘和累加等。再介紹一下指令類型：

1） load/store: 這兩個指令用于從DDR中加載數(shù)據(jù)到片上或者從片上存儲數(shù)據(jù)到DDR中。

2） computational指令：根據(jù)LSTM的運算模式分成了兩種，一個是spMx指令，用于計算矩陣乘法，另外一個是EWOP，這個用于點乘，累加，三種激活。

4. 總結

總結一下，這篇文章我們主要介紹了針對LSTM實現(xiàn)硬件加速的方式：稀疏化。稀疏化會大大降低權重參數(shù)，降低計算量以及存儲空間。同時比較了兩種稀疏化方式（fine-grained和bank-balanced）的不同。介紹了LSTM硬件實現(xiàn)的基本架構和指令集。

1. Cao, S., et al., Efficient and Effective Sparse LSTM on FPGA with Bank-Balanced Sparsity, in Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays - FPGA '19. 2019. p. 63-72.

2. Huizi Mao, S.H., Jeff Pool, Wenshuo Li, Xingyu Liu, Yu Wang, William J. Dally, Exploringthe Regularity of Sparse Structurein Convolutional Neural Networks. NIPS, 2017.

3. Song Han , J.K., Huizi Mao, Yiming Hu, Xin Li, Yubin Li, Dongliang Xie, Hong Luo, Song Yao, Yu Wang, Huazhong Yang and William J. Dally, ESE: Efficient Speech Recognition Engine with Sparse LSTM on FPGA, in Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays - FPGA. 2017. p. 75-84.