首發(fā)于個人博客
算法基礎(chǔ)
EIE（Efficient Inference Engine）的算法基礎(chǔ)是一種被稱為Deep Compression的神經(jīng)網(wǎng)絡(luò)壓縮算法。EIE可以說是為Deep Compression量身定制的硬件，Deep Compression的算法流程如下所示：
- 剪枝：將小于某個閾值的權(quán)值直接置為0南窗，這一操作引入權(quán)值的稀疏性
- 量化：這里的量化是一種非線性量化珊蟀，通過k近鄰類聚算法確定量化中心和量化間隔
- 編碼：原文中使用霍夫曼編碼壓縮權(quán)值的存儲辙纬，EIE中使用CSC壓縮存儲方式
Deep Compression壓縮
Deep Compression壓縮分為剪枝批什、量化和編碼操作卧斟。其中剪枝為對所有權(quán)值做以下操作：
其中T為剪枝閾值糠涛，該步驟將所有小于剪枝閾值T的權(quán)值置為0援奢，引入了權(quán)值的稀疏性。原文中對于VGG結(jié)構(gòu)的剪枝后忍捡，卷積層的非零參數(shù)量一般還剩原參數(shù)量的30%~60%中集漾，全連接層的非零參數(shù)量一般僅剩5%以下，由于全連接層參數(shù)占參數(shù)的主要部分砸脊，因此全網(wǎng)絡(luò)的非零參數(shù)量僅剩下原有的7.5%具篇。考慮VGG是比較容易產(chǎn)生冗余的網(wǎng)絡(luò)凌埂，因此對其他網(wǎng)絡(luò)的剪枝效果可能差于VGG網(wǎng)絡(luò)驱显。剪枝閾值T在剪枝過程中為超參數(shù)，需要綜合考慮剪枝效果和剪枝后網(wǎng)絡(luò)的性能表現(xiàn)多次試驗確定瞳抓。
量化操作為對于每個層埃疫，使用k-近鄰類聚算法類聚。類聚算法產(chǎn)生指定數(shù)量的類聚中心挨下，所有屬于某一類的權(quán)值都被直接賦予類聚中心的值熔恢。隨后使用修改過的優(yōu)化算法運行一定輪數(shù)的訓(xùn)練，調(diào)整類聚中心的值（權(quán)值從屬關(guān)系不改變）臭笆，具體過程參見Deep Compression論文叙淌，這里僅考慮結(jié)果秤掌，進行完量化后，每一層的權(quán)值張量變?yōu)橐粋€同形狀的標號張量和一個解碼表鹰霍。標號張量標記每個位置的元素屬于的類別闻鉴，一般僅有25bit（即分為432類）；解碼表標記每個類別的數(shù)據(jù)茂洒，如下圖所示：
現(xiàn)在考慮量化對實現(xiàn)的影響孟岛。原有的高精度權(quán)值張量（取bit）的非零參數(shù)量為M，則需要的存儲空間為
bit督勺。量化后權(quán)值張量改為標號張量渠羞，標號的位數(shù)一般遠遠低于權(quán)值數(shù)據(jù)，取為
智哀，需要存儲空間為
次询；另考慮編碼表，編碼表需要的bit數(shù)為
瓷叫。則量化后權(quán)值需要的存儲空間占原有比例為：
一般來說僅有5bit（VGG網(wǎng)絡(luò)）屯吊，因此有
，則可以發(fā)現(xiàn)將權(quán)值的存儲空間降低到
摹菠，有效的緩解了存儲瓶頸盒卸。但是權(quán)值使用時，需要根據(jù)標號張量中的標號從編碼表中查詢權(quán)值次氨，再將其與輸入進行運算蔽介，比原有矩陣直接運算多一步查詢，需要通過硬件查詢糟需。
Deep Compression論文中為了進一步壓縮權(quán)值的存儲屉佳，在量化后使用霍夫曼編碼壓縮矩陣的存儲。EIE為了方便的硬件實現(xiàn)洲押，使用CSC方法壓縮稀疏權(quán)值矩陣武花。
CSC稀疏矩陣表示
CSC（compressed sparse column）為一種稀疏矩陣的表示方法，其將一個稀疏矩陣壓縮表示為三個向量杈帐。首先考慮向量的壓縮方法体箕，每個稀疏向量被壓縮為兩個非稀疏向量，如下所示的向量：
將其壓縮為兩個長度相等的向量挑童，第一個向量為按順序排列的所有的非稀疏元素累铅，第二個向量為對應(yīng)位置的非稀疏元素與前面一個非稀疏元素中間的0數(shù)量，上述向量壓縮完成如下所示：
u為非零元素站叼，z為兩個非零元素之間0的數(shù)量娃兽。例如表示第一個非0元素為1，該元素之前有2個零尽楔；
表示第二個非0元素為2投储，該元素之前沒有0（原向量中為
）第练。由于這里的z向量使用的為int4類型數(shù)據(jù)，因此第三個非零數(shù)據(jù)3之前的18個零超出了表示范圍玛荞，因此在v中添加一個0元素娇掏，即其中
表示第三個數(shù)據(jù)為0，之前有15個0勋眯。這個數(shù)據(jù)并不是非零數(shù)據(jù)婴梧，是為了能使用int4表示18而額外補充的數(shù)據(jù)。之后的
為要表示的數(shù)據(jù)3客蹋，之前有2個零塞蹭，和前一條一起表示間隔18個零的情況，如下圖所示：
隨后考慮矩陣的表示方法讶坯，CSC稀疏表示將矩陣的每一列視為一個向量進行壓縮浮还，每一列都產(chǎn)生一個v向量和一個z向量，第i列產(chǎn)生的向量和
向量的長度和其他列均可能不同闽巩。將每一列的v向量按列號依次連接，z向量按列號依次連接担汤，獲得矩陣的v和z向量涎跨，為了區(qū)分不同列，額外引入u向量崭歧，u向量長度為列數(shù)加1隅很，表示每一列的v或z向量在矩陣v和z向量中的位置，即第i列的v和z向量在矩陣的v和z向量的第
個到第
元素之間率碾，u[0]固定為0叔营。如下圖所示：
最終，一個稀疏矩陣將被壓縮到三個向量U所宰、V和Z中绒尊，該方式僅保存非零數(shù)據(jù)（為了表示超過Z限制額外引入的0除外），同時Z和U向量使用的數(shù)據(jù)類型一般比U小仔粥，因此可以有效的壓縮稀疏矩陣婴谱。
EIE結(jié)構(gòu)
PE結(jié)構(gòu)
EIE（Efficient Inference Engine）作為一種Engine，主要作為加速器系統(tǒng)組件使用躯泰，因此論文中并未提出明確的系統(tǒng)架構(gòu)谭羔，而是重點描述了其PE的結(jié)構(gòu)，PE結(jié)構(gòu)圖如下：
PE按功能為以下幾個部分：
- 藍色底色部分為緩存部分麦向，分布緩存了CSC格式表示矩陣方法下的U瘟裸、V和Z向量以及Deep Compression產(chǎn)生的解碼表和產(chǎn)生的部分和輸出數(shù)據(jù)。
- 紫色底色部分為標號處理部分诵竭，標號累加為一個累加器话告，通過累加一個向量CSC表示中之前的元素的z部分產(chǎn)生該元素在向量中的實際絕對位置兼搏；列地址生成從矩陣從U向量中獲取某一列的數(shù)據(jù)在V和Z向量中的起始和結(jié)束位置。
- 橙色底色部分為算數(shù)運算部分超棺，輸入數(shù)據(jù)和解碼后的權(quán)值相乘并和之前的結(jié)構(gòu)相加向族，結(jié)果保存在輸出緩存中，當運算完成時棠绘，通過ReLu單元激活后輸出件相。
該PE如何映射運算將在后續(xù)章節(jié)[算法映射]中表述。
CSC編碼器
PE運算產(chǎn)生的結(jié)果并不是CSC方法表示氧苍。一般來說夜矗，在ReLU函數(shù)之前的輸出數(shù)據(jù)并不具有稀疏性，但是ReLU函數(shù)將所有負數(shù)輸出置為0让虐，引入了輸入\輸出數(shù)據(jù)的稀疏性紊撕，因此需要將輸出數(shù)據(jù)進行CSC編碼，CSC編碼器結(jié)構(gòu)如下所示：
論文中PE以4個一組赡突，每個PE輸出一個輸出數(shù)據(jù)及其絕對標號对扶，非零數(shù)據(jù)檢測器從PE0的輸出數(shù)據(jù)開始依次檢測，若發(fā)現(xiàn)非0數(shù)據(jù)惭缰，則通過絕對標號計算CSC格式的相對標號浪南，同時輸出器數(shù)據(jù)和相對標號，實現(xiàn)CSC編碼漱受。
算法映射
矩陣-向量乘法
原論文中以4個PE為一組络凿，計算矩陣乘法。輸入權(quán)值和輸入數(shù)據(jù)以下圖為例：
矩陣乘法計算的目標為：
上圖中絮记，有a=8、b=8虐先。權(quán)值矩陣的第i行數(shù)據(jù)保存在標號為的PE中并由該PE負責計算怨愤。第i個PE的所有權(quán)值行向量順序堆疊組成一個新權(quán)值矩陣
，這里新權(quán)值矩陣為2行赴穗。標號為i的PE中存儲的是新權(quán)值矩陣
的CSC表示憔四。
EIE映射算法的原理如下圖所示，綜合考慮輸入數(shù)據(jù)和權(quán)值的稀疏性般眉，將矩陣-向量乘法分解為多個向量相乘了赵，當且僅當對應(yīng)位置上的元素均不為0時才進行計算，因此可以減少很多0之間的運算甸赃。
EIE的PE輸入為一個CSC格式壓縮的稀疏向量柿汛，將每個元素的數(shù)據(jù)和標號（v和z）依次輸入數(shù)據(jù)隊列和標號隊列。處理一個數(shù)據(jù)時，從數(shù)據(jù)隊列中取出數(shù)據(jù)D并從標號隊列中取出標號络断，標號
通過標號累加器變?yōu)橄蛄康慕^對坐標I裁替。以上圖中所述第一個數(shù)據(jù)X0為例，其相z元素為0貌笨，即之前沒有0弱判，因此X0的絕對位置為0。輸入向量CSC格式累加過程如下所示：
隨后通過查詢奇數(shù)U緩存锥惋，
查詢偶數(shù)緩存昌腰。分別從偶數(shù)U緩存和奇數(shù)U緩存中獲取地址各一個：
- 若I為奇數(shù)，則從奇數(shù)緩存中讀取的數(shù)據(jù)為起始地址
膀跌，從偶數(shù)緩存中讀取的數(shù)據(jù)為結(jié)束地址
- 若I為偶數(shù)遭商，則從偶數(shù)緩存中讀取的數(shù)據(jù)為起始地址
對于X0而言捅伤，對應(yīng)絕對位置為0劫流，讀出起始地址為0，結(jié)束地址為1丛忆；對于X2祠汇，讀出起始地址為1，結(jié)束地址為2熄诡；對于X5座哩，讀取起始地址為3，讀取終止地址為4粮彤。對于的情況，說明該輸入數(shù)據(jù)對應(yīng)的列無非0數(shù)據(jù)姜骡，可直接跳過該輸入數(shù)據(jù)的處理過程导坟。隨后使用
和
之間的值（不包括
，即
）從V緩存和Z緩存中讀取權(quán)值圈澈。對于X0惫周，讀出權(quán)值
和相對位置0，對于X2康栈，讀取權(quán)值
和相對位置0递递；對于X5，讀取權(quán)值
和相對位置1啥么。根據(jù)這些權(quán)值從編碼表中查詢真實權(quán)值登舞。相對位置進行與輸入相同的權(quán)值累加計算真實權(quán)值WI，計算結(jié)果分別為0悬荣、0和1菠秒。
隨后輸入數(shù)據(jù)與讀出的真實權(quán)值依次相乘，相乘的結(jié)果與輸出緩存中位置為WI的數(shù)據(jù)累加氯迂，過程如下所示：
累加完成后践叠，輸出緩存每個地址存儲的就是對應(yīng)絕對位置的輸出結(jié)果言缤，完成矩陣-向量乘法映射。
卷積映射
卷積映射在原論文中沒有提到禁灼，一下為基于結(jié)構(gòu)對映射卷積方式的猜測管挟，其映射卷積的方式可能為將卷積拆分為多個矩陣乘法實現(xiàn)，如下圖所示：
PE的輸入為廣播輸入弄捕，因此所有PE的輸入數(shù)據(jù)必須相同僻孝，而所有權(quán)值均為本地存儲，因此權(quán)值應(yīng)當不在PE之間交換察藐，由上推測出卷積的映射方法應(yīng)當將一個的卷積變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=K%20%5Ctimes%20K" alt="K \times K" mathimg="1">個
卷積實現(xiàn)皮璧。上圖舉出了一種
卷積在EIE上實現(xiàn)的可能方案。每個PE計算一個輸出通道為CO+1分飞，輸入通道為CI+1的
卷積悴务，所有PE計算完成后，將結(jié)果錯位相加即可獲得
卷積的計算結(jié)果譬猫，錯位相加過程如下所示：
