存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构。在本章中，我们将探索存储器层次结构是怎么构建的，体会到多种存储设备之间属性的美妙融合，以及程序的属性在这当中起到的作用。

存储技术和趋势

随机访问存储器

现在大多数人所熟悉的内存其实叫做随机访问存储器（RAM），分为两类——静态（SRAM）和动态（DRAM），它们之间是根据存储单元实现方式来区分的。

  • SRAM不需要定期刷新，DRAM需要
  • SRAM访问速度比DRAM快一个数量级
  • 一般将SRAM用于高速缓存，容量不超过几兆字节
  • DRAM广泛用于主存以及图形显卡的帧缓存中
  • 两者的相同点是都需要通电，一旦断电，所有的信息都会丢失

非易失性存储器

非易失性存储器即使是在断电后，依然保存着它们的信息，它们的通用名称是只读存储器（ROM）

传统机械硬盘

虽然现在越来越多电脑已经改为使用固态硬盘，但是还是有必要了解一下硬盘的组成的。传统的机械硬盘有许多不同的部件：

机械硬盘有许多片磁盘(platter)组成，每一片磁盘有两面；每一面由一圈圈的磁道(track)组成，而每个磁道会被分隔成不同的扇区(sector)。

上图是一个磁盘的视图，多个磁盘组合起来是这样的：

读取一个扇区的第一个比特是非常耗时的，之后的都几乎可以忽略不计；读取一个双字的访问时间，硬盘比 SRAM 慢 40,000 倍，比 DRAM 慢 2500 倍；如果比较访问一个单字的时间，这个差距会更大。

最后需要知道的就是逻辑分区和实际的物理分区的区别，为了使用方便，会用连续的数字来标志所有可用的扇区，具体的映射工作由磁盘控制器完成。

像显卡、监视器、鼠标键盘和磁盘这样的设备都是通过I/O总线连接到CPU和内存中的，同系统总线和存储器总线不同，I/O总线设计成与底层CPU无关。虽然相比系统总线和存储器总线速度较慢，但是它可以容纳种类繁多的第三方I/O设备。

固态硬盘

接下来介绍一下固态硬盘，内部结构如下

固态硬盘中分成很多的块(Block)，每个块又有很多页(Page)，大约 32-128 个，每个页可以存放一定数据（大概 4-512KB），页是进行数据读写的最小单位。但是有一点需要注意，对一个页进行写入操作的时候，需要先把整个块清空（设计限制），而一个块大概在 100,000 次写入之后就会报废。

与传统的机械硬盘相比，固态硬盘在读写速度上有很大的优势。但是因为设计本身的约束，连续访问会比随机访问快，而且如果需要写入 Page，那么需要移动其他 Page，擦除整个 Block，然后才能写入。现在固态硬盘的读写速度差距已经没有以前那么大了，但是仍然有一些差距。

不过与机械硬盘相比，固态硬盘存在一个具体的寿命限制，价格也比较贵，但是因为速度上的优势，越来越多设备开始使用固态硬盘。

总线

数据流通过称为总线的共享电路在CPU和主存之间传输，总线是用来传输地址、数据和控制信号的一组平行的电线，通常来说由多个设备共享，类似于不同城市之间的高速公路，可以传输各类数据。CPU 通过总线和对应的接口来从不同的设备中获得所需要的数据，放入寄存器中等待运算。

I/O桥接器将系统总线的电信号翻译成存储器总线的电信号。

假设 CPU 需要从硬盘中读取一些数据，会给定指令，逻辑块编号和目标地址，并发送给磁盘控制器。然后磁盘控制器会读取对应的数据，并通过 DMA(direct memory access)把数据传输到内存中；传输完成后，磁盘控制器通过中断的方式通知 CPU，然后 CPU 完成之后的工作。

总线上连接的各个设备，其访问速度有天壤之别，不同的技术发展速度不同，更加剧了这个情况。

比方说磁盘的读写速度，30 年大概只提高了一个数量级多一点，所以固态硬盘的出现，一下拯救了劳苦大众（提高了两个数量级），DRAM 的发展，一路从 DDR12345 发展来，速度大概提高了一个数量级，不过 SRAM 则是在同一个起点愣是多跑了一个数量级，总体来说是跟着 CPU 的发展走的。不过 CPU 的发展在 2003 年也遇到了问题（单个核心基本到极限），不过多核的出现以及技术优化，总体来说还是使得执行速度越来越快。

那么这么大的时间差距，怎么办呢？难道根据木桶理论，都要取决于最慢的那个吗？不一定！局部性原理(Locality)可以在一定程度上拯救世界。

