Cache

cache 原理

缓存 是一种临时存储数据的硬件或软件组件，旨在加快后续对该数据的访问速度。当您请求数据时，计算机会先检查 缓存 中是否存在该数据。如果存在（称为 “缓存命中”，Cache Hit），则可以直接从 缓存 中获取数据，而无需访问内存，从而节省时间和资源。如果 缓存 中不存在该数据（称为 “缓存未命中”，Cache Miss），则需要从内存获取数据，并将其存储在 缓存 中，以备将来使用。

cache 工作原理

缓存（cache）是计算机系统中的一种用于加速数据访问的技术，其原理是在高速存储介质中暂时存储常用数据，以便更快地满足后续的访问请求。

缓存 对于程序执行的加速主要来自于 计算机程序 的 时间局部性（Temperal Locality）和 空间局部性（Spatial Locality）：

时间局部性

时间局部性指的就是 “刚刚用过的数据，很可能很快又会被用到。

这种特性常见于 循环结构和频繁访问的变量，例如循环中的计数器或者经常读取的配置值：

int sum = 0;
int arr[1000];

// 初始化数组
// ....
// 访问同一个变量 i 很多次
for (int i = 0; i < 1000; i++) {
    sum += arr[i];   // 访问 arr[i]
    sum += arr[i];   // 再次访问 arr[i]
}

在 缓存 设计中，利用 时间局部性 意味着一旦数据被加载到 缓存 中，它应该在那里保留一段时间，因为很可能很快会再次需要它。

空间局部性

如果一个数据项被访问，那么存储在其附近的数据项也很可能在不久的将来被访问。

这种特性在数组遍历或结构体访问时尤为明显，因为这些数据元素通常在内存中是连续存储的。

利用 空间局部性 的 缓存 设计会在访问一个数据项时，同时把它附近的数据也加载到 缓存 中，因为这些数据很可能在接下来的操作中被用到。

cache 概念

• cache 行（cache line）：cache 行 中包含 各种标记字段（flag）和 数据（cache 块）
• 缓存块（cache 块）：cache 中的一块存储空间，是与 主存 进行数据交换的基本单元
• 主存块：主存 中的一块存储空间，主存块 的大小一般与 cache 块 一致
• 块内偏移：某一个地址在块内的偏移，找到对应的块后，通过块内偏移找到该地址的具体位置
• 块大小：用于判断块内偏移的位数，比如 $1024=2^{10}$ ，所以 1KB 的块对应的块内偏移位数为 10

缓存块

Cache block（缓存块），是计算机系统中用于存储的最小数据单元，它是 缓存 中的一个固定大小的数据块。每个 缓存块 包含一定数量的字节或字（通常是 2 的幂次方个字节），并用于存储从 主存（或更低级别的 缓存）中加载的数据。

cache block 的目的是为了方便对于 主存（main memory）数据的 缓存，主存块 的大小与 缓存块 大小一致，这样就可以将 缓存块 和 主存块 对应起来。

cache 中的存储空间可以被分为若干个 cache 块，主存 也可以被分为若干个 主存块，主存 和 cache 间的数据置换是以 块 为基本单位的。
这可以和页式内存进行类比，虚拟内存和物理内存都被分为若干个页面，物理内存空间的置换以 页面 为基本单位。

缓存块的大小？

Cache block 的大小在不同计算机体系结构中可以有所不同，通常以字节（bytes）或字（words）为单位来表示。典型的 缓存块 大小可以是 32 字节、64 字节、128 字节等。较大的 缓存块 可以容纳更多的数据，提高了数据的局部性，但在某些情况下，较小的 缓存块 可能更适合，特别是对于小规模的数据访问。

cache 和主存映射方式

Cache 的容量远小于主存，而主存中的任意一个数据块在程序运行过程中，都有可能被调入 Cache。 因此，体系结构必须回答一个核心问题：

当某个主存块需要进入 Cache 时，它可以（或应该）放到 Cache 的哪个位置？

