存儲器的層次結(jié)構(gòu)

存儲技術(shù)

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

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

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

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

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

動態(tài) RAM 芯片就封裝在內(nèi)存模塊中，比內(nèi)存更大的存儲部件是磁盤，發(fā)現(xiàn)自己在舊文你真的了解硬盤嗎？對磁盤總結(jié)的已經(jīng)不錯了，就直接過渡到局部性上面去了吧。

局部性

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

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

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

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

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

當(dāng)然，不僅數(shù)據(jù)引用有局部性，取指令也有局部性。比如for循環(huán)，循環(huán)體中的指令是按順序執(zhí)行的，并且會被執(zhí)行多次，所以它有良好的空間局部性和時間局部性。

高速緩存

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

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

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

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

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

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

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

編寫緩存友好的代碼

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;
}

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

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

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

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

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

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