bittern.cn
5计算机体系结构：构造式方法

存储层次

缓存的艺术

Cache虚拟内存TLB一致性

🎯 AI 时代的学习建议：不要只读理论。理解这一章的设计动机（为什么需要这个概念？）和边界条件（什么情况下会失效？）。当 AI 生成的代码涉及这些概念时，你能判断它是否用对了场景。AI 能帮你总结内容，但无法替代你亲手阅读、思考、建立直觉的过程。

第5章 存储层次（缓存的艺术） Memory Hierarchy: The Art of Caching

一、导读

1.1 本章学习目标

在本章结束时，你将能够：

  • 理解存储层次结构的设计原理，掌握局部性原理（时间局部性和空间局部性）如何使缓存技术成为可能
  • 分析和设计 Cache 的三种组织方式：直接映射、组相联和全相联，理解各自的优缺点和适用场景
  • 掌握 Cache 替换策略，包括 LRU、FIFO、随机替换等算法的原理和性能比较
  • 理解虚拟内存的工作机制，包括页表结构、地址翻译过程和多级页表的优化
  • 掌握 TLB（Translation Lookaside Buffer）的设计，理解它如何加速地址翻译过程
  • 分析多核系统中的缓存一致性问题，理解 MESI 等一致性协议的工作原理
  • 编写缓存友好的代码，能够识别和避免伪共享、缓存抖动等性能问题

1.2 为什么本章如此重要

存储层次是计算机体系结构中最具艺术性的设计之一。处理器速度的增长远远快于内存速度的增长，这一"内存墙"问题使得存储系统的设计成为决定系统整体性能的关键因素。现代处理器的时钟频率可以达到数 GHz，但主内存的访问延迟仍然在 50-100ns 左右，相当于数百个时钟周期。如果没有缓存技术，处理器将花费大部分时间等待内存数据，计算能力将严重浪费。

缓存的核心思想是利用局部性原理：程序在短时间内的内存访问往往集中在较小的区域。时间局部性指最近访问过的数据很可能再次被访问；空间局部性指访问某个地址后，很可能很快访问附近的地址。基于这两个特性，将频繁访问的数据存储在快速但容量小的缓存中，可以显著减少平均内存访问时间。

存储层次的设计还涉及到深刻的工程权衡。更大的缓存可以减少缺失率，但增加了访问延迟和硬件成本；更高的相联度可以减少冲突缺失，但增加了比较器和多路选择器的复杂度。这些权衡没有绝对的最优解，需要根据具体应用场景来选择。

从软件角度看，理解存储层次对于编写高性能程序至关重要。两个功能等价的程序，由于内存访问模式不同，性能可能相差数倍甚至数十倍。矩阵乘法中循环顺序的选择、数据结构布局的优化、NUMA 感知的编程，都依赖于对存储层次的深入理解。

1.3 核心问题引导

在阅读本章时，请思考以下问题：

为什么不能只用一种既快又大又便宜的存储器？存储层次设计的根本动机是什么？

直接映射 Cache 的主要缺点是什么？组相联 Cache 如何解决这个问题？代价是什么？

Cache 缺失可以分为哪几类（强制缺失、容量缺失、冲突缺失）？各自的优化策略是什么？

虚拟内存解决了什么问题？如果没有虚拟内存，操作系统和应用程序会面临哪些困难？

TLB 缺失的代价为什么特别高？如何减少 TLB 缺失率？

在多核系统中，为什么缓存一致性是一个难题？嗅探协议和目录协议各有什么优缺点？

什么是"伪共享"（false sharing）？如何在多线程编程中避免它？

二、核心概念详解

2.1 局部性原理与存储层次结构

局部性原理（Principle of Locality）是存储层次设计的理论基础。它包含两个方面：时间局部性（temporal locality）指最近被访问的数据在不久的将来很可能再次被访问；空间局部性（spatial locality）指访问某个内存地址后，很可能很快访问相邻的内存地址。

程序的行为通常表现出显著的局部性。循环结构导致时间局部性（循环变量和循环体内的数据被反复访问）；顺序访问数组导致空间局部性（连续访问相邻元素）；栈操作也表现出强烈的局部性（最近压栈的数据很可能首先被弹出）。