这个从 主存块 → Cache 块 的对应规则，就称为 映射方式（Mapping）。

从抽象角度看，映射本质上定义了三件事：

1. 可放置性：
   一个主存块，允许放入 Cache 的哪些位置？
2. 唯一性或灵活性：
   是只能放到一个固定位置，还是可以放到多个位置，甚至任意位置？
3. 硬件代价与性能权衡：
   放得越自由，命中率越高，但查找与比较逻辑越复杂； 放得越受限，硬件越简单，但冲突失效（conflict miss）越频繁。

不同的映射方式，本质上就是在 命中率、访问速度、硬件复杂度 三者之间做不同取舍。

按照“一个主存块能映射到多少个 Cache 块”这一自由度的不同，常见的映射方式可以分为：

• 直接映射（Direct Mapped）：只能映射到 唯一一个 Cache 块
• 全相联映射（Fully Associative）：可以映射到 任意一个 Cache 块
• 组相联映射（Set Associative）：只能映射到 某一组中的任意一个 Cache 块

下面我们从最简单、硬件代价最低的直接映射开始分析。

直接映射

在 直接映射（directed mapped）缓存 中，每个 主存块 只能映射到缓存中的 一个特定缓存块。这意味着每个 主存块只有一个缓存块可以存储它。

主存块号 $k$ 映射到缓存块号的计算公式为：

其中：

• $k$ 为主存块号（从 0 开始编号），
• $M$ 为缓存中的总块数。

全相联映射

在 全相联缓存（full associative）中，主存 中的任何块可以映射到缓存中的 任意缓存块。

其映射关系可表示为：

或更形式化地描述为：

其中 $C$ 为缓存总行数。

由于这种映射关系不是唯一的，而是任意的，所以在根据物理地址去访问 cache 的时候，需要通过 遍历所有 cache 行 来判断是否命中。

如果 cache 的所有行都是满的，新的数据会根据某种 替换策略 来替换 cache 中的某一个 cache 块。

组相联映射

组相联缓存（set associative 或 group associative）是 直接映射缓存 和 全相联缓存 之间的一种 折中方案。它将缓存块分为多个 组，每个组包含多个缓存块。主存块可以 映射到组中的任意一个缓存块。

当我们说一个缓存是 N 路组相连 的，意味着缓存被分为多个 组，每个 组 有 N 个 缓存块（N 路）。这样，当一个内存地址被映射到一个特定的组时，它可以放在该 组的任何一个缓冲块（一路）上。

如果一个组是满的，新的数据会根据某种 替换策略 来替换组中的一个 缓存块。

组相联映射中，主存块地址到缓存组索引的计算公式为：

其中：

• 缓存总块数 $=\text{组数}\times \text{路数}$
• $N$ 表示 $N$ 路组相联

硬件结构

下图展示的是一个 二路组相联 Cache 的结构示意图。

访问时，物理地址中的 组号（index） 用于定位到 Cache 中的某一 组。该 组 包含两个 Cache 块，每个块有 valid 位 和 tag 字段。

地址中的 tag 会同时送入两个 比较器，分别与组内两个块的 tag 进行匹配，并结合 valid 位 判断是否命中。

如果命中，选择器（multiplexer）根据比较结果，从两个块中选出正确的数据输出给处理器。若都未命中，则访问 主存。

• 比较器（Comparator）：用于判断 Cache 块 中的 tag 是否与当前地址匹配，决定是否命中；
• 选择器（Multiplexer）：在多个块中有可能命中的情况下，负责根据比较结果选出正确的数据路径。

映射方式对比

假设 cache 有 M 个 cache 块，对于块号为 k 的 主存块：

• 直接映射：被映射到块号 k % M 的 cache 块
• 全相连映射：可能被映射到任意一个 cache 块
• 组相连映射：对于 m 路组相连，被映射到组号为 k % (M / m) 的 cache 组 中的任意一个 cache 块

