前言

作为一个程序员，你需要理解存储器层次结构，因为它对应用程序的性能有着巨大的影响。如果你的程序需要的数据是存储在 CPU 寄存器中的，那么在指令的执行期间，在 0 个周期内就能访问到它们。如果存储在高速缓存中，需要 4~75 个周期。如果存储在主存中，需要上百个周期。而如果存储在磁盘上，需要大约几千万个周期。

随机访问存储器

Random Access Memory（随机访问存储器）

• Static RAM（静态 RAM，SRAM）

• Dynamic RAM（动态 RAM，DRAM）

SRAM

SRAM 将每个 bit 位的信息存储在一个双稳态的存储器单元内，每个存储单元需要六个晶体管来实现。

双稳态结构与钟摆模型相似，当钟摆倾斜到最左边或者最右边时，它的状态是最稳定的。从其他任何位置，钟摆都会倒向一边或另一边。

由于 SRAM 存储器单元的双稳态特性，只要有电，它就会永远地保持它的值。

DRAM

与 SRAM 相比，DRAM 存储信息的原理是电容充电。对于 DRAM 结构，每个 bit 位的存储对应一个电容和一个晶体管，这个电容是非常非常小的。与 SRAM 不同，DRAM 的存储单元对干扰十分敏感，当电容的电压被扰乱之后，就再也无法恢复到干扰之前。虽然 SRAM 的速度要比 DRAM 块，但是在价格方面要更贵。

处理器芯片内的 cache（高速缓存）采用的就是 SRAM，而内存采用的是 DRAM。此外，DRAM 还有另外一个缺陷，就是还会有很多原因导致漏电，使得 DRAM 会在 10~100 毫秒内失去电荷。幸运的是，计算机运行的时钟周期是以纳秒来衡量的，所以相对而言这个保持时间是比较长的。内存系统必须周期性地通过读出，然后重写来刷新内存每一位。

结构

图中展示了一个 16x8 的 DRAM 芯片，其中 16 表示的是超单元的个数，8 表示每个超单元可以存储 8 bit 的数据。

由于存储领域从来都没有为 DRAM 的阵列元素确定一个标准的名字，原书采用 "超单元" 一词来表示 DRAM 的存储单元。

通过这张图，可以看到所有的超单元被组织成一个 4x4 的阵列，每个超单元可以通过类似坐标的方式 (i, j) 进行寻址。

整个 DRAM 芯片通过地址引脚和数据引脚与内存控制器相连，而内存控制器主要是用来管理内存的。

例如，我们需要从 DRAM 芯片中读出图中所示的超单元 (2, 1)。

首先，内存控制器发送行地址 2 到 DRAM 芯片，DRAM 作出的响应就是将整个第二行的内容全部复制到内部的行缓冲区中。

接下来，内存控制器发送列地址 1 到 DRAM 芯片，DRAM 对应的操作是从这个行缓冲区中复制对应的数据位，并把它们发送到内存控制器。

为什么设计者分两次进行地址传送？

这是因为 DRAM 芯片的设计人员将存储单元设计成了二维的阵列，而不是线性数组，这样的好处是可以降低芯片上地址引脚的数量。如果将示例中 128 位（16x8）DRAM 的存储单元用线性数组来表示。那么地址范围就是 0~15，为了实现线性寻址需要 4 个地址引脚而不是 2 个。二维阵列组织的缺点是必须分两步发送地址，这增加了访问时间。

内存模块

图中展示了一个内存模块的基本组成，一共用了 8 个 DRAM 芯片，分别用编号 0~7 来表示。

每个 DRAM 芯片大小是 8MX8（8MX8bit，64Mbit），也就是 8MB。 因此，整个模块的大小为 64MB。

之前提到过，每个超单元可以存储 8bit 的数据，那么对于 8 字节（64bit）的数据就需要 8个超单元来存储。不过这 8个超单元并不在同一个 DRAM 芯片上，而是平均分布在 8 个 DRAM 芯片上，其中 DRAM 0 存储低 8 位，DRAM 1 存储下一个字节，以此类推，DRAM 7 存储最高 8 位。

