存储器的层次结构

《深入理解计算机系统》 第六章

存储器的层次结构对应用程序的性能有着巨大的影响。

• 如果程序需要的数据是存储在CPU寄存器中的，那么在指令执行期间，0个cycle就可以访问到它们。
• 如果存储在cache中，需要4-75个cycle。
• 如果存储在主存中，需要上百个cycle。
• 如果存储在磁盘中，需要几千万个cycle，在毫秒级。

局部性(locality)做得比较好的程序，能够将自己频繁使用的数据放到较高层次的存储器中，因此也能运行得更快。
我们应该注意自己写的程序的局部性，也应该掌握分析程序局部性的方法。

不同层次的存储器中，cache作为CPU与主存之间的缓存区域，对应用程序的影响最大。

---

访问主存
数据流通过总线(bus)在CPU和主存之间传输。

总线是一组并行的导线，能携带地址、数据、控制信号。
数据和地址信号可以用同一组导线，也可用不同的。取决于总线的设计。
控制线携带的信号用于同步，并标识当前的事务。比如当前的事务是到主存还是磁盘？是读还是写？总线上的信息是地址还是数据？

下图是一个示例计算机系统的配置。其中I/O桥接器(I/O bridge)芯片组(其中包括内存控制器)，将系统总线的电子信号翻译成内存总线的电子信号。它也将系统总线和内存总线连接到I/O总线，不过这里我们暂且忽略。

当CPU执行一个读操作，比如
movq A, %rax 将地址A的内容加载到寄存器rax中。
CPU芯片上的总线接口(bus interface)会在总线上发起读事务。读事务分为3步：

1. CPU将地址A放到系统总线上，I/O桥将信号传递到内存总线。
2. 主存收到内存总线上的地址信号，根据地址从DRAM中取出数据字，并将数据写到内存总线。
   I/O桥将内存总线信号翻译成系统总线信号，并沿着系统总线传递。
3. CPU收到系统总线上的数据，读取数据并赋值到寄存器%rax。

对应的，当CPU执行一个写操作，比如
movq %rax,A 将rax的内容写到地址A。
CPU发起写事务，同样有3个步骤：

1. CPU将地址放到系统总线上，内存从内存总线读出地址，并等待数据到达。
2. CPU将%rax中的数据复制到系统总线。
3. 内存从内存总线读出数据字，并将这些位存储到DRAM中。

此处的例子比较简单，CPU直接给出物理地址，没有涉及到虚拟地址的转换，也就没有涉及到MMU等硬件。

---

局部性
这部分内容，直接看《深入理解计算机系统》6.2更好，里面的内容组织得非常合理，因此不再在此处重复。

---

存储器层次结构

下图展示了存储器层次结构中缓存的一般性概念。
第k+1层的存储器被划分成连续的组块(chunk)，又称块(block)。每个块都有一个唯一的地址或名字，使之区别于其他的块。块通常是固定大小，但也可以是可变大小的。
如下图中，k+1层存储器被划分为16个大小固定的块，编号为0~15。
第k层的缓存有4个块的空间，此时包含块4, 9, 14, 3的副本。

数据总是以“块”为单位进行复制的。虽然相邻层之间的块大小固定，但是其他层之间可以有不同的块大小。
比如上面分层的图中，L1和L0之间的传送通常用1个字大小的块。
L2和L1之间，以及L3和L2之间，L4和L3之间的传送，通常使用几十个字节的块。
L5和L4之间的传送通常用几百或几千字节的块。
一般来说较低层的设备访问时间长，而为了补偿较长的访问时间，倾向于使用较大的块。

当程序要在k+1层中查找某个数据d时，它会先去第k层中查找。
如果第k层中刚好有，则我们称此为缓存命中(cache hit)。
如果第k层中没有，我们称此为缓存不命中(cache miss)。
当发生cache miss时，第k层的缓存会从第k+1层缓存中取出包含d的那一块。如果第k层的缓存满了，则替换现存的块。替换哪个块由缓存的替换策略(replacement policy)决定。也许用随机替换策略，也许用最少被使用(LRU)替换策略等。

---

高速缓存存储器
随着CPU和主存之间逐渐增大的差距，系统设计者在CPU寄存器文件和主存之间插入了SRAM高速缓存存储器，称为L1高速缓存。
虽然之后又加入了L2高速缓存、L3高速缓存，但我们这里假设只有一个L1高速缓存。

设一个m位的计算机系统，每个存储器地址有m位，形成个不同的地址。
这样一个机器的高速缓存被组织成一个有个高速缓存组(cache set)的数组。
每个组包含E个高速缓存行(cache line)。
每个行由一个字节的数据块(block)组成。一个有效位(valid bit)指明这个行是否包含有意义的信息。还有t=m-(b+s)个标记位(tag bit)，唯一地标识存储在这个高速缓存行中的块。

高速缓存的容量指所有块的大小的和。标记位和有效位不包括在内。
C = S组 * E行 * B字节

当CPU要从主存地址A中读一个字时，它先将地址A发送到高速缓存。
高速缓存对地址A的解析见上图(b)。

1. 检查s个组索引，指示了这个字在哪个组中。
2. t个标记位告诉我们这个字在哪一行中。当且仅当设置了有效位且该行的标记位与地址A中的标记位相匹配时，组中的这一行才包含这个字。
3. b个块偏移位给出了在B个字节的数据块中的字偏移。

我们可以发现，t个标记位 + s个索引位 + b个块偏移，刚好是m位，因此这种格式可以用来解释内存的地址，并将其与高速缓存对应起来。

• 高速缓存的S个组，是与s个索引位对应的，即。
• 高速缓存每一行的B个字节，是与b个块偏移对应的，即。
• 但是高速缓存的行数E，与t个标记位，没有对应关系。一般E是远远小于的。

阅读书中6.4.2 (5)，你可以动手实践一下高速缓存的工作流程。
阅读书中6.4.2 (6)，你会学到“抖动”的概念，即因为两个内存块被映射到高速缓存的同一个cache line，导致高速缓存反复地替换这个cache line，使得有良好空间局部性的程序，cache miss率反而很高。

如果你发现了“抖动”现象，修改起来也很容易。只需要对数据结构进行填充，使得两个数据映射到不同的cache line，就能消除抖动。