---
tags: ncku-course
---
# [Memory Hierarchies and Optimizing Matrix Multiplication](https://people.eecs.berkeley.edu/~demmel/cs267_Spr99/Lectures/Lect_02_1999b.pdf)

## Understanding Caches

先介紹理想與實際上的 processor model。

* Idealized Uniprocessor Model
* 處理器的操作包括了記憶體的存取以及算術邏輯運算等，而這些運算所需要的 cost 大致上都是相同的。
* 編譯器與處理器可能會為了優化效能，會在確保執行結果的情況下重排指令。

* Uniprocessor Cost: Reality
* 不同的記憶體操作有著不同的 cost，所以會利用 cache 來儲存最近使用或附近的資料，以達成資料的重用。
* 在處理器中擁有多個運算單元，可以同時對不同類型的資料進行操作，也就是所謂的 superscalar。可是不同的指令順序也會有著不同的 cost。
* 再來就是最底層的 pipeline，透過分成數個 stages 來加速。

還提及 memory hierarchy。


並介紹常見的兩個 locality。

* spatial locality
相鄰的記憶體資料在短時間中可能被用到 (空間上)。
* temporal locality
最近使用到的資料在短時間中可能被用到 (時間上)。

// i 是 temporal locality
for (int i = 0; i < 1000; ++i) {
    // A[i + 1] 和 A[i] 是 spatial locality
    A[i + 1] = A[i] + 1;
}

再來是複習基本的 cache 方式，例如 direct-mapped 和 N-way associative。

假設 cache 可以存放 4 個 word 大小的 block。欲存取的記憶體地址為 0, 8, 0, 6, 8。

* direct-mapped
可以發現 direct-mapped 比較容易發生 conflict 的狀況。

* N-way associative
可以看到 fully associative 可以解決 conflict 的問題。
但從 cache 中讀取資料時必須透過 comparator 來確定該從哪一個 block 中抓，花費較大。
所以為了從兩者間取平衡點，通常會用 8-way associative。

最後做了一個實驗來測試記憶體的效能。

實驗的方法是分配長度為 arraySize 的陣列，然後每 stride 讀取一次記憶體。

Pseudo code 如下。

for (arraySize = 4KB; arraySize < 8MB; arraySize *= 2) {
    for (stride = 1; stride <= arraySize / 2; stride *= 2)  {
        for (i = 0; i < arraySize; i += stride) {
            for (k = 0; k < repeats; k++) {
                MEMORY_OPERATION_ON(A[i])
            }
        }
    }
}

實驗結果如下，從圖中的幾個轉折點我們可以推測出電腦的相關規格。


1. Array Size
我們大致上可以分為三個 group，分界線分別為 8K 以及 512K。從這邊我們可以推測出 cache size 以及記憶體存取時間。

在同一個 level 的 cache 時，擁有相近的存取時間，因此可以推斷 L1 大小為 8K，L2 大小為 512K。

而從 1M 開始，我們可以發現時間劇增，根據上面 memory hierarchy 的圖片，可以合理推斷 300ns 為記憶體存取時間。

2. Stride Size
在這一部份，又可以分為三個 group，分界線分別為 32 bytes 以及 8K。

當超過 cache line size 和 page size 時會需要額外的時間來進行存取，所以我們推論 32 bytes 為 cache line size，而 8K 為 page size。

## Optimizing Matrix Multiplication

在這一個區塊中，先以簡單的範例來引入 cache 對效能的影響，像是針對下面兩種 pseudo code 來分析。這一部份所討論的議題與 naive 版本中所提及的十分相似，都是在討論 access pattern。

// Algorithm 1
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        A[i, j] = B[i, j] + C[i, j];
    }
}

// Algorithm 2
for (int j = 1; j <= n; ++j) {
    for (int i = 1; i <= n; ++i) {
        A[i, j] = B[i, j] + C[i, j];
    }
}

接著正式以矩陣作為範例，利用代數的方式對 unblocked 與 blocked 兩種方式進行分析，這部份分別對應到 naive 以及 submatrix 兩個版本。



再來他提到 Strassen 演算法。

在原本的矩陣乘法當中，我們必須使用 8 個乘法以及 4 個加法運算。

而在 Strassen 當中，透過將大矩陣分割為 $2 \times 2$ 的分塊矩陣，並搭配下列公式，可以使之只需要 7 個乘法和 18 個加法。

$P_{1} = (A_{11}+A_{22})(B_{11}+B_{22})$
$P_{2} = (A_{21}+A_{22})B_{11}$
$P_{3} = A_{11}(B_{12} - B_{22})$
$P_{4} = A_{22}(B_{21}-B_{11})$
$P_{5} = (A_{11}+A_{12})B_{22}$
$P_{6} = (A_{21}-A_{11})(B_{11}+B_{12})$
$P_{7} = (A_{12}-A_{22})(B_{21}+B_{22})$

$C_{11} = P_{1}+P_{4}-P_{5}+P_{7}$
$C_{12} = P_{3}+P_{5}$
$C_{21} = P_{2}+P_{4}$
$C_{22} = P_{1}+P_{3}-P_{2}+P_{6}$

透過減少運算過程中的乘法，讓時間變短。更詳細的推導與相關實驗在[分組共筆](https://hackmd.io/s/Hk-llHEyx#strassen-algorithm)中都有提及。

## 結論

### Understanding Caches

* 就算是簡單的程式，其實際效能也必須考慮到系統架構，使得這個問題變得更複雜。
* 對於架構、程式而言，微小的變動也會造成極大的效能差異。
* 為了撰寫效能更好的程式，我們必須考慮到系統架構，就算是 uniprocessor 也是一樣。
* 在測量實際效能時情況較為複雜，通常會以簡單的 model 協助分析。

### Optimizing Matrix Multiplication

* 在 uniprocessor 架構中，為撰寫有效率的程式，必須考慮以下幾點
* 記憶體的 cost、size 和 level
* 了解 processor 中的並行化設計
* 分塊在許多矩陣乘法中是常見的技巧。
* 各優化技巧可套用於 uniprocessor 或其他 processor 架構中，但分塊大小需要根據系統架構進行微調。

## 參考資料

* [Empirical Evaluation of the CRAY-T3D: A Compiler Perspective](http://pages.cs.wisc.edu/~remzi/Postscript/isca95.pdf)
* [國立成功大學 計算機組織 講義](http://ideal.csie.ncku.edu.tw/comporg2015/Ch5_MemoryHierarchy-1.pdf)