# Tiled Matrix Multiplication 筆記

## 基本觀念

將大矩陣分成小區塊（tile）進行乘法，可以提升快取記憶體命中率，加速矩陣運算。

以 $4 \times 4$ 矩陣為例，tile size 設為 $2$，則矩陣會被分割為 $2 \times 2$ 的區塊矩陣。

---

## 矩陣切割範例

矩陣 $A$（$4 \times 4$）：

$$
\begin{bmatrix}
A_{00} & A_{01} \\
A_{10} & A_{11}
\end{bmatrix}
$$

矩陣 $B$（$4 \times 4$）：

$$
\begin{bmatrix}
B_{00} & B_{01} \\
B_{10} & B_{11}
\end{bmatrix}
$$

矩陣 $C$（$4 \times 4$）：

$$
\begin{bmatrix}
C_{00} & C_{01} \\
C_{10} & C_{11}
\end{bmatrix}
$$

其中，每個區塊($\alpha_{xx}$)都是 $2 \times 2$ 小矩陣。

---

## 區塊矩陣乘法公式（$C = A \times B$）

| 區塊 $C_{ij}$ | 計算公式 |
|---------------|-----------|
| $C_{00}$ | $A_{00} \times B_{00} + A_{01} \times B_{10}$ |
| $C_{01}$ | $A_{00} \times B_{01} + A_{01} \times B_{11}$ |
| $C_{10}$ | $A_{10} \times B_{00} + A_{11} \times B_{10}$ |
| $C_{11}$ | $A_{10} \times B_{01} + A_{11} \times B_{11}$ |

---

## 計算公式的邏輯解釋

每個 $C_{ij}$ 是由 A 的 row tile $A_{i,k}$ 與 B 的 column tile $B_{k,j}$ 相乘後加總而來。

公式推廣到N維為：

$$
C_{ij}^{T \times T} = \sum_{k} A_{ik}^{T \times T} \cdot B_{kj}^{T \times T}
$$

其中：
- $T$：tile size
- $i, j, k$：tile 區塊索引（tile row / col）

---

## 邊界處理：無法整除 tile size 的情況

實際矩陣大小 $N \times N$ 常常無法被 tile size $T$ 整除，此時：

- 最右邊 / 最下邊的 tile **可能不完整**
- 若不處理，會造成記憶體越界（特別在 GPU 上會錯誤）
- 常見解法為：
- **超出範圍就填 0**
- 或者使用 `if` 檢查是否越界才進行計算

---

### 延伸的公式處理邏輯

當 tile size 不能整除矩陣尺寸時：

$$
C_{ij}^{T \times T} = \sum_k A_{ik}^{T \times T} \cdot B_{kj}^{T \times T}
\quad \text{其中超出範圍的元素設為 0}
$$

例如：
- 若 $i \geq N$ 或 $j \geq N$，則 $C[i][j]$ 不需寫入
- 若 $k \geq N$，則忽略對應 $A[i][k] \cdot B[k][j]$ 的乘積