Efficient Processing of Deep Neural Networks, A Tutorial and Survey小結精讀
Introduction to Hardware
DNN常有的結構包含Convolution和Fc Layer，而這兩種Layer的點積運算仰賴於MAC(乘法累加器)，而MAC會藏在ALU中。
而一塊運算單元中，Hardware會有不少的ALU。對於Hardware的分類，作者將其分成兩大類，分別是Temporal Architecture和Spatial Architecture。
Temporal Architecture and Spatial Architecture
Temporal Architure主要包含CPU和GPU，原因在於CPU和GPU常使用SIMD和SIMT的技術和最佳化演算法來節省運算時間。
而Spatial Architure就是加速器，常用ASIC和FPGA實作，是透過將Register File和Control Logic放在ALU旁邊達到節省能耗的效果。
Temporal Architecture
對於Temporal Architecture，作者專注於演算法的最佳化討論。
FC Layer and Convolutional Layer
首先作者介紹FC Layer和Convolutional Layer是如何在CPU和GPU中做運算。
FC Layer的部分，實際上就是2維的Input和Filter做內積，如果Input不是2維，像是包含了Channel和Batch Size的話，那就要將矩陣Flatten後變成2維，其中一維的大小是Batch Size。而CPU和GPU在處理內積時，就能使用SIMD和SIMT。
Convolutional Layer的部分，如果想要更進一步加速運算，可以將Convolution攤成1維陣列，Input攤成的對應的二維陣列，最後就能轉換成矩陣內積。缺點就是轉換後的Input Fmap會變大，尤其當有多個Filter時，就要有多次重複的Input Fmap。
Convolution Optimization
接著作者對於矩陣內積提出了兩種最佳化的方法。一種是快速傅立葉變換，另一種是Strassen Algorithm。
如何透過快速傅立葉變換進行內積的話，可以參考這篇，最後可以知道複雜度從O(No^2 * Nf^2)變成O(No^2 * log No)，其中Nf是Filter的長和寬度，No是Output的長度和寬度。
另一種Strassen Algorithm的話，可以參考這篇，最後可以知道複雜度從O(N^3)變成O(N^(log7/log2))。
從FFT的複雜度可以觀察到，Nf^2不一定比log No來的大，所以作者說要盡量在Filter比較大(filter > 5 * 5)時使用FFT。而Strassen
Algorithm是用在矩陣乘法，前面提到當矩陣內積轉換成矩陣乘法時，Input會變大，尤其在Filter大小越大時，Input變大速度特別快，所以Strassen
Algorithm適合在Filter較小(filter < 3 * 3)時使用。
Spatial Architecture
作者提到MAC在運作時，會從DRAM讀取3筆資料分別進行乘法和加法，最後再將1筆資料寫回DRAM，而從圖中可以看到各個單元的能耗比較，會發現DRAM的能耗會是ALU的上百倍。為了減少能耗，Spatial Architecture就此誕生，Spatial Architecture的特點就是將Register File和Control Logic直接放在ALU旁邊，組成Processing Engine(PE)。
Data Reuse
既然PE中的Register File放在ALU旁邊，為了讓Register File內的東西可以重複被使用，所以作者探討了Data Reuse的時機。
Data Reuse可以分成Convolutional Reuse，Fmap Reuse和Filter
Reuse。Convolutional Reuse就是Convolutional
Layer進行運算時，Filter和Input都會重複使用。而Fmap Reuse和Filter
Reuse則是可能會有一筆資料對應到多筆Filter或是多筆資料對應到一筆Filter的情形。而Filter
Reuse常見的情況出自於Batch Size > 1的時候，就會有多筆資料一直使用同個Filter。
Term Explanation
在介紹AI加速器的種類前，先簡單提AI加速器相關的術語。
對於一般的電腦，如果有一個Program，被Compiler編譯後，得到Binary code，再拿去給Processor執行，而Processor的構造會被稱作Architecture。
而AI加速器的邏輯跟上述的事情其實很像，首先會先把DNN透過Mapper，得到對應的Mapping，再將Mapping交給DNN
Accelerator執行，而DNN Accelerator的構造會被稱作Dataflow。
Dataflow
關於AI加速器的Dataflow，主要可以分成4種主要架構，分別是Weight Stationary(WS)，Output Stationary(OS)，No Local Reuse(NLR)和Row Stationary(RS)。
Weight Stationary(WS)
WS的目標就是最小化讀Weights的能耗，也就是最大化Weights從Register File中取得的機會。
Output Stationary(OS)
OS的目標就是最小化讀寫Partial Sum的能耗，也就是最大化Partial Sum從Register File中取得的機會。
其中，OS Dataflow又能根據Channel和Activation的數量，分成3種變體，分別是OSA，OSB，OSC。OSA Dataflow主要處理Convolution，OSC主要處理FC Layer，而OSB架構介在OSA和OSB中間。
No Local Reuse(NLR)
從RS和OS Dataflow看到，Register File可以減少能耗，但相對的會增加不少面積，因此產生了NLR，目標在於最大化Global Buffer儲存能力，最小化Off-Chip Memory Bandwidth。
Row Stationary(RS)
RS的目標就是最大化所有類型的Data在RF中重複使用的機會。
舉個例子，下圖中1維Convolution的話，可以看到PE中的RF，裡面的Filter完全不動，只位移Input和Partial Sum來完成運算，而Filter和Input沒有位移很多，正是Data Reuse的展現。
2維陣列的話，與1維陣列的不同，是使用了多個PE，然後Filter還是沒動，每次計算Row也只有位移Input和Partial Sum。
如果有多個Channel和Batch Size大於1的情況，就是透過連接和交錯，就能獲得對應的輸出。
Dataflow Example
作者為了講述Dataflow如何運行DNN，給了一個範例，Eyeriss DNN
Accelerator，其PE Array大小為12*14。
這時會遇到兩個問題:
PE Array和Layer大小不同
像左圖，如果Layer很小，那就可以安排一次塞多張Layer到PE Array上。若像右圖，如果Layer很大，那就可以透過裁剪，把Layer塞到PE Array上。
Data不知道要傳去哪個對應的PE Array
作者說可以使用Multicast Network解決這個問題，最簡單的做法就是廣播所有的Data，然後透過PE Array中的Control Logic篩選PE需要的Data。
Dataflow Comparision
接著比較WS，OS，NLR和RS的能耗。
下圖是在跑Convolutional
Layer時，每個Dataflow能耗的比較。能看到RS因為最大化RF重複使用各種數據，RF能耗最大，但整體能耗最小。NLR因為沒有RF，資料都塞Buffer，所以Buffer能耗最大。剛剛有提過OSA
Dataflow專門處理Convolution，所以OSA能耗比OSC小。
下圖也還是跑Convolutional
Layer時，每個Dataflow能耗的比較。可以看到WS因為最大化RF重複使用Weight，所以Weight的能耗最小。OS因為最大化RF重複使用Partial
Sum，所以Partial Sum的能耗最小。
下圖跟上圖不同在於，下圖是跑FC
Layer時，每個Dataflow能耗的比較。因為OSC Dataflow專門處理FC
Layer，所以OSC能耗比OSA小。
最後一張圖是在講述，用RS Dataflow跑AlexNet的能耗分析。可以看到L1 ~
L5大多為Convolutional Layer，而Convolutional Layer的RF能耗高。L6 ~
L8大多為FC Layer，而FC Layer的Dram能耗高。但是，比例上來說，L1 ~
L5用了大部分的能耗。而未來的NN Model也是朝著越用越多Convolutional
Layer的趨勢在走，所以作者覺得未來應該盡量改良Convolution。
Reference
Efficient Processing of Deep Neural Networks: A Tutorial and Survey, Part V. : https://arxiv.org/pdf/1703.09039.pdf