存儲器的層次結構

存儲技術

我們在買電腦時都會關注內存、處理器、硬盤等部件的性能，都想內存盡可能大，硬盤最好是固態的。

不知道你有沒有遇到過自己寫了大半天的文檔，因為不小心突然關機了，自己辛苦忙活了幾個小時的成果又得重寫的情況?？墒悄闶欠裣脒^為什么關機了就會丟失這些信息呢？為什么硬盤上的文件沒有丟？

會丟的那部分信息肯定是和電有關系的，不然也不會一斷電就丟信息。內存就是這樣的部件，更專業一點的稱呼是隨機訪問存儲器。

隨機訪問存儲器（RAM）分靜態和動態的兩種，靜態 RAM 是將信息存儲在一個雙穩態的存儲單元里。什么叫雙穩態呢？就是只有兩種穩定的狀態，雖然也有其它狀態，但即使細微的擾動，也會讓它立馬進入一個穩定的狀態。

動態 RAM 使用的是電容來存儲信息，學過物理的都知道電容這個概念，它很容易就會漏電，使得動態 RAM 單元在 10~100 ms 時間內就會丟失電荷（信息），但是不要忘記，計算機的運行時間是以納秒計算的，1 GHz 的處理器的時鐘周期就是 1 ns，更何況現在的處理器都不止 1 GHz，所以 ms 相對于納秒來說是很長的，計算機不用擔心會丟失信息。

動態 RAM 芯片就封裝在內存模塊中，比內存更大的存儲部件是磁盤，發現自己在舊文你真的了解硬盤嗎？對磁盤總結的已經不錯了，就直接過渡到局部性上面去了吧。

局部性

局部性通常有兩種不同的形式：時間局部性和空間局部性。在一個具有良好時間局部性的程序中，被引用過一次的內存位置很可能在不遠的將來會再被多次引用；同樣在一個具有良好空間局部性的程序中，如果一個內存被引用了一次，那么程序很可能在不遠的將來引用附近的一個內存位置。

不要小看局部性，局部性好的程序會比局部性差的程序運行的更快，要往高級程序員走，這是肯定需要了解的。我們選擇把一些常用的文件從網盤下下來，利用的就是時間局部性。

下面這段代碼，再簡單不過，我們僅觀察一下其中的v向量，向量v的元素是一個接一個被讀取的，即按照存儲在內存中的順序被讀取的，所以它有很好的空間局部性；但是每個元素都只被訪問一次，就使得時間局部性很差了。實際上對于循環體中的每個變量，這個函數要么具有好的空間局部性，要么具有好的時間局部性。

int sumvec(int v[N]){
    int i, sum = 0;
    for(i = 0; i < N; i++){
        sum += v[i];
    }
    return sum;
}

像上面的代碼，每隔 1 個元素進行訪問，稱之為步長為 1 的引用模式。一般而言，隨著步長的增加，空間局部性下降。

當然，不僅數據引用有局部性，取指令也有局部性。比如for循環，循環體中的指令是按順序執行的，并且會被執行多次，所以它有良好的空間局部性和時間局部性。

高速緩存

不同存儲技術的訪問時間差異很大，而我們想要的是又快又大的體驗，然而這又是違背機械原理的。為了讓程序運行的更快，計算機設計者在不同層級之間加了緩存，比如在 CPU 與內存之間加了高速緩存，而內存又作為磁盤的緩存，本地磁盤又是 Web 服務器的緩存。多次訪問一個網頁，會發現有一些網絡請求的狀態碼是 300，這就是從本地緩存讀取的。

如下圖所示，高速緩存通常被組織為下面的形式，計算機需要從具體的地址去拿指令或者數據，而這個地址也被切分為不同的部分，可以直接映射到緩存上去?？聪旅嬖敿毜慕榻B應該更容易理解。

直接映射高速緩存每個組只有一行。高速緩存確定一個請求是否命中，然后抽取出被請求的字的過程分為：組選擇、行匹配、字抽取三步。

比如當 CPU 執行一條讀內存字w的指令，首先從w地址中間抽取出s個組索引位，映射到對應的組，然后通過t位標記確定是否有字w的一個副本存儲在該組中；最后使用b位的塊偏移確定所需要的字塊是從哪里開始的。

上面這個圖，還有下面這個表，對應著看，由于能力有限，感覺怎么都講不好，多盯著一會兒，應該就會獲得一種豁然開朗之感。

直接映射高速緩存造成沖突不命中的原因在于每個組只有一行，組相聯高速緩存放松了這一限制，每個組都保存多于一行的高速緩存行，所以在組選擇完成之后，需要遍歷對應組中的行進行行匹配。

當然，我們可以把每個組中的緩存行數繼續擴大，即全相聯高速緩存，所有的緩存行都在一個組，它總共只有一個組。因此對地址的劃分就不需要組索引了，如下圖所示。

編寫緩存友好的代碼

float dotprod(float x[8], float y[8]){
    float sum = 0.0;
    int i;
    for(i = 0; i < 8; i++){
        sum += x[i] * y[i];
    }
    return sum;
}

這段函數很簡介，就是計算兩個向量點積的函數，而且對于x和y來說，這個函數具有很好的空間局部性，如果使用直接映射高速緩存，那它的緩存命中率并不高。

從表中就能看到，每次對x和y的引用都會導致沖突不命中，因為我們在x和y的塊之間抖動，即高速緩存反復的加載替換相同的高速緩存塊組。

我們只需要做一個小小的改動，就能讓命中率大大提高，即讓程序運行的更快。這個改動就是把float x[8]改為floatx[12]，改動后的索引映射就變成下面那樣了，非常的友好。

再來看一個多維數組，函數的功能是對所有元素求和，兩種不同的寫法。

// 第一種
int sumarrayrows(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;
}

// 第二種
int sumarrayrows(int a[M][N]){
    int i, j, sum = 0;
    for(j = 0; j < M; j++){
        for(i = 0; i < N; i++){
            sum += a[i][j];
        }
    }
    return sum;
}

從編程語言角度來看，兩種寫法的效果是一樣的， 都是求數組所有元素的和，但是深入分析就會發現，第一種寫法會比第二種運行的更快，因為第二種寫法一次緩存命中都不會發生，而第一種寫法會有 24 次緩存命中，所以第一比第二種運行更快是必然的結果，第一種和第二種的緩存命中模式分別如下所示（粗體表示不命中）。