本文介紹稀疏LSTM的硬件架構(gòu)，一種是細(xì)粒度稀疏化，權(quán)重參數(shù)分布隨機(jī)，另外一種是bank-balance稀疏化。

1. 文章結(jié)構(gòu)

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

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

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

2. fine-grained稀疏化

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

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

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

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

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

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

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

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

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

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

3. bank-balance架構(gòu)

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

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

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

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

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

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

4. 總結(jié)

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

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.