第 6 章：存储器层次结构

主题：存储器层次结构 (The Memory Hierarchy)
目标：理解局部性、Cache 组织与失效行为；能从地址拆分和访问轨迹分析性能，并将 Cache 友好原则用于矩阵、Stencil 和科学计算内核。

1. 本章核心视角

处理器运算很快，数据移动却往往很慢。存储器层次结构用“小而快的上层存储”缓存“大而慢的下层存储”，以较低成本接近快速存储的访问体验。

flowchart TB
    A["寄存器<br/>最快、最小"] --> B["L1 Cache"]
    B --> C["L2 Cache"]
    C --> D["LLC / L3 Cache"]
    D --> E["主存 DRAM"]
    E --> F["SSD / HDD / 网络存储"]

一般而言，越靠近处理器，容量越小、延迟越低、每字节成本越高；越远离处理器，容量越大、延迟越高。

重点：程序通常不是“访问一个元素”，而是在搬运一个 Cache Line。性能优化的关键，是让被搬来的相邻数据尽量被真正使用。

2. 为什么需要层次结构

理想存储器同时拥有寄存器般的速度、磁盘般的容量和磁盘般的成本，但物理实现无法三者兼得。层次结构利用程序访问的局部性，使多数访问命中在较快层。

这一章关注 CPU Cache 与主存。虚拟内存把 DRAM 和磁盘组织为另一种层次结构，第九章会系统讨论。

3. 局部性：Cache 有效的根源

3.1 时间局部性

若一个数据项刚被访问，它不久后再次被访问的概率较高，则具有时间局部性 (Temporal Locality)。

int sum = 0;
for (int i = 0; i < n; ++i)
    sum += a[i];

变量 sum 在每轮循环中被反复使用，通常一直留在寄存器中。

3.2 空间局部性

若一个位置被访问，其附近位置不久后也被访问，则具有空间局部性 (Spatial Locality)。

for (int i = 0; i < n; ++i)
    sum += a[i];

C 数组连续存放，访问 a[i] 时载入的 Cache Line 还包含后续多个元素，因此顺序遍历通常高效。

3.3 局部性不是算法复杂度

两个都是 O(n) 的循环，Cache 行为可能完全不同：

/* 连续访问：空间局部性好 */
for (int i = 0; i < n; ++i)
    sum += a[i];

/* 大步长访问：每次可能只用到一条 Cache Line 的一个元素 */
for (int i = 0; i < n; i += stride)
    sum += a[i];

渐进复杂度描述工作量随规模的增长，局部性描述同样工作量在真实机器上的数据移动代价。两者都必须分析。

4. Cache 的基本组织

Cache 将下层存储划分为固定大小的块 (Block)，同时也称 Cache Line；将其中一部分块的副本保存在上层。

flowchart LR
    A["CPU 访问地址"] --> B["查找 Cache Set"]
    B --> C{"Tag 匹配且有效？"}
    C -->|"命中 Hit"| D["返回 Cache Line 中的数据"]
    C -->|"失效 Miss"| E["从下一层取整条 Block"]
    E --> F["必要时替换旧 Line"]
    F --> D

一个 Cache 可由三组参数描述：

总数据容量为 S × E × B，不包括 Tag、有效位与替换状态等元数据。

5. 地址拆分

设机器地址为 m 位，一个地址在 Cache 查找中被拆为：

┌──────────── Tag (t bits) ────────────┬ Set index (s bits) ┬ Block offset (b bits) ┐
│                                      │                    │                       │
└──────────────────────────────────────┴────────────────────┴───────────────────────┘

t = m - s - b

• Block offset：选择 Cache Line 内的具体字节；
• Set index：选择要查询的 Set；
• Tag：区分映射到同一 Set 的不同内存块。

访问时，硬件用 Set index 找到一组候选 Line，再比较 Tag 和有效位。命中后，再依据 Block offset 取出对应字节。

5.1 一个计算示例

假设 32 位地址、B = 64 B、S = 256、E = 4：

b = log2(64)  = 6
s = log2(256) = 8
t = 32 - 8 - 6 = 18

所以低 6 位是块内偏移，接下来的 8 位选择 Set，剩余 18 位为 Tag。注意：地址如何拆分只取决于当前 Cache 的 B 和 S，不取决于 E。

6. 三种映射方式

6.1 直接映射

直接映射 Cache 的 E = 1。每个内存块只能映射到唯一 Set：

优点是实现简单、命中判断快；缺点是两个频繁访问且映射到同一 Set 的块会互相驱逐，形成冲突失效。

6.2 组相联

组相联 Cache 的 E > 1。一个块仍只映射到一个 Set，但可放进该 Set 的任意 Line。它在硬件复杂度与冲突失效之间折中，是现代 CPU Cache 的常见形式。

