CSAPP 第六章 存储器层次结构

存储器系统各层的原理和属性

在对系统的研究学习中，我们假定了一个简单的计算机系统模型，CPU 执行指令，而存储器系统为 CPU 存放指令和数据。在简单模型中，存储器系统是一个线性的字节数组，而 CPU能够在一个常数时间内访问每个存储器位置。

实际上，存储器系统 (memory systcm) 是一个具有不同容量、成本和访问时间的存储设备的层次结构。CPU 寄存器保存着最常用的数据。越靠近 CPU 的存储器读写速度越快，容量越小。

存储技术

基本的存储技术有：SRAM 存储器、DRAM 存储器、ROM存储器以及旋转的和固态的硬盘

随机访问存储器

随机访问存储器（Random-Access Memory，RAM）分为两类：静态的和动态的。其中静态 RAM（SRAM）比动态的（DRAM）更快，但也更贵。

SRAM 用来作为高速缓存存器，既可以在 CPU 芯片上，也可以在片下。DRAM 用来作为主存以及图形系统的帧缓冲区。

静态RAM（SRAM）

SRAM 将每个位存储在一个双稳态的（bistable）存储器单元里。它的属性是：可以无限期地保持在两个不同的电压配置(configuration)或状态(state)之一，其他任何状态都是不稳定的。

如下图：中间图的状态虽然可以保持，但实际上是亚稳态的——只要有细微的扰动就会破坏它所谓的稳态，最后都会趋于最左或最右的状态。

由于 SRAM 存储器单元的双稳态特性，只要有电，它就会永远地保持它的值。即使有干扰（例如电子噪音）来扰乱电压，当干扰消除时，电路就会恢复到稳定值。

动态RAM（DRAM）

DRAM 将每个位存储为对一个电容的充电。与 SRAM 不同，DRAM 存储器单元对干扰非常敏感。当电容的电压被扰乱之后，它就永远不会恢复了。

会有很多原因导致 DRAM 漏电，使得 DRAM 单元在 10~100 毫秒时间内失去电荷。但是因为这时间还是足够长的，我们可以周期性地重写来刷新每一位，或者使用纠错码发现每个单元的错误位。

下表展示了 SRAM 和 DRAM 的特性：

传统的DRAM

DRAM 芯片中的单元（位）被分成 d 个超单元（supercell），每个超单元都由 w 个 DRAM 单元组成。

如下图展示的是一个 16X8 的 DRAM 芯片的组织：

信息通过引脚的外部连接器流入和流出芯片，每个引脚传递一位信号。如上图 data 和 addr 都是引脚：8 个 data 引脚，传送一个字节到芯片或从芯片传出一个字节； 2 个 addr 引脚，它们携带 2 位的行和列超单元地址。

每个 DRAM 芯片被连接到某个称为内存控制器（emory controller）的电路，这个电路可以一次传送 w 位到每个 DRAM 芯片或一次从每个 DRAM 芯片传出 w 位。为了读出超单元 (i,j)的内容，内存控制器将行地址发送到 DRAM，然后是列地址j。DRAM 把超单元 (i,j) 的内容发回给控制器为响应。行地址称为 RAS（Row Access Strobe，行访问选通脉冲）请求。列地址 i 称为 CAS（Column Access Strobe，列访问选通脉冲）请求。

需要注意的是，RAS 和 CAS 请求共享相同的 DRAM 地址引脚。

内存模块

DRAM 芯片封装在内模块（memory module）中

要取出内存地址 A 处的一个字，内存控制器将 A 转换成一个超单元地址 (i,j) ，并将它发送到内存模块，然后内存模块再将和广播到每个 DRAM。作为响应，每个 DRAM 输出它的 (i,j) 超单元的8 位内容。模块中的电路收集这些输出，并把它们合并成一个 64 位字，再返回给内存控制器。

非易失性存储器

如果断电，DRAM 和 SRAM 会丢失它们的信息，从这个意义上说，它们是易失的（volatile）。而非易失性存储器（nonvolatile memory）即使是在关电后仍然保存着它们的信息。

