CSAPP - 08.MEM-02

主要内容 (Overview)：
本章深入探讨了计算机系统中最重要的性能优化组件之一：高速缓存 (Cache Memories)。

缓存的基本组织结构：如何将巨大的内存空间映射到小容量的缓存中（直接映射、组相联、全相联）。
缓存的读写机制：CPU 如何查找数据，以及写入数据时的策略（写穿透 vs 写回）。
缓存对性能的影响：通过具体的矩阵乘法示例，展示了缓存友好的代码如何带来数量级的性能提升。
编写高速缓存友好的代码：给程序员的实战指南，如何利用局部性原理优化程序。

Motivation：
随着 CPU 和内存速度差距的拉大，Cache 成为了系统性能的瓶颈所在。理解 Cache 的工作原理，不再把内存看作一个平坦的数组，而是理解其层次结构，是编写高性能代码（High Performance Computing）的必备技能。

计算机组成原理笔记：高速缓存 (Cache Memories)

1. 为什么需要高速缓存？(Why Caching?)

1.1 存储技术的趋势 (Storage Trends)

CPU 速度：每 18 个月翻一番（摩尔定律）。
内存速度：增长缓慢，远落后于 CPU。
差距 (The Gap)：CPU 和内存之间的速度差距越来越大。如果 CPU 每次都要等内存，性能将极其低下。

1.2 解决方案：局部性 + 缓存 (Locality + Cache)

利用程序的局部性原理 (Locality)，我们将最常访问的数据放在离 CPU 最近、速度最快的小容量存储器中，这就是 Cache。
SRAM vs DRAM：Cache 使用 SRAM（快但贵），主存使用 DRAM（慢但便宜）。

2. 通用高速缓存存储器组织结构 (General Cache Organization)

为了解决：如何在极短的时间内（几个时钟周期），从巨大的主存地址空间（m 位地址）中，精准地找到我们需要的那个字节是否藏在极小的缓存里？
这种组织方式本质上是一种硬件哈希表（Hardware Hash Map）

高速缓存 (Cache)：
- 物理介质：SRAM (静态随机存取存储器)。
- 位置：集成在 CPU 芯片内部 (L1, L2, L3)。
- 特点：速度极快，但容量小、造价贵。
主存 (Main Memory)：
- 物理介质：DRAM (动态随机存取存储器)，即通常说的“内存条”。
- 位置：插在主板上，通过总线连接 CPU。
- 逻辑视图：对 CPU 而言，主存只是一个巨大的、线性的字节数组 Array[0...N]。
地址翻译机制：
- CPU 发出的总是 $m$ 位的物理地址（例如 64 位）。
- Cache 控制器负责将这个线性的地址**“切分”**，映射到 Cache 内部特定的二维硬件结构中进行快速查找。

一个高速缓存系统由四个核心参数 $(S, E, B, m)$ 定义。这完全描述了 CPU 内部 SRAM 的物理硬件布局。

2.1 几何参数定义

$S$ (Sets, 组数)：
- 缓存被分为 $S$ 个组 (Cache Sets)。
- $S$ 必须是 2 的幂，即 $S = 2^s$ 。这里的 $s$ 是地址中用于索引组的位数 (Set Index bits)。
$E$ (Lines/Ways, 行)：
- 每个组包含 $E$ 个缓存行 (Cache Lines)。
- 这决定了缓存的类型（ $E=1$ : 直接映射； $E>1$ : 组相联）。
$B$ (Block Size, 块大小)：
- 每个缓存行存储的数据大小为 $B$ 字节。
- $B$ 必须是 2 的幂，即 $B = 2^b$ 。这里的 $b$ 是地址中用于块内定位的位数 (Block Offset bits)。
- 重要意义： $B$ 决定了主存与缓存之间数据流转的最小颗粒度。当发生未命中 (Miss) 时，硬件会一次性搬运 $B$ 个字节（利用空间局部性），而不仅仅是请求的那 1 个字节。
$m$ (Address Bits, 地址位数)：
- 物理内存地址的总位数 (例如 64 位)。

2.2 地址划分 (Address Breakdown)

当 CPU 发出一个 $m$ 位的物理地址时，Cache 硬件会将其位级表示切分为三个部分，用于定位数据：

m \text{ bits} = \underbrace{t \text{ bits}}_{\text{Tag}} \ |\ \underbrace{s \text{ bits}}_{\text{Set Index}} \ |\ \underbrace{b \text{ bits}}_{\text{Block Offset}}

