FPGA：AI 算力基礎 - Systolic Array

# FPGA：AI 算力基礎 - Systolic Array ## 0. 基礎 ![basic](https://hackmd.io/_uploads/rJUUrdmBbx.png) - 傳統上只使用一個PE運算 - 若將PE組成陣列，可將資料流過每個PE重複運算 > 將重複、大量的運算平行處理就可以加速整體計算 ## 1. 一維卷積 ### 1.1 何謂一維卷積 **- 最基本的 AI 運算** - 權重 window(filter) = $[1, 1, 1]$ ，是固定的 - 輸入一位陣列 = {1, 2, 3, 4, ...} - 輸出y: $$ y = [6, 9, 12, ...] \\ $$ 其中: - $y_1 = 1*1 + 1*2 + 1*3$ - $y_2 = 1*2 + 1*3 + 1*4$ - $y_3 = 1*3 + 1*4 + 1*5$ ### 1.2 基礎的設計 (Weight Stationary) *權重固定不動，只有輸入數據動* #### 1.2.1 基礎 ![conv_1d](https://hackmd.io/_uploads/BJnPDO7r-l.png) - 輸入 $x_i$ 由上方一次廣播到所有PE - 在 t=2 時可以正式開始輸出 #### 1.2.2 另一個選擇 ![conv_1d_plus](https://hackmd.io/_uploads/HyqQKuXBZg.png) - 輸入 $x_i$ 逐個通過PE，並使用加法器 #### 缺點： 1.2.1 要**一次廣播**到所有PE 1.2.2 要進行完乘法後**一次**匯總到adder > 當window很大時，Bus會隨之變大 > Bus: *多個硬體元件之間，用來傳輸資料、位址與控制訊號的一組共享訊號線* ### 1.3 Output Stationary(去掉Bus的設計) ![conv_1d_plus_without_bus](https://hackmd.io/_uploads/rJOFVK7Bbl.png) - 輸入 $x_i$ 由左邊進去 - 權重 $w_1, w_2, w_3$ 由右邊進去 - 上述兩者都會空一拍才繼續輸入 - 只有在**紅點**的時候，PE才在運算中 > 優點：不需要Bus廣播數據 > 缺點：不能所有PE同時運作，仍可提昇硬體利用率 --- ## 2. 資料流的卷積總得來說就是：權重預先載好了，矩陣元素由左往右走而已 ![1](https://hackmd.io/_uploads/H1FKna4r-l.png) ![2](https://hackmd.io/_uploads/r1YKna4rZx.png) ![4](https://hackmd.io/_uploads/rytF2aVHbe.png) ![6](https://hackmd.io/_uploads/SkFF3aVH-g.png) --- [參考](https://blog.csdn.net/wangwangmoon_light/article/details/121890472) ## 3. 資料流的矩陣乘法 **- TPU的核心是 N * N （N=256）的 MAC單元** 假設需要計算： $$ C=A×B $$ 對於 $(C[i,j])$： $$ C[i,j] = \sum_k A[i,k] \cdot B[k,j] $$ 可以看到 **每一個元素 (C[i,j]) 的計算是由多個乘法與加總組成**。這種運算有兩個特性： 1. **乘加操作高度重複** → 很適合並行化。 2. **每個 (C[i,j]) 的計算可以獨立進行** → 可以分配給不同的處理PE。 →若 $C$ 為3x3矩陣，總共需要 **9** 個運算單元 --- ### 先備知識： ##### 以 2*2 說明 - 矩陣： $$ A = \begin{bmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{bmatrix},\quad B = \begin{bmatrix} b_{00} & b_{01} \\ b_{10} & b_{11} \end{bmatrix} $$ $$ C = \begin{bmatrix} a_{00}b_{00}+a_{01}b_{10} & a_{00}b_{01}+a_{01}b_{11} \\ a_{10}b_{00}+a_{11}b_{10} & a_{10}b_{01}+a_{11}b_{11} \end{bmatrix} $$ - 最小的單位是 ```ini MAC = (a × b) + acc ``` - 所以每一個輸出元素（例如 c₀₀）本質上就是： ```makefile clk = 1: acc = 0 # 清0 clk = 2: acc += a00 × b00 clk = 3: acc += a01 × b10 ``` - 假設硬體只有 1 個 MAC - 算出一個輸出c00要3個clk-cycle - 全部算完就要3 * 4 ＝ 12 個clk-cycle（很慢、但面積小） ### 實務常見：將 PE 排成矩陣的樣子(PE-Array) ```css B列 ↓ PE11 PE12 ┌───┐ ┌───┐ A行 → │C11│ │C12│ └───┘ └───┘ PE21 PE22 ┌───┐ ┌───┐ │C21│ │C22│ └───┘ └───┘ ``` ##### Top Module 資料的流動說明: 1. **A 資料**從左側進入矩陣（沿行移動）。 2. **B 資料**從上方進入矩陣（沿列移動）。 4. 每一拍:A會輸入一行元素；B會輸入一列元素 - ``` A = [[1,2], [3,4]] B = [[5,6], [7,8]] ``` - clk = 1: input 1,3, 5,6 - clk = 2: input 2,4, 7,8 4. example - ``` // 2*2的版本 input [DATA_WIDTH-1:0] A_in0; // 第一行的元素 input [DATA_WIDTH-1:0] A_in1; // 第二行的元素 input [DATA_WIDTH-1:0] B_in0; // 第一列 input [DATA_WIDTH-1:0] B_in1; // 第二列 // 綜合的版本 input [DATA_WIDTH-1:0] A_in [0:N-1]; input [DATA_WIDTH-1:0] B_in [0:N-1]; output [DATA_WIDTH-1:0] C_out [0:N-1][0:N-1]; ``` --- ### 以 2*2 說明內部PE矩陣資料的流動 - 矩陣： $$ A = \begin{bmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{bmatrix},\quad B = \begin{bmatrix} b_{00} & b_{01} \\ b_{10} & b_{11} \end{bmatrix} $$ $$ C = \begin{bmatrix} a_{00}b_{00}+a_{01}b_{10} & a_{00}b_{01}+a_{01}b_{11} \\ a_{10}b_{00}+a_{11}b_{10} & a_{10}b_{01}+a_{11}b_{11} \end{bmatrix} $$ ##### 1. 每個PE負責計算對應C的元素 ```yaml Matrix C output positions: C00 C01 C10 C11 PE Layout: PE00 PE01 PE10 PE11 ``` ##### 2. clk = 1 A矩陣的第一行從左方流入 B矩陣的第一列從上方流入未接到兩筆資料的即等待 ```yaml Inputs: b00 b01 ↓ ↓ a00 → PE00 PE01 a10 → PE10 PE11 PE00: C00 = a00*b00 PE01: waiting PE10: waiting PE11: waiting ``` ##### 3. clk = 2 ```yaml Inputs: b10 b11 ↓ ↓ a01 → PE00 → a00 → PE01 ↓ ↓ b00 b01 ↓ ↓ a11 → PE10 → a10 → PE11 PE00: C00 = a00*b00 + a01*b10 PE01: C01 = a00*b01 PE10: C10 = a10*b00 PE11: C11 ``` ##### 4. clk = 3 ```yaml Inputs: ↓ ↓ → PE00 → a01 → PE01 ↓ ↓ b01 b11 ↓ ↓ → PE10 → a11 → PE11 PE00: C00 = a00*b00 + a01*b10 PE01: C01 = a00*b01 + a01*b11 PE10: C10 = a10*b00 + a11*b10 PE11: C11 = a10*b01 ``` ##### 4. clk = 4 ```yaml PE00: C00 = a00*b00 + a01*b10 PE01: C01 = a00*b01 + a01*b11 PE10: C10 = a10*b00 + a11*b10 PE11: C11 = a10*b01 + a11*b11 ``` #### 總得來說：clk 時序表格 | clk | PE00 | PE01 | PE10 | PE11 | 註解 | | --- | -------------- | -------------- | -------------- | -------------- | ------------------------ | | 1 | C00 = a00*b00 | waiting | waiting | waiting | 第一輪輸入 a00, b00 | | 2 | C00 += a01*b10 | C01 = a00*b01 | C10 = a10*b00 | waiting | 第二輪輸入 a01, a10, b10, b01 | | 3 | waiting | C01 += a01*b11 | C10 += a11*b10 | C11 = a10*b01 | 第三輪輸入 a11, b11 | | 4 | done | done | done | C11 += a11*b11 | 最終累加完成 | --- ## 硬體設計練習：設計 2×2 PE-Array 矩陣乘法加速器 ##### **1. 系統功能** 設計一個 2×2 的 systolic PE-Array，用於計算矩陣乘法：每個 PE 使用 2-stage MAC 計算對應 (C_{ij}) 的部分乘積並累加。 --- ##### **2. 模組規格** ###### **輸入** * `clk` : 時鐘 * `rst` : 同步重置，高電位有效 * `A_in[7:0]` : A 矩陣元素 * `B_in[7:0]` : B 矩陣元素 * `C_in[15:0]` : 累加前部分和 ###### **輸出** * `C_out[15:0]` : 累加後結果 ###### **功能描述** 每個 clk 做： 1. **Stage 1**（乘法） * 計算 `mult = A_in * B_in` * 將 `mult` 暫存到寄存器 `mult_reg` 2. **Stage 2**（加法） * 將 `mult_reg` 加到 `C_in` * 輸出到 `C_out` > ⚠️ 注意：Stage 1 與 Stage 2 在不同 clk 週期完成 > 這意味著每個部分積的累加會延遲一個 clk --- ##### **3️⃣ 2×2 PE-Array Top Module** * 由 4 個 PE 組成 2×2 PE-Array * A 從左側輸入，沿行流動 * B 從上方輸入，沿列流動 * 每個 PE 使用 2-stage MAC * 輸出： ``` C00, C01, C10, C11 ``` --- ##### **4️⃣ 輸入範例** ``` A = [[1,2], [3,4]] B = [[5,6], [7,8]] ``` --- ##### **5️⃣ 預期輸出** ``` C = [[19, 22], [43, 50]] ``` > ⚠️ 注意：由於 2-stage MAC pipeline，每個 PE 的最終 C_out 需要延遲 1~2 clk 才會產生完整結果 --- ##### **6️⃣ Testbench 要求** 1. 撰寫 **2-stage MAC PE 模組** 2. 撰寫 2×2 PE-Array Top Module 3. Testbench： * clk 週期 10ns * rst 高電位清零 * 將上述矩陣 A/B 輸入 PE-Array * 顯示最終矩陣 C 4. 模擬結果要與預期輸出一致 5. 額外練習： * 顯示每個 clk 每個 PE 的 Stage1 與 Stage2 計算值 --- 💡 **重點提示** * 因為每個 PE 有兩個 stage，所以矩陣乘法的完![5](https://hackmd.io/_uploads/H1KYnpESbl.png)整累加會延遲幾個 clk * 在 testbench 中，你可以在每個 clk 觀察： * `mult_reg`（Stage1 暫存） * `C_out`（Stage2 累加）

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.