Cache

cache 原理

cache 工作原理

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

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

1. 时间局部性：
   • 如果一个数据项被访问，那么它在不久的将来很可能再次被访问。
   • 这种特性常见于循环结构和频繁访问的变量，例如循环中的计数器或者经常读取的配置值。
   • 在缓存设计中，利用时间局部性意味着一旦数据被加载到缓存中，它应该在那里保留一段时间，因为很可能很快会再次需要它。
2. 空间局部性：
   • 如果一个数据项被访问，那么存储在其附近的数据项也很可能在不久的将来被访问。
   • 这种特性在数组遍历或结构体访问时尤为明显，因为这些数据元素通常在内存中是连续存储的。
   • 利用空间局部性的缓存设计会在访问一个数据项时，同时把它附近的数据也加载到缓存中，因为这些数据很可能在接下来的操作中被用到。

cache 概念

• 缓存块（cache 块）：cache 中的一块存储空间
• 主存块：主存中的一块存储空闲，主存块的大小一般与 cache 块一致
• 块内偏移：某一个地址在块内的偏移，找到对应的块后，通过块内偏移找到改地址的具体位置
• 块大小：用于判断块内偏移的位数，比如$1024 = 2^{10}$，所以 1KB 的块对应的块内偏移位数为 10

缓存块

什么是缓存块？

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

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

缓存块的大小？

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

cache block 的大小在题目中一般会给你。

cache 和主存映射方式

1. 直接映射

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

例子

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

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

2. 全相联映射

在全相联缓存（full associative）中，主存中的任何块可以映射到缓存中的任何缓存块。这意味着主存块的地址没有限制，可以映射到任何可用的缓存块。

例子

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

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

3. 组相联映射

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

N 路组相联

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

例子

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

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

cache 地址结构

当给定一个物理地址时，需要判断该地址对应的主存块可能被哪些 cache 块所缓存，并且检查所有可能的 cache 块的 tag 字段以判断是否被缓存，所以 cache 地址的结构从逻辑上可以分为如下部分：

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

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

cache 存储结构

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

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

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

cache 中的块替换算法

块替换算法适用于全相联映射和组相联映射，因为一个主存块可能被多个cache块中的某一个 所缓存，查询和替换过程如下：

• 根据 cache 块匹配字段找到所有可能缓存 该物理地址对应主存块 的 cache 块
• 遍历所有可能缓存该主存块的cache块
  • 如果cache块的有效位为0，则替换该cache块，将主存块加载进来，并将有效位设置为1，停止遍历
  • 如果cache块的tag字段与物理地址的tag字段相匹配，则表示该次地址查询命中cache，停止遍历
• 如果遍历完所有cache块都无法满足如上条件时，则根据块替换算法选择一个cache块进行替换

当我们访问一个物理地址时未命中时，需要将对应的主存块加载到 cache 中，如果这个该主存块对应的 cache 块都满了的话，就需要替换掉其中的某个 cache 块，替换算法包含如下种类：

• LRU
• FIFO
• 随机算法
• LFU

这里的具体思想与操作系统中的页面置换算法一致，请参考页面置换算法

cache 写策略

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

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

• write-through（全写法）：每次写操作都会同时更新缓存和主存。
• write-back（回写法）：当数据被修改时，它首先被缓存在 cache 中，只有当 cache 块被替换时才写入对应的主存块。

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

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

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

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

不同映射方式对比

视频讲解