存储器层次结构
存储器层次结构的中心思想是，对于每个 k，位于 k 层的更快更小的存储设备作为位于 k + 1 层的更大更慢的存储设备的缓存。
局部性
时间局部性：
同一数据对象可能被多次使用。一旦一个数据对象在第一次不命中时被复制到缓存中，我们就会期望后面对目标有一系列的访问命中。因为缓存比低一层的存储设备更快，对后面的命中的服务会比最开始的不命中的快很多。空间局部性：
块通常包含多个数据对象。我们会期望后面对该块中其他对象的访问能补偿不命中后复制该块的花费。
应用
将注意力集中在内循环上，大部分计算和内存访问都发生在这里。
一旦从存储器中读入了一个数据对象，就尽可能多使用它，从而使得程序中的时间局部性最大。
通过按照数据对象存储在内存中的顺序、以步长为 1 来读数据，可使空间局部性最大。
考虑函数sumvec :
int sumvec(int v[N]) {
int i, sum = 0;
for (i = 0; i < N; i ++)
sum += v[i];
return sum;
}
首先，对于局部变量 i 和 sum，循环体有良好的时间局部性。因为它们都是局部变量，合理的优化编译器都会把他们缓存在寄存器文件中。现在考虑一下对向量 v 的步长为 1 的引用。一般来说，如果一个高速缓存块大小为 B 字节，那么一个步长为 k 的引用模式（k 以字为单位）平均每次循环会有 min(1, (wordsize * k) / B) 次缓存不命中。当 k = 1 时，它取最小值，所以对 v 的步长为 1 的引用确实是高速缓存友好的。假设 v 是块对齐的，字为 4 个字节，高速缓存块为 4 个字，而高速缓存初始为空（冷缓存）。然后，无论是什么样的高速缓存结构，对 v 的引用都会得到下面的命中和不命中模式：
在这里，对 v[0] 的引用会不命中，而相应的包含 v[0] ~ v[3] 的块会被从内存加载到高速缓存中。因此，接下来的三个引用都会命中。依次类推，每四个引用中，三个会命中，在这种冷缓存的情况下，这是能做到的最好情况。
总之，上面的示例说明了两个关于编写高速缓存友好代码的重要问题：
对局部变量的反复引用是最好的，因为编译器能将它们缓存在寄存器文件中（时间局部性）
步长为 1 的引用模式是最好的，因为存储器层次结构中所有层次上的缓存都是将数据存储为连续的块（空间局部性）
在对多维数组进行操作的程序中，空间局部性尤其重要。
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;
}
假设对这个高速缓存做与对 sumvec 一样的假设。那么对数组 a 的引用会得到下面的命中和不命中模式：
如果交换循环的次序：
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;
}
将会得到下面的命中和不命中模式：
较高的不命中率对运行时间可以有显著的影响。例如在桌面机器上，sumarrayrows 运行速度比 sumarraycols 快 25 倍。