当处理器向内存控制器发起读取数据的请求时，内存控制器将地址转换成超单元的地址（i, j），然后把它发送到内存模块。内存模块再将行地址 i 和列地址 j 广播到每个 DRAM，每个 DRAM 都会输出它对应超单元的数据。最终内存模块将所有超单元的数据合并成一个 64bit 的数据返回给内存控制器。

补充

为了跟上迅速增长的处理器速度，市场上会定期推出新的 DRAM。这些新的 DRAM 都是基于传统的 DRAM 单元，然后进行一些优化。例如我们经常在电脑配置清单看到 DDR3、DDR4 或者 LPDDR 等字样。

其中 DDR 的全称是 DDR SDRAM（Double Data-Rate Synchronous DRAM，双倍速率同步动态随机存储器），S 表示同步，而不是静态，不要与 SRAM 混淆。这里只需要知道同步 DRAM 比异步的速度更快就可以了。

关于 DDR2，DDR3，以及 DDR4 这些缩写中的数字（2, 3, 4）表示不同代，例如 4 代的 DDR 要比 3 代的 DDR 读写速度要快，速度的提升主要依靠扩大预取缓冲区的位数。例如 DDR4 的预取缓冲区是 16 bit，DDR3 是 8 bit。

此外，智能手机中的内存几乎全部都是采用 LPDDR，其中 LP 是 Low Power 的缩写，与 DDR4 相比，LPDDR 的功耗更低，不过 DDR4 的延迟更小。目前，市场上有许多商务笔记本也开始选用 LPDDR 作为内存，所以 LPDDR 更适合应用在功耗敏感的设备上。

磁盘

前言

无论是 SRAM 还是 DRAM，它们都需要在有电的情况下才能保存数据，而磁盘在断电的情况下也能保存数据。

机械磁盘

机械磁盘，也称旋转磁盘。它主要依靠盘片来存储数据，盘片的表面涂有磁性的记录材料。通常情况下，磁盘由一个或者多个盘片组成。这些盘片被固定在一个可以旋转的主轴上，主轴带动盘片以固定的旋转速率进行高速的旋转。

例如图中这个磁盘包含三个盘片，一共有 6 个表面可以用来存储数据。

其中盘片的表面被划分成了一圈一圈的磁道，具体如下图所示，每个磁道又被分成了多个扇区，通常情况下，每个扇区可以存储 512 个字节的数据。其中，扇区之间会有一些间隙，这些间隙是用来存放扇区的标识信息，不能用来存储数据。

磁盘通过读/写头来读写存储在盘片表面的数据，盘片的每个表面都对应着一个独立的读/写头，所有的读/写头连接到一个传动臂上，通过传动臂在半径方向上的移动，这样读/写头可以读取任意磁道上的数据，我们把这种机械运动称为寻道。

通过传动臂的移动，可以将读/写头定位在任意磁道上，在完成寻道之后，读/写头就保持不动了。

如果想要完成对目标扇区的读写操作，需要通过盘片旋转来配合。读/写头可以读出相应的数据位，也可以修改相应数据的值。注意，所有的读/写头都是垂直排列，一致行动的。其中读/写头距离磁盘表面的高度大约是 0.1 微米，在这样狭小的间隙里，任何微小的灰尘或者剧烈的震动都有可能导致读/写头撞向盘面，从而导致磁盘损坏。

通常我们关注最多的是磁盘的容量，也就是能存多少数据，这里需要特别注意的是，磁盘制造商会使用 GB 或 TB 为单位来标识磁盘的容量。但是这里的 1GB 等于 10 的 9 次方字节，1TB 等于 10 的 12 次方字节（对于 SRAM 和 DRAM 这一类设备，通常情况下，K 等于 2 的 10 次方，M 等于 2 的 20 次方，但是对于像磁盘和网络这样的 I/O 设备，通常情况下，K 等于 10 的 3 次方，M 等于 10 的 6 次方等等）。

除了容量之外，磁盘的读写速度也是一个非常重要的指标：