组索引 (Set Index, $s$ bits)：
- 作用：定位组。
- 决定去哪一个“抽屉” ( $0 \dots S-1$ ) 里查找。
- 计算： $s = \log_2 S$ 。
标记位 (Tag, $t$ bits)：
- 作用：身份验证。
- 因为多个内存块可能映射到同一个组，Tag 用于确认组里的这一行数据是否真的是我们需要的那块。
- 计算： $t = m - (s + b)$ 。
块偏移 (Block Offset, $b$ bits)：
- 作用：数据提取。
- 在找到的那个 $B$ 字节的数据块中，精确定位到我们要读写的具体字节位置。
- 计算： $b = \log_2 B$ 。

2.3 物理缓存行结构 (Physical Cache Line Structure)

每一个物理缓存行 (Cache Line) 不仅仅存储数据，还包含元数据。它由以下三部分组成：

组成部分	大小	作用
Valid Bit (有效位)	1 bit	标记该行是否存储了有意义的数据（冷启动时为 0
Tag (标记)	$t$ bits	存储该数据块对应的内存地址高位，用于与 CPU 地址中的 Tag 进行
Data Block (数据块)	$B$ bytes	实际存储的主存数
Dirty Bit （脏位）	1 bit	如果缓存采用“写回”策略（只改缓存，不马上改内存），还需要一个 Dirty Bit。它标记这行数据是否被 CPU 修改过。如果是脏的，在被驱逐时必须写回内存

总容量计算：缓存的数据容量 = $S \times E \times B$ 字节。（不包括 Tag 和 Valid Bit 占用的空间）

3. 缓存映射策略 (Cache Mapping Strategies)

根据关联度 $E$ 的不同，Cache 分为三类：

3.1 直接映射缓存 (Direct Mapped Cache, E=1)

特点：每一组只有一行 ( $E=1$ )。
查找过程：
1. 组选择 (Set Selection)：根据地址中的 $s$ 位索引找到唯一对应的组。
2. 行匹配 (Line Matching)：检查该组中那唯一一行的有效位是否为 1，且 Tag 是否匹配。
3. 字抽取 (Word Extraction)：如果匹配（Hit），根据 $b$ 位偏移量取出数据。
缺点：容易发生冲突未命中 (Conflict Miss)。如果两个频繁访问的地址映射到同一个组，它们会不停地互相驱逐（Thrashing）。

3.2 组相联缓存 (E-way Set Associative Cache, 1 < E < C/B)

特点：每一组有多行（例如 E=2, 4, 8）。
查找过程：
1. 组选择：同上，找到对应的组。
2. 行匹配：并行检查该组内所有 $E$ 行的 Tag。只要有一行匹配且有效，就是命中。
优点：减少了冲突未命中，因为一个组可以容纳多个映射到此的块。
替换策略 (Replacement Policy)：当组满了需要放入新块时，需要选择一行驱逐。常用策略：
- LRU (Least Recently Used)：最近最少使用。
  - 系统会记录每个数据块最后一次被访问的时间。当需要驱逐时，选择那个时间戳最老（也就是距离现在最久没有被使用过）的块。
  - 基于时间局部性假设。
  - 优点：性能最好，最符合大多数程序的运行规律，命中率通常最高。
  - 缺点：实现昂贵，硬件需要维护一个复杂的队列或时间戳，每次访问都要更新顺序，硬件开销大。
- LFU (Least Frequently Used)：最不常使用。
  - 保留热门数据：对于长期频繁使用的数据保护得很好。
  - “历史包袱” (Aging Problem)：这是 LFU 最大的由于。比如一个数据在程序启动时用了 1000 次（计数很高），但之后再也没用过。因为它的计数器太高了，它会一直赖在缓存里不走。通常需要配合“定期衰减”机制来解决。
- Random：随机替换。
  - 实现极简：硬件极其简单，不需要存储额外的历史信息，速度极快。
  - 不够智能：可能会运气不好，把下一秒马上要用的关键数据给踢走了，导致发生未命中。
  - 在缓存很大时，Random 的表现其实出人意料地不错，并没有比 LRU 差太多。

3.3 全相联缓存 (Fully Associative Cache, S=1)

