Cache

cache 原理

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

cache 工作原理

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

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

1. 时间局部性：

如果一个数据项被访问，那么它在不久的将来很可能再次被访问。

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

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

2. 空间局部性：

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

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

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

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 block 的大小在题目中一般会给你。

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个组，可能对应组内的任何一个缓存块。

上图是一个二路组相连的硬件结构概要图，通过物理地址中的组号（index）找当 cache 中的相应组。然后再用标记字段（tag）去与组中每个 cache 块进行匹配，并检查 valid 字段是否设置为 1，如果符合以上条件的话则通过二路选择器输出 cache 块中的内容。

对比

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 的存储结构可以理解为一张表：

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

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

cache 中的块替换算法

块替换算法适用于全相联映射和组相联映射，因为一个主存块可能被多个 cache 块中的某一个 所缓存。但是在直接映射方式中不存在替换算法，因为一个主存块只可能被一个 cache 块所缓存，如果需要替换的话直接替换对应的 cache 块就行。

cache 块替换的过程如下：

• 根据 cache 块匹配字段找到所有可能缓存 该物理地址对应主存块 的 cache 块
• 遍历所有可能缓存该主存块的 cache 块
  • 如果 cache 块的有效位为 0，则替换该 cache 块，将主存块加载进来，并将有效位设置为 1，停止遍历
  • 如果 cache 块的 tag 字段与物理地址的 tag 字段相匹配，则表示该次地址查询命中 cache，停止遍历
• 如果遍历完所有 cache 块都无法满足如上条件时，则根据块替换算法选择一个 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）通常会一起使用，适用于那些写操作频繁的情况。

不同映射方式对比