# Cache 的基本思路

存储器层次结构

解决内存墙带来的 CPU 和主存协作问题

在使用主存（相对大而慢）之余，添加一块小而快的 cache

Cache 位于 CPU 和主存之间，可以集成在 CPU 内部或作为主板上的一个模块

Cache 中存放了主存中的部分信息的 “副本”

# Cache 的工作流程

主存中的一个块对应着 Cache 中的一个行

检查（Check）：当 CPU 试图访问主存中的某个字时，首先检查这个字是否在 cache 中

检查后分两种情况处理：

命中（Hit）：如果在 cache 中，则把这个字传送给 CPU

未命中（Miss）：如果不在 cache 中，则将主存中包含这个字固定大小的块（block）读入 cache 中，然后再从 cache 传送该字给 CPU

# 命中和未命中的判断

Cache 通过标记（tags）来标识其内容在主存中的对应位置

# 程序访问的局部性原理

类型：

时间局部性：在相对较短的时间周期内，重复访问特定的信息（也就是问相同存储位置的信息）

空间局部性：在相对较短的时间周期内，访问相邻存储位置的数据

顺序局部性：当数据被线性排列和访问时，出现的空间局部性的一种特殊情况（比如访问一维数组中的元素）

# 向 Cache 传送内容

利用 “时间局部性”

将未命中的数据在返回给 CPU 的同时存放在 Cache 中，以便再次访问时命中

# 传送块而不是传送字

利用 “空间局部性”

将包含所访问的字的块存储到 Cache 中，以便在访问相邻数据时命中

# 平均访问时间

# Cache 未命中原因

# 义务失效（Compulsory Miss）/ 冷启动失效（Cold Start Miss）

第一次访问一个块时

# 容量失效 （Capacity Miss）

Cache 无法保存程序访问所需的所有数据块，则当某数据块被替换后，又重新被访问，则发生失效

# 冲突失效（Conflict Miss）

多个存储器位置映射到同一 Cache 位置

# Cache 的设计要素

# 映射功能（Mapping Function）

# 直接映射

将主存中的每个块映射到一个固定可用的 cache 行中

假设 $i$ 是 cache 行号，$j$ 是主存储器的块号，$c$ 是 cache 的行数

$ i = j $ $mod$ $c$

# （块）标记

假设 cache 有 4 行，每行包含 8 个字；主存中包含 128 个字。访问主存的地址长度为 7 位，则：

• 最低的 3 位：块内地址

• 中间的 2 位：映射时所对应的 Cache 行号

• 最高的 2 位：区分映射到同一行的不同块，记录为 Cache 标记（一行分配 4 个块，共四行 16 个块）

标记代表了你是这一行 / 组的第几个块，通过标记判断是否命中。

tag = j /c （块号整除以行数）（组相联那就除以组数）

• gpt 的解释

  在计算机体系结构中，** 缓存（cache）** 是一种用于加速数据访问的小型高速存储器，主要用于减少从主存中读取数据的延迟。直接映射（Direct Mapping）是缓存中一种简单且常用的映射机制。它将主存中的每一个内存块映射到缓存中唯一的一个缓存行位置。这种固定的映射关系使得直接映射缓存的实现简单且高效。

  # 1. 直接映射的原理

  在直接映射缓存中，主存中的每一个块都可以映射到缓存中的一个固定位置。假设有一块主存和一个较小的缓存，主存中的每个块会根据其地址被映射到缓存中的一个特定行。具体映射方法如下：

  [缓存行号 = （内存块地址） \bmod （缓存行数）]

  # 2. 地址分解

  为了确定主存中的地址应该映射到缓存的哪个位置，内存地址通常会分为以下三部分：

  • 标记位（Tag）： 用于标识数据块的唯一性，确保找到的数据块是正确的。

  • 索引位（Index）： 用于指定数据在缓存中的行位置。

  • 块内偏移（Block Offset）： 用于找到数据块内的具体字节。

  通过这种分解，缓存可以快速判断主存地址是否在缓存中。

  # 3. 直接映射的优缺点

  • 优点： 实现简单，访问速度快，开销小。

  • 缺点： 由于每个内存块都只能映射到缓存中的一个位置，可能会出现冲突导致频繁的缓存替换（Cache Miss）。例如，当多个内存块被映射到同一行时，它们会不断替换，从而降低缓存命中率。

  # 4. 例子

  假设有 4 行缓存（行号为 0 到 3），主存块会按照如下方式映射：

  • 主存块 0、4、8... 都映射到缓存行 0

  • 主存块 1、5、9... 都映射到缓存行 1

  • 主存块 2、6、10... 都映射到缓存行 2

  • 主存块 3、7、11... 都映射到缓存行 3

  当访问主存中块 4 的数据时，数据会被加载到缓存行 0。如果接下来访问块 0 或块 8，数据依然在缓存行 0，这可能导致缓存命中失败（Cache Miss）。

  # 总结

  直接映射是一种效率较高的缓存映射方式，适合对实现复杂度要求不高的系统。但由于映射固定，容易产生冲突失效（Conflict Miss），对程序的访问模式敏感。