关联度

Cache 关联度（associativity）描述的是一块 主存地址 可以被映射到 缓存 中多少个不同的位置（cache lines）。

根据上面提及的 映射方式对比 可知关联度对比：

全相联 > 组相联 > 直接映射

更高的关联度意味着 缓存冲突 减少，命中率 提高。但是另一方面，硬件开销（比较器、替换策略复杂度）和访问延迟增加。所以关联度选择需权衡性能与成本。

cache 地址结构

当给定一个 物理地址 时，Cache 的访问过程可以抽象为三个连续的问题：

1. 这个地址属于主存中的哪一个块？
2. 这个主存块在 Cache 中可能出现在哪些位置？
3. 这些位置中是否真的缓存了该主存块？

逻辑划分

因此，从 “硬件判定流程” 的角度，物理地址在逻辑上可划分为以下三部分：

块内地址

• 作用： 确定访问数据在一个 主存块 / cache 块 内的具体偏移
• 位数： ${\log }_2(\text{块大小})$
• 说明： 这一部分 只用于块内寻址，与映射方式无关

Cache 块匹配字段

• 作用： 用于 缩小搜索范围，确定该主存块可能被缓存在哪些 cache 块中
• 含义因映射方式而异：

• 字段含义：Cache 块号（Cache Block Index）
• 作用： 一个主存块 只能映射到唯一的一个 cache 块
• 位数： ${\log }_2(\text{cache 块数})$

• 字段含义：无
• 作用： 一个主存块 可能被缓存到任意一个 cache 块
• 位数： $0$
• 说明： 必须 并行比较所有 cache 块的 tag

• 字段含义：组号（Set Index）
• 作用： 一个主存块 只能映射到某一组内的若干 cache 块
• 位数： ${\log }_2(\text{组数})$

总结一下三种映射方式的块匹配字段的计算方法：

标记

• 作用： 在已确定的候选 cache 块（或某一组）中， 通过比较 tag 判断是否真正命中
• 位数：

物理地址对应

具体而言，给定一个物理地址，访问 Cache 时的各个字段的对应方式如下图所示：

其中 块内偏移、cache 块号（直接映射）、cache 组号（组相联映射）的位数可以直接根据 cache 的参数计算出来，Tag 字段的位数需要通过物理地址的位数减去其他字段的位数来得到。

cache 存储结构

cache 存储的内容大体上来说可以分为 数据 和 元数据 这两个部分：

• 数据部分：即 cache 块（cache block），缓存了某个主存块的内容
• 元数据部分：对 cache 访问的过程进行控制

cache 的存储结构可以理解为一张表：

其中字段的含义与 页表 近似，下面列出了：

• 有效位（valid）：
  • 该 cache 行 是否存储有缓存数据，位数为 1 位。
• 标记（tag）：
  • 根据物理地址中的 tag 字段与该字段匹配，以判断是否命中，位数按照 cache 地址结构 进行计算。
• 脏位（dirty）：
  • 标记该 cache 是否修改过，与 写策略 相关。
    • 如果采用 直写法，则无需设置 脏位。
    • 如果采用 回写法，设置 1 位 脏位。
  • 该字段也常被称为 修改位。
• 访问位（reference）：
  • 用于记录访问信息，服务于 块替换算法，其位数取决于替换算法。
  • 如果采用 LRU 替换算法，则 访问位 的位数为 $lo{g}_2(\text{主存快对应的缓存块数量})$ 。
• 数据块（block）：
  • 缓存的数据块，为 主存块 的一个副本。

cache 中的块替换算法

块替换算法适用于 全相联映射 和 组相联映射，因为在这两种组织方式中，同一主存块可能被 多个 cache 块 中的任意一个所缓存；因此当需要把新块写入时必须决定把哪一个已有的 cache 块淘汰。而在 直接映射方式 中，主存块只能对应唯一的 一个 cache 块，如果发生冲突，直接用新块覆盖该 cache 块即可，无需额外的替换算法。