存储在 ROM 设备中的程序通常被称为固件（firmware）。

访问主存

数据流通过称为总线（bus）的共享电子电路在处理器和 DRAM 主存之间传递信息。每次CPU 和主存之间的数据传送都是通过一系列步骤来完成的，这些步骤称为总线事务（bus transaction）：

• 读事务（read transaction）从主存传送数据到 CPU。
• 写事务（write transaction）从 CPU 传送数据到主存

总线是一组并行的导线，能携带地址、数据和控制信号。控制线携带的信号会同步事务，并标识出当前正在被执行的事务的类型。

如下图便是一个计算机系统的配置：

系统总线（system bus）连接 CPU 和 I/O 桥接器，内存总线（memory bus）连接 I/O 桥接器和主存。

接下来我们看两个实例：

CPU 执行 movq A %rax 这个操作时，地址 A 存储的内容将被加载到寄存器 %rax 中，总线接口会在总线上发起读事务，读事务有三个步骤组成：

• 首先 CPU 将地址 A 放到系统总线上，I/O 桥将信号传递到内存总线。
• 接下来主存检测到内存总线上的地址信号，从内存总线读地址，从 DRAM 中读取数据字，并将数据写到内存总线。 I/O 桥将内存总线信号翻译成系统总线信号，沿着总线传递。
• 最后 CPU 检测到总线上的数据并读取，将其复制到寄存器 %rax 中。

具体如下图：

CPU 执行 movq %rax,A 这个操作时，寄存器 %rax 的内容被写到地址 A ，CPU 会发起写事务。同样，写事务也有三个基本步骤：

• 首先 CPU 将地址放在内存总线上，内存从总线读出地址并等待数据到达

• CPU 将 %rax 中的数据字复制到系统内存总线

• 最后主存从内存总线读出数据字，并将这些位存储在 DRAM 中

具体如下图：

磁盘存储

磁盘是广为应用的保存大量数据的存储设备，存储数据的数量比 RAM 大得多，但从磁盘读取数据也要比 RAM 慢许多。

磁盘构造

磁盘驱动器（disk drive），简称磁盘。一个磁盘是由多个盘片构成的，封装在一个密封的容器里。每个盘片有两面（或者称为表面）覆盖着磁性记忆材料。转盘中间有一个可以选装的主轴，使得盘片以固定的旋转速率旋转。

每个盘片包含多个同心圆组成的磁道，每个磁道会被划分为一组扇区，每个扇区包含相等数量的数据位（通常是512字节）。扇区之间由一些间隙（gap）分隔开,这些间隙中不存储数据位。间隙存储用来标识扇区的格式化位。

柱面是指每个盘的同一磁道的集合，比如每个盘的第一个同心圆组成了第一个柱面。

磁盘容量

磁盘上可记录的最大位数成为它的最大容量，或者简称容量。磁盘容量由以下技术因素决定：

• 记录密度（recoding density）（位/英寸）：磁道一英寸的段中可以放入的位数。
• 磁道密度（trackdensity）（道/英寸）：从盘片中心出发半径上一英寸的段内可以有的磁道数目
• 面密度（areal density）（位/平方英寸）：记录密度与磁道密度的乘机

我们计算面密度只要根据下面的公式即可：
$$
磁盘容量=\frac{字节数}{扇区}\times\frac{平均扇区数}{磁道}\times\frac{磁道数}{表面}\times\frac{表面数}{盘片}\times\frac{盘片数}{磁盘}
$$

磁盘操作

磁盘用读/写头（read/write head）来读写存储在习性表面的位，而读写头连接到一个传动臂的一端。每个盘面都有一个独立的读/写头。读/写头垂直排列，一致行动。在任何时刻，所有的读/写头都位于同一个柱面上。

通过沿着半径轴前后移动这个传动臂，驱动器可以将读/写头定位在盘面上的任何磁道上。这样的机械运动称为寻道（seek）。

如下图：

读写头在磁盘表面大约 0.1 微米处飞翔（这应该是直译来的叭不过也是生动形象嗷），所以盘面上微小的灰尘也会影响读写操作，如果读写头遇到了灰尘这类障碍物就会停下来，撞到盘面，这就是所谓的读/写头冲撞。因此磁盘总是密封的。