• 举例

  好，下面我们通过一个简单的例子来说明直接映射缓存的读取数据过程。

  # 假设条件

  1. 主存和缓存参数：

     • 主存有 32 个块（Block），每个块 1 字节。

     • 缓存有 8 行（Cache Lines），每行 1 字节，因此只能缓存 8 个块的数据。

  2. 映射规则：

     • 使用直接映射，即 缓存行号 = （主存块地址）mod（缓存行数） 。

     • 主存地址分为标记位和索引位两部分：

       • 索引位：用来找到缓存行的位置（这里需要 (\log_2 (8) = 3 ) 位）。

       • 标记位：用于区分属于同一个缓存行的不同主存块。

  # 示例

  假设我们需要访问主存地址 12 和 28 ，来看在直接映射缓存中的情况。

  # 步骤 1：访问主存地址 12

  1. 确定索引和标记位：

     • 地址 12 的二进制表示为 1100 。

     • 低 3 位 100 为索引位，对应的是缓存中的第 4 行（ 100 二进制即 4 ）。

     • 剩下的高位 1 是标记位，用来确认数据块来源。

  2. 缓存操作：

     • 如果缓存行 4 里已经存有标记 1 的数据，表示数据命中，可以直接从缓存中读取。

     • 如果缓存行 4 的标记位不同，表示数据不在缓存中（缓存未命中）。此时，需要从主存中加载地址 12 的数据到缓存的第 4 行，并将标记位更新为 1 。

  # 步骤 2：访问主存地址 28

  1. 确定索引和标记位：

     • 地址 28 的二进制表示为 11100 。

     • 低 3 位 100 为索引位，对应的仍然是缓存中的第 4 行。

     • 高位 11 是标记位，用于区分不同的数据块。

  2. 缓存操作：

     • 缓存行 4 目前存的是标记为 1 的数据块（即主存地址 12 的数据）。

     • 因为标记位不匹配（ 1 不等于 11 ），发生冲突未命中（Conflict Miss）。此时，需要将主存地址 28 的数据块加载到缓存行 4 ，并更新标记为 11 。

  # 总结

  在这个例子中，访问主存地址 12 和 28 都映射到了缓存的第 4 行，但由于它们有不同的标记位，在访问 28 时导致了缓存替换。直接映射缓存的这种特性，使得某些相邻的内存块可能频繁发生缓存未命中。

# 关联映射（全相联映射）

一个主存块可以装入 cache 任意一行

示例：

假设 cache 有 4 行，每行包含 8 个字；主存中包含 128 个字。访问主存的地址长度为 7 位，则：

最低的 3 位：块内地址（1 个块里 8 个字）

最高的 4 位：块号，记录为 Cache 标记 （16 个块，随机放到行中）