6.3 全相联

全相联 Cache 只有一个 Set，任意块可放在任意 Line。冲突最少，但需要比较大量 Tag，硬件成本高；常见于容量较小的特定结构，例如某些地址转换缓存。

7. 命中、失效与替换

7.1 失效分类

常用的三类失效 (3C)：

在多核系统里还可能有一致性失效：其他核心修改了共享数据，本核心缓存副本失效。这与并发、Cache Coherence 相关，不应误归为普通 3C 失效。

7.2 替换策略

Set 已满且发生失效时，需要选一条 Line 驱逐。理想的 LRU (Least Recently Used) 驱逐最久未使用项，但高相联 Cache 中精确实现成本较高，实际硬件常采用近似 LRU、随机或其他策略。

软件不能依赖某种精确替换顺序。优化应减少不必要的工作集和冲突，而不是试图“骗过”某一代 CPU 的替换器。

8. 写操作策略

读失效只需取回所需 Block；写操作还涉及下层何时更新。

对于连续大数组的“只写一次、不再读取”，把整条 Line 读入后再覆盖可能浪费带宽；现代编译器或 Intrinsics 有时会使用 non-temporal store，但它需要准确的访问语义和测量支持。

9. Cache 性能指标

平均内存访问时间 (AMAT) 的基础模型为：

多级 Cache 中，L1 的失效代价包含继续访问 L2 的时间；L2 的失效再继续传播到 LLC 和 DRAM。AMAT 有助于估算趋势，但真实处理器的乱序执行、预取和多个未完成失效会使单个访问延迟与总程序时间并不一一对应。

10. 真实处理器的 Cache 层次

现代多核 CPU 通常每个核心私有 L1 指令 Cache 与数据 Cache，可能还有私有 L2；更低层 LLC 往往由多个核心共享。具体容量、相联度、是否包含上层数据，均依 CPU 型号而定。

flowchart TB
    C1["Core 0<br/>Registers"] --> L11["L1I / L1D"]
    C2["Core 1<br/>Registers"] --> L12["L1I / L1D"]
    L11 --> L21["Private or shared L2"]
    L12 --> L22["Private or shared L2"]
    L21 --> LLC["Shared LLC"]
    L22 --> LLC
    LLC --> DRAM["DRAM"]

不要把“L3 一定包含 L2”当作普遍事实。不同微架构可能采用 inclusive、exclusive 或 non-inclusive 策略，性能分析应以目标机器的文档和测量为准。

11. 矩阵访问与行优先布局

C/C++ 多维数组按行优先 (row-major) 排列：

double a[ROWS][COLS];
/* a[i][0], a[i][1], ... 在内存中连续 */

因此内层循环优先递增列下标通常更友好：

/* 好：连续读取 */
for (size_t i = 0; i < rows; ++i)
    for (size_t j = 0; j < cols; ++j)
        sum += a[i][j];

/* 差：跨行大步长读取 */
for (size_t j = 0; j < cols; ++j)
    for (size_t i = 0; i < rows; ++i)
        sum += a[i][j];

第二种写法不一定总慢：若数组很小，整块数据可留在 Cache；若编译器做了变换，差异也可能缩小。问题在于规模增长后，跨步访问更容易浪费每条 Cache Line。

12. 矩阵乘法与分块

朴素矩阵乘法的算法复杂度为 O(n^3)，但循环顺序决定访问局部性。

/* C[i][j] += A[i][k] * B[k][j] */
for (size_t i = 0; i < n; ++i)
    for (size_t j = 0; j < n; ++j)
        for (size_t k = 0; k < n; ++k)
            c[i][j] += a[i][k] * b[k][j];

在行优先布局中，b[k][j] 随 k 变化是跨行访问，通常不友好。交换 j 与 k 循环，可让 B 和 C 的内层访问更连续：

for (size_t i = 0; i < n; ++i)
    for (size_t k = 0; k < n; ++k) {
        double aik = a[i][k];
        for (size_t j = 0; j < n; ++j)
            c[i][j] += aik * b[k][j];
    }

12.1 分块 (Blocking / Tiling)

当矩阵大到无法同时装入 Cache 时，将矩阵划为小块，使一个子块在被驱逐前完成更多计算：

for (size_t ii = 0; ii < n; ii += BS)
    for (size_t kk = 0; kk < n; kk += BS)
        for (size_t jj = 0; jj < n; jj += BS)
            for (size_t i = ii; i < min(ii + BS, n); ++i)
                for (size_t k = kk; k < min(kk + BS, n); ++k) {
                    double aik = a[i][k];
                    for (size_t j = jj; j < min(jj + BS, n); ++j)
                        c[i][j] += aik * b[k][j];
                }

