Cache原理

一、课程学习主线

1.1 本课程前后逻辑

课程主线围绕”如何让程序运行得更快”逐步展开：

1. CPU 设计：从最基本的数据通路和控制开始。
2. 流水线设计：通过空间换时间，让多条指令不同阶段并行执行。
3. 更深流水线：五级流水可以继续扩展到十级、十五级甚至二十多级，但复杂度快速上升。
4. 指令级并行（ILP）：静态方法由编译器调度指令；动态方法如 Tomasulo 等硬件调度方法。
5. 数据级并行（DLP）：进一步利用数据结构、数据布局和访问模式。
6. 存储层次结构：进入 Cache、主存、外存等 memory hierarchy 的讨论。

1.2 大模型时代下的基础知识

大模型生成的代码往往量很大、结构不一定清楚。如果团队成员直接提交一大段无法理解的生成代码，后续合并、调试和维护会非常困难。工具越强，越需要人能判断它生成的结果是否合理，以及为什么合理。基础知识不一定会在工作中被机械套用，但它会决定你能否提出正确的问题、看懂设计背后的取舍，并进一步提出改进。

1.3 课程方法论：多拿信息，再做设计

做设计前，不要只盯着局部实现。尽量把已有信息全部摆出来：数据如何组织、如何访问、代码如何处理数据、是否有规律、是否能调整数据结构或访问顺序。计算机发展早期更偏”算法驱动”，现在大量场景转向”数据驱动”：先分析数据特征，再设计模型和系统。

对应到存储系统：

• 如果知道数据会顺序访问，可以利用空间局部性。
• 如果知道某个变量反复使用，可以放到寄存器或靠近 CPU 的结构中。
• 如果知道访问模式会造成大量 miss，就需要调整数据布局、访问顺序或 Cache 组织方式。

二、存储层次结构的动机

2.1 功耗墙与内存墙

计算机系统发展中有两个重要瓶颈：

1. 功耗墙（Power Wall）：CPU / GPU / 服务器芯片的功耗和散热限制越来越明显。
2. 内存墙（Memory Wall）：处理器计算速度很快，但如果拿不到数据，计算单元就只能等待。

2.2 存储器层次

典型存储层次：

基本规律：离 CPU 越近，越快、越小、越贵；离 CPU 越远，越慢、越大、越便宜。不同层次的容量和速度都会增长，但数量级关系不会改变。因此，存储层次结构不是可有可无的优化，而是处理速度、容量、成本之间矛盾的核心方法。

2.3 为什么 Cache 仍然重要

即使现在 GPU、大模型和大规模并行计算非常热门，也不能只看 GPU 而跳过 CPU 和 Cache：

• CPU 仍然承担大量控制、调度、推理服务和系统任务。
• 大模型推理和服务端计算仍然需要大量 CPU 参与。
• CPU 的访问模式、指令控制和数据依赖复杂，对 Cache 的要求很高。

三、局部性原理

3.1 时间局部性与空间局部性

Cache 之所以有效，根本原因是程序访问通常具有局部性：

1. 时间局部性（Temporal Locality）：最近访问过的数据或指令，短时间内很可能再次访问。
2. 空间局部性（Spatial Locality）：如果访问了某个地址，接下来很可能访问它附近的地址。

3.2 循环代码的局部性

循环体中的指令如 I4, I5, I6, I7, I8 会反复执行。指令地址本身连续，因此访问 I4 后很快访问 I5、I6 等，体现空间局部性。循环多次执行同一段代码，同一批指令会反复访问，体现时间局部性。

3.3 数组求和例子

数组元素按地址顺序存放，如 A[0], A[1], A[2], ...。如果每次顺序访问，取来一个 Cache 块后，块内相邻元素也会很快被用到。求和变量 sum 会被反复使用，适合放在寄存器中。数组顺序访问利用了空间局部性，sum 的重复使用利用了时间局部性。

3.4 二维数组访问顺序

1
2
3
4
5
for (i = 0; i < M; i++) {
    for (j = 0; j < N; j++) {
        sum += A[i][j];
    }
}