磁盘以扇区大小的块来读写数据。对扇区的访问时间（access time）有三个主要的部分：

• 寻道时间（seek time）：为了读取某个目标扇区的内容，传动首先将读/写头定位到包含目标扇区的磁道上。移动传动臂所需的时间称为寻道时间。
• 旋转时间（rotational latency）：一旦读/写头定位到了期望的磁道，驱动器等待目标扇区的第一个位旋转到读/写头下。这个步骤的性能依赖于当读/写头到达目标扇区时盘面的位置以及磁盘的旋转速度。
• 传送时间（transfer time）：一个扇区的传送时间依赖于旋转速度和每条磁道的扇区数目。

逻辑磁盘块

我们所看到的磁盘比较复杂，为了便于操作系统读取磁盘数据，现代磁盘为我们构造了一个简单的视图，是一个 B 个扇区大小的逻辑块序列，磁盘封装中有一个设备叫磁盘控制器维护了逻辑块号（对操作系统的抽象）和磁盘扇区（物理扇区）之间的映射关系。

操作系统想要执行 IO 操作读写文件的时候，就会发送一个逻辑块号给磁盘控制器翻译成一个三元组（盘面，磁道，扇区）找到对应的值进行读写。

连接 I/O 设备

输人/输出（I/O）设备，都是通过 I/O 总线连接到CPU和主存的。

有以下集中设备可以连接到总线：

• 通用串行总线（Universal Serial Bus，USB）控制器是一个连接到USB总线的设备的中转机构，USB 总线是一个广泛使用的标准。
• 图形卡（或适配器）包含硬件和软件逻辑，它们负责代表CPU在显示器上画像素。
• 主机总线适配器连接磁盘。
• 其他的设备，例如网络适配器，可以通过将适配器插入到主板上空的扩展槽中，从而连接到 I/O 总线，这些插槽提供了到总线的直接电路连接。

访问磁盘

CPU 使用一种称为内存映I/O（memory-mapped I/O）的技术来向I/O设备发射命令。在使用内存映射 I/O 的系统中，地址空间中有一块地址是为与 I/O 设备通信保留的，这样的地址称为一个 I/O 端口。

当一个设备连接到总线时，它与个或多个端口相关联（或它被映射到一个或多个端口）。

一般发出请求之后，CPU就会去做其他的工作，因为读取磁盘相对于执行指令来说是慢了好几个数量级的。

在磁盘控制器收到指令之后，将逻辑块信号翻译成扇区地址，读该扇区的内容，然后将这些内容直接传送到主存，不需要 CPU 来干涉。这种设备可以自己执行读写而不需要 CPU 的干涉的过程称为直接内存访问（Direct Memory Access，DMA）

传送完成之后，磁盘控制器会给 CPU 发一个中断信号来通知 CPU 已经完成了数据传送的操作。基本思想就是通过发送信号给 CPU 芯片的外部引脚，让 CPU 暂停执行的工作，跳转到一个操作系统的例程，执行完一些擦做之后回到被中断的地方。

固态硬盘

固态硬盘（Solid Stack Disk，SSD）是一种基于闪存的存储技术。

一个 SSD 封装由一个或者多个闪存芯片和闪存翻译层组成，闪存芯片替代传统旋转磁盘中的机械驱动器，而闪存翻译层是一个硬件/固件设备，扮演与磁盘控制器相同的角色，将对逻辑块的诺求翻译成对底层物理设备的访问。

SSD 的读比写要快得多，性能差别是有底层的闪存基本属性来决定的。一个闪存由 B 个快的序列组成，每个块由 P 页组成，而数据是以页的单位来读写的。只有在一页所属的块整个被擦除之后，才能写这一页（通常是指该块中的所有位都被设置为1）。不过，一旦一个块被擦除了，块中每一个页都可以不需要再进行擦除就写一次。在大约进行100000次重复写之后，块就会磨损坏。只要有一个块磨损坏，这个硬盘就不能再使用了。

