Introduction to Hardware
DNN 常見的運算包含 Convolution 與 FC Layer，這兩類 Layer 的核心多半是大量點積運算，而點積又會仰賴 MAC（Multiply-Accumulate，乘法累加器）。在硬體裡，MAC 通常會放在 ALU 中，因此一塊運算單元會配置不少 ALU 來支撐高吞吐量。
這篇 survey 將 DNN 運算硬體分成兩大類：
- Temporal Architecture：代表是 CPU、GPU。
- Spatial Architecture：代表是 ASIC、FPGA 這類 DNN accelerator。
Temporal Architecture and Spatial Architecture
Temporal Architecture 主要包含 CPU 與 GPU。這類架構通常透過 SIMD、SIMT 與演算法最佳化來縮短運算時間。
Spatial Architecture 則比較接近加速器的設計思路，常見實作是 ASIC 或 FPGA。它會將 Register File 與 Control Logic 放在 ALU 附近，藉此減少資料搬移，降低能耗。
Temporal Architecture
Temporal Architecture 的重點比較偏向「如何把 DNN 運算轉成適合 CPU/GPU 執行的形式」。
FC Layer and Convolutional Layer
FC Layer 本質上就是 2 維 Input 與 Filter 的內積。如果 Input 原本不是 2 維，例如包含 Channel 或 Batch Size，就會先 flatten 成 2 維矩陣，其中一維通常是 Batch Size。轉成矩陣乘法後，CPU/GPU 就可以用 SIMD 或 SIMT 來加速。
Convolutional Layer 也可以用類似方式處理：把 convolution kernel 攤成 1 維陣列，再把 Input 攤成對應的 2 維陣列，最後轉成矩陣內積。缺點是轉換後的 Input feature map 會變大，尤其在多個 Filter 同時計算時，Input feature map 會被重複展開。
Convolution Optimization
作者提到兩種常見的矩陣內積最佳化方法：
- FFT：適合把 convolution 轉到頻域計算。
- Strassen Algorithm：適合加速矩陣乘法。
FFT 的複雜度可從 O(No^2 * Nf^2) 降到 O(No^2 * log No)，其中 Nf 是 Filter 的長寬，No 是 Output 的長寬。不過 Nf^2 不一定比 log No 大，因此作者建議 Filter 較大時，例如 filter > 5 * 5，再考慮 FFT。
Strassen Algorithm 則是把矩陣乘法從 O(N^3) 降到 O(N^(log7/log2))。由於 convolution 轉矩陣乘法時，Filter 越大，展開後的 Input 越容易膨脹，所以 Strassen 比較適合 Filter 較小的情境，例如 filter < 3 * 3。
Spatial Architecture
MAC 運作時會從 DRAM 讀取資料、進行乘法與加法，最後再把結果寫回 DRAM。從能耗比較可以看到，DRAM 存取的成本是 ALU 運算的上百倍。
因此 Spatial Architecture 的目標是減少資料搬移。它會把 Register File 與 Control Logic 放在 ALU 旁邊，組成 Processing Engine（PE），讓資料能在更靠近運算單元的位置被重複使用。
Data Reuse
PE 中的 Register File 離 ALU 很近，因此設計重點會變成如何提高 Data Reuse。作者將 Data Reuse 分成三種：
- Convolutional Reuse：Convolution 運算中，Filter 與 Input 都會被重複使用。
- Fmap Reuse：一筆 Feature Map 資料可能被多個 Filter 使用。
- Filter Reuse：多筆資料可能共用同一個 Filter，常見於
Batch Size > 1。
Term Explanation
在介紹 AI 加速器的種類前，先整理幾個常用術語。
一般電腦程式會先透過 Compiler 編譯成 Binary code，再交給 Processor 執行；Processor 的結構通常稱為 Architecture。
AI 加速器的流程很像：DNN 會先透過 Mapper 轉成對應的 Mapping，再交給 DNN Accelerator 執行；DNN Accelerator 的資料流設計則稱為 Dataflow。
Dataflow
AI 加速器的 Dataflow 主要可以分成 4 種：
Weight Stationary（WS）
WS 的目標是最小化讀取 Weights 的能耗，也就是盡量讓 Weight 留在 Register File 中重複使用。
Output Stationary（OS）
OS 的目標是最小化讀寫 Partial Sum 的能耗，也就是盡量讓 Partial Sum 留在 Register File 中。
OS Dataflow 又可以依照 Channel 與 Activation 的數量分成 OSA、OSB、OSC。OSA 主要處理 Convolution，OSC 主要處理 FC Layer，OSB 則介於兩者之間。
No Local Reuse（NLR）
Register File 可以減少能耗，但會增加面積。NLR 則反過來弱化 local reuse，目標是最大化 Global Buffer 的儲存能力，並最小化 Off-Chip Memory Bandwidth。
Row Stationary（RS）
RS 的目標是最大化所有類型資料在 Register File 中的重複使用機會。以 1 維 Convolution 為例，PE 中的 Filter 幾乎固定不動，只位移 Input 與 Partial Sum 來完成運算。
2 維陣列的概念也類似，只是會使用多個 PE。Filter 仍然維持相對固定，每次計算 Row 時主要位移 Input 與 Partial Sum。
如果有多個 Channel 或 Batch Size 大於 1，則可以透過連接與交錯的方式得到對應輸出。
Dataflow Example
作者使用 Eyeriss DNN Accelerator 作為範例，它的 PE Array 大小為 12 * 14。
這時會遇到兩個問題：
- PE Array 和 Layer 大小不同：Layer 較小時，可以一次塞多張 Layer 到 PE Array；Layer 較大時，則可以透過裁切或 folding 塞進 PE Array。
- 資料不知道要傳到哪個 PE：可以使用 Multicast Network 解決。最簡單的做法是廣播資料，再由 PE Array 中的 Control Logic 篩選每個 PE 需要的資料。
Dataflow Comparision
接著比較 WS、OS、NLR 與 RS 的能耗表現。
在 Convolutional Layer 中，RS 因為最大化 Register File 中的資料重複使用，所以 RF 能耗較高，但整體能耗最低。NLR 因為沒有 RF，資料都放在 Buffer，因此 Buffer 能耗最高。OSA 專門處理 Convolution，所以能耗也比 OSC 更低。
從另一個角度看，WS 因為最大化 Weight reuse，所以 Weight 能耗最低；OS 因為最大化 Partial Sum reuse，所以 Partial Sum 能耗最低。
在 FC Layer 中，OSC 因為更適合 FC Layer，所以能耗比 OSA 小。
最後一張圖是使用 RS Dataflow 跑 AlexNet 的能耗分析。L1 ~ L5 多為 Convolutional Layer，RF 能耗較高；L6 ~ L8 多為 FC Layer，DRAM 能耗較高。整體來看，L1 ~ L5 消耗了大部分能量，而後續神經網路也越來越偏向大量使用 Convolution，因此改善 Convolution 的資料搬移與重複使用會非常重要。