特点：只有 1 个组，该组包含所有行 ( $E = C/B$ )。
查找过程：没有组索引，地址只分为 Tag 和 Offset。必须并行搜索所有行的 Tag。
应用：因为硬件并行搜索极其昂贵，只用于容量很小但缺失代价极高的缓存（如 TLB 页表缓存）。

4. 缓存的写操作 (Writes)

写操作 (Writes) 要复杂得多，因为我们修改了缓存中的数据后，必须考虑如何让主存（Main Memory）也知道数据变了。

根据 CPU 想要写入的数据是否已经在缓存中，我们将情况分为 写命中 (Write Hit) 和 写未命中 (Write Miss)。

1. 写命中 (Write Hit)

场景：CPU 想要修改地址 A 的数据，而地址 A 对应的数据块已经存在于缓存中。

此时有两种主流策略来处理更新：

策略 A: 写穿透 (Write-through)

机制：CPU 修改缓存中数据的同时，立即将这个新数据写入到主存（或下一级缓存）中。
流程：
1. 更新 Cache 中的行。
2. 同时发起一个总线写事务，更新 Memory 中的块。
优点：
- 简单：易于实现。
- 一致性好：主存中的数据始终是最新的。这对于多核处理器或 DMA（直接内存访问）非常重要。
缺点：
- 慢 (Slow)：每次写操作都要访问主存，速度受限于主存带宽。
- 总线流量大 (High Bandwidth)：即使是反复修改同一个变量，也会产生大量的总线写请求。

策略 B: 写回 (Write-back) —— 现代高性能 CPU 首选

机制：CPU 只修改缓存中的数据，不立即写入主存。
- 只有当这一行数据因为冲突被驱逐 (Evicted) 出缓存时，才将它写回主存。
关键技术：脏位 (Dirty Bit)
- 缓存行结构中增加一个 Dirty Bit。
- 当 CPU 修改了某一行，将 Dirty Bit 置为 1。
- 当该行被替换时：
  - 如果 Dirty Bit == 1：说明这行被改过，必须写回主存。
  - 如果 Dirty Bit == 0：说明这行没动过，直接覆盖即可，不用写回。
优点：
- 极快：写操作以 Cache 速度进行，不需要等主存。
- 节省带宽：如果一个变量被修改 100 次（例如循环计数器），只会产生 1 次主存写操作（被驱逐时）。
缺点：
- 复杂：需要额外的硬件（Dirty Bit）和控制逻辑。
- 不一致：主存中的数据可能是旧的（Stale），这在多核环境下需要复杂的缓存一致性协议（如 MESI）来解决。

2. 写未命中 (Write Miss)

场景：CPU 想要修改地址 A 的数据，但地址 A 不在缓存中。

此时也有两种策略，通常与写命中策略搭配使用：

策略 A: 写分配 (Write-allocate) —— 通常搭配 Write-back

机制：“先搬进来，再修改”。
1. 将地址 A 所在的整个块从主存读入 (Load) 缓存（分配一行）。
2. 在缓存中修改这个块的数据。
逻辑：假设利用局部性原理，如果我现在写了这个数据，哪怕它不在缓存里，我接下来很可能还会读/写它，所以把它搬进来是值得的。
缺点：第一次写会比较慢，因为多了一次“读主存”的操作。

策略 B: 非写分配 (No-write-allocate) —— 通常搭配 Write-through

机制：“直接绕过缓存”。
- 直接把数据写入主存。
- 不将该块加载到缓存中。
逻辑：既然不在缓存里，我就不破坏缓存现在的布局了，直接写到底层存储去。

3. 总结与典型组合

虽然理论上有 4 种组合，但实际工程中主要使用以下两种：

组合 1：Write-back + Write-allocate (回写 + 写分配)

代表：Intel Core i7/i9, Linux 内存系统。
特点：尽可能把所有数据操作都留在 Cache 内部解决。
性能：利用局部性原理，性能最高，适合绝大多数现代应用。

组合 2：Write-through + No-write-allocate (直写 + 非写分配)

代表：一些简单的嵌入式处理器，或者图形显存。
特点：逻辑简单。如果程序只是单纯地“写数据”（如初始化大数组）而不再读它，这种策略效率反而更高（避免了把数据读进 Cache 的开销）。

特性	Write-through (直写)	Write-back (回写)
内存一致性	内存总是最新的	内存可能是旧的
总线流量	高 (每次写都占用)	低 (仅驱逐时占用)
硬件需求	低	高 (需要 Dirty Bit)
写未命中策略	通常用 No-write-allocate	通常用 Write-allocate
适用场景	简单系统，对一致性要求高	高性能通用计算