• gpt 的解释

  全相联映射（Fully Associative Mapping）是一种缓存映射机制，与直接映射不同，它不限制每个主存块固定映射到特定缓存行，而是允许主存中的任意块加载到缓存的任何行。这种灵活的映射方式消除了缓存行冲突，能够更有效地利用缓存空间，但也需要更复杂的查找机制。

  # 全相联映射的基本原理

  在全相联映射中，主存中的任何一个数据块都可以存放在缓存的任意行中。因此，不需要像直接映射那样有固定的缓存行位置，而是通过标记位来判断主存块是否在缓存中。

  • 标记位（Tag）： 唯一标识主存块，和缓存中的每一行比较标记位来判断缓存命中。

  • 块内偏移（Block Offset）： 指定数据块内部的具体字节位置（用于确定具体的字节偏移）。

  # 访问过程

  当处理器需要访问某个内存地址时，全相联映射的访问过程如下：

  1. 从主存地址中提取标记位。

  2. 将这个标记位与缓存中所有行的标记位逐一比较。

     • 如果找到一个匹配的标记位，则表示缓存命中，可以直接从缓存中读取数据。

     • 如果没有找到匹配项，则表示缓存未命中，需要从主存中加载数据到缓存。

  # 缓存替换策略

  因为全相联映射允许任意数据块存放到任意缓存行，所以当缓存已满且需要加载新数据时，必须选择一个缓存行进行替换。常用的替换策略包括：

  • FIFO（先进先出）： 最早进入缓存的块最先被替换。

  • LRU（最近最少使用）： 替换最长时间未被访问的块，适用于大部分程序的访问模式。

  • LFU（最少使用频率）： 替换访问次数最少的块，适用于频繁访问相对固定数据的场景。

  # 优缺点

  优点：

  • 没有缓存行冲突，因为任何数据块可以存放到缓存的任意位置。

  • 在某些访问模式下，命中率可能比直接映射和组相联映射更高。

  缺点：

  • 需要比较所有缓存行的标记位，硬件实现复杂。

  • 替换策略的管理需要更多的硬件资源和复杂的算法。

  # 示例

  假设我们有一个小缓存，包含 4 行，可以存放 4 个字节的数据，每行可存放主存中的任意数据块：

  1. 访问主存地址 5：缓存为空，将主存地址 5 的数据块加载到缓存行 1。

  2. 访问主存地址 9：缓存中没有地址 9 对应的数据，将它加载到缓存行 2。

  3. 再次访问主存地址 5：缓存中找到标记匹配的缓存行 1，所以直接命中，读取数据。

  4. 访问主存地址 12：如果缓存已满，选择一行替换。例如，使用 LRU 替换最近未访问的行。

  # 总结

  全相联映射通过允许任意主存块存放到任意缓存行，消除了缓存行冲突，适用于对命中率要求高的应用。然而，它实现复杂且需要替换策略，在硬件上更难实现，因此常用于小型缓存或与其他映射方式（如组相联映射）结合使用。

# 组关联映射（组相联映射）

Cache 分为若干组，每一组包含相同数量的行，每个主存块被映射到固定组的任意一行

分组是连续分组，即第 01 行是第 0 组，第 23 行是第 1 组……

假设 $s$ 是 cache 组号，$j$ 是主存块号，$S$ 是组数

$s$ $= $ $j$ $mod$ $S$

K - 路组关联映射：

K = C / S（C 为行数，S 为组数）

示例：

假设 cache 有 4 行，每行包含 8 个字（即块大小为 8 个字，cache 里的一行对应着内存里的一个块），分成 2 个组；主存中包含 128 个字。访问主存的地址长度为 7 位，则：

最低的 3 位：块内地址（一个块内有 8 个字）

中间的 1 位：映射时所对应的 Cache 中的组（2 个组）

最高的 3 位：区分映射到同一组的不同块，记录为 Cache 标记（一个组内分了 8 个块）

• gpt 的解释

  组相联映射（Set Associative Mapping）是缓存映射的一种折中方式，结合了直接映射和全相联映射的优点。它将缓存分成多个组（Set），每组包含若干个缓存行，每个内存块可以映射到一个特定的组，但可以存放在组中的任何缓存行。这种映射方式能够有效减少缓存冲突，同时又避免了全相联映射的高复杂度。

  # 组相联映射的基本原理

  在组相联映射中，缓存分为 N 个组，每组包含 k 个缓存行（这种缓存通常称为 k 路组相联缓存）。主存中的每个块只能映射到缓存中的一个组，但在组内的 k 个缓存行中可以任选一个来存放。

  • 映射方式：通过主存地址找到数据所在的组（类似直接映射），然后在组内的所有缓存行中查找对应的标记位（类似全相联映射）。

  • 标记位（Tag）： 用于区分同一组中不同内存块的标记，确保是正确的数据块。

  • 组索引位（Set Index）： 用于找到特定的数据组。

  • 块内偏移（Block Offset）： 用于定位块内的具体字节。

  # 地址分解

  假设有一个 (2^m) 大小的缓存，分为 ( 2^s ) 个组，每组有 k 个缓存行。主存地址分为以下几部分：

  • 标记位（Tag）： 用来确认数据块的唯一性。

  • 组索引位（Set Index）： 用于定位缓存中的特定组，组数为 (2^s)。

  • 块内偏移（Block Offset）： 用于在数据块内找到具体的字节。

  # 访问过程

  1. 从主存地址中提取组索引位，找到数据块映射到的组。

  2. 在该组中，依次检查 k 个缓存行的标记位：

     • 如果找到匹配的标记位，则缓存命中，可以直接读取数据。

     • 如果没有找到匹配项，则缓存未命中，需要从主存中加载数据块到缓存的该组中一个空闲或替换的行。

  # 替换策略

  如果目标组中的缓存行已满且需要加载新数据，则需要选择一个行进行替换。常用的替换策略与全相联映射类似，包括：

  • LRU（最近最少使用）： 替换组内最近最少被访问的缓存行。

  • 随机替换：随机替换一个缓存行，简单且快速。

  # 示例

  假设有一个 4 路组相联缓存，总共 8 行，即缓存分成 2 个组，每组 4 行。

  1. 访问主存地址 4：

     • 计算组索引，找到主存地址 4 映射到缓存的第 0 组。

     • 检查第 0 组的所有缓存行，发现没有匹配的标记位。

     • 将主存地址 4 的数据块加载到第 0 组的一个空闲行。

  2. 访问主存地址 12：

     • 计算组索引，发现地址 12 也映射到第 0 组。

     • 检查第 0 组中的缓存行，发现没有匹配的标记位。

     • 将主存地址 12 的数据块加载到第 0 组的一个空闲行。

  3. 再次访问主存地址 4：

     • 计算组索引，找到第 0 组。

     • 发现标记位匹配，因此命中，可以直接读取数据。

  4. 访问主存地址 20：

     • 计算组索引，地址 20 映射到第 1 组。

     • 组内没有匹配的标记位，将地址 20 的数据块加载到第 1 组的一个空闲行。

  # 优缺点

  优点：

  • 通过将缓存分成多组，减少了直接映射中的缓存冲突。

  • 查找过程比全相联映射简单，硬件开销相对较低。

  缺点：

  • 比直接映射复杂度略高，硬件上需要实现组内的部分相联查找。

  # 总结

  组相联映射通过折中策略，将缓存划分成多个组，每个主存块只能映射到特定组，组内缓存行可以灵活存放数据。它在减少缓存冲突的同时，不需要全相联映射的复杂硬件支持，因此被广泛应用于现代处理器的缓存设计中。