局部性原理

一个编写良好的计算机程序倾向于展示出良好的局部性。也就是它们更倾向于引用最近使用过的数据项临近的数据项或其本身。这种倾向性，被称为局部性原理，这是程序的一个基本的、持久的属性，对硬件和软件系统的设计都有着极大的影响。

局部性有两种不同的形式：

  1. 时间局部性：最近被引用的存储器地址可能在不久的将来再次被引用。
  2. 空间局部性：下一个被引用的地址可能与当前正在使用的地址是临近的。

举个例子：

1
2
3
4
5
sum = 0;
for (i = 0; i < n; i++){
    sum += a[i];
}
return sum;

在这个循环中，每一次都会执行相同的指令，这满足时间局部性；

每次循环访问的数组地址是连续的，满足空间局部性。

再看下一个例子，实现相同的目标的两段代码：

1
2
3
4
5
6
for (i = 0; i < n; i++) {
    for (j = 0; j < m; j++) {
        sum += a[i][j];
    }
}
return sum;
1
2
3
4
5
6
for (j = 0; j < n; j++) {
    for (i = 0; i < m; i++) {
        sum += a[i][j];
    }
}
return sum;

这两段代码最终的结果都是数组a的和，但是它们在效率上是有一定区别的。

二维数组在内存中的排列是按照先行后列，即：1行1列，1行2列……n行m列，第一段代码遍历数组的顺序和在内存中的排列是一致的，每次访问的地址都是上一次访问的临近位置，满足空间局部性；而第二段代码遍历数组的顺序在内存中是跳跃的。所以代码1的实际执行效率会更高。

根据这个特性，在遍历数组时，尤其是高维数组，要注意按照内存中的排列顺序来访问。

存储器层次结构

我们已经研究了一些存储技术的属性，得到了这种基本原则：

  • 存储容量越大的设备，越便宜，速度越慢；
  • CPU和主存之间的速度差距越来越大；
  • 一个编写良好的程序倾向于展示出良好的局部性。

计算机技术中一个令人惊喜的巧合是，硬件和软件的这些基本属性互补的很完美，它们这种互补的性质使人们想到一种组织存储器系统的方法，称为存储器层次结构。

存储器层次结构的中心思想是，位于第K层的存储设备作为第K+1层存储设备的缓存。根据局部性原理，程序会更倾向于访问第K层的数据，而非第K+1层，这样就减少了访问时间。

缓存命中

当程序需要第K+1层中的某个数据对象时，首先在第K层中查找，如果找到，就称为缓存命中。这要比从第K+1层读取对象要快。

缓存未命中

如果第K层中没有那个对象，就称为缓存未命中，这时就要从第K+1层中取出那个对象块，如果此时第K层的缓存已经满了的话，可能就会覆盖掉现存的一个块。

缓存未命中的类型

  1. 强制性失效(Cold/Compulsory Miss)：如果第K层缓存是空的，此时访问任何数据都不会命中。

  2. 容量失效(Capacity Miss)：程序通常是按照一系列阶段来运行的，每个阶段访问某个相对稳定的集合，称为工作集，当缓存的大小不够大，无法容纳下工作集时，就会发生容量失效。

  3. 冲突失效(Confilict Miss)：这与缓存的实现方式有关，大多数缓存，特别是硬件缓存，因为它们必须被设计地较为简单，这限制了块可以放置的位置，块可以被放置在一个小的集合中（有时只是一个块）。

    假设缓存大小为4，内存中的第i块将被放到缓存中的(i%mod4)处，如果程序的请求顺序为0，8，0，8…这时，缓存足够保存所有被访问的对象，但是由于这些对象会被映射到同一个缓存块中，导致每次都不会命中，这种情况称为冲突失效。

高速缓存存储器

高速缓存存储器是完全由硬件自动管理的 SRAM 内存，位于CPU寄存器文件和主存之间，在现代操作系统中，它位于CPU芯片上，访问速度几乎和寄存器一样快，典型的是1或2个时钟周期。

然后我们需要关注高速缓存存储器的三个关键组成部分（注意区分大小写）：

  • S 表示集合(set)数量
  • E 表示每个集合中数据行(line)的数量
  • B 表示每个缓存块(block)保存的字节数目

在图上表示出来的就是：

所以缓存中存放数据的空间大小为：C=S×E×B

实际上可以理解为三种层级关系，对应不同的索引，这样分层的好处在于，通过层级关系简化搜索需要的时间.。

当处理器需要访问一个地址时，会先在高速缓冲存储器中进行查找，查找过程中我们首先在概念上把这个地址划分成三个部分：

读取

