上一篇：[C 語言筆記--Day01] Hello World

大綱

1. 什麼是 memory hierarchy?
2. cache 的運作方式
3. 因為 cache 如此運作，所以寫程式時該注意的事情
4. 程式碼範例
5. 結論

什麼是 memory hierarchy?

在 memory hierarchy 中：
愈上層，速度快、容量小、貴
愈下層，速度慢、容量大、便宜

用個比喻來說明：

假如我有 1000 本書，不過我只有 10 本書是比較常用到的，

把常用到的 10 本書放到我的書桌旁的書架上（memory hierarchy 較高的地方）
其他的 990 本書放到紙箱裡（memory hieraarchy 較低的地方）

當我要找書時

先看書桌旁的書架上有沒有我要的書
如果沒有，再去紙箱裡找
從書架上找到書後，就把找到的書放到書架上
並且挑一本比較不常用到的書放到紙箱裡

在寫 c 語言時，通常了解圖中 L0, L1 的層級大概就行了

不過 register 跟 main memory 的速度差太多了，所以需要圖中 L1~L3 的 cache 來進行加速

cache 的運作方式

cache 的目標在於加速最上層（register）抓取到資料的動作

cache 的設計建立在以下的想法：

1. 曾經使用過的 資料/指令 會有很大的機率再次使用
2. 當我使用了某個 資料/指令 有很大的機率再次使用在他附近的 資料/指令
3. 加速以上 1、2 這兩種情況
4. 所謂的加速，其實就是把他們放到 memory hierarchy 中較高的位置

所以當我們抓取了記憶體中的某一份資料，這份資料以及在他附近的資料也會一起背放到 cache 中

因為 cache 如此運作，所以寫程式時該注意的事情

寫程式時要注意儘量抓資料時要抓取附近的資料，這樣才符合 cache 的運作方式
這稱為 locality ，而 locality 又分為以下兩種

• temporal locality：使用之前使用過的資料
• spatial locality：使用附近的資料

程式碼範例：

範例一

// good locality
int sum_array_rows(int a[M][N])
{
    int i, j, sum = 0;

    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
            sum += a[i][j];
    return sum;
}

// bad locality
int sum_array_cols(int a[M][N])
{
    int i, j, sum = 0;

    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            sum += a[i][j];
    return sum;
}

sum_array_rows 的 locality 比較好，因為他抓取資料時是照著記憶體的位置的順序抓取

sum_array_cols 的 locality 比較差，因為他抓取資料時是跳著抓取的

雖然說以複雜度的觀點而言，這兩個 function 的複雜度是一樣的，

但是 sum_array_rows 在抓取資料時，會有比較高的機率在 memory hierarchy 中比較高的 level 抓取到，

所以他的執行效率會比較好

範例二

定義以下資料結構：

#define N 1000
 typedef struct {
     int vel[3];
     int acc[3];
 } point;

point p[N];

假如要把 point 中的 val, acc 全部都設為 0 了話
以下式最好的方式，因為他完全依尋 address 的順序：

// good locality

void clear1(point *p, int n)
{
    int i, j;
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < 3; j++)
            p[i].vel[j] = 0;
        for (j = 0; j < 3; j++)
            p[i].acc[j] = 0;
    }
}

這個方式雖然寫起來比較方便，但 locality 比較差：

// bad locality

void clear2(point *p, int n)
{
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < 3; j++) {
            p[i].vel[j] = 0;
            p[i].acc[j] = 0;
        }
    }
}

結論

寫程式時要注意 locality，因為他會影響執行的效率

參考資料：
https://scs.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=06dfcd19-1024-49eb-add8-3486a38d1426