基于局部性原理，存储系统被组织为层次结构：

  • 寄存器：访问延迟约 0.5ns，容量约几十到几百个字节，与 CPU 核心同速
  • L1 Cache：访问延迟约 1-4 个时钟周期，容量 32-64KB，通常分为指令 Cache 和数据 Cache
  • L2 Cache：访问延迟约 10-20 个时钟周期，容量 256KB-1MB，通常每核独立
  • L3 Cache：访问延迟约 30-50 个时钟周期，容量 4-32MB，多核共享
  • 主内存（DRAM）：访问延迟约 50-100ns（约 200-400 个时钟周期），容量 8-128GB
  • 固态硬盘（SSD）：访问延迟约 50-200us，容量 256GB-4TB
  • 机械硬盘（HDD）：访问延迟约 5-10ms，容量 1-20TB

存储层次的核心指标是平均内存访问时间（AMAT）：

AMAT = 命中时间 + 缺失率 * 缺失代价

每一层的目标是最小化 AMAT。通过让大部分访问在高层缓存中命中，系统的平均访问时间可以接近 L1 Cache 的访问延迟，同时拥有接近主内存的容量。

2.2 Cache 的组织方式

Cache 的核心问题是如何组织数据，使得查找操作既快速又准确。当 CPU 发出内存地址时，Cache 需要快速判断请求的数据是否在缓存中（命中检测），如果命中则返回数据。Cache 的组织方式决定了命中检测的机制。

内存地址被分为三个字段：标记（Tag）、索引（Index）和块内偏移（Block Offset）。索引用于选择 Cache 中的特定行（set），标记用于在该行中确认数据是否匹配，块内偏移用于在缓存块（cache line）内定位具体的字节。

直接映射 Cache（Direct-Mapped Cache）：每个内存块只能映射到 Cache 中的一个固定位置。索引位数 = log₂(Cache 行数)。命中检测只需要比较一个标记。优点是硬件简单、速度快；缺点是冲突缺失率高（两个频繁使用的地址如果映射到同一行，会反复驱逐对方）。

地址: | 标记 (Tag) | 索引 (Index) | 块偏移 (Offset) |
Cache行: 有效位 + 标记 + 数据块
命中条件: 有效位=1 且 索引匹配 且 标记匹配

全相联 Cache（Fully Associative Cache）：内存块可以放在 Cache 的任意位置。没有索引字段，命中检测需要同时比较所有行的标记。优点是灵活性最高、冲突缺失率最低；缺点是比较器数量多（需要 O(n) 个比较器），硬件成本高，只适用于小容量 Cache（如 TLB）。

组相联 Cache（Set-Associative Cache）：直接映射和全相联的折中。Cache 被分为若干组（set），每组包含 k 行（k-way 相联）。内存块首先通过索引映射到特定组，然后可以在该组的任意一行中存放。命中检测需要在组内所有行中并行比较标记。

常见的配置有 2-way、4-way、8-way 和 16-way 相联。现代处理器的 L1 Cache 通常采用 8-way 相联，L2/L3 Cache 采用 4-16 way 相联。相联度越高，冲突缺失越少，但命中检测延迟和功耗也越大。

2.3 Cache 替换策略与写入策略

当 Cache 缺失且目标组已满时，需要选择一个现有块进行替换（驱逐）。替换策略的目标是最小化未来的缺失率。

最优替换（OPT/Belady）：替换未来最长时间不会被访问的块。这是理论最优策略，但需要预知未来的访问序列，无法在硬件中实现。它主要用于仿真中评估其他策略的性能。

最近最少使用（LRU, Least Recently Used）：替换最长时间未被访问的块。LRU 利用时间局部性，通常表现接近 OPT。但真正的 LRU 实现需要维护访问顺序信息，对于高相联度 Cache，硬件开销较大。近似 LRU（如伪 LRU）通过减少状态位来降低开销。

先进先出（FIFO）：替换最早进入 Cache 的块。实现简单（只需一个计数器），但不考虑访问模式，性能通常不如 LRU。

随机替换（Random）：随机选择一个块替换。实现最简单，性能出乎意料地接近 LRU（尤其在相联度较高时）。一些商用处理器（如某些 ARM 核心）使用随机替换以简化硬件。