块大小 BS 受元素大小、Cache 容量、相联冲突、寄存器数量与多线程共享行为影响，不存在适用于所有机器的固定神奇数字。高性能 BLAS 库会进一步做多级分块、寄存器分块与 SIMD 微内核。

注意：上例展示访问思想。实际内核还要处理 C 初始值、边界块、对齐、向量化和数值验证。

13. 面向 Stencil 与仿真内核的局部性

二维或三维 Stencil 每次更新一个网格点，读取附近邻居。它的算术量有限，通常比矩阵乘法更接近内存带宽受限。

for (size_t i = 1; i + 1 < ny; ++i)
    for (size_t j = 1; j + 1 < nx; ++j)
        next[i][j] = 0.25 * (
            cur[i - 1][j] + cur[i + 1][j] +
            cur[i][j - 1] + cur[i][j + 1]);

对于船海工业仿真中的有限差分、有限体积和波场传播，可优先检查：

13.1 数组结构与结构体数组

若一个内核每次只需要速度分量 u，结构体数组 (AoS) 会连带搬入 v、w、压力等不需要字段；数组结构 (SoA) 更容易获得连续有效访问。

/* AoS */
struct Cell { double u, v, w, p; } cell[N];

/* SoA */
struct Field { double u[N], v[N], w[N], p[N]; } field;

AoS 对“一次需要同一单元全部字段”的操作也有优势。数据布局必须匹配热点访问模式，而不是机械追随某一种范式。

13.2 多线程：伪共享

不同线程写入彼此独立的变量，若变量恰好落在同一 Cache Line，仍会触发 Cache Line 在核心间反复失效，这称为伪共享 (False Sharing)。

Thread 0 写 counters[0] ─┐
                          ├─ 同一 Cache Line → 一致性流量
Thread 1 写 counters[1] ─┘

常见缓解方法是让线程写入独占的连续大区间、对独立频繁写变量做填充或对齐、并在最终阶段归约。填充会增加内存占用，应先用 Profiling 确认问题。

14. 预取、带宽与延迟隐藏

硬件预取器会识别规则的顺序或固定步长访问，提前把后续 Cache Line 拉近处理器。它对线性数组扫描很有效，对链表、哈希表、稀疏矩阵的间接寻址效果有限。

乱序执行和多条独立加载可以隐藏一部分内存延迟，但无法凭空增加 DRAM 带宽。对带宽受限的循环，减少传输字节数往往比增加算术操作更重要。

可用算术强度做初步判断：

• 算术强度低：优先考虑访存、数据复用与循环融合；
• 算术强度高：更可能受 SIMD 或计算吞吐限制；
• 真实传输字节数取决于 Cache 行为，不能只数源代码中的变量个数。

这与第五章的 Roofline 视角相连：性能上界由计算峰值与可用内存带宽共同决定。

15. 如何观察 Cache 行为

15.1 基础工具

perf stat -r 5 \
  -e cycles,instructions,cache-references,cache-misses \
  ./solver

不同 CPU 可用的事件名称和含义不同。通用 cache-misses 往往较粗略；需要分析 L1、L2、LLC 或带宽时，应查阅本机 PMU 事件并使用对应工具。

15.2 Cachegrind 与访问轨迹

Valgrind 的 Cachegrind 可用模拟方式统计指令和数据访问，适合教学与小规模对比：

valgrind --tool=cachegrind ./program
cg_annotate cachegrind.out.*

它不等同于真实硬件：现代预取、乱序、多核一致性和具体替换策略都难以完整模拟。它适合解释“访问模式是否明显变好”，不适合直接预测真实运行时间。

15.3 Cache Lab

CSAPP 的 Cache Lab 通常包括两部分：

转置的难点不在公式，而在读 A 与写 B 的访问如何映射到相同 Set。小块分块可使源块和目标块同时留在 Cache，显著降低冲突与容量失效。

16. 常见坑

17. 本章复习路线

flowchart LR
    A["掌握时间/空间局部性"] --> B["会拆分 Tag、Set、Offset"]
    B --> C["能手算命中、失效与替换"]
    C --> D["分析矩阵访问和分块"]
    D --> E["连接到 Stencil、带宽与多线程"]
    E --> F["用工具验证访问假设"]

本章最终应能回答：

1. 为什么 Cache 要以 Block 而非单个字节作为传输单位？
2. 给定 m、s、E、b，如何计算 Cache 容量并拆分地址？
3. 强制、容量与冲突失效分别意味着什么？
4. 为什么行优先语言中内层循环通常应遍历最后一维？
5. 分块为何能改善矩阵乘法或转置的性能？
6. 为什么一个 Stencil 内核常受内存带宽而非浮点峰值限制？
7. 多线程程序中，伪共享为何会让“互不写同一变量”的线程仍然变慢？