固态硬盘能耗低，速度快，但是反复写之后会磨损。闪存翻译层中的平均磨损逻辑试图通过将曹处平均分配在所有的块上来最大化每个块的寿命。同样，高性能带来的必定是昂贵的价格，不过因为 SSD 越来越受欢迎，它们之间的价格差距也在逐步减少。

存储技术趋势

我们对存储技术的研究，有以下几点重要的思想：

• 不同的处处技术有不同的价格和性能折中。

  在存储速度方面，SRAM > DRAM > SSD > 旋转磁盘，同样性能高的硬件设备的造假也更高

• 不同存储技术的价格和性能属性变化的速率不同

  

局部性

计算机程序通常是具有局部性的，它们会倾向于引用自己附近的内存区域或者是自己本身，比如一个循环程序，它就会反复执行一个局部的代码或者是局部的一个变量，这种倾向性被称为局部性原理。

• 时间局部性：被引用过的内存位置很有可能再被多次引用
• 空间局部性：如果一个内存被引用过一次，那么很有可能引用附近的一个内存位置

只要目标函数满足其一，我们就称这个函数 ” 有良好的局部性 “

对数据引用的局部

我们来看一个例子，下面的函数对向量的元素求和：

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

N=8 时，引用模式入下：

地址	0	4	8	12	16	20	24	28
内容	$$v_0$$	$$v_1$$	$$v_2$$	$$v_3$$	$$v_4$$	$$v_5$$	$$v_6$$	$$v_7$$
访问顺序	1	2	3	4	5	6	7	8

这个函数的元素是被按照他们在内存中的顺序来读取的，所以对于变量v，这个函数有很好的空间局部性。

像 sumvec 函数这样顺序访问每一个元素的函数，具有步长为1的引用模式，我们称这样的引用模式为顺序引用模式。一个连续向量中，每隔 k 个元素进行访问，就称为步长为 k 的引用模式。步长为 1 的引用模式是程序中空间局部性常见和重要的来源。一般而言，随着步长的增加，空间局部性下降。

接下来两个例子分别展示了局部性很好和很差的两个程序：

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

int sum2(int a[M][N])
{
    int i,j,sum=0;
    for(i=0;i<N;i++)
    {
        for(j=0;j<M;j++)
        {
            sum+=a[j][i];
        }
    }
}

空间局部性体现在访问 a[i] 数组上，因为下一次循环就会访问上一次访问过的元素的后面一个位置。

时间局部性就体现在访问 sum 变量上，因为每次都会取得 sum 变量去进行运算。

sum1 的局部性就比 sum2 要好得多。sum1每次循环会制造步长为 1 的空间移动，而 sum2 每次循环会制造间隔为 N 的空间移动

在 a[M][N] 中， a[i][j]~a[i][j+1] 地址紧邻，而 a[i][j] 和 a[i+1][j] 相差了 N 个 int 的数据）。

取指的局部性

• 空间局部性体现在循环内部，所有指令都是紧挨着运行的。

• 时间局部性体现在循环内部，一条指令会在将来被执行多次。

局部性小结

• 复引用相同变量的程序有良好的时间局部性。

• 对于具有步长为 k 的引用模式的程序，步长越小，空间局部性越好。

  具有步长为1的引用模式的程序有很好的空间局部性。在内存中以大步长跳来跳去的程序空间局部性会很差。

• 对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。

存储器结构层次

我们再前两节了解到存储技术和计算机软件的属性：

• 存储技术：不同存储技术的访问时间差异很大，越靠近 CPU 容量越小、速度越快、造价也更高
• 计算机软件：我们的程序需要有良好的局部性

而硬件和软件之间的基本属性互相补充的很完美，我们现代计算机系统中使用了一种组织存储器系统的方法——存储器体系结构。具体如下图：

存储器体系结构中的缓存

高速缓存是一个小而快速的存储设备，它作为存储在更大、也更慢的设备中的数据对象的缓冲区域。使用高速缓存的过程称为缓存。