T_access = T_seek + T_rotation + T_transfer

对于扇区的访问时间主要分为三部分，分别是寻道时间、旋转时间以及传送时间。

• Seek time（寻道时间）：当目标扇区所处的磁道与当前读/写头所在的磁道不同时，那么传动臂需要将读/写头移动到目标扇区所在磁道，传动臂移动所需的时间就是寻道时间。

寻道时间取决于读/写头的当前位置与目标位置的距离，寻道有可能发生在两个相邻的磁道之间，此时寻道时间会比较短，也有可能是从最内侧磁道移动到最外侧磁道，遇到这种情况时寻道时间就会比较长。因此，寻道时间并不是一个固定的数值。通过对随机扇区的访问测试，通常平均寻道时间在 3~9 ms 左右。

• Rotational latency（旋转时间）：一旦读/写头移动到期望的磁道上，接下来还需要等待目标扇区的第一个数据位旋转到读/写头下才能读取数据。

这个过程的性能由两个因素决定，一个是当前读/写头所在扇区位置与目标扇区的距离，最坏的情况是，读/写头刚刚错过了目标扇区，所以必须等待盘片转一整圈才能读取数据。另外一个是盘片的旋转速度，例如一个磁盘的旋转速率是 7200 RPM（转每分），也就是说盘片一分钟可以转 7200 圈，那么转一圈大约需要 8ms，所以，在最坏的情况下的最大旋转延迟大约是 8ms。对于一般情况，平均旋转时间是最大旋转延迟的一半，约为 4ms。

最后，当读/写头位于目标扇区时，就可以开始读取（或者写入）数据了。

• Transfer time（传送时间）：一个扇区的传送时间依赖于旋转速度以及每条磁道的扇区数目。

假设每条磁道的平均扇区数是 400 个，转一圈需要 8ms，所以转过一个扇区大约需要 0.02ms，也就是说数据传送需要 0.02ms 就可以完成。

通过以上分析可以看出，访问一个磁盘扇区所花费的时间主要是寻道时间和旋转时间。

从操作系统的视角来看，整个磁盘被抽象成了一个个的逻辑块序列。每个逻辑块的大小与磁盘扇区的容量是一致的，都是 512 个字节。磁盘内部有一个小的固件设备，称为磁盘控制器。它维护着逻辑块与实际磁盘扇区之间的映射关系，当操作系统执行从硬盘读取数据到内存时，操作系统会发送一个命令到磁盘控制器，这个命令就是让磁盘控制器读取特定逻辑块号的数据。根据磁盘的结构特性，可以使用（盘面，磁道，扇区）这样的三元组来唯一标识每一个物理扇区。磁盘控制器上的固件程序的任务就是将逻辑块号翻译成对应的三元组信息。接下来，控制器会根据这个三元组的信息来执行移动读/写头以及旋转盘面的操作。然后，读/写头会把读到的数据放在一个缓冲区中，最后将目标数据复制到内存里。

固态硬盘

固态硬盘是由一个或者多个闪存芯片组成的，它使用闪存芯片取代了传动臂加盘片这种机械式的工作方式，除此之外，固态硬盘还包含一个闪存转换层（flash translation layer，FTL），其功能与磁盘控制器类似，都是将操作系统对逻辑块的请求翻译成对底层物理设备的访问。不同的是闪存芯片是基于 Nand Flash 实现的。

内部结构组成：

每一颗闪存芯片是由一个或者多个 Die 组成，每个 Die 可以分为多个 plane，每个 plane 包含多个 block，这里的 block 与逻辑块是没有关系的，Block 内部又分成多个 page，如下图所示：

对于固态硬盘，数据是以 page 为单位读写的，与机械磁盘相比（扇区的大小总是固定的 512 字节），对于不同规格的闪存芯片，其中 page 大小可能并不相同，在有些闪存芯片中一个 page 的大小是 512 字节，还有的是 1KB 或者 2KB，甚至更大。传统的机械磁盘包含读和写这两个基本操作，而固态硬盘除了这两个操作外，还多了一个擦除的操作。

