存储器的层次结构

存储技术

我们在买电脑时都会关注内存、处理器、硬盘等部件的性能，都想内存尽可能大，硬盘最好是固态的。

不知道你有没有遇到过自己写了大半天的文档，因为不小心突然关机了，自己辛苦忙活了几个小时的成果又得重写的情况。可是你是否想过为什么关机了就会丢失这些信息呢？为什么硬盘上的文件没有丢？

会丢的那部分信息肯定是和电有关系的，不然也不会一断电就丢信息。内存就是这样的部件，更专业一点的称呼是随机访问存储器。

随机访问存储器（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，这就是从本地缓存读取的。

如下图所示，高速缓存通常被组织为下面的形式，计算机需要从具体的地址去拿指令或者数据，而这个地址也被切分为不同的部分，可以直接映射到缓存上去。看下面详细的介绍应该更容易理解。

直接映射高速缓存每个组只有一行。高速缓存确定一个请求是否命中，然后抽取出被请求的字的过程分为：组选择、行匹配、字抽取三步。

比如当 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 次缓存命中，所以第一比第二种运行更快是必然的结果，第一种和第二种的缓存命中模式分别如下所示（粗体表示不命中）。