存储器体系结构的中心思想是，对于每个 k ，位于 k 层的更快更小的存储设备作为位于 k+1 层的更大更慢的存储设备的缓存。例如，本地磁盘作为通过网络从远程磁盘取出的文件（例如Web页面）的缓存，主存作为本地磁盘上数据的缓存，依此类推，直到最小的缓存—— CPU 寄存器组。

如上图，数据总是以块大小为传送单元（transfer unit）在第 k 层和第 k+1 层之间来回复制的。

虽然在层次结构中任何一对相邻的层次之间块大小是固定的，但是其他的层次对之间可以有不同的块大小，比如 CPU 和 Cache 之间可能只有十几个字节的大小，而主存到硬盘之间可能有几兆甚至几十兆的大小。

缓存命中

当程序刚好需要第 k+1 层的某个缓存数据对象 d 时，他首先会在当前存储的第 k 层的第一个块中寻找，倘若 d 刚好在 k 层中，那么就是我们所说的缓存命中。

缓存不命中

如果第 k 层没有我们想要找的缓存数据对象 d ，就叫做缓存不命中。当发生缓存不命中时，第 k 层的缓存从第 k+1 层缓存中取出包含 d 的那个块，如果第 k 层的缓存已经满了，可能就会覆盖现存的一个块。

覆盖现存块的过程称为替换或者驱逐这个块，被驱逐的块叫做牺牲块。而决定替换哪个块是由缓存的替换策略来控制的。

缓存不命中的种类

强制不命中

有一种命中称为强制不命中或冷不命中（cold miss），是指当第 k 层的缓存为空时，此时无论访问什么数据都会发生不命中。

只要发生了不命中，第 k 层的缓存就需要执行某个放置策略，最灵活的替换策略是我们允许 k+1 层中的块放在任何一个位置，因为随机的放置块，需要用到的时候需要遍历整个 k 层存储器，代价很高。

因此，硬件缓存通常是采用更加严格的放置策略，将第 k+1 层的某个快限制放置在第 k 层块的一个小小的子集中。例如，上图中，因为 k+1 层的第 i 块只会放到 k 层中第 i mod 4 块的位置上。我们在寻找的时候，就可以用很低的复杂度快速判断我们的块在不在第 k 层了。

冲突不命中

上面提到的限制性的放置策略会引起另一种不命中叫冲突不命中（conflict miss）。在这种情况中，缓存足够大，能够保存被引用的数据对象，但是因为这些对象会映射到同一个缓存块，缓存会一直不命中。比如，如果程序请求块 0，然后块 8，然后块 0，然后块 8，依此类推，在第 k 层的缓存中，对这两个块的每次引用都会不命中，然而 k 层的缓存还有很多空间可以使用。

数量不命中

如果循环体过大，或者是数组遍历过大，我们也有概率发生不命中，因为这个大小已经远远超过缓存能容纳的大小，此时缓存会经历容量不命中（capacity miss），就是说缓存太小了，容纳不下。

缓存管理

管理缓存的逻辑可以是硬件、软件或者时两者的结合：

• 编译器管理寄存器文件是缓存层次结构的最高层。它决定当发生不命中时何时发射加载，以及确定哪个寄存器来存放数据。
• L1、L2和 L3 层的缓存完全是由内置在缓存中的硬件逻辑来管理的。
• 在一个有虚拟内存的系统中，DRAM 主存作为存储在磁盘上的数据块的缓存，是由操作系统软件和 CPU 上的地址翻译硬件共同管理的。
• 对于一个具有像 AFS 这样的分布式文件系统的机器来说，本地磁盘作为缓存，它是由运行在本地机器上的 AFS客户端进程管理的。

存储器体系结构概念小节

概括来说，基于缓存的存储器体系结构行之有效，是因为较慢的存储设备比较快的存储设备更便宜，还因为程序倾向于展示局部性：

• 利用时间局部性：由于时间局部性，同一数据对象可能会被多次使用。一旦一个数据对象在第一次不命中时被复制到缓存中，我们就会期望后面对该目标有一系列的访问命中。因为缓存比低一层的存储设备更快，对后面的命中的服务会比最开始的不命中快很多。
• 利用空间局部性：块通常包含有多个数据对象。由于空间局部性，我们会期望后面对该块中其他对象的访问能够补偿不命中后复制该块的花费。