由于闪存编程（写入）原理的限制，只能将 1 改为 0，而不能将 0 改为 1，所以一个 page 在写入数据之前，所有的存储位都是 1，对于写入操作而言，本质上就是将某些存储位从 1 变为 0。需要特别注意的是写入操作是以 page 为单位的，在写入之前页是需要擦除的，不能直接覆盖，对于擦除操作是以 block 为单位的，擦除操作的本质就是将所有的存储位都变成 1。当一个 block 完成了擦除操作，那么这个 block 中包含的所有 page 都被擦除了，此时所有的 page 都能够执行一次写操作。在经过一定次数的擦除之后，block 就会发生磨损，一旦一个 block 发生损坏之后，就不能再使用了，因此，固态硬盘中的闪存翻译层会使用平均磨损算法，将擦除平均到所有的块上来最大化每个块的寿命。如果平均磨损处理的好，固态硬盘也要好多年才能磨损坏。

比起机械硬盘，固态硬盘有很多优点，由于它是由半导体存储器构成的，没有移动的机械部件，因此随机访问时间比机械磁盘要快，功耗也更低，同时也更抗摔。缺点就是固态硬盘的价格要贵一些。

程序的局部性

局部性通常有两种不同的形式：时间局部性和空间局部性。如果被引用过的内存位置很可能在不远的将来还会被多次引用，此时，该程序具有良好的时间局部性；如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置，此时，我们可以说程序具有良好的空间局部性。

代码示例：

int sumvec(int v[N])
{
    int i, sum = 0;
    
    for(i = 0; i < N; i++)
        sum += v[i];
    return sum;
}

这个函数的功能是对一个向量的元素求和，其中变量 sum 在每次循环迭代中被引用一次，因此，对于 sum 来说，有好的时间局部性；另一方面，由于 sum 是个标量，不存在空间局部性的特点。向量 v 的元素是按照顺序一个接一个来读取的，如下图所示：

读取的顺序与存储在内存中的顺序是一致的，因此，对于变量 v，函数有很好的空间局部性，不过时间局部性很差，因为每个向量元素只被访问一次。综上所述，循环体中的变量要么有好的空间局部性，要么有好的时间局部性，所以该函数具有好的局部性。

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;
}

这个函数是对一个二维数组的元素进行求和运算，其中嵌套循环是按照行优先的顺序来读取数组元素的，也就是说内层 for 循环先读第一行元素，读完之后，再读第二行，以此类推。由于数组在内存中的顺序也是按照行优先的顺序存储的，所以该函数访问数组元素的顺序与内存中的存储顺序是一致的，此时，可以说这个函数具有良好的空间局部性。

改动一下该函数：

int sumarrayrows(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;
}

具体的改动方案是交换了 i 和 j 的循环，这使得程序空间局部性变差，这是因为访问顺序与存储顺序不一致了。

一般而言，有良好局部性的程序比局部性差的程序运行的更快。现代计算机系统的各个层次的设计都利用了局部性原理，例如高速缓存（cache）就是利用程序的局部性来提高 CPU 访存速度。

存储器层次结构

最高是寄存器，CPU 可以在一个时钟周期内访问它们，然后是基于 SRAM 的高速缓存，访问它们一般需要几个时钟周期，接下来是基于 DRAM 的内存，访问内存需要几十到几百个时钟周期，再往下是磁盘，虽然速度慢，但是容量大，最后，有些系统还包括远程服务器磁盘，需要通过网络来访问。

存储器层次结构的中心思想是速度更快、容量更小的存储设备作为速度更慢、容量更大的存储设备的缓存。

缓存

缓存在计算机系统中无处不在，例如图中第 k+1 层的存储器被划分为 16 个大小固定的块，每个块都有唯一的地址，这里我们用编号 0~15 来表示，第 k 层的存储器有 4 个块的空间，每个块的大小与 k+1 层的块一样，数据总是以块为单元在第 k 层和第 k+1 层之间来回复制。

