# 【ML】TinyML and Efficient Deep Learning Computing Note

## [Lecture Website](https://hanlab.mit.edu/courses/2023-fall-65940)

## Lecture 2 Basics of Deep Learning

### Deep Learning Continuous to Scale
深度學習模型持續擴大，模型的大小是指數型上升的，資本的力量!
問題是算力無法跟上，記憶體也是，所以才有AI Data Center需求跟分布式訓練

### Grouped Convolution Layer
#### 背景
AlexNet作者當年背景，由於GPU不是很發達，所以在做卷積運算時，需要分割卷基層的權重跟輸入的特徵，因而誕生。
#### 概念
Group Convolution Layer 是一種卷積層，它將輸入特徵圖分成多個組，對每個子組進行卷積操作。
- 輸入特徵圖 : $X : (n, c_{i}, h_{i}, w_{i})$
- 輸出特徵圖 : $Y : (n, c_{o}, h_{o}, w_{o})$
- Weights : $W : (c_o, c_i, k_h, k_w) \rightarrow (\text{g} \cdot c_{o}/\text{g}, c_i/\text{g}, k_h, k_w)$
- Bias：$b: (c_{o},)$

| Variable | Define |
| -------------- | --------------------- |
| $n$ | Batch size |
| $c_{i}, c_{o}$ | Input/Output Channels |
| $h_{o}, h_{o}$ | Input/Output height |
| $w_{o}, w_{o}$ | Input/Output width |
| $k_h$, $k_w$ | Kernel Height/Width |
| $g$ | Groups |


### Depthwise Convolution Layer
#### 背景
google的MobileNet，需要在手機等邊緣裝置上裝載模型，需要降低卷基層
#### 概念
將 Grouped Convolution $g = c_o = c_i$ 變成為 Depthwise Convolution，每一個kerenl只會跟一個特徵層做卷積，在空間特徵上失去了不同通道特徵的交互作用，因此會影響效果
- 輸入特徵圖 : $X : (n, c_{i}, h_{i}, w_{i})$
- 輸出特徵圖 : $Y : (n, c_{o}, h_{o}, w_{o})$
- Weights : $W : (c_o, c_i, k_h, k_w) \rightarrow (c_{o}, k_h, k_w)$
- Bias：$b: (c_{o},)$

### Normalization Layer
特徵的正規化有以下優點
* 穩定訓練過程，確保特徵保持一定分布
由於每次特徵分布都確保是平均為0方均差為1
* 正歸化會導致特徵失去原有分布，故新增兩個可以學習參數 $(\gamma,\beta)$ 作為補償
\begin{align}
\mu &= \frac{1}{N} \sum_{i=1}^{N} x_i \\
\sigma^2 &= \frac{1}{N} \sum_{i=1}^{N} (x_i - \mu)^2 \\
\hat{x}_i &= \frac{x_i - \mu}{\sqrt{\sigma^2 + \epsilon}} \\
y_i &= \gamma \hat{x}_i + \beta
\end{align}


在 Pytorch 實現中，推論需要將模型手動設置成推論模式，才會不影響 Batch Layer 的 running mean 跟 running val

model.eval()

Feature Scaling 能夠讓下一層的Layer看到分布上一至的特徵，不會因為某個原因造成特徵值過大導致偏差過大，這樣的作法能夠讓神經網路的Loss對Weight的curve更加平滑，或者說明讓下一層的特徵能夠看到一致分布的特徵
### Activation Functions
* 引入非線性的元素，讓神經網路可以逼近任意函數
* 不同的線性函數擁有不同的梯度狀況
* $\text{ReLU}$ 最省成本比較好進行量化，並維持正向響應神經元的梯度，

### Efficiency Metrics
How should we measure the efficiency of neural networks?
**3個影響模型大小的因素**
1. 模型大小 $\rightarrow$ 存儲空間有關(Parameters vs Model Size)
2. 運算速度 $\rightarrow$ 運算的延遲速度(Latency vs Throughput)
3. 能耗 $\rightarrow$ 消耗的能量為多少(Memory > Compute)

**2個核心指標**
1. Compute 計算
2. Memory 記憶體空間

### Latency 延遲
Measure the delay for a specific task


### Throughput 吞吐量
Measures the rate at which data is processed

### Latency 延遲 vs Throughput 吞吐量
Latency與 Throughput 之間是沒有絕對關係的
1. 高吞吐量不代表低延遲，可能他是平行處理的
2. 低延遲不代表高吞吐量，可能他是單線程

### Energy Consumption
能耗上，將 **Data的移動** 與 **Data reference** 會造成更多能量消耗，DRAM就是個最耗能的操作

### Number of Parameters
| Layer | \# Parameters (bias is ignored) |
| --------------------- |:-------------------------------------------------------------------------------------------------------------- |
| Linear Layer | $c_o \cdot c_i$ |
| Convolution | $c_o \cdot c_i \cdot k_h \cdot k_w$ |
| Grouped Convolution | $\frac{c_o}{g} \cdot \frac{c_i}{g} \cdot k_h \cdot k_w \cdot g$ $=c_o \cdot c_i \cdot k_h \cdot k_w \cdot \frac{1}{g}$ |
| Depthwise Convolution | $c_o \cdot k_h \cdot k_w$ |

### Model size
* Model Size is measures the storage for the weights of the given neural network.
* In general, if the whole model uses the same data type
* $Model size = \text{parameter} \cdot \text{Bit Width}$
* Example:Alex Net has 61M parameters
* 32 bit
* $61M \cdot 4 Bytes = 224 MB (224 \times 10^6 Bytes)$
* 8 bit
* $61M \cdot 1 Bytes = 61 MB (224 \times 10^6 Bytes)$
* Example GPT3 has 1750B
* 32 bit
* $175B \cdot 4 Bytes = 700GB (700 \times 10^9 Bytes)$