高速缓存存储器

早期计算机系统的存储器结构层次只有三层： CPU 寄存器、DRAM 主存储器和磁盘存储。

随着 CPU 和主存之间逐渐增大的差距，系统设计者在 CPU 寄存器文件和主存之间插入了一个小的 SRAM 高速缓存存储器，称为 L1 高速缓存（一级缓存）。而后一级缓存也无法弥补性能之间的差距，程序设计者又在 L1 高速缓存和主存之间插入了一个更大的高速缓存，称为 L2 高速缓存。有些现代系统还包括一个比 L2 更大的高速缓存 L3 高速缓存。

接下来的章节中都是以只有一个 L1 高速缓存的情况来学习的。

通用的高速缓存存储器组织结构

高速缓存的组织如下：

一个机器的高速缓存组被组织为一个有 $$S =2^s$$ 个高速缓存组的数组，每个组包含 E 个高速缓存行。每行有一个 $$B=2^b$$ 字节的数据块组成。一个有效位指明这个行是否包含有意义的信息，还有 t=m-(b+s)​ 个标记位唯一的标识存储在这个高速缓存中的块。

一般而言，高速缓存的结构可以用元组 (S,E,B,m) 来描述，高速缓存的大小（或者容量）C指的是所有块大小的和，标记为和有效位并不包括在内，所以 C=SxExB。

那么高速缓存是如何工作的呢？

还是感觉书上说的很难懂

如上图 (b) ，我们的一个完整的内存地址共有 m 位，这 m 位被分为三个字段，分别是：组索引位（s位）、标记位（t位）和块偏移位（b位）。

• 组索引位（s位）：组索引位用于确定数据应该存储在哪个组（group）中。这里有S个组，索引值从 0 开始编号，每个组包含多个缓存行。
• 标记位（t位）：标记位用于确定每个缓存行的内容是否与访问的地址所需数据匹配。如果缓存行中存储的数据与访问的数据相匹配，并且有效位被设置，则表示命中了缓存。
• 块偏移位（b位）：块偏移位用于确定缓存行中的哪个字节存储了需要的数据，因为每个缓存行大小为B字节。

当 CPU 请求数据时，地址被分解为组索引、标记和块偏移位。首先使用组索引位找到对应的组，然后在该组中查找标记位匹配的缓存行，如果找到匹配的行并且有效位被设置，则表示缓存命中，CPU可以直接从缓存中获取数据。

直接映射高速缓存

根据每个组的高速缓存行数 E ，高速缓存被分为不同的类。其中每一组只有一行的高速缓存称为直接映射高速缓存。

高速缓存确定一个请求是否命中，然后抽取出被请求的字的过程分为三步：1）组选择、2）行匹配、3）字抽取

组选择

组选择先屏蔽掉低 b 位的块偏移之后，取得低 s 位，这个数值就是组号。如果我们把高速缓存看作是一个关于组的一维数组，那么这些组的索引位就是这个对应在数组的索引。

行匹配

取得高 t 位，只有这一位和标记位完全对应上才说明 cache 行里面装的是我们想要的数据。

字选择

一旦前两个步骤命中，我们就可以根据块偏移来确定字的位置了

行匹配和字选择的流程如下图：

不命中时的行替换

如果缓存不命中，那么它需要从存储器体系结构中的下一层取出被请求的块，然后将新的块存储在组索引位指示的组中的一个高速缓存行中。对于直接映射高速缓存来说，每个组只包含有一行，替换策略非常简单：用新取出的行替换当前的行。

运行中的直接映射高速缓存

假设我们有一个直接映射高速缓存，(S,E,B,m)=(4,1,2,4)，高速缓存有 4 个组，每个组一行，每个块 2 个字节，而地址是4 位的。

我们这里用列表来模拟高速缓存，可以将所有的地址都列出来：

在最开始的时候，高速缓存都是空的：

组	有效位	标记位	块[0]	块[1]
0	0
1	0
2	0
3	0