替换过程

cache 块替换的基本过程（以全相联或组相联为例）：

1. 定位可能的候选块
   根据 cache 块匹配字段（即组相联中的组号或全相联中的全部块），找出所有可能缓存该物理地址对应的主存块的 cache 块。
2. 遍历候选块
   对每个候选块执行以下检查：
   • 有效位为 0：如果发现该块的有效位为 0，说明它是空闲的。此时直接把主存块加载进来，设置有效位为 1，更新tag，停止遍历（命中空闲块）。
   • tag 匹配：如果块的tag与物理地址的tag相同，说明该块已经缓存了目标主存块，命中 cache，停止遍历。
3. 需要替换时的处理
   若遍历完所有候选块后既没有找到空闲块，也没有出现 tag 匹配，则必须按照 块替换算法（如 LRU、FIFO、随机等）选择其中 一个 cache 块 进行淘汰，然后把新主存块写入该块，更新 有效位 与 tag。

flowchart TD
    A[CPU访问物理地址] --> B{在cache中命中吗？}
    B -- 是 --> C[访问cache，完成操作]
    B -- 否 --> D[找到所有候选cache块]
    D --> E{是否存在有效位为0的空闲块？}
    E -- 是 --> F[将主存块加载到空闲块，设置有效位为1，更新tag]
    F --> G[完成操作]
    E -- 否 --> H{是否有tag匹配块？}
    H -- 是 --> I[命中cache，访问cache]
    I --> G
    H -- 否 --> J[按替换算法选择一个cache块进行淘汰]
    J --> K[将新主存块写入被淘汰块，更新有效位和tag]
    K --> G

当 CPU 访问某个物理地址而在 cache 中未命中时，需要把该地址所在的 主存块 调入 cache。如果该 主存块 映射到的 cache 块（即同一路径或同一个集合）已经全部占满，就必须在这些已占用的 cache 块 中挑选一个进行替换。常用的替换策略有 FIFO（先进先出）、LRU（最近最少使用）和 LFU（最不经常使用）等。

这套思路与操作系统中的页面置换算法本质相同，详情请参见 页面置换算法。

cache 写策略

因为 cache 实际上存储的是主存的一个小副本，所以对于写操作，就需要考虑两者间的数据一致性的问题。

cache 的写策略代表当我们对某个物理地址上的数据进行写入时，应该如何写入对应的存储单元，以及如何协调 cache 和 主存之间的 数据一致性，写策略按照地址查询是否命中 cache 可以分为四种方式。

命中时

如果某次地址查询命中 cache，可以使用如下策略：

• 直写法 （Write Through）：
  • 每次写操作都会同时更新缓存和主存。
  • 这种写策略是 同步的，每次更新 缓存 时要同步地更新 主存。
• 回写法 （Write Back）：
  • 当数据被修改时，它首先被缓存在 cache 中，只有当 cache 块被替换时才写入对应的主存块。
  • 这种写策略是异步的，并不是写入 cache 后立马就要写入主存，可以多次写入 cache 后在另一个时刻再将cache 块写入主存。

未命中时

如果 没有命中 cache，也有如下策略：

• 写分配法 （Write Allocate）：
  • 物理地址对应主存块被 加载 到 cache 块中（先执行一次对应主存块的读操作），然后更新 cache 块
• 非写分配法 （Not Write Allocate）：
  • 不加载 主存块至 cache 中，直接更新主存块，只有当执行读操作时才将主存块加载进入 cache 块

策略的组合

命中 和 未命中 的方法常常通过如下方式一起使用：

• 直写法（write-through）和 非写分配法（not-write-allocate）通常会一起使用，适用于那些写操作不频繁或者写操作不太可能访问同一数据的情况。
• 回写法（write-back）和 写分配法（write-allocate）通常会一起使用，适用于那些写操作频繁的情况。