### Number of Activations
* Activations就是激活函數的輸入或輸出，兩種定義都有，這邊就是要量測輸入輸出的特徵大小因為這有可能是IOT設備上的瓶頸(Bottleneck)
* Activations在不同層的分布會差很多喔!

下圖表明一件事情，參數量降低後，但是 Peak Activation 並不會降低太多，由於inverted bottleneck 上設計就是將特徵先擴展，並用較大 kernel 取特徵，最後在還原回來。

### Number of Multiply-Accmulate Operation
* Multiply-Accumulate operation (MAC)
乘積累加運算，將b跟c乘完後跟累加器A相加在放入累加器
* Matrix-Vector Multiplication (MV)
* General Matrix-Matrix Multiplication (GEMM)
備註:$\text{MACs}$為$\text{MAC}$複數版本而已

### Number of Floating Point Operations (FLOP)
MAC包含了兩次浮點數操作
1. 乘法操作
2. 加法操作

重點: 約等於兩倍的$\text{MAC}$
$\text{FLOP} = 2 \times \text{MAC}$
| Layer | FLOPs Calculation |
| --------------------- |:------------------------------------------------------------------------- |
| Linear Layer | $c_o \cdot c_i$ |
| Convolution | $c_o \cdot c_i \cdot k_h \cdot k_w \cdot h_o \cdot w_o$ |
| Grouped Convolution | $c_o \cdot c_i \cdot k_h \cdot k_w \cdot \frac{1}{g} \cdot h_o \cdot w_o$ |
| Depthwise Convolution | $c_i \cdot k_h \cdot k_w \cdot h_o \cdot w_o$ |
## Lecture 11 TinyEngine and Parallel Processing

### Parallel Computing Techniques

#### Loop Reordering 迴圈重新排序

執行迴圈的時候讀取資料的時候，可以按行 ( row-major order ) 與按列( column-major order )循訪中，依照環境放元素的方式選擇，可以在不改變迴圈的情況下達成加速，**因為可以增加cache的命中率**，進而達成性能的提升。
* Improve Data Locality
* Data movement(cache miss) is much more expense.
* Chuck of memory is fetched at a time(cache line).
* Reduce Cache Miss
* Chang the order of loop iterative variable
* Index Order: $(i,\ j,\ k) \rightarrow (i,\ k,\ j)$


#### Loop Tiling 循環分磚

在面對巨型資料處理時，如果矩陣大小大到 **cache** 放不下，那麼在執行 Data Reference 就有可能將資料從 cache 放出來，以讓其他元素可以進行操作，這樣便會造成 cache miss 的開銷，因此需要將大矩陣分解成小矩陣依序處理
* 為什麼能夠改進 Cache miss的情況
* 使用 Partition Loop
* 確保資料在 Cache 裡面，直到被使用為止
* 讓 Loop 循環的元素大小可以 Fitting 到 Cache Size 是最佳的

### Loop Unrolling 循環展開

也就是將迴圈操作展開，暴力解法，對於小 kerenl 卷積層適用，其實就是將迴圈一部份展開
* 能夠減少循環的維護(循環條件判斷與計數器累加)
* 可能增加程式碼的大小

### SIMD (single instruction, multiple data) programming

#### What is the Instruction set

* 作為軟體與硬體間的溝通橋樑，定義了軟體如何控制硬體
* 能夠知道處理器甚麼時候完成與如何完成

### Instruction set Types

1. Complex Instruction Set Computer(CISC)
2. Reduced Instruction set Computer(RISC)

### SIMD introduction

一種平行化處理的技術，透過單一指令將多組資料同時操作
* Vector Register (向量暫存器)
* 一種特殊的暫存器，可以儲存與處理多筆資料
* Vector Operations (向量操作)
* 對多筆資料進行邏輯與算數運算
* 優勢
* 大幅增加程式碼的 Throughput and speed
* 增加能量的使用效率


### SEE
SSE 是 Intel的SIMD擴展，
* **SSE:** `_mm_load_ps`/`_mm_mul_ps`/`_mm_add_ps`
* **mm :** multi-media
* **load/mul/add :** load/multiply/add
* **ps :** packed single-precision

### NEON
NEON 是ARM處理器的SIMD擴展，
* **NEON:** `vld1q_f32`/`vmulq_f32`/`vaddq_f32`
* **v :** vector
* **ld/mul/add :** load/multiply/add
* **1 :** number of vector
* **q :** quadword(8 bytes)

### Multi-threading
使用多個 Thread加速處理程序，多 Thread 處理的資料最好不要有相關性，最好是獨立的，避免資料同步問題

#### Two Type of Tools
1. Pthreads
* A C library for creating and managing POSIX threads
2. OpenMP
* An API for C/C++ and Fortran to support parallel programming using shared-memory model.

### CUDA Programming
詳情參照
- [【CUDA】CUDA Programming Note](/-vx2yQneSsWW84Y06zU2ZQ)

### im2col

### Point-Wise Convolution
在 Pytorch 中資料格式為 $B \times C \times H \times W$ ，如果今天使用 $\text{Conv} 1 \times 1$ ，會造成 Cache Miss，因為每次 Reference Tensor 都需要跳著處理元素，因此會先將 Tensor Memory Layout 處理成 $B \times H \times W \times C$ ，就能夠增加 Data Locality


### Depth-Wise Convolution
而 Depth-Wise 則跟 Point-Wise 則是相反的，採用 $B \times C \times H \times W$ 的 Memory Layout


### Winograd Convolution

加速卷積運算

# Reference
1. [animatedai](https://animatedai.github.io/)