当前第 k 层存储器包含了四个块的副本，对于相邻层之间的块大小是固定的，然而不相邻的层次之间，块的大小是不一样的。例如，寄存器与 L1 cache 之间传送的块大小通常是一个字，L2 cache 与 L1 cache 之间传送的块大小通常是几十个字节，内存与磁盘之间则是几百个或者几千个字节。一般来说，层次结构中离 CPU 越远的设备访问时间就越长，为了弥补访问过程中浪费的时间，因此倾向于使用较大的块。

几个缓存的基本概念：

• Cache Hit（缓存命中）：当程序需要第 k+1 层的某个数据对象 d 时，它首先从第 k 层的数据块中检索是否包含目标数据 d 的副本，如果目标数据 d 刚好缓存在第 k 层中，我们将这种情况称为缓存命中；

• Cache Miss（缓存不命中）：如果第 k 层没有缓存目标数据 d，我们将这种情况称为缓存不命中；

如果第 k 层的缓存已经满了，这时包含目标数据的块就会覆盖现存的一个块，我们把这个过程称为替换，被替换的块有时也称为牺牲块。决定替换哪个块是由缓存的替换策略来具体决定，常用的替换策略有随机替换以及 LRU 等。

基于 SRAM 的高速缓存

早期计算机系统的存储器层次结构只有三层，分别是寄存器文件、内存以及磁盘，由于 CPU 与内存之间的性能差距逐渐增大，于是系统设计者在寄存器文件和内存之间插入了一个小的基于 SRAM 的高速缓存，称为 L1 cache，其访问速度和寄存器差不多，大约需要 4 个时钟周期。随着 CPU 和内存之间的性能差距继续增大，系统设计者又在 L1 cache 和内存之间插入了一个更大的高速缓存，称为 L2 cache，其访问时间大约需要 10 个时钟周期。还有些计算机系统中还包含了一个更大的 L3 cache，它位于 L2 cache 和内存之间。

Cache

整个 cache 被划分成一个或者多个 set（组），这里我们用变量 S 表示 set 的个数，每个 set 包含一个或者多个 cache line（高速缓存行），这里我们用变量 E 来表示一个 set 中 cache line 的行数。

每个 cache line 由三部分组成，分别是有效位（valid）、标记（tag）、数据块（cache block）。其中有效位的长度是一个 bit，它表示当前 cache line 存储的信息是否有效，当 valid 等于 1 时，表示数据有效，当 valid 等于 0 时，表示数据无效。标记是用来确定目标数据是否存在于当前的 cache line 中。至于数据块就是一小部分内存数据的副本，大小用 B 来表示。

通常来说，cache 的结构可以用元组 (S, E, B, m) 来描述，cache 大小是指所有数据块的和，其中有效位和标记位不包括在内，因此 cache 的容量可以通过下面的公式来描述：

C = S * E * B

当 CPU 执行数据加载从内存地址 A 处读取数据时，根据存储器层次原理，CPU 将地址 A 发送到 cache，如果 cache 中保存着目标数据的副本，它就立即将目标数据发回给 CPU，那么 cache 是如何知道自己是否包含目标数据的副本呢？

假设目标数据（地址 A）的地址长度为 m 位，这个地址被参数 S 和 B 分成了三个字段，具体如下图所示：

首先，我们可以通过长度为 s 的组索引位来确定目标数据存储在哪个 set 中，接下来我们需要确定目标数据放在哪一行，确定具体的行是通过长度为 t 的标记来实现的，不过还需要注意一点，此时有效位必须等于 1，也就是说需要有效位和标记共同来确定目标数据属于哪一行。最后，我们需要根据长度为 b 的块偏移量来确定目标数据在数据块中的确切地址。

通过以上三步，cache 就能够确定是否命中。

直接映射

根据每个 set 所包含的 cache line 的行数不同，cache 被分为不同的类。当每个 set 只有一个 cache line，也就是 E 等于 1 时，我们将这种结构的 cache 称为直接映射（cache）。

CPU 从 cache 中获取数据分为三步：

• set selection（组选择）

