一、直接映射

Cache 是位于 CPU 和主存之间的高速存储器。由于容量远小于主存，需要规定主存块可以放入哪些 Cache 行。

1. 映射规则

直接映射：每个主存块只能放入唯一指定的 Cache 行。 映射规则为：

Cache 行号=主存块号 mod Cache 总行数\boxed{\text{Cache 行号}=\text{主存块号}\bmod\text{Cache 总行数}}

其中， mod \bmod 表示取余数，每个 Cache 行可以存放一个主存块。

映射示例与冲突不命中

假设主存有 16 个块（编号 0～15），Cache 有 4 行（编号 0～3），则 Cache 行号=主存块号 mod 4\text{Cache 行号}=\text{主存块号}\bmod 4。

Cache 行号 能映射到该行的主存块
0 0、4、8、12
1 1、5、9、13
2 2、6、10、14
3 3、7、11、15

重点： 多个主存块可以映射到同一 Cache 行，但不能同时存放在这一行。

例如，CPU 先访问主存块 0，再访问主存块 4：

  1. 块 0 装入 Cache 第 0 行。
  2. 块 4 也必须放入第 0 行，因此替换块 0。
  3. 再次访问块 0 时，需要重新装入。

这种因多个主存块竞争同一 Cache 行而产生的不命中，称为冲突不命中（Conflict Miss）。

2. 主存地址划分与命中判断

直接映射下，主存地址通常划分为三部分：

高位 中间位 低位
标记（Tag） 行索引（Index） 块内偏移（Offset）
  • Tag：区分映射到同一行的不同主存块。
  • Index：确定访问哪一条 Cache 行。
  • Offset：按字节编址时，确定块内的哪个字节。

重点： 一个非负整数对 2n2^n 取余，结果等于其二进制表示的低 nn 位。因此，当 Cache 行数为 2n2^n 时，可用主存块号的低 nn 位作为行索引。

标记位数的计算

直接映射下，若主存块数与 Cache 块数均为 2 的整数次幂，则：

标记位数=log⁡2主存块数Cache 块数\boxed{\text{标记位数}=\log_2\frac{\text{主存块数}}{\text{Cache 块数}}}

其中，Cache 块数就是 Cache 行数；主存块数按题目给出的主存容量或完整地址空间计算。主存块号由 Tag 和行索引组成，因此标记位数等于 log⁡2主存块数−log⁡2Cache 块数\log_2\text{主存块数}-\log_2\text{Cache 块数}，也就是主存地址位数 − 行索引位数 − 块内偏移位数。

例如，前述主存有 16 个块、Cache 有 4 行，标记位数为 log⁡2(16/4)=2\log_2(16/4)=2 位。

命中判断

CPU 访问数据时：

  1. 根据地址中的 Index 找到对应 Cache 行。
  2. 检查该行的有效位，并比较地址 Tag 与该行保存的 Tag。
  3. 命中（Hit）：有效位为 1 且 Tag 相同，按 Offset 读取数据。
  4. 未命中（Miss）：有效位为 0 或 Tag 不同，从主存调入对应数据块，并更新 Tag 和有效位。

3. 优点与缺点

优点 缺点
硬件结构简单，实现成本较低 容易产生冲突不命中
地址查找速度快 Cache 空间可能无法充分利用
频繁替换可能降低命中率

即使其他行空闲，发生冲突的块也只能替换指定行。

4. 例题：计算 Cache 的总存储容量

题目： 采用 64 位存储地址，直接映射 Cache 的数据容量为 16 KiB，每个数据块为 4 字，求 Cache 的总存储容量（用 bit 表示）。

本例按以下条件计算：按字节编址，1 字 = 32 bit = 4 Byte，每行包含数据、Tag 和 1 位有效位，不计脏位等其他管理信息。 字长与管理位的设置会影响结果，应以题目给出的条件为准。

区分地址位数与数据容量

  • 64 位地址：一个主存地址用 64 个二进制位表示。按字节编址时，理论上可表示 2642^{64} 个字节地址，并不意味着实际安装了这么大的内存。
  • 16 KiB 数据容量：Cache 能存放 16×1024=1638416\times1024=16384 Byte 的数据。

两者共同决定 Tag 的位数：Cache 需要保存 Tag，才能识别每行中的数据来自哪个主存块。

第一步：计算 Cache 行数

每个数据块包含 4 字，因此块大小为：

B=4×4=16 ByteB=4\times4=16\text{ Byte}

Cache 行数为：

N=16×102416=1024=210N=\frac{16\times1024}{16}=1024=2^{10}

因此，行索引需要 10 位。

第二步：划分 64 位主存地址

标记 Tag 行索引 Index 字偏移 字节偏移
50 位 10 位 2 位 2 位
  • 块内偏移：每块 16 Byte，需要 log⁡216=4\log_2 16=4 位。其中 2 位选择块内的字，另外 2 位选择字内的字节。
  • 行索引：共 1024 行，需要 log⁡21024=10\log_2 1024=10 位。
  • Tag：地址中去掉行索引和块内偏移后，剩余位数为：