写入策略决定了 CPU 写入 Cache 时的行为：

写直达（Write-Through）：写入 Cache 的同时写入下一级存储。优点是简单、数据一致性好；缺点是写入带宽需求大。

写回（Write-Back）：写入只修改 Cache 中的数据，标记为"脏"（dirty）。只有当脏块被替换时才写入下一级存储。优点是减少写入带宽；缺点是增加了复杂性（需要脏位），且在替换时可能产生额外的写入延迟。现代处理器普遍采用写回策略。

2.4 虚拟内存与页表

虚拟内存是现代操作系统的基础设施。它为每个进程提供一个独立的、连续的地址空间（虚拟地址空间），通过地址翻译机制将虚拟地址映射到物理地址。虚拟内存解决了几个关键问题：

进程隔离：每个进程拥有独立的虚拟地址空间，不能直接访问其他进程的内存，提供了安全和稳定性保障。

简化编程：程序员不需要关心物理内存的实际布局，可以使用连续的虚拟地址空间，操作系统和硬件负责映射到分散的物理页面。

内存共享：通过让多个进程的虚拟页面映射到同一物理页面，可以实现进程间的内存共享（如共享库）。

超售内存：虚拟地址空间的总量可以超过物理内存的大小，操作系统通过页面置换将不活跃的页面换出到磁盘。

地址翻译的核心数据结构是页表（Page Table）。页表记录了每个虚拟页（Virtual Page, VP）到物理页帧（Physical Page Frame, PPN）的映射关系。典型的页面大小为 4KB。

对于 32 位虚拟地址空间和 4KB 页面，有 2²⁰（约 100 万）个虚拟页。每个页表项（PTE）包含物理页帧号、有效位、保护位、脏位等，通常 4 字节。整个页表需要 4MB 内存，对于 64 位地址空间则更加庞大。

多级页表通过层次化结构减少页表的内存占用。以两级页表为例：虚拟地址分为页目录索引、页表索引和页内偏移三部分。页目录的每个条目指向一个页表，只有被使用的虚拟页范围才需要分配对应的页表。这种"按需分配"的策略可以显著减少页表的内存占用。

现代 64 位系统通常使用 4 级页表（x86-64）或 3 级页表（ARM 的 4KB 页面配置），甚至 5 级页表（用于支持更大的地址空间）。

2.5 TLB 与地址翻译加速

TLB（Translation Lookaside Buffer）是页表的缓存，用于加速地址翻译过程。如果没有 TLB，每次内存访问都需要先查询页表（可能需要多次内存访问），然后再访问实际数据，这将使内存访问延迟增加数倍。

TLB 通常采用全相联或组相联组织，容量为 32-1024 个条目。每个 TLB 条目包含虚拟页号（VPN）、物理页帧号（PPN）以及保护位、有效位等信息。地址翻译时，TLB 并行比较所有条目的 VPN 字段，如果命中则直接返回 PPN。

TLB 命中时间通常为 1-4 个时钟周期，远快于页表遍历（可能需要数十到数百个周期）。现代处理器的 TLB 命中率通常在 99% 以上。

TLB 可以分为指令 TLB（ITLB）和数据 TLB（DTLB），分别服务于指令获取和数据访问。更大的工作集可能导致 DTLB 缺失增加，影响性能。大页（Huge Pages, 2MB 或 1GB）可以减少 TLB 压力，因为同样大小的内存区域需要更少的 TLB 条目。

TLB 缺失处理分为两种情况：如果缺失的页面在物理内存中（TLB 条目被替换出去了），只需从页表中读取 PTE 并填入 TLB；如果页面不在物理内存中（页面错误/page fault），则需要操作系统介入，从磁盘读取页面到物理内存，更新页表，然后重新执行导致缺失的指令。页面错误的处理代价非常高（毫秒级），应尽量避免。

三、深入分析与讨论

3.1 Cache 性能优化：3C 模型分析

Cache 缺失可以用 3C 模型分类：