• line matching（行匹配）

• word extraction（字抽取）

组选择

根据组索引值来确定目标数据属于哪个 set，例如图中组索引的长度是 5 位，这些二进制位被解释成一个无符号数。因此，长度为 5 的组索引位最大可以检索 32 个 set。当 s 等于 00000，此时组选择的结果是 set 0。

行匹配

假设每个 set 只有一个 cache line，当前 cache line 的有效位等于 1，也就是说此时 cache line 中的数据是有效的。然后我们需要对比 cache line 中的标记与地址中的标记位是否一致，如果一致，表示目标数据一定在当前的 cache line 中；另一方面，如果不一致，或者有效位等于 0，表示目标数据不在当前的 cache line 中。因此，行匹配最终的结果无非就是命中或者不命中。

字抽取

这一步需要根据偏移量来确定目标数据的确切位置，例如图中数据块的大小为 8 个字节，用编号 0~7 来表示。当块偏移等于 100 时，它表明目标数据的起始地址位于字节 4 处，这里我们假设目标数据的长度为四个字节。这样一来，我们就可以获得目标数据的副本了。

经过以上三步，cache 就可以将目标数据返回给 cpu 了。

不命中

cache 需要从存储器层次结构的下一层取出被请求的块，由于直接映射每个 set 只包含一行，因此替换策略十分简单，直接用新取出的行来替换当前的行就可以了。

具体例子

假设我们有一个直接映射的 cache，它包含 4 个 set，每个 set 有一行，每个数据块包含两个字节，其中地址 m 是 4 位。

由于地址是 4 位，整个地址空间可以用编号 0~15 来表示，标记位和索引位连起来可以唯一的标识每一个内存块。

需要注意每个内存块包含两个字节，例如块 0 是由地址 0 和地址 1 组成的。以此类推，整个内存空间被分成了 8 个块。

但是示例中的 cache 只有 4 个 set，因此就会出现两个内存块映射到同一个 set 的情况。例如块 0 和块 4 都映射到了 set 0，块 1 和块 5 都映射到了 set 1。

模拟 cpu 的读操作。这里假设 cpu 每次读取的数据都是一个字节。最开始时，整个 cache 都是空的，即所有的 cache line 的有效位都等于 0。图中表格的每一行代表一个 cache line。

第一步，当 cpu 读取地址 0 的数据时，经过组选择之后，发现 set 0 的有效位等于 0，此时不命中。接下来 cache 会从内存中取出包含目标数据的块，并把数据块放在 set 0 中，然后 cache 返回位于块 0 处的目标数据 m[0]。

第二步，当 cpu 读取地址 1（0001）的字时，由于目标数据 m[1] 已经在 cache 中，这次 cache 是命中的。cache 根据地址 m 进行组选择，行匹配以及字抽取之后，然后将目标数据 m[1] 返回给 cpu，此时 cache 的状态没有发生变化。

第三步，当 cpu 读地址 13（1101）的字，根据地址 13 的组索引位（10）进行组选择之后，发现 set 2 的有效位等于 0，所以发生不命中。这时，cache 把块 6 加载到 set 2 中，然后从 cache line 中抽取目标数据返回给 cpu。

第四步，当 cpu 读取地址 8（1000）的字，根据地址 8 的组索引位（00）进行组选择之后，发现 set 0 的有效位是 1。但是，进行标记对比后，发现并不匹配。

此时，需要用块 4 替换块 0。替换之后，cache 再返回目标数据到 cpu。

最后一步，当 cpu 再去读地址 0 的字，又会发生不命中，这是因为前面引用地址 8 的数据时，我们替换了块 0。由于不同的块刚好映射到同一个 set 中，虽然整个 cache 还有空闲的空间，当发生交替引用时，还是会出现不命中的情况。我们把这种现象称为冲突不命中。实际上冲突不命中在真实的程序中是很常见的，它会导致一些令人困惑的性能问题。

冲突不命中

对于变量 x 和 y 来说，这个函数具有良好的局部性。