5. 缓存性能指标 (Cache Performance Metrics)

未命中率 (Miss Rate): $Misses / Accesses$ (通常 L1: 3-10%, L2: <1%)。
命中率 (Hit Rate): $1 - Miss Rate$ 。
命中时间 (Hit Time): 从 Cache 读数据的延迟 (L1: ~4 cycles)。
未命中惩罚 (Miss Penalty): 从下一层取数据的额外时间 (L2: ~10 cycles, Main Memory: 50-200 cycles)。

平均访问时间 (AMAT, Average Memory Access Time):

T_{avg} = T_{hit} + MR \times T_{miss\_penalty}

哪怕只有 1% 的 Miss Rate，如果 Miss Penalty 很大，也会严重拖慢整体性能。

6. 编写高速缓存友好的代码 (Writing Cache-Friendly Code)

这是对程序员最重要的部分。

6.1 核心原则

关注内循环 (Focus on Inner Loops)：大部分计算发生在这里。
最大化空间局部性 (Maximize Spatial Locality)：
- 以 步长为 1 (Stride-1) 的方式顺序读取数据。
- 避免大步长跳跃访问。
最大化时间局部性 (Maximize Temporal Locality)：
- 一旦把数据读进来，就尽可能多地使用它，防止它被驱逐。

6.2 案例分析：矩阵乘法 (Matrix Multiplication)

计算 $C = A \times B$ ，其中 $A, B, C$ 均为 $n \times n$ 矩阵，数据类型为 double（8字节），Cache Block 大小为 32 字节（容纳 4 个 double）。

1. 朴素算法 (ijk Permutation)

最常见的实现方式，三重循环嵌套：

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        sum = 0.0;
        for (k = 0; k < n; k++)
            sum += A[i][k] * B[k][j];
        C[i][j] = sum;
    }
}

缓存未命中分析 (Miss Rate Analysis)：

假设： $n$ 非常大，缓存很小（无法装下一整行）。
对 A 的访问 (A[i][k])：
- 模式：行优先扫描 (Stride-1)。
- 局部性：良好 (Spatial Locality)。
- 未命中率：每读 1 个 Block 发生 1 次 Miss。若 Block 能存 4个 double，Miss rate = $1/4$ 。
对 B 的访问 (B[k][j])：
- 模式：列优先扫描 (Stride-n)。
- 局部性：极差。每次访问都跳过 $n$ 个元素，大概率跳转到缓存中不存在的块。
- 未命中率：100% (Miss rate = 1.0)。
总未命中数：每次迭代产生 $1.25$ 次 Misses。总 Misses $\approx 1.25 n^3$ 。

2. jik 模式 —— 性能中等/较差

for (j=0; j<n; j++)
  for (i=0; i<n; i++) {
    sum = 0.0;
    for (k=0; k<n; k++) // 内层循环变量 k
      sum += A[i][k] * B[k][j];
    C[i][j] = sum;
  }

访问模式分析:
- 内层循环依然是 k 递增。
- 内存访问模式与 ijk 完全一致：A 是 Stride-1，B 是 Stride-N。
结论: 性能受到 B 矩阵列扫描的限制，速度较慢。

3. kij 模式 (优化算法) —— 性能最佳

for (k=0; k<n; k++)
  for (i=0; i<n; i++) {
    r = A[i][k]; // 在内层循环中是常数，放入寄存器
    for (j=0; j<n; j++) // 内层循环变量 j
      C[i][j] += r * B[k][j];
  }

访问模式分析:
- B[k][j]: 内层循环 j 递增，访问 B 的同一行相邻元素。Stride-1 (行扫描)，空间局部性极好。
- C[i][j]: 内层循环 j 递增，访问 C 的同一行相邻元素。Stride-1 (行扫描)，空间局部性极好。
- A[i][k]: 在内层循环中 i, k 不变，r 常驻寄存器，无访存开销。
Miss Rate: $\approx 0.5$ (B 为 0.25, C 为 0.25，考虑 write-allocate 等因素总体极低)。
结论: 仅通过改变循环顺序，将所有内存访问都变成了顺滑的行扫描，充分利用了 Cache Block，性能比 ijk快得多。

4. jki / kji 模式 (反面教材) —— 性能最差

