存儲器層次結(jié)構(gòu)
存儲器層次結(jié)構(gòu)的中心思想是，對于每個 k，位于 k 層的更快更小的存儲設(shè)備作為位于 k + 1 層的更大更慢的存儲設(shè)備的緩存。
局部性
時間局部性：
同一數(shù)據(jù)對象可能被多次使用。一旦一個數(shù)據(jù)對象在第一次不命中時被復(fù)制到緩存中，我們就會期望后面對目標(biāo)有一系列的訪問命中。因為緩存比低一層的存儲設(shè)備更快，對后面的命中的服務(wù)會比最開始的不命中的快很多。空間局部性：
塊通常包含多個數(shù)據(jù)對象。我們會期望后面對該塊中其他對象的訪問能補償不命中后復(fù)制該塊的花費。
應(yīng)用
將注意力集中在內(nèi)循環(huán)上，大部分計算和內(nèi)存訪問都發(fā)生在這里。
一旦從存儲器中讀入了一個數(shù)據(jù)對象，就盡可能多使用它，從而使得程序中的時間局部性最大。
通過按照數(shù)據(jù)對象存儲在內(nèi)存中的順序、以步長為 1 來讀數(shù)據(jù)，可使空間局部性最大。
考慮函數(shù)sumvec :
int sumvec(int v[N]) {
int i, sum = 0;
for (i = 0; i < N; i ++)
sum += v[i];
return sum;
}
首先，對于局部變量 i 和 sum，循環(huán)體有良好的時間局部性。因為它們都是局部變量，合理的優(yōu)化編譯器都會把他們緩存在寄存器文件中?，F(xiàn)在考慮一下對向量 v 的步長為 1 的引用。一般來說，如果一個高速緩存塊大小為 B 字節(jié)，那么一個步長為 k 的引用模式（k 以字為單位）平均每次循環(huán)會有 min(1, (wordsize * k) / B) 次緩存不命中。當(dāng) k = 1 時，它取最小值，所以對 v 的步長為 1 的引用確實是高速緩存友好的。假設(shè) v 是塊對齊的，字為 4 個字節(jié)，高速緩存塊為 4 個字，而高速緩存初始為空（冷緩存）。然后，無論是什么樣的高速緩存結(jié)構(gòu)，對 v 的引用都會得到下面的命中和不命中模式：
在這里，對 v[0] 的引用會不命中，而相應(yīng)的包含 v[0] ~ v[3] 的塊會被從內(nèi)存加載到高速緩存中。因此，接下來的三個引用都會命中。依次類推，每四個引用中，三個會命中，在這種冷緩存的情況下，這是能做到的最好情況。
總之，上面的示例說明了兩個關(guān)于編寫高速緩存友好代碼的重要問題：
對局部變量的反復(fù)引用是最好的，因為編譯器能將它們緩存在寄存器文件中（時間局部性）
步長為 1 的引用模式是最好的，因為存儲器層次結(jié)構(gòu)中所有層次上的緩存都是將數(shù)據(jù)存儲為連續(xù)的塊（空間局部性）
在對多維數(shù)組進(jìn)行操作的程序中，空間局部性尤其重要。
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;
}
假設(shè)對這個高速緩存做與對 sumvec 一樣的假設(shè)。那么對數(shù)組 a 的引用會得到下面的命中和不命中模式：
如果交換循環(huán)的次序：
int sumarraycols(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;
}
將會得到下面的命中和不命中模式：
較高的不命中率對運行時間可以有顯著的影響。例如在桌面機(jī)器上，sumarrayrows 運行速度比 sumarraycols 快 25 倍。