直接映射缓存

具体在从缓存中读取一个地址时，首先我们通过 set index 确定要在哪个 set 中寻找，确定后利用 tag 和同一个 set 中的每个 line 进行比对，找到 tag 相同的那个 line，最后再根据 block offset 确定要从 line 的哪个位置读起（这里的而 line 和 block 是一个意思）。

当 E=1 时，也就是每个 set 只有 1 个 line 的时候，称之为直接映射缓存(Direct Mapped Cache)，如下图所示：

这种情况下，因为每个 set 对应 1 个 line，反过来看，1 个 line 就需要一个 set，所以 set index 的位数就会较多（和之后的多路映射对比）。具体的检索过程就是先通过 set index 确定哪个 set，然后看是否 valid，然后比较那个 set 里唯一 line 的 tag 和地址的 t bits 是否一致，就可以确定是否缓存命中。

命中之后根据 block offset 确定偏移量，因为需要读入一个 int，所以会读入 4 5 6 7 这四个字节（假设缓存是 8 个字节）。如果 tag 不匹配的话，这行会被扔掉并放新的数据进来。

我们来看一个具体的例子来理解是如何工作的，寻址空间 M=16 字节，即4位地址，对应 B=2, S=4, E=1, 我们按照如下顺序进行数据读取：

  1. 0 00 0,miss
  2. 0 00 1,hit
  3. 0 11 1 ,miss
  4. 1 00 0,miss
  5. 0 00 0,miss

缓存的最终情况，x 表示没有内容：

1
2
3
4
5
Set  v  Tag  Block1  Block2
 0   1   0     A1      A2
 1   0   x     x       x
 2   0   x     x       x
 3   1   0     A6      A7

有 4 组 set，所以需要 2 位 set index，在查找的时候，会根据中间两位来确定在哪个 set 中，地址 0 和 8 中间两位相同，会产生冲突，导致连续的未命中，这个问题可以通过多路组相联高速缓存来解决。

多路组相联高速缓存

当 E 大于 1 时，也就是每个集合中有大于 1 个 line 时，称为 E 路组相联高速缓存。

这里的 E 等于 2， 就是两路组相联缓存，每个 set 有两个 line，所以只有 2 个 set，set index 也只需要 1 位了，tag 增加为 2 位。

再来一遍刚刚那个例子：

  1. 00 0 0,miss
  2. 00 0 1,hit
  3. 01 1 1 ,miss
  4. 10 0 0,miss
  5. 00 0 0,hit

缓存的最终情况，x 表示没有内容：

1
2
3
4
5
Set  v  Tag  Block1  Block2
 0   1  00     A1      A2
 0   1  10     A8      A9
 1   1  01     A6      A7
 1   0  x      x       x

现在因为每个 set 中有两个 line，即使 8 和 0 的 set index 一致，它们也可以同时放到 set0中，而不会发生替换，所以最后一次访问 0，也不会失效。

写入

在将数据写入到存储设备中时，不同的层级可能会存放同一个数据的不同拷贝（缓存，内存，硬盘），如果发生写入命中（要写入的地址在缓存中存在），更新了缓存中的数据之后，那么怎么更新该数据在内存中的拷贝呢，有两种策略：

  1. Write- throug(直写)：立即更新内存中的数据拷贝。这种方式中内存始终保存着最新的数据，但是耗费高。
  2. Write-back(写回)：用一个特殊的标志位标记该数据被修改，当这条数据在缓存中被覆盖时，才更新内存中的拷贝。

当写入未命中时，也有两种方法：

  1. Write- allocate(写分配)：将目标内存块加载到缓存中，在缓存中更新该缓存块。
  2. Not- write- allocate(非写分配)：直接将数据写入到内存块中。

这四种策略通常的搭配是：

  • Write-through + No-write-allocate
  • Write-back + Write-allocate

其中第一种可以保证绝对的数据一致性，第二种效率会比较高（通常情况下）。

高速缓存参数的性能影响

使用一些指标来衡量缓存的性能：

  1. 命中率：在一个程序或程序的一部分在执行期间，缓存命中的比率；
  2. 命中时间：冲缓存传送一个字到CPU所需的时间，包括 set 选择，line 选择，字选择的时间，对于 L1 缓存来说，命中时间通常是 1-2 个时钟周期；
  3. 未命中开销：由于未命中导致的额外所需时间。

优化缓存的成本和性能的折中是一份很精细的工作，例如高速缓存大小、块大小、相联度、写策略等都是需要考虑的因素。

参考资料

  1. The Memory Hierarchy
  2. Cache Memories
  3. wdxtub的博客