如果数组按行优先存储，上面这种顺序访问会连续访问内存位置，空间局部性好。若交换循环顺序（外层 j，内层 i），访问会在内存中跨很大步长跳转，破坏空间局部性，导致频繁访问主存。实验结果表明两种写法可相差约 21.5 倍。这说明代码逻辑完全相同不代表性能相同，数据布局和访问顺序会显著影响 Cache 命中率。

四、Cache 的基本概念

4.1 Cache 的位置和作用

Cache 位于 CPU 和主存之间，是一个容量较小但速度很快的缓冲区：

• CPU 发出一个主存地址。
• 如果目标指令或数据已经在 Cache 中，则直接从 Cache 返回。
• 如果不在 Cache 中，则访问下一级存储，将数据块调入 Cache，再返回给 CPU。

4.2 指令 Cache 与数据 Cache

CPU 执行指令时至少涉及两类访问：

1. 指令存储访问（I-Cache）：取指令，访问模式通常与控制流、循环、分支有关。
2. 数据存储访问（D-Cache）：load/store 数据，访问模式与数据结构、数组、对象布局等有关。

这两类访问特征不完全一样，因此现代处理器常常对指令 Cache 和数据 Cache 分别优化。

4.3 Hit 与 Miss

• Hit（命中）：要访问的数据在 Cache 中。
• Miss（缺失）：要访问的数据不在 Cache 中。

4.4 Miss 时发生什么

当发生 Cache miss 时，通常需要：

1. 去下一级存储查找对应数据块。
2. 找到后，将数据返回给 CPU。
3. 同时将该数据块复制到 Cache 中。
4. 如果 Cache 中有空闲行，直接放入。
5. 如果没有空闲行，需要选择一个已有 Cache 行替换出去。

这引出几个核心问题：主存如何分块？主存块和 Cache 行之间如何映射？Cache 满了以后替换哪一行？写数据时如何保证 Cache 和主存一致？

五、Cache 行、块与元数据

5.1 Block、Line、Slot

主存会被分成大小相等的块（block），Cache 中对应的存储单元可称为 Cache line、slot、block。常见块大小可能是 16B、32B、64B 等。

5.2 Valid 位

Cache 行中除了数据本身，还需要存放状态位。最基本的是 valid bit：

• valid = 0：该 Cache 行无效，内容不能使用。
• valid = 1：该 Cache 行有效，可以参与命中判断。

5.3 Tag 与 Data

Cache 行通常至少包含：

1
valid | tag | data

其中 data 是真正缓存的数据块，tag 用于说明该 Cache 行当前存的是哪一个主存块，valid 用于说明该行是否有效。

5.4 Cache 对谁透明

Cache 对普通程序员和编译器通常是透明的——程序员仍然写普通 load/store，编译器不需要为每次访问显式管理 Cache 行。但 Cache 对操作系统不完全透明——进程切换时，地址空间变化，可能需要刷新或失效某些 Cache / TLB 状态。

六、Cache 映射方式

6.1 直接映射

直接映射规定：每个主存块只能放到 Cache 中的一个固定行。

映射公式： \(\text{cache line index} = \text{memory block number} \bmod \text{number of cache lines}\)

优点：计算简单、硬件实现容易、命中时间短。缺点：灵活性差，多个常用块映射到同一行会反复相互替换，造成大量 conflict miss。

地址分解：

1
tag | index | block offset

• block offset：定位块内具体字节或字。
• index：定位 Cache 中哪一行。
• tag：判断该行当前是否是目标主存块。

命中判断：根据 index 取出对应 Cache 行，检查 valid 位是否有效，比较地址中的 tag 与 Cache 行保存的 tag。

6.2 全相联映射

全相联映射规定：任意主存块都可以放到 Cache 的任意一行。

优点：灵活性最高，避免直接映射中的很多冲突缺失。缺点：访问时需要把目标 tag 与所有 Cache 行的 tag 比较，需要大量比较器和较大的 tag 存储，硬件复杂、功耗高。

