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

1. 文章結構

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

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

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

2. fine-grained稀疏化

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

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

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

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

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

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

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

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

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

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

3. bank-balance架構

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

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

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

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

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

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

4. 總結

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

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.