”组“这一列不是高速缓存的一部分，后四列才是高速缓存实际的位

CPU 在执行读操作时，会发生以下几个步骤：

读地址 0 的字：

组 0 的有效位为 0 ，缓存不命中，执行替换策略。高速缓存从内存中取出块 0 ，并把这个块存储在组 0 中。然后高速缓存新去除的块的 m[0] 。

组	有效位	标记位	块[0]	块[1]
0	1	0	m[0]	m[1]
1	0
2	0
3	0

读地址 1 的字：

高速缓存命中，立即从高速缓存行中的块[1]中返回 m[1] 。高速缓存的状态没有变化。

读地址 13 的字：

读地址 13 的字，找到组 2，有效位为 0，执行替换策略。

组	有效位	标记位	块[0]	块[1]
0	1	0	m[0]	m[1]
1	0
2	1	1	m[12]	m[13]
3	0

读地址 8 的字

读地址 8 的字，找到组 0，有效位为 1，标记位没有对上，发生不命中，执行替换策略。

组	有效位	标记位	块[0]	块[1]
0	1	1	m[8]	m[9]
1	0
2	1	1	m[12]	m[13]
3	0

读地址 0 的字：

缓存不命中，因为我们前面替换了块 0 。

组	有效位	标记位	块[0]	块[1]
0	1	0	m[0]	m[1]
1	0
2	0		m[12]	m[13]
3	0

冲突不命中

在直接映射高速缓存中，同一组的不同行多次被反复访问，会导致直接映射高速缓存一直不命中（因为只有一行，每次都需要替换）。例如：

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

这个程序看起来是具有很好的局部性的，但事实上有可能 x[i] 与 y[i] 的组号永远相同。

假设 cache 行的行长为 4，x 数组与 y 数组地址紧邻，那么就会出现这种情况：

循环的第一次迭代引用 x[0]，缓存不命中会导致包含 x[0]x[3] 的块被加载到组 0。接下来是对 y[0] 的引用，又一次缓存不命中，导致包含 y[0]y[3]的块被复制到组 0，覆盖前一次引用复制进来的 x 的值。现在我们有一个冲突不命中，而且实际上后面每次对 x 和 y的引用都会导致冲突不命中，这种情况我们叫抖动，因为每次循环，它一直在 x 和 y 之间来回访问。

我们的修正思路也很容易，只需要在 x 数组之后填充上 B 个字节（例如把 float[8] 定义为 float[12] ），让它们映射到不同组当中即可解决问题。

索引位在中间位的原因

高位做索引的话，一些连续的内存块就会映射到相同的高速缓存快。而相比较而言，相邻的快总是映射到不同的高速缓存中。而中间位索引的命中率相较高位索引也要高得多。

组相联高速缓存

直接映射高速缓存中冲突不命中造成的问题源于每个组只有一行，组相联高速缓存（set associative cache）放松了这条限制，所以每个组都保存有多于一个的高速缓存行。一个1<E<C/B 的高速缓存通常称为 E 路组相联高速缓存。

如下图是 E=2 的组相联高速缓存：

组选择

和直接映射高速缓存组一样

行匹配和字选择

行匹配需要检查多个行的有效位和标记位。

相联存储器是一个 (key,value) 对的数组，以 key 为输入，返回与输入的 key 相匹配的 (key,value) 对中的 value 值。因此我们可以把组相联高速缓存中的每个组都看成一个小的相联存储器，key 是标记和有效位，而 value 就是块的内容。

不命中时的行替换

因为组相联高速缓存中一组有很多行，我们就需要用一定的替换策略来决定替换的行：

最简单的替换策略就是随机选择一行，其他更复杂的策略利用了局部性原理，以使在比较近的将来引用被替换的行的概率最小。

• 最不常使用（Least-Frequently-Used，LFU）策略：会替换在过去某个时间窗口内引用次数最少的那一行（适用于空间局部性较高的程序）。
• 最近最少使用（Least-Recently-Used，LRU）策略：会替换最后一次访问时间最久远的那一行（适用于时间局部性较高的程序）。