6.3 组相联映射

组相联映射是直接映射和全相联映射的折中：

• 先把 Cache 行分成若干组（set）。
• 某个主存块只能映射到固定组。
• 但在该组内部，可以放到任意一路（way）。

映射公式： \(\text{set index} = \text{memory block number} \bmod \text{number of sets}\)

组间是直接映射，组内是全相联。若只有 1 个组则退化为全相联，若每组只有 1 行则退化为直接映射。

6.4 关联度、标记位与开销

以 32 位地址、Cache 有 4K 行、block 大小为 16B 为例：

关联度越高，候选位置越灵活，但 tag 存储、比较器和控制逻辑都会增加。设计 Cache 时要同时看 hit time、miss rate、miss penalty、元数据开销、替换算法复杂度和目标层级。

七、命中率与平均访问时间

7.1 平均访问时间公式

设命中率为 $\alpha$，Cache 访问时间为 $T_C$，主存访问时间或 miss penalty 为 $T_M$：

$T_C$ 是每次访问都要付出的成本，只有 miss 时才额外付出 $T_M$。

7.2 命中率计算例子

例 1：Cache 访问时间为 4 ns，主存访问时间为 40 ns，希望平均访问时间达到 5 ns。代入得： \(5 = 4 + (1-\alpha)\times 40\) \(\alpha = 97.5\%\)

例 2：Cache 访问时间为 1 ns，主存访问时间为 20 ns：

八、替换算法

8.1 FIFO

FIFO（First-In, First-Out）：最早进入 Cache 的行先被替换。思路简单，但最早进入不代表最近不用，某些访问序列会造成严重颠簸。

8.2 LRU

LRU（Least Recently Used）：替换最近最少使用的行。如果某个数据已经很久没被访问，将来短期内继续不用的概率较高。缺点是需要记录”最近使用”信息，每次访问都可能更新状态，在多路组相联中需要额外计数器。

8.3 LFU

LFU（Least Frequently Used）：替换使用频率最低的行。需要维护访问频率，对历史访问过多的数据可能不够敏感。

8.4 Random

随机替换：不精细维护历史信息，随机选一行替换。实现非常简单，不需要维护复杂标志位。平均效果在一些场景下并不差。当精妙算法的额外开销抵消收益时，随机可能是很实用的选择。

九、写操作与一致性问题

Cache 设计中必须解决的问题：

• 写命中时是直接写回主存，还是先只改 Cache？
• Cache 中被修改的数据是否需要 dirty bit？
• 替换一行时，如果该行被改过，是否需要写回主存？
• 多核或 DMA 场景下，多个缓存副本之间如何保持一致？

十、Cache 与 lab 的关系

后续 lab 会进入 memory 相关部分：MMU 是一个重点方向，TLB 实现有挑战，如果能进一步做 Cache 会更完整。原子指令一定要做，因为它和操作系统密切相关。原子指令的核心是读-改-写过程不能被其他操作打断，而 Cache 使 memory 系统变复杂后，原子性保证也更复杂。

十一、核心总结

1. 存储层次结构是解决速度、容量、成本矛盾的基本方法。
2. Cache 的有效性来自程序的时间局部性和空间局部性。
3. 程序访问顺序会显著影响 Cache 命中率，二维数组行/列遍历可以造成数量级差异。
4. Cache 行除了数据，还需要 valid、tag、dirty 等元数据。
5. 直接映射简单快速但容易冲突，全相联最灵活但比较器和 tag 开销高，组相联是折中方案。
6. 平均访问时间可用 $T_{\text{avg}} = T_C + (1-\alpha)T_M$ 来理解，命中率对性能影响极大。
7. 替换算法需要在效果和实现复杂度之间折中；FIFO、LRU、LFU、Random 各有取舍。
8. Cache 对普通程序员看似透明，但对系统程序员、操作系统、原子指令和性能优化并不透明。
9. 大模型可以帮助写代码和解释代码，但不能替代对体系结构基础知识和设计取舍的理解。

• Previous
  群论梳理
• Next
  索引全景