Tag 位数=64−10−4=50 位\text{Tag 位数}=64-10-4=\boxed{50\text{ 位}}

第三步：计算总存储容量

每一行需要存储：

内容 位数
数据（Data） 16×8=12816\times8=128 bit
标记（Tag） 50 bit
有效位（Valid） 1 bit
合计 179 bit

整个 Cache 有 1024 行，因此：

总存储容量=1024×(128+50+1)=183296 bit\boxed{\text{总存储容量}=1024\times(128+50+1)=183296\text{ bit}}

换算为其他单位：

183296 bit=179 Kib=22.375 KiB183296\text{ bit}=179\text{ Kib}=22.375\text{ KiB}

其中，1 Kib=1024 bit1\text{ Kib}=1024\text{ bit}，1 KiB=1024 Byte1\text{ KiB}=1024\text{ Byte}。

5. 易混点：哪些内容需要存进 Cache？

重点： 通常所说的 Cache 容量是数据容量；计算包含管理信息的总存储容量时，还要计入 Tag、有效位等。

容量类型 包含内容 本例结果
数据容量（标称容量） 只计算 Data 16 KiB
总存储容量（按本例条件） Data + Tag + Valid 183296 bit，即 22.375 KiB

64 位地址虽然分成多个字段，但并非所有地址字段都要存入 Cache 行：

地址字段 作用 是否需要存入 Cache 行
Tag（50 位） 判断是否为目标主存块 需要
行索引（10 位） 定位 Cache 行 不需要，由行的位置确定
字偏移（2 位） 选择块内的字 不需要，用于选取数据
字节偏移（2 位） 选择字内的字节 不需要，用于选取数据

计算总容量时，计入需要保存的 Tag 和管理位；Index、Offset 用于定位，不额外占用每行的存储位。

二、全相联映射

1. 映射规则与地址划分

全相联映射：任意主存块都可以放入 Cache 的任意一行。 例如，Cache 有 4 行时，主存块 2 可以放在第 0、1、2、3 行中的任意一行，存放位置没有固定限制。

全相联映射下，主存地址只分为两部分：

高位 低位
主存块号，即标记（Tag） 块内地址（Offset）
  • Tag：判断目标主存块是否已经存放在 Cache 中。
  • 块内地址：确定数据在块内的具体位置。

重点： 全相联映射没有行索引字段，Tag 就是完整的主存块号；直接映射中的 Tag 只是主存块号的高位部分。

因为无法根据行索引定位，全相联映射需要将地址中的 Tag 与 Cache 各有效行的 Tag 进行比较，通常通过并行比较来查找数据，因此硬件较复杂。

2. 例题：划分主存地址

假设主存容量为 64 KiB、Cache 数据容量为 4 KiB、每块大小为 1 KiB，按字节编址，采用全相联映射。

计算项目 计算过程 结果
主存地址位数 64 KiB=216 Byte64\text{ KiB}=2^{16}\text{ Byte} 16 位
块内地址位数 1 KiB=210 Byte1\text{ KiB}=2^{10}\text{ Byte} 10 位
Tag 位数 16−1016-10 6 位
Cache 行数 4 KiB/1 KiB4\text{ KiB}/1\text{ KiB} 4 行

因此，主存地址划分为：

标记 Tag 块内地址 Offset
6 位 10 位

虽然 Cache 有 4 行，地址中仍然没有行索引字段。

3. 没有行索引，如何找到数据？

假设 Cache 各行都有效，并保存了以下数据：

Cache 行号 Tag 数据
0 3 主存块 3 的数据
1 5 主存块 5 的数据
2 7 主存块 7 的数据
3 12 主存块 12 的数据

CPU 访问主存块 7 时：

  1. 从主存地址中提取 Tag，得到 7。
  2. 将 7 与 Cache 所有有效行的 Tag 比较。
  3. 第 2 行的 Tag 等于 7，Cache 命中。
  4. 根据块内地址，从第 2 行的数据块中选取具体数据，返回 CPU。

不需要提前知道块 7 在第 2 行，比较 Tag 就能找到它。

如果所有有效行的 Tag 都不匹配，则 Cache 未命中，需要从主存调入对应块。若 Cache 已满，还要按替换算法选择一行进行替换。

4. 优点与缺点

优点 缺点
存放位置灵活，可充分利用 Cache 空间 硬件实现复杂
不会因主存块竞争固定 Cache 行而产生冲突不命中 需要比较多个 Cache 行的 Tag，比较电路成本较高

5. 主存块的边界与调入范围

主存块的边界固定

块的划分由块大小决定。假设每块大小为 1 KiB=1024 Byte1\text{ KiB}=1024\text{ Byte}，主存按以下固定边界划分：

主存块号 主存地址范围 块内地址范围
0 0～1023 0～1023
1 1024～2047 0～1023
2 2048～3071 0～1023
3 3072～4095 0～1023

每个块的块内地址都从 0 开始。全相联映射中，表中的主存块号就是 Tag。

访问块中间的地址时，调入哪个范围？