所有这些策略都需要额外的时间和硬件。但是，越往存储器体系结构下面走，远离CPU，一次不命中的开销就会更加昂贵，用更好的替换策略使得不命中最少也变得更加值得了。

全相联高速缓存

全相联高速缓存是有一个包含所有高速缓存行的组（也就是 E=C/B）组成的。如下：

组选择

因为全相联高速缓存只有一个组，所以对应的地址中是没有组索引位的，我们默认就是组 0 。

行匹配和字选择

和其他的一样）

因为高速缓存电路必须并行地搜索许多相匹配的标记，构造一个又大又快的相联高速缓存很困难，而且很昂贵。因此，全相联高速缓存只适合做小的高速缓存。

有关写的问题

前面我们都在学习读的操作，写的情况比读要复杂的多。

假设我们要写一个已经缓存了的字 w（写命中，write hit）。在高速缓存更新了它的 w 的副本之后，怎么更新 w 在层次结构中紧接着低一层中的副本呢？

• 直写（write-through），就是立即将 w 的高速缓存块写回到紧接着的低一层中。

  直写的缺点是每次写都会引起总线流量。

• 写回（write-back），尽可能地推迟更新，只有当替换算法要驱逐这个更新过的块时，才把它写到紧接着的低一层中。

  由于局部性，写回能显著地减少总线流量，但是它的缺点是增加了复杂性。高速缓存必须为每个高速缓存行维护一个额外的修改位（dirty bit），表明这个高速缓存块是否被修改过。

对于不命中也有相应的解决方案：

• 写分配（write-allocate），加载相应的低一层中的块到高速缓存中，然后更新这个高速缓存块。

  写分配试图利用写的空间局部性，但是缺点是每次不命中都会导致一个块从低一层传送到高速缓存。

• 非写分配（not-write-allocate），避开高速缓存，直接把这个字写到低一层中。

直写高速缓存通常是非写分配的，写回高速缓存通常是写分配的。

实际的高速缓存

我们一直假设高速缓存只保存数据，实际上高速缓存及保存数据，也保存指令。只保存指令的高速缓存，称为 i-cache，而只保存数据的称为 d-cache，既保存数据又保存指令的高速缓存叫统一高速缓存 unified cache 。

高速缓存的性能影响

有许多指标来衡量高速缓存的性能：

• 不命中率（miss rate）。在一个程序执行或程序的一部分执行期间，内存引用不命中的比率。它是这样计算的：不命中数量/引用数量。
• 命中率（hit rate）。命中的内存引用比率。它等于 1-不命中率。
• 命中时间（hit time）。从高速缓存传送一个字到CPU所需的时间，包括组选择、行确认和字选择的时间。对于L1高速缓存来说，命中时间的数量级是几个时钟周期。
• 不命中处罚（miss penalty）。由于不命中所需要的额外的时间。L1不命中需要从L2得到服务的处罚，通常是数10个周期；从L3得到服务的处罚，50个周期；从主存得到的服务的处罚，200个周期。

高速缓存大小的影响

一方面，较大的高速缓存可能会提高命中率。另一方面，使大存储器运行得更快总是要难一些的。较大的高速缓存可能会增加命中时间，所以我们才会有 L1、L2 、L3 的高速缓存自小到大的顺序。

块大小的影响

大的块有利有弊，较大的块能更高地利用空间局部性，帮助提高命中率。但是可能对时间局部性利用不足，增加命中时间。

相联度的影响

较高的相联度（也就是E的值较大）的优点是降低了高速缓存由于冲突不命中出现抖动的可能性，不过较高的相联度会造成较高的成本。

写策略的影响

一般来说，高速缓存越往下层，越是采取写回的方式而不是直接写。

编写高速缓存友好的代码

• 步长为 1 的代码可以在循环体内部，尽量减少缓存的不命中率。

• 对局部变量反复引用，因为反复引用的局部变量编译器会考虑放在寄存器当中。

---

我闺闺的一个比赛

好玩好玩，和养成游戏一样！！🥳

什么时候 CTF 也可以做成这个样子

总经理办公室比其他房间都大，我闺闺是万恶的大资本家！