强制缺失（Compulsory Miss）：第一次访问某个块时必然发生的缺失，因为该块不在 Cache 中。强制缺失无法通过改变 Cache 组织来消除，只能通过预取（prefetching）来隐藏延迟。增大块大小可以减少强制缺失次数（因为每次从内存加载更多的数据）。

容量缺失（Capacity Miss）：由于 Cache 容量有限，无法容纳所有需要的块而导致的缺失。即使使用最优替换策略也会发生。增加 Cache 容量是减少容量缺失的直接方法，但受成本和功耗限制。

冲突缺失（Conflict Miss）：由于 Cache 的映射约束，多个块竞争同一组（set）导致的缺失。在直接映射 Cache 中最严重，随着相联度增加而减少。增加相联度或使用更好的替换策略可以减少冲突缺失。

实际优化中，可以通过性能分析工具（如 perf、cachegrind）来测量程序的缺失率，识别缺失热点，然后针对性地优化数据结构布局或访问模式。

3.2 多核缓存一致性与 MESI 协议

在多核处理器中，每个核心通常拥有私有的 L1 和 L2 缓存，共享 L3 缓存和主内存。当一个核心修改其缓存中的数据时，其他核心缓存中的同一数据副本就变成了过期数据。缓存一致性协议确保所有核心看到的内存值是一致的。

MESI 协议是最经典的缓存一致性协议。它为每个缓存行定义四种状态：

  • Modified（已修改）：数据只存在于当前核心的缓存中，且已被修改，与内存中的值不同
  • Exclusive（独占）：数据只存在于当前核心的缓存中，且未被修改，与内存中的值一致
  • Shared（共享）：数据可能存在于多个核心的缓存中，所有副本一致
  • Invalid（无效）：缓存行无效，不能被使用

状态转换由核心间的通信消息驱动。当一个核心要写入处于 Shared 状态的缓存行时，它需要先通知其他核心将该行置为 Invalid（称为"失效"操作），然后将自己的副本转为 Modified。这种通过嗅探（snooping）总线消息来维护一致性的方式称为嗅探协议。

嗅探协议适用于核心数量较少的系统（通常 8 核以下），因为总线带宽随核心数量增长而成为瓶颈。对于更大规模的多核系统，目录协议（Directory Protocol）通过维护一个记录每个缓存行被哪些核心共享的目录来减少通信开销。

3.3 缓存友好的编程实践

理解存储层次对于编写高性能程序至关重要。以下是几个关键的优化技术：

数组访问顺序：在 C/C++ 中，多维数组按行优先（row-major）顺序存储。按行遍历数组可以利用空间局部性，使 Cache 行中的连续数据被依次访问。按列遍历则会导致频繁的 Cache 缺失。

c
// 缓存友好：按行遍历
for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    sum += A[i][j];  // 连续访问内存

// 缓存不友好：按列遍历
for (int j = 0; j < N; j++)
  for (int i = 0; i < N; i++)
    sum += A[i][j];  // 每次跳跃 N 个元素

伪共享（False Sharing）：当两个线程修改同一缓存行中的不同变量时，会导致缓存行在两个核心之间反复传递，严重降低性能。解决方法是对齐数据结构，确保不同线程访问的变量不在同一缓存行中。

数据局部性优化：通过循环融合（将多个遍历同一数组的循环合并为一个）、分块（将大数组分为适合缓存大小的小块）等技术，可以提高数据的时间局部性和空间局部性。

四、实践案例

4.1 案例：矩阵乘法的缓存优化

矩阵乘法 C = A * B 是缓存优化的经典案例。朴素实现的三重循环按 i-j-k 顺序执行，对 B 矩阵的访问是按列的，导致大量 Cache 缺失。

分块（blocking/tiling）优化将大矩阵分为适合 L1 Cache 大小的小块，对每个小块执行乘法。这样，小块中的数据可以完全驻留在 L1 Cache 中，大幅减少缺失率。

c
#define BLOCK_SIZE 64  // 根据 L1 Cache 大小调整
for (int ii = 0; ii < N; ii += BLOCK_SIZE)
  for (int jj = 0; jj < N; jj += BLOCK_SIZE)
    for (int kk = 0; kk < N; kk += BLOCK_SIZE)
      for (int i = ii; i < ii + BLOCK_SIZE; i++)
        for (int j = jj; j < jj + BLOCK_SIZE; j++)
          for (int k = kk; k < kk + BLOCK_SIZE; k++)
            C[i][j] += A[i][k] * B[k][j];

