第4章 存储层次设计（缓存的艺术）
一、导读
1.1 本章学习目标
在本章结束时，你将能够：
- 理解存储层次结构的设计原理，掌握局部性原理（时间局部性和空间局部性）及其在存储设计中的应用
- 分析缓存的三种映射方式（直接映射、组相联、全相联）的命中率、访问延迟和硬件复杂度权衡
- 计算缓存的有效访问时间（AMAT），考虑命中时间、缺失率和缺失惩罚
- 理解虚拟内存的工作机制，包括页表结构、多级页表和 TLB 的设计
- 掌握缓存替换策略（LRU、FIFO、随机替换等）的原理和性能差异
- 了解预取技术和非阻塞缓存如何隐藏内存访问延迟
- 分析存储层次对程序性能的实际影响，包括缓存友好的编程技巧
1.2 为什么本章如此重要
存储层次是计算机体系结构中最能体现"平衡设计"思想的部分。处理器速度的增长远快于内存速度的增长——这一差距被称为"内存墙"（Memory Wall）。自 1980 年代以来，处理器频率每年增长约 50%-60%，而 DRAM 的访问延迟每年仅改善约 7%-10%。今天，一次主存访问可能需要 300 个以上的处理器时钟周期。
如果没有存储层次结构，处理器的强大算力将大量浪费在等待数据上。缓存（Cache）通过在处理器和主存之间插入一层或多层高速小容量存储器，利用程序的局部性将常用数据保持在靠近处理器的位置，从而大幅减少平均内存访问时间。现代处理器的 L1 缓存命中率通常可达 95% 以上，这意味着 95% 以上的内存访问只需 1-4 个时钟周期即可完成。
存储层次的设计对软件性能的影响是巨大的。一个缓存友好的程序可能比缓存不友好的程序快 10 倍以上，即使两者执行的指令数相同。矩阵乘法的不同遍历顺序、数组的行列存储方式、数据结构的内存布局，这些看似与处理器无关的编程决策，实际上通过影响缓存命中率而对性能产生深远影响。
从系统设计的角度看，存储层次也是成本优化的关键。如果所有存储都使用 SRAM（缓存技术），成本将高得不可接受；如果全部使用 DRAM（主存技术），性能将低得无法使用。存储层次通过在正确的层级放置正确容量的正确类型存储器，实现了性能和成本的最优平衡。
1.3 核心问题引导
在阅读本章时，请思考以下问题：
为什么缓存不能做得和主存一样大？容量、速度和成本之间存在怎样的权衡？
组相联缓存为什么比直接映射缓存的命中率更高？为什么不全用全相联？
什么是"缓存别名"（Cache Aliasing）问题？它在虚拟地址缓存和物理地址缓存中分别如何处理？
TLB 缺失的代价有多大？为什么需要多级页表？
为什么矩阵按列遍历（对行主序存储而言）会导致大量的缓存缺失？
预取技术能否完全消除内存延迟？它的局限性在哪里？
非阻塞缓存（Miss-Speculative 或 Hit-Under-Miss）如何提高指令级并行度？
二、核心概念详解
2.1 局部性原理与存储层次
局部性原理（Principle of Locality）是存储层次设计的理论基础。它指出程序在一段时间内倾向于重复访问一小部分地址空间。
时间局部性（Temporal Locality）：如果一个内存位置被访问了，那么在不久的将来它很可能再次被访问。典型的例子是循环中的变量——每次循环迭代都会访问循环控制变量和累加器。
空间局部性（Spatial Locality）：如果一个内存位置被访问了，那么它附近的内存位置很可能很快被访问。典型的例子是数组的顺序遍历——访问 a[i] 之后很可能访问 a[i+1]。
存储层次利用局部性原理，将最常用的数据放在最快（也最贵）的存储层，将不常用的数据放在较慢（也较便宜）的存储层。典型的存储层次从快到慢依次为：寄存器（0 延迟） -> L1 缓存（1-4 周期，32-64KB） -> L2 缓存（10-12 周期，256KB-1MB） -> L3 缓存（30-50 周期，数 MB 到数十 MB） -> 主存 DRAM（200-400 周期，数 GB 到数 TB） -> 磁盘/SSD（数百万周期）。
有效访问时间（Average Memory Access Time, AMAT）是衡量存储层次性能的关键指标：
AMAT = 命中时间 + 缺失率 x 缺失惩罚对于多级缓存：
AMAT = L1命中时间 + L1缺失率 x (L2命中时间 + L2缺失率 x L3缺失惩罚)设计目标是使 AMAT 最小化。这需要同时考虑每一级的命中时间（与缓存大小和 associativity 相关）、缺失率（与缓存容量、行大小和 associativity 相关）和缺失惩罚（与下一级存储的延迟相关）。
2.2 缓存映射方式
缓存映射决定了主存中的某个块（Block/Line）可以放在缓存的哪个位置。三种基本的映射方式在命中率和硬件复杂度之间做出不同的权衡。
直接映射（Direct Mapped）：每个主存块只能映射到缓存中的唯一位置。映射关系为：缓存索引 = 主存块号 mod 缓存行数。
直接映射的优点是硬件简单——只需要比较标签（Tag）即可判断命中，无需替换策略。缺点是冲突缺失（Conflict Miss）较多——即使缓存中有空闲位置，如果两个活跃块映射到同一行，也会反复缺失。
全相联（Fully Associative）：主存块可以放在缓存的任何位置。查找时需要将请求地址的标签与缓存中所有行的标签同时比较。
全相联的优点是冲突缺失为零（在容量允许的情况下），命中率最高。缺点是需要大量的比较器（Content-Addressable Memory, CAM），硬件开销大、功耗高、速度慢。全相联只适用于小容量缓存（如 TLB）。
组相联（Set Associative）：将缓存分为若干组（Set），每组包含 N 行（N-way associativity）。主存块映射到唯一的组，但可以在组内的任意一行中放置。映射关系为：组索引 = 主存块号 mod 组数。
组相联是直接映射和全相联的折中。2-way 组相联的冲突缺失比直接映射减少约 30%-50%，而硬件复杂度仅增加一倍。现代处理器的 L1 缓存通常使用 4-way 或 8-way 组相联，L2/L3 缓存使用 8-way 到 16-way 组相联。
研究表明，10-way 组相联已经可以接近全相联的命中率，因此更高的 associativity 带来的收益很小，不值得增加硬件复杂度。
2.3 缓存替换策略
当缓存缺失且目标组已满时，需要选择一个现有块进行替换。替换策略的目标是最大化未来的命中率。
最优替换（Belady's OPT / MIN）：替换未来最长时间不会被访问的块。这是理论上的最优策略，但需要预知未来的访问序列，无法实际实现。OPT 通常用作其他策略的性能上限参考。
最近最少使用（LRU, Least Recently Used）：替换最长时间未被访问的块。LRU 利用时间局部性，假设最近被访问的块在不久的将来还会被访问。
真正的 LRU 需要精确跟踪组内所有行的访问顺序。对于 N-way 组相联，精确 LRU 需要 N! 种状态（N 个块的排列），实现复杂度随 N 指数增长。因此，实际处理器通常使用近似 LRU：
伪 LRU（Pseudo-LRU）：使用树结构近似 LRU 行为，每行只需要 1 位状态。4-way 组相联的伪 LRU 只需要 3 位状态（一棵二叉树），远少于精确 LRU 的 4! = 24 种状态。
随机替换（Random Replacement）：随机选择一个块替换。实现最简单，性能在大多数情况下接近 LRU。某些场景下（如存在扫描访问模式）甚至优于 LRU。
LRU 的问题：LRU 对扫描访问模式（Scan Access Pattern）表现很差。当程序顺序遍历一个大于缓存的数组时，LRU 会不断替换刚加载的块，导致每次访问都是缺失。解决方案包括插入策略（新块插入到 LRU 位置而非 MRU 位置）和扫描检测机制。
2.4 虚拟内存与 TLB
虚拟内存为每个进程提供独立的地址空间，实现了内存保护、内存共享和内存扩展（使用磁盘作为虚拟内存的后端存储）。
虚拟地址到物理地址的翻译通过页表（Page Table）完成。页表将虚拟地址空间划分为固定大小的页（通常 4KB），每页映射到一个物理页帧（Page Frame）。页表存储在内存中，每次地址翻译需要额外的内存访问。
为了加速地址翻译，引入了 TLB（Translation Lookaside Buffer），即快表。TLB 是一个小型的全相联缓存，存储最近使用的虚拟页到物理页的映射。TLB 命中时，地址翻译只需 1 个周期；TLB 缺失时，需要遍历页表（多级页表可能需要 4 次内存访问），代价可达数百个周期。
多级页表（Multi-level Page Table）解决了页表过大的问题。32 位地址空间、4KB 页大小时，单级页表需要 2²⁰ = 1M 个条目，占用 4MB 内存。使用两级页表，外层页表只包含指向内层页表的指针，未使用的地址空间不需要分配页表，大幅减少了页表的内存占用。
现代 64 位处理器通常使用四级页表（如 x86-64 的 PML4 -> PDPT -> PD -> PT），支持 48 位虚拟地址空间（256TB）。TLB 通常采用分级结构：L1 TLB（小容量、低延迟，分为指令 TLB 和数据 TLB）和 L2 TLB（大容量、稍高延迟，统一 TLB）。
2.5 预取与非阻塞缓存
预取（Prefetching）是在数据被实际请求之前将其加载到缓存中的技术，目的是隐藏内存访问延迟。
硬件预取：由硬件自动检测访问模式并进行预取。最常见的硬件预取器是流预取器（Stream Prefetcher），它检测顺序访问模式并预取后续缓存行。更复杂的预取器可以检测跨步访问（Stride Access）和指针追逐（Pointer Chasing）模式。
硬件预取的关键挑战是准确性——错误的预取不仅浪费带宽，还可能驱逐有用的缓存行。预取应该在"足够早"（数据在被需要之前到达）和"不过早"（避免浪费带宽和驱逐有用数据）之间取得平衡。
软件预取：由编译器或程序员插入预取指令（如 x86 的 PREFETCH、ARM 的 PRFM）。编译器可以在循环中提前数个迭代插入预取指令，使数据在需要时已经在缓存中。软件预取的优点是精确（编译器了解程序语义），缺点是增加了代码量且预取时机需要仔细调整。
非阻塞缓存（Non-blocking Cache / Miss-Speculative Cache）：传统缓存在处理一次缺失时会阻塞所有后续访问。非阻塞缓存允许在处理缺失的同时继续服务后续的命中请求。
"命中在缺失之下"（Hit Under Miss）：允许缓存命中在缺失处理期间继续服务。这提高了 ILP，因为独立的内存访问不会因为前一个缺失而被阻塞。
"缺失在缺失之下"（Miss Under Miss）：允许同时处理多个缺失。这需要缓存具有多个缺失状态寄存器（MSHR, Miss Status Holding Register），每个 MSHR 跟踪一个进行中的缺失。现代处理器通常支持 8-16 个并发缺失。
非阻塞缓存对科学计算等具有大量独立内存访问的程序特别有效，可以将有效内存带宽提高 2-3 倍。
三、深入分析与讨论
3.1 缓存性能分析：AMAT 的实际计算
考虑一个具体的存储层次配置：
L1 缓存：32KB，4-way 组相联，64 字节行大小，命中时间 1 周期，缺失率 3%
L2 缓存：256KB，8-way 组相联，64 字节行大小，命中时间 10 周期，缺失率 10%（局部缺失率）
主存：延迟 200 周期
AMAT = 1 + 0.03 x (10 + 0.10 x 200)
= 1 + 0.03 x (10 + 20)
= 1 + 0.03 x 30
= 1 + 0.9
= 1.9 周期如果将 L1 缺失率降低到 2%（通过增大缓存或提高 associativity）：
AMAT = 1 + 0.02 x 30 = 1.6 周期性能提升 = 1.9 / 1.6 = 1.19，即 19% 的改进。
这个计算说明了几个重要观点：L1 缓存的缺失率即使只降低 1 个百分点，也能带来显著的性能提升；L2 缓存的缺失率对 AMAT 的影响相对较小（因为 L1 缺失率本身已经很低）；降低缺失惩罚（如使用更快的主存）同样有效但通常成本更高。
3.2 缓存一致性与多核存储
在多核处理器中，每个核心通常有私有的 L1 和 L2 缓存，共享 L3 缓存。这引入了缓存一致性问题：如果核心 A 修改了共享变量的值，核心 B 的缓存中可能还保存着旧值。
MESI 协议是最经典的缓存一致性协议。每个缓存行有四种状态：Modified（已修改）、Exclusive（独占）、Shared（共享）、Invalid（无效）。当一个核心写入共享数据时，协议通过总线嗅探（Bus Snooping）或目录（Directory）机制通知其他核心将其缓存行标记为无效。
缓存一致性协议的开销是不可忽视的。在高竞争场景下（多个核心频繁读写同一缓存行），一致性流量可能占据大量总线带宽，导致严重的性能下降。这种现象被称为"伪共享"（False Sharing）——两个核心修改不同的变量，但这些变量恰好在同一缓存行中。
解决伪共享的方法包括：调整数据结构使不同核心的变量不在同一缓存行中（Padding）、使用线程本地存储、减少共享数据的更新频率。
3.3 存储层次对编程的启示
理解存储层次对于编写高性能代码至关重要。以下是几个关键的编程实践：
数组遍历顺序：对于行主序（Row-major）存储的二维数组（如 C/C++），按行遍历比按列遍历的缓存友好性高得多。按行遍历时，相邻的内存访问是连续的，空间局部性极好；按列遍历时，每次访问跳跃一个行的宽度，可能导致大量缓存缺失。
// 缓存友好：按行遍历
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
sum += a[i][j]; // 连续访问
// 缓存不友好：按列遍历
for (int j = 0; j < M; j++)
for (int i = 0; i < N; i++)
sum += a[i][j]; // 跳跃访问数据结构的内存布局：将频繁一起访问的字段放在一起（结构体数组 AoS vs 数组结构体 SoA）。在 SIMD 向量化场景中，SoA 布局通常更优，因为它允许连续加载同一字段的不同元素。
循环分块（Loop Tiling/Blocking）：将大矩阵运算分成适合缓存的小块，减少缓存缺失。矩阵乘法的分块实现可以将性能提高数倍。
四、实践案例
4.1 Intel Core i7 的存储层次设计
Intel Core i7（Nehalem 微架构）的存储层次是一个经典的工程设计案例。
L1 缓存：每核心 32KB 指令缓存（8-way）+ 32KB 数据缓存（8-way），命中延迟 4 周期。指令缓存和数据缓存分离，避免了结构冒险。
L2 缓存：每核心 256KB，8-way 组相联，命中延迟 10 周期。L2 是每核心私有的，与核心同频运行。
L3 缓存：所有核心共享 4-8MB，16-way 组相联，命中延迟约 30-40 周期。L3 采用非阻塞设计，支持多个并发缺失。
TLB 层次：L1 数据 TLB（64 条目，4-way）和 L1 指令 TLB（128 条目，4-way），L2 统一 TLB（512 条目，4-way），L3 TLB（1024 条目，全相联）。多级 TLB 设计有效减少了 TLB 缺失的惩罚。
这个层次化设计使得 95% 以上的内存访问在 L1 完成（4 周期），4.5% 在 L2 完成（10 周期），不到 0.5% 需要访问 L3 或主存。有效 AMAT 约为 5-6 个周期。
4.2 矩阵乘法分块优化案例
考虑 1000x1000 矩阵乘法 C = A x B。朴素实现的三层循环：
for (int i = 0; i < 1000; i++)
for (int j = 0; j < 1000; j++)
for (int k = 0; k < 1000; k++)
C[i][j] += A[i][k] * B[k][j];B 矩阵按列访问（B[k][j] 中 k 递增），每次跳跃一行（4000 字节），远超缓存行大小。对于 32KB 的 L1 数据缓存，B 矩阵的工作集（1000 x 4 字节 = 4KB）虽然可以放入缓存，但由于 A 和 C 也在竞争缓存空间，实际缺失率很高。
使用分块优化（块大小 64x64）：
for (int ii = 0; ii < 1000; ii += 64)
for (int jj = 0; jj < 1000; jj += 64)
for (int kk = 0; kk < 1000; kk += 64)
for (int i = ii; i < ii+64; i++)
for (int j = jj; j < jj+64; j++)
for (int k = kk; k < kk+64; k++)
C[i][j] += A[i][k] * B[k][j];每个块的三个矩阵工作集为 3 x 64 x 64 x 4 = 48KB，接近 L1 缓存大小。块内访问具有良好的空间局部性，缓存缺失大幅减少。实测性能提升可达 5-10 倍。
五、常见误区与注意事项
误区一：缓存越大越好
错误理解：增大缓存总是能提高性能。正确理解：缓存增大确实可以降低缺失率，但收益递减。从 32KB 增大到 64KB 可能降低 5% 的缺失率，但从 8MB 增大到 16MB 可能只降低 0.5%。同时，更大的缓存意味着更长的访问延迟（因为信号传播距离增加）和更大的面积与功耗。设计者需要在容量和延迟之间找到平衡点。
误区二：全相联缓存是最好的选择
错误理解：全相联缓存命中率最高，所以应该使用全相联。正确理解：全相联缓存的查找需要与所有行同时比较标签，硬件开销随容量线性增长。对于大容量缓存（如 8MB L3），全相联的比较器面积和功耗是不可接受的。组相联在命中率和硬件复杂度之间提供了最佳的工程折中。
误区三：TLB 缺失不重要
错误理解：TLB 命中率总是很高，不需要关注。正确理解：TLB 缺失的代价极高——一次 TLB 缺失需要遍历多级页表，可能需要 4 次内存访问（数百个周期）。对于工作集超过 TLB 覆盖范围的大内存程序（如大型数据库、图处理），TLB 缺失可能成为性能瓶颈。使用大页（Huge Page, 2MB 或 1GB）可以增加 TLB 的覆盖范围，减少 TLB 缺失。
误区四：缓存对程序性能的影响只与硬件有关
错误理解：缓存性能完全由硬件设计决定，软件无法影响。正确理解：程序的内存访问模式对缓存性能有决定性影响。同样的硬件上，缓存友好的程序可能快 10 倍以上。数组遍历顺序、数据结构布局、循环分块等编程技巧可以显著改善缓存行为。
六、本章小结
存储层次设计是平衡速度、容量和成本的核心工程。局部性原理是存储层次的理论基础，通过在不同层级放置不同特性的存储器来逼近理想存储系统。缓存的三种映射方式在命中率和硬件复杂度之间做出不同的权衡，组相联是最常用的折中方案。替换策略影响缓存的长期行为，近似 LRU 是实际中最常用的策略。虚拟内存和 TLB 提供了内存抽象和保护，多级页表减少了页表的内存开销。预取和非阻塞缓存是隐藏内存延迟的有效技术。存储层次的理解对于编写高性能代码同样重要，数组遍历顺序和循环分块等编程技巧可以显著改善缓存行为。
七、思考题与练习
一个直接映射缓存有 1024 行，每行 64 字节。计算以下虚拟地址的缓存索引和标签（假设 32 位地址，12 位偏移）：0x12345678、0x12345878、0x12346678。哪些地址会相互冲突？
计算以下缓存配置的 AMAT：L1 缓存命中率 96%，命中时间 2 周期；L2 缓存命中率 85%，命中时间 12 周期；主存访问延迟 250 周期。如果将 L1 增大使命中率提高到 98%，AMAT 改善多少？
分析以下代码的缓存行为（假设 L1 数据缓存为 32KB，64 字节行大小，直接映射）：
int a[1024][1024];
for (int j = 0; j < 1024; j++)
for (int i = 0; i < 1024; i++)
a[i][j] = 0;估算缓存缺失次数，并提出优化方案。
解释为什么 4-way 组相联缓存的替换不能使用精确 LRU 的计数器方案（即每个行一个计数器）。提出一种伪 LRU 的实现方案。
比较 MESI 协议和 MSI 协议的区别。在什么场景下 MESI 的 Exclusive 状态能带来性能优势？
设计一个预取策略来优化链表遍历的缓存性能。链表节点分散在内存中，每个节点包含一个数据字段和一个指向下一个节点的指针。
分析大页（2MB Huge Page）对 TLB 性能的影响。如果程序的工作集为 500MB，使用 4KB 页和 2MB 页分别需要多少个 TLB 条目来覆盖整个工作集？