float dotprod(float x[8], float y[8])
{
    float sum = 0.0;
    int i = 0;
    
    for(i = 0; i < 8; ++i)
        sum += x[i] * y[i];
       
    return sum;
}

因此，我们期望 cache 有较高命中率。然而实际情况并非如此。

假设数组 x 的第一个元素位于地址 0 处，每个元素长度为 4 个字节，因此可以得到数据 x 各个元素的起始地址。数组 y 紧跟其后，y[0] 的地址从 32 开始，具体如图所示：

当程序开始运行时，循环在第一次迭代时引用了元素 x[0]，此时发生不命中，cache 把包含 x[0]~x[3] 的块加载到 set 0。

接下来，又立刻引用了数组元素 y[0]，有一次不命中，这时 cache 把包含 y[0]~y[3] 的块加载到 set 0。

这里需要注意的是，之前 set 0 中存储的内容数据块是 x[0]~x[3] 的数据，那么这些数据会被 y[0]~y[3] 覆盖。后面每次对 x 和 y 的引用都会导致 cache line 的替换。我们把这种现象称为“抖动”。

综上所述，即使程序具有良好的空间局部性，同时我们的 cache 也有足够的空间来存放数组 x 和 y 的数据块，但是每次引用还是会产生冲突不命中，究其原因是这些块被映射到了同一个 set 中。这种抖动的出现可能会导致运行速度下降 2 到 3 倍。

如何处理？

我们可以把数组的长度由 8 变为 12，数组 y 还是紧跟在 x 的后面，此时数组 y 的起始地址发生了改变。

从而避免了 x 和 y 的元素被映射到同一个 set 中，这样一来，通过这种数据填充的方式就可以消除抖动，从而解决冲突不命中的问题。

为什么用中间的位来做索引

如果高位用做索引，那么一些连续的内存块就会映射到相同的高速缓存块。如图所示：

头四个块映射到第一个高速缓存组，第二个四个块映射到第二个组，依此类推。如果一个程序有良好的空间局部性，顺序扫描第一个数组的元素，那么在任何时刻，高速缓存都只保存着一个块大小的数组内容。这样对高速缓存的使用效率很低。相比较而言，以中间位作为索引，相邻的块总是映射到不同的高速缓存行。

组相联 Cache

直接映射的每个 set 只有一行，因此容易发生冲突不命中，与直接映射不同，组相联 cache 的每个 set 允许包含多个 cache line。也就是说 E 是大于 1 的，不过每个 set 最多不能超过 C/B 个 cache line。

例如图中每个 set 包含两个 cache line，我们将这种结构称为 2 路组相联 cache。

组相联 cache 确定一个请求是否命中，同样需要经过组选择、行匹配以及字抽取这三步。

组选择

组相联 cache 组选择的过程与直接映射 cache 是一样的，都是通过组索引位来确定目标数据属于哪一个 set，具体如图所示：

行匹配

由于组相联 cache 的每个 set 包含多个 cache line，所以需要遍历这个 set 中的每一行来寻找一个有效位等于 1，并且与地址中的标记位相匹配的 cache line。

如果找到了符合条件的 cache line，表示命中。

字抽取

接下来，根据块偏移从这一行的数据块中抽取目标数据。

如果找不到符合条件的 cache line，表示不命中。此时 cache 必须从内存中取出包含目标数据的块。不过，一旦 cache 取出这个块，应该替换哪一行呢？

如果存在空行，也就是 valid 等于 0 的 cache line，那么这个空行就是不错的选择。但是如果这个 set 中没有空行，这时我们需要从中选择一个非空行作为被替换的对象，同时希望 cpu 不会很快引用这个被替换的行。

替换策略

• 最简单的替换策略就是随机选择一行，然后进行替换；

• 最不常使用策略（LFU）会替换在过去某个时间段内引用次数最少的那一行；

• 最近最少使用策略（LRU）会替换最后一次访问时间最久远的那一行。

全相联 cache 的组织结构

整个 cache 只有一个 set，也就是说一个 set 包含了所有的 cache line。