# 三种映射方式比较

三种方式的相关性

如果 K = 1，组关联映射等同于直接映射

如果 K = C，组关联映射等同于关联映射

K 是一组中行的数目，C 是 Cache 的行数

• 关联度：一个主存块映射到 cache 中可能存放的位置个数

  • 直接映射：1

  • 关联映射：C

  • 组关联映射：K

  关联度越低，命中率越低，判断是否命中的时间越短，标记所占额外空间开销越小

  • 直接映射的命中率最低，命中时间最短，标记最短。

  • 关联映射的命中率最高，命中时间最长，标记最长。

# 替换算法

• 最近最少使用算法（Least Recently Used, LRU）

• 先进先出算法（First In First Out, FIFO）

• 最不经常使用算法（Least Frequently Used, LFU）

• 随机替换算法（Random）

# 最近最少使用算法 LRU

替换掉在 cache 中最长时间未被访问的数据块

实现：

• 增加 LRU 位，来标记访问时间（01234…… 数字越小表示越久没被访问）每次替换为 0 的块。

LRU 位需要额外的硬件实现，会增加 cache 访问时间

# 先进先出算法 FIFO

替换掉在 Cache 中停留时间最长的块

实现：时间片轮转法或环形缓冲技术

• 每行包含一个标识位

• 当同一组中的某行被替换时，将其标识位设为 1，同时将下一行的标识位设为 0

• 如果被替换的是该组中的最后一行，则将该组中的第一行的标识位设为 0

• 替换掉标识位为 0 的行中的数据块

标识位需要额外的硬件实现

# 最不经常使用算法 LFU

替换掉 cache 中被访问次数最少的数据块

实现：为每一行设置计数器

# 随机替换算法

随机替换

# 写策略

考虑到主存和 Cache 的一致性，当 Cache 中某个数据块被修改时，需要考虑该数据块是否被修改。若被修改了，则在替换之前，需要将修改后的数据块写回主存。

# 写直达 Write Through

所有写操作都同时对 cache 和主存进行

会产生大量主存访问。

# 写回 Write Back

先更新 cache 中的数据，当 cache 中某个数据块被替换时，如果它被修改了，才被写回主存

利用一个 ** 脏位（dirty bit）** 或者使用位（use bit）来表示块是否被修改

# 缓存未命中时的写策略

• 写不分配（Write Non-Allocate）：直接将数据写入主存，无需读入 cache

  • 优点：避免 cache 和主存中的数据不一致

  • 通常搭配：写直达

• 写分配（Write Allocate）：将数据所在的块读入 cache 后，在 cache 中更新内容

  • 优点：利用了 cache 的高速特性，减少写内存次数

  • 通常搭配：写回法

# 行大小

假设从行的大小为一个字开始，随着行大小的逐步增大，则 Cache 命中率会增加

当行大小变得较大之后，继续增加行大小，则 Cache 命中率会下降

# Cache 数目

略