例如，CPU 访问主存地址 1500。由于：

1500=1×1024+4761500=1\times1024+476

因此，该地址属于主存块 1，块内偏移为 476；采用全相联映射时，Tag 为 1。

重点： 若 Cache 中没有该块，应调入整个主存块 1，即地址 1024～2047 的数据，而不是从地址 1500 开始读取 1024 个字节。

调入完成后，再根据块内偏移 476 选取 CPU 需要的数据。主存块边界和调入范围这一规则对直接映射、全相联映射都适用。

三、组相联映射

1. 映射规则与组的划分

组相联映射：组间采用直接映射，组内采用全相联映射。 每个主存块只能放入固定的一组，但可以放在组内的任意一行。

假设 Cache 共 8 行，分为 4 组，每组 2 行，就称为 2 路组相联映射。“路数”就是每组包含的 Cache 行数。

组号 组内包含的 Cache 行
0 第 0、1 行
1 第 2、3 行
2 第 4、5 行
3 第 6、7 行

主存块映射到哪一组，由以下规则确定：

组号=主存块号 mod 组数\boxed{\text{组号}=\text{主存块号}\bmod\text{组数}}

本例共有 4 组，因此组号为 主存块号 mod 4\text{主存块号}\bmod 4。

主存块号 映射组号 能放的位置
0 0 第 0 组的任意一行
1 1 第 1 组的任意一行
2 2 第 2 组的任意一行
3 3 第 3 组的任意一行
4 0 第 0 组的任意一行
5 1 第 1 组的任意一行
8 0 第 0 组的任意一行

主存块 0、4、8 都映射到第 0 组，但该组只有两行，最多只能同时存放其中两个块。

2. 组内存放与替换示例

依次访问主存块 0、4、8，观察第 0 组的变化：

阶段 组内第 0 行 组内第 1 行 说明
初始状态 空 空 两行都空闲
访问块 0 后 主存块 0 空 装入一条空行
访问块 4 后 主存块 0 主存块 4 装入另一条空行，无需替换块 0
访问块 8 后 主存块 8 主存块 4 组已满，假设按替换算法选中块 0

重点： 映射到同一组的多个主存块可以占据组内不同的行，减少因固定行竞争而产生的冲突；但目标组已满时，仍需在该组内替换。

直接映射中，竞争同一行的块可能互相替换；组相联映射中，只要目标组还有空行，就可以同时保存这些块。

3. 主存地址划分与命中判断

组相联映射的主存地址划分为三部分：

高位 中间位 低位
标记（Tag） 组索引（Index） 块内偏移（Offset）
  • Tag：区分映射到同一组的不同主存块。
  • 组索引：确定访问哪一组。
  • 块内偏移：确定块内的具体数据位置。

重点： 主存地址中没有组内行索引。组内采用全相联映射，需要比较目标组内各有效行的 Tag，才能找到具体行。

CPU 访问数据时：

  1. 根据组索引找到对应的 Cache 组。
  2. 比较地址中的 Tag 与组内各行保存的 Tag，并检查有效位。
  3. 命中：存在有效位为 1 且 Tag 相同的行，按块内偏移读取数据。
  4. 未命中：没有匹配的有效行，从主存或下一级 Cache 调入对应块；若目标组已满，按替换算法在组内选择一行替换。

4. 例题：划分主存地址

假设主存地址长度为 16 位，按字节编址，Cache 数据容量为 128 Byte，每块大小为 16 Byte，采用 2 路组相联映射。

计算项目 计算过程 结果
Cache 行数 128÷16128\div16 8 行
组数 8÷28\div2 4 组
块内偏移位数 log⁡216\log_2 16 4 位
组索引位数 log⁡24\log_2 4 2 位
Tag 位数 16−4−216-4-2 10 位

因此，16 位主存地址划分为：

标记 Tag 组索引 Index 块内偏移 Offset
10 位（第 15～6 位） 2 位（第 5～4 位） 4 位（第 3～0 位）

本例为 2 路组相联映射，因此命中判断只需比较选中组内两行的 Tag。

四、三种映射方式对比

比较项目 直接映射 全相联映射 组相联映射
映射位置 固定一行 任意一行 固定一组内的任意一行
地址索引 行索引 无 组索引
Tag 比较范围 指定的一行 所有有效行 指定组内的有效行
替换范围 指定行 整个 Cache 指定组内
硬件复杂度 低 高 中等

在 Cache 容量和主存块大小固定的条件下，三种映射方式的特性对比：

  1. 命中率： 直接映射最低，全相联映射最高。
  2. 判断开销与所需时间： 直接映射最小、最快，全相联映射最大、最慢。
  3. 标记存储开销： 直接映射最少，全相联映射最多。

直接映射和全相联映射都可以看作组相联映射的特殊情况：

  • 每组只有 1 行：就是直接映射。
  • 整个 Cache 只有 1 组：就是全相联映射。

我已急哭，
学了好久，有点累了。
剩下的那个组相联明天再说吧。(嘻嘻，已完成😋 ———— 一天后的我)