实测表明，分块优化可以将矩阵乘法的性能提升 2-5 倍，具体效果取决于矩阵大小和缓存配置。

4.2 案例：TLB 缺失对性能的影响

一个典型的性能陷阱是处理大规模数据时 TLB 缺失率激增。例如，遍历一个 1GB 的数组（使用 4KB 页面需要 256K 个 TLB 条目），而处理器的 DTLB 只有 64-1500 个条目，将导致极高的 TLB 缺失率。

使用大页（2MB 大页只需 512 个条目覆盖 1GB 数据）可以显著减少 TLB 缺失。在 Linux 中，可以通过 hugetlbfs 或透明大页（THP）来使用大页。实测表明，对于大规模数据访问密集型应用，使用大页可以带来 10-30% 的性能提升。

五、常见误区与注意事项

误区一：认为更大的 Cache 总是更好。 更大的 Cache 减少缺失率，但也增加了命中时间（因为更大的 Cache 需要更长的信号传播路径）和功耗。此外，Cache 容量增加对容量缺失有效，但对冲突缺失的效果取决于相联度。最优的 Cache 设计需要在容量、相联度、命中时间和功耗之间取得平衡。

误区二：认为 Cache 对程序员不可见。 虽然 Cache 对程序员是"透明"的（不需要显式管理），但程序的内存访问模式直接影响 Cache 性能。两个功能等价的程序可能因为访问模式不同而有数倍的性能差异。编写缓存友好的代码是高性能编程的基本要求。

误区三：忽视写入操作对 Cache 性能的影响。 很多优化只关注读取性能，但写入操作同样重要。写回策略在替换脏块时会产生额外的写入延迟；伪共享会导致缓存行在核心之间反复传递。在多线程程序中，需要特别注意写入模式对缓存一致性的影响。

误区四：认为虚拟内存是"免费"的。 虚拟内存提供了强大的抽象，但地址翻译本身有代价。TLB 缺失需要遍历页表（可能多级），页面错误需要从磁盘读取数据。对于内存密集型应用，TLB 缺失和页面错误可能成为性能瓶颈。使用大页、优化数据布局、控制工作集大小都是减少虚拟内存开销的有效手段。

六、本章小结

本章深入讲解了存储层次结构的设计原理和关键技术。局部性原理是缓存技术的理论基础，存储层次通过在不同层级使用不同速度和容量的存储介质，实现了接近最快存储的访问速度和接近最大存储的容量。Cache 的三种组织方式（直接映射、组相联、全相联）在命中率和硬件复杂度之间提供了不同的权衡。虚拟内存通过页表实现地址翻译，为每个进程提供独立的地址空间。TLB 加速了地址翻译过程，是多级页表实际可用的关键。在多核时代，缓存一致性协议（如 MESI）确保各核心缓存的数据一致性。理解存储层次有助于编写缓存友好的代码，避免伪共享和 TLB 缺失等性能陷阱。

七、思考题与练习

一个 4-way 组相联 Cache，容量为 64KB，块大小为 64 字节。计算索引位数、标记位数和 Cache 行数。

解释直接映射 Cache 中的"抖动"（thrashing）现象。给出一个导致抖动的具体访问序列示例。

比较 LRU 和随机替换策略在不同相联度下的性能差异。为什么在高相联度下随机替换的性能接近 LRU？

画出 MESI 协议的状态转换图，标注每种转换触发的条件和通信消息。

分析以下代码的缓存访问模式，指出性能瓶颈并提出优化方案：

```c

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

B[j][i] = A[i][j];

```

计算一个两级页表系统的内存占用。虚拟地址 32 位，页面大小 4KB，每个 PTE 4 字节。如果 90% 的虚拟页面未被使用，实际页表占用多少内存？

解释为什么写回策略比写直达策略更适合现代处理器。写回策略有什么潜在风险？

研究 NUMA（非统一内存访问）架构的特点，分析它对多线程程序性能的影响以及相应的编程策略。

5/6存储层次
0%