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 和主存映射方式

直接映射

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

假设主存块的数量为 N，cache 块的数量为 M。那么第 k 个主存块对应的cache 块号为 k % M。

假设我们有一个 256KB 的缓存，其中每个缓存块是 64B，对于直接映射的 cache：

• 缓存 被分为 256KB / 64B = 4096 个 缓存块。
• 内存 中的数据可以直接映射到这 4096 个位置中的其中一个，比如第 10000 个 主存块 映射到 10000 % 4096 = 1808 个 缓存块。
• 当一个新的数据块需要被加载时，它会替换掉当前映射到该位置的数据块，不管缓存的其他位置是否为空。

全相联映射

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

假设我们有一个 256KB 的缓存，其中每个缓存块是 64B，对于全相联映射的 cache：

• 缓存被分为 256KB / 64B = 4096 个 缓存块。
• 全相联缓存中的每个主存块可以放置在任何缓存块中，即第 0 到第 4095 个缓存块都可以存储该主存块。
• 当缓存满时，基于某种 替换策略 替换掉 4096 个 缓存块 中的某一个。

组相联映射

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

当我们说一个缓存是 N 路组相连 的，意味着缓存被分为多个 组，每个 组 有 N 个 缓存块（N 路）。这样，当一个内存地址被映射到一个特定的 组 时，它可以放在该 组 的任何一个 缓冲块（一路）上。如果一个 组 是满的，新的数据会根据某种 替换策略 来替换组中的一个 缓存块。

假设我们有一个 256KB 的 缓存，其中每个 缓存块 是 64B，我们希望有 4 路组相联的组织。

• 这意味着 缓存 被分为 256KB / 64B = 4096 个 缓存块。
• 因为是 4 路组相联，所以这些块被进一步组织为 4096 / 4 = 1024 个 组。
• 每个 组 包含 4 个位置（即 4 路），任何内存地址映射到这个 组 的时候，可以放在这四个位置中的任何一个。
• 比如第 10000 个 主存块 位于第 10000 % 1024 = 784 个 组，可能对应组内的任何一个 缓存块。

硬件结构

下图展示的是一个 二路组相联 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 块 所缓存，并且检查所有可能的 cache 块 的 tag 字段以判断是否被缓存，所以 cache 地址 的结构从逻辑上可以分为如下部分：

• 标记（tag）：判断当前地址是否命中对应的 cache 块
• cache 块匹配字段：通过该字段判断 主存块 可能被哪些 cache 块 缓存
  • 对于 直接映射 为块号（cache block number）：位数为 $log_2{(\text{\small cache 块数量})}$
  • 对于 全相联映射 为空，因为每一个 主存块 都可能被任何一个 cache 块 所缓存
  • 对于 组相联映射 为组号（group number）：位数为 $log_2{(\text{组数})}$
• 块内地址（block offset）：物理地址在 主存块 内的偏移

总结三种不同映射方式的地址结构如下：

cache 存储结构

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

其中字段的含义与页表近似：

• 有效位（valid）：
  • 该 cache 行 是否存储有缓存数据，位数为 1 位。
• 标记（tag）：
  • 根据物理地址中的 tag 字段与该字段匹配，以判断是否命中，位数按照 cache 地址结构 进行计算。
• 脏位（dirty）：
  • 标记该 cache 是否修改过，与 写策略 相关。
    • 如果采用 直写法，则无需设置 脏位。
    • 如果采用 回写法，设置 1 位 脏位。
  • 该字段也常被称为 修改位。
• 访问位（reference）：
  • 用于记录访问信息，服务于 块替换算法，其位数取决于替换算法。
  • 如果采用 LRU 替换算法，则 脏位 的位数为 $log_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）通常会一起使用，适用于那些写操作频繁的情况。