具体的行数 E 可以通过 C/B 计算得到。C 表示 cache 的容量，B 表示数据块的大小。

由于全相联 cache 只有一个 set，所以默认总是选择 set 0。

这样一来，地址只需要划分成标记和块偏移即可，具体如图所示：

关于全相联 cache 的行匹配和字选择与组相联 cache 是一样的，它们之间的主要区别就是 cache line 规模大小的问题。由于硬件实现和成本的问题，全相联 cache 只适合做容量较小的高速缓存，例如虚拟内存系统中的 TLB 可以使用这种结构。

写操作

实际上，cache 关于读的操作比较简单，不过写入的情况要复杂一些，当 CPU 需要往内存中写入数据时，需要考虑两种情况：

• Write Hit（写命中）

  • write-through（写穿透）：CPU 在写 cache 的同时写内存（更低一级 cache），这种策略的好处是内存（更低一级 cache）的数据永远都是新的，cache 替换时直接扔掉旧的数据就可以。

  • write-back（写回）：CPU 只写 cache，不写内存（更低一级 cache），写回的好处是写 cache 时比较省事儿，不用关注是否与内存（更低一级 cache）一致。只有当替换算法要驱逐这个更新的块时，再写回到内存里（更低一级 cache）。不过这种策略会增加 cache 的复杂性，为了表明每个数据块是否被修改过，每一个 cache line 需要增加一个额外的修改位。

• Write Miss（写不命中）

  • write-allocate（写分配）：就是先把目标数据所在的块从内存（更低一级 cache）加载到 cache 中，然后再往 cache 中写。

  • no-write-allocate（写不分配）：绕开 cache，直接把要写的内容写到内存（更低一级 cache）里。

通常情况下，写分配与写回搭配使用，写不分配与写穿透搭配使用。

Intel Core i7 高速缓存

其中每个处理器芯片包含四个核心，每个核都有自己私有的 L1 i-cache、L1 d-cache 和 L2 cache，所有的核心共享芯片内的 L3 cache。注意所有基于 SRAM 的高速缓存都是在处理器芯片内部。

之前我们一直假设 cache 只保存程序的数据，实际上，cache 既保存数据，也保存指令，把只保存指令的高速缓存称为 i-cache，只保存数据的高速缓存称为 d-cache。既保存指令又保存数据的高速缓存称为统一的高速缓存。采用独立的 i-cache 和 d-cache 的好处是 CPU 可以同时读指令和数据，此外，还能确保数据访问不会与指令访问形成冲突不命中。

不同层次 cache 的特性以及参数：

访问时间、容量大小以及相联的方式等等。

一方面，容量较大的 cache 可能会提高命中率，不过使容量较大的 cache 运行的更快要更难一些。最终导致的结果是容量较大的 cache 可能会增加命中的时间，这就是为什么 L1 cache 比 L2 cache 小，L2 cache 比 L3 cache 小的原因。数据块的大小也会影响 cache 的性能，较大的块能够利用程序中可能存在的空间局部性，帮助提高命中率。不过对于给定的 cache 大小，块越大就意味着 cache 的行数越少。这样一来，虽然对空间局部性好的程序是有利的，但是时间局部性好的程序的命中率就会受到损害。此外，当发生不命中时，较大的块的处罚也会增大。因此块越大，传送的时间也就越长。

在 Intel Core i7 处理器中，L1 cache 和 L2 cache 都是 8 路组相联的，L3 cache 采用的是 16 路组相联，也就是说对于 L1 cache 和 L2 cache，每个 set 中有 8 个 cache line，L3 cache 的每个 set 有 16 个 cache line。每个 set 中 cache line 的数量越多，那么由于冲突不命中导致的抖动现象发生的几率就越低。不过相联度越高，实现的复杂度就越高，访问速度就很难再提高了。所以最终相联度应该如何选择，需要在命中时间和不命中处罚之间做一个折中的处理。

最后一个因素就是写策略的影响，一般而言，L1 cache 与 L2 cache 之间用写穿透的多一些，越往下层，写回策略比写穿透用的更多。