如果内层循环是 i 递增，那么 A[i][k] 和 C[i][j] 都会变成 Stride-N (列扫描)。
这是最糟糕的情况，双重列扫描会导致 Cache 频繁颠簸 (Thrashing)。

循环顺序	内层循环	内存访问模式 (A, B, C)	Misses / Iter	性能评价
ijk / jik	`k`	A: Stride-1 (快) B: Stride-N (慢)	~1.25	中等 (受限于 B)
jki / kji	`i`	A: Stride-N (慢) C: Stride-N (慢)	~2.0	最差 (双重慢)
kij / ikj	`j`	B: Stride-1 (快) C: Stride-1 (快)	~0.50	最好 (双重快)

在编写处理多维数组的循环时，务必让最内层循环的索引对应数组最右侧的下标（例如 Array[...][i] 中的 i）。这能保证访问地址是连续的，最大化空间局部性。

5. 分块算法 (Blocking / Tiled Matrix Multiplication)

核心思想：利用分治策略，将大的矩阵乘法分解为多个小块（Sub-blocks）的乘法。保证小块的大小能完全装入 L1 Cache 中。

代码逻辑：

// B 是分块大小 (Blocking Factor)
for (i = 0; i < n; i += B) {          // 外层 i
    for (j = 0; j < n; j += B) {      // 外层 j
        for (k = 0; k < n; k += B) {  // 外层 k
            /* B x B mini matrix multiplications */
            // 这里的 min 是为了处理边缘情况（n 不能被 B 整除时）
            for (i1 = i; i1 < min(i + B, n); i1++) {
                for (j1 = j; j1 < min(j + B, n); j1++) {
                    double r = 0; // 使用寄存器临时存储
                    for (k1 = k; k1 < min(k + B, n); k1++) {
                        r += A[i1*n + k1] * B[k1*n + j1];
                    }
                    C[i1*n + j1] += r;
                }
            }
        }
    }
}

分块约束条件：

为了避免冲突未命中，我们需要保证参与计算的三个小块（A 的子块、B 的子块、C 的子块）能同时驻留在缓存中。
即： $3 \times (B \times B) \times \text{sizeof(element)} < \text{Cache Size}$ 。
缓存未命中分析 (Miss Rate Analysis)：

假设 Cache Block 可以存 8 个元素。
每计算一个 $B \times B$ $B \times B$ 大小的 C 子块，我们需要加载：
- A 的一个 $B \times B$ 子块。
- B 的一个 $B \times B$ 子块。
加载一个子块的 Miss 数： $B^2 / 8$ 。
总运算量：我们需要计算 $(n/B) \times (n/B) = (n/B)^2$ 个 C 的子块。
对于每个 C 的子块，我们需要遍历 $n/B$ 次 A 和 B 的子块乘法。
总 Miss 数公式： $\text{Total Misses} = (\frac{n}{B})^3 \times (2 \times \frac{B^2}{8}) = \frac{n^3}{4B}$
性能对比：
朴素算法 Misses： $O(n^3) \sim \frac{9}{8} n^3$
分块算法 Misses： $O(n^3 / B)$
结论：性能提升了 $B$ 倍（通常 B 可取 16~32 左右），这是一个巨大的优化。

分块算法将内存访问模式从“扫描全图”变成了“局部高频访问”。通过让数据在被驱逐出 Cache 之前被尽可能多地复用，极大地利用了时间局部性 (Temporal Locality)。
但是要求缓存大小大于三个块。

6.3 存储器山 (The Memory Mountain)

读吞吐量 (Read Throughput) 是 步长 (Stride) 和 工作集大小 (Working Set Size) 的函数。
我们可以画出一个三维图（山），山峰是 L1 Cache，山谷是 Main Memory。
优秀的代码应该尽可能停留在“山顶”（利用 L1 Cache）。

7. 总结 (Summary)

Cache 是透明的：硬件自动管理，程序员无需显式控制，但可以通过代码风格影响它。
局部性是关键：利用好时间局部性和空间局部性，你的程序就能飞快。
优化策略：
- 重新排列循环（如矩阵乘法的 ijk -> kij）。
- 使用分块技术 (Blocking) 处理大数据集。

CSAPP

#CSAPP

CSAPP - 08.MEM-02

https://yima-gu.github.io/2026/01/14/CSAPP/08-MEM-02/

作者

Yima Gu

发布于

2026年1月15日

许可协议

Network - 01.Application Layer 上一篇

CSAPP - 08.MEM-01 下一篇