Cache

主存容量大，但速度仍然比 CPU 慢得多。Cache 逻辑上位于 CPU 和主存之间（物理上通常集成在CPU内部），对于所有程序员和 OS 透明，用更快的 SRAM 保存主存中近期可能访问的数据副本，从而缓和 CPU 与主存之间的速度差距。

Cache 依赖的是局部性原理：

局部性	在 Cache 中的体现
时间局部性	刚访问过的主存块留在 Cache 中，短时间内再次访问时可命中
空间局部性	一次从主存调入整个块，后续访问相邻地址时可直接命中

Cache 与主存之间以块为单位交换数据。主存被划分为若干主存块，Cache 被划分为若干 Cache 行；一行 Cache 存放一个主存块的副本。

Note

“Cache 行”“Cache 块”常指同一个东西：Cache 中能容纳一个主存块的空间。

Cache 对于所有程序员和 OS 透明，即 **Cache 功能全部由硬件实现**。

现代处理器中的 Cache 常见两种组织特征：

组织方式	含义	作用
分离 Cache	将指令 Cache 和数据 Cache 分开，常记为 I-Cache 与 D-Cache	取指令和读写数据可以并行进行，减少结构冲突
多级 Cache	设置 L1、L2、L3 等多级 Cache，越靠近 CPU 越快、越小、越贵	用 L1 追求速度，用后续层级扩大容量，逐级缓冲 CPU 与主存的速度差

通常 L1 Cache 最靠近核心，容量最小、速度最快；L2、L3 容量更大但速度更慢。一次访问若在 L1 未命中，会继续查 L2、L3，仍未命中才访问主存。

Cache 行

一个 Cache 行不仅保存数据块本身，还要保存一些判断和维护状态所需的额外信息。

字段	作用	何时需要
数据块	保存主存块的副本	必有
标记 `Tag`	说明这一行当前保存的是哪个主存块	必有
有效位 `Valid`	说明这一行内容是否有效	必有
修改位 `Dirty`	说明这一行是否被 CPU 修改过但尚未写回主存	采用回写法时需要
替换控制位	记录替换算法所需状态	采用需要状态的替换算法时需要

地址划分

CPU 给出一个主存地址后，Cache 会把它解释成几段：

$$
\text{主存地址} = \text{Tag} + \text{Index} + \text{Block Offset}
$$

其中：

字段	含义
`Block Offset`	块内地址。块大小为 $B$ Byte 且按字节编址时，占 $\log_2 B$ 位
`Index`	行号或组号。用于定位可能命中的 Cache 行或组
`Tag`	标记。用于判断定位到的位置中保存的到底是不是目标主存块。比较器可以并行地比较 `Tag` 的每一位然后快速得出是否相等的结论。即比较器的位数由 `Tag` 决定。
如果主存是按字编址，块内地址位数要按“每块包含多少个字”计算；如果是按字节编址，块内地址位数按“每块多少 Byte”计算。

Index 和 Block Offset 都来自 CPU 地址，但它们不会作为 Cache 表项的元数据保存下来。Index 用来找到要查的行或组；Block Offset 用来在已经命中的数据块中选择字节或字。

Cache 表项除了一块的数据，真正额外保存的是 Tag、Valid、Dirty 以及替换控制位。见[[#Cache 行|前文]]。

映射方式

主存块调入 Cache 时，必须确定能放到哪里。这就是映射方式。

直接映射

直接映射中，每个主存块只能放入唯一的 Cache 行：

$$
\text{Cache 行号} = \text{主存块号} \bmod \text{Cache 行数}
$$

地址划分为：

$$
\text{Tag} \ |\ \text{Cache 行号} \ |\ \text{Block Offset}
$$

直接映射硬件简单，查找快，但冲突明显：如果两个频繁访问的主存块映射到同一行，它们会反复替换。

全相联映射

全相联映射中，一个主存块可以放入任意 Cache 行。地址中没有行号或组号，只有：

$$
\text{Tag} \ |\ \text{Block Offset}
$$

查找时需要把目标 Tag 和所有有效行的 Tag 比较。它减少了固定位置冲突，但比较硬件复杂，并且 Cache 满时一定需要替换算法决定换出哪一行。

组相联映射

组相联映射折中处理：Cache 被分成若干组，每组有若干行。主存块先映射到某一组，再放入该组内任意一行。

$$
\text{Cache 组号} = \text{主存块号} \bmod \text{Cache 组数}
$$

地址划分为：

$$
\text{Tag} \ |\ \text{组号} \ |\ \text{Block Offset}
$$

若每组有 $E$ 行，称为 $E$ 路组相联。因而比较器需要 $E$ 个。组内有多个候选位置，因此组内需要替换算法。

三种映射方式总览

映射方式	候选位置	地址字段	查找代价	冲突情况
直接映射	唯一 Cache 行	`Tag + 行号 + Block Offset`	最低，只查一行	最容易冲突
全相联映射	任意 Cache 行	`Tag + Block Offset`	最高，要比较所有行	固定位置冲突最少
组相联映射	唯一组内的任意一行	`Tag + 组号 + Block Offset`	介于两者之间，只比较组内各行	介于两者之间

Cache 命中过程

一次 Cache 访问可以按下面顺序理解：

CPU 给出主存地址。
用 Index 找到一个 Cache 行或一个 Cache 组。
检查候选行的 Valid 位。
比较候选行保存的 Tag 与地址中的 Tag。
若 Valid=1 且 Tag 相等，则命中；再用 Block Offset 取出块内目标数据。
若没有候选行满足条件，则未命中，需要从主存调入目标块。

命中不是只看行号或组号

Index 只负责缩小查找范围。真正判断是不是目标主存块，还要看 Valid 和 Tag。

# 替换算法

未命中时，如果目标行或目标组中还有空行，直接调入即可；如果已经满了，就要选择一个旧块换出。替换算法决定换出谁。

常见策略：

算法	思想	特点
FIFO	换出最早进入 Cache 的块	实现简单，但不关心最近是否使用
LRU	换出最久没有被访问的块	更贴近时间局部性，但需要维护使用次序
Random	随机选择一个块换出	硬件简单，行为不稳定

FIFO

FIFO 的关键是维护调入队列。某个块调入 Cache 时排到队尾；Cache 满后再发生未命中，就换出队头，也就是最早调入的块。命中时只说明这个块已经在 Cache 中，不会改变 FIFO 队列顺序。因此 FIFO 需要保存进入先后顺序，或维护等价的队列/指针状态。

FIFO 的执行过程

设 Cache 有 3 行，全相联，初始为空，采用 FIFO。访问块序列为 1, 2, 3, 1, 4, 2, 5, 1。

步骤	访问块	FIFO 队列，左侧最早进入	结果
1	1	`1`	未命中，调入 1
2	2	`1 2`	未命中，调入 2
3	3	`1 2 3`	未命中，调入 3
4	1	`1 2 3`	命中，队列顺序不变
5	4	`2 3 4`	未命中，换出 1
6	2	`2 3 4`	命中，队列顺序不变
7	5	`3 4 5`	未命中，换出 2
8	1	`4 5 1`	未命中，换出 3

命中 2 次，总访问 8 次。

LRU

LRU 的依据是时间局部性：最近使用过的块，短时间内更可能再次使用；最久没有使用的块，继续保留的价值最低。因此每次命中后，要把该块更新为“最近使用”；每次未命中且需要替换时，换出“最久未使用”的块。LRU 需要维护最近使用次序，精确实现时通常需要替换控制位。

Random

Random 不维护进入时间或最近使用顺序。发生未命中且候选位置已满时，随机选一个块换出。它的硬件代价低，但同一访问序列下可能得到不同的命中结果。Random 通常不需要为每个 Cache 行保存替换状态。

访问命中率

命中率就是访问命中的比例：

$$
\text{命中率} = \frac{\text{命中次数}}{\text{总访问次数}}
$$

计算时按访问顺序逐次模拟 Cache 状态：命中就计一次命中，未命中就调入目标块；如果候选位置已满，再按替换算法换出旧块。

一般步骤是：

把访问地址转换成主存块号。
根据映射方式确定访问的位置：直接映射定位到唯一行，组相联定位到某一组，全相联可放入任意行。
在候选行中查 Valid 和 Tag：Valid=0 表示该行不能合法访问，必未命中；Valid=1 且 Tag 相等才命中；Valid=1 但 Tag 不等，说明该行保存的是别的主存块，也未命中。
命中则命中次数加 1，并按替换算法更新状态。
未命中则把目标块调入 Cache；若有 Valid=0 的空行，优先放入空行；若候选位置已满，按[[#替换算法]]换出旧块。
最后用命中次数除以总访问次数。

访问序列的命中率

设 Cache 有 3 行，全相联，初始为空，采用 LRU。访问块序列为 1, 2, 3, 1, 4, 2, 5, 1。

步骤	访问块	访问后 Cache 状态，左侧最近使用	结果
1	1	`1`	未命中
2	2	`2 1`	未命中
3	3	`3 2 1`	未命中
4	1	`1 3 2`	命中
5	4	`4 1 3`	未命中，换出 2
6	2	`2 4 1`	未命中，换出 3
7	5	`5 2 4`	未命中，换出 1
8	1	`1 5 2`	未命中，换出 4

只有第 4 次命中，所以：

$$
H = \frac{1}{8}
$$

用循环顺序访问数组时要先判断访问序列会落到哪些主存块。块大小决定一次未命中能带来多少相邻元素。

同时，由于循环时下标只增不减，即序列中块的序号一定单调增加，替换算法对命中率没有影响。

若元素大小为 $s$ Byte，块大小为 $B$ Byte，则每块可容纳：

$$
k = \frac{B}{s}
$$

顺序扫描长度为 $n$ 的一维数组时，需要访问的主存块数为：

$$
\left\lceil \frac{n}{k} \right\rceil
$$

若 Cache 初始为空，且一个块在被连续访问完之前不会被替换，则每个块第一次访问未命中，块内其余元素命中。

顺序扫描一维数组

int a[1000000] 按地址连续存放，int 为 4B 且每个元素边界对齐，块大小为 64B，所以每个 Cache 块能放：

$$
k = 64 / 4 = 16
$$

顺序访问 a[0] 到 a[999999] 时，每 16 个连续元素属于同一个主存块。若 Cache 初始为空，且不会在同一块内访问期间被替换，则每块第一次访问未命中，后面 15 个元素命中。

未命中次数：

$$
\left\lceil \frac{1000000}{16} \right\rceil = 62500
$$

总访问次数为 $1000000$，命中次数为：

$$
1000000 - 62500 = 937500
$$

命中率：

$$
H = \frac{937500}{1000000} = 93.75%
$$

对每个元素读后再写

仍设 int a[1000000] 连续存放，int 为 4B 且每个元素边界对齐，块大小为 64B，每块 16 个 int。执行：

1 2	for (int i = 0; i < 1000000; i++) a[i] = a[i] + 1;

对每个 a[i]，先读旧值，再写新值。按“读一次、写一次”分别计算访问，总访问次数为：

$$
2 \times 1000000 = 2000000
$$

每个主存块第一次被读入时发生一次读未命中；同一块内后续读写都命中。需要访问的主存块数为：

$$
\left\lceil \frac{1000000}{16} \right\rceil = 62500
$$

若 Cache 初始为空，写命中采用回写法，且块不会提前被替换，则未命中次数为 $62500$，命中次数为：

$$
2000000 - 62500 = 1937500
$$

命中率：

$$
H = \frac{1937500}{2000000} = 96.875%
$$

每次同时访问相邻元素

执行：

1 2	for (int i = 0; i < 1000000; i++) a[i] = a[i] + a[(i + 1) % 1000000];

每轮至少涉及两次读和一次写：读 a[i]、读 a[(i+1)%1000000]、写 a[i]。仍设每块 16 个 int。除块边界处外，a[i] 和 a[i+1] 在同一块；当 $i= k \cdot 16 -1, k = 0,1,\dots$ 时，第二个读会跨到下一块。

全数组涉及的块数为：

$$
\left\lceil \frac{1000000}{16} \right\rceil = 62500
$$

顺序推进时，每个主存块第一次出现时未命中一次。最后一轮 i=999999 会访问 a[0]；块 0 已经被替换，因此再多 1 次未命中。

总访问次数：

$$
3 \times 1000000 = 3000000
$$

未命中次数约为：

$$
62500 + 1 = 62501
$$

命中率约为：

$$
H = \frac{3000000 - 62501}{3000000}
$$

行优先与列优先

int a[4096][4096] 按行连续存放，int 为 4B，块大小为 64B，即每块 16 个 int。

行优先访问时，地址基本连续：

1
2
3

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

总共访问：

$$
4096 \times 4096 = 16777216
$$

个元素。涉及的主存块数为：

$$
\frac{16777216}{16} = 1048576
$$

若块不会在同一块内连续访问期间被替换，则行优先访问未命中 $1048576$ 次，命中：

$$
16777216 - 1048576 = 15728640
$$

命中率为：

$$
H_{\text{row}} = \frac{15728640}{16777216} = 93.75%
$$

列优先访问时：

1
2
3

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

相邻两次访问 a[i][j] 和 a[i+1][j] 相隔一整行：

$$
4096 \times 4B = 16KB
$$

这个跨度远大于 64B 的块大小。对固定列 j 来说，连续访问的 4096 个元素几乎都落在不同主存块中。等访问下一列 j+1 时，理论上会再次用到上一列对应的那些块，但这要求 Cache 能在整整 4096 次跨行访问后仍保留这些块；如果 Cache 容量或映射方式做不到，列优先就会接近每次访问都未命中。

因此，在按行连续存放的二维数组中，行优先访问能充分利用空间局部性，命中率通常较高；列优先访问的步长是一整行，在大矩阵上很难利用一个 Cache 块内的相邻元素，若 Cache 不能保留下一列还要复用的那些块，命中率会明显下降，甚至接近每次访问都未命中。

# 写策略

读操作不会修改数据，因此读命中和读不命中主要影响是否需要调入块。写操作会改变副本内容，所以必须处理Cache 与主存的一致性。

写策略分两层：写命中时怎么做，写不命中时怎么做。

写命中

策略	做法	影响
全写法	同时写 Cache 和主存	主存始终较新，但写流量大，常配写缓冲
回写法	只写 Cache，并置 `Dirty=1`；块被替换时再写回主存	写流量少，但主存可能暂时不是最新值。需要额外的`Dirty`位

写不命中

策略	做法	常见搭配
写分配	先把主存块调入 Cache，再在 Cache 中写	常与回写法搭配
非写分配	不调入 Cache，直接写主存	常与全写法搭配

常见组合是：

组合	直观理解
回写法 + 写分配	既然后续可能继续改这个块，就先调入 Cache，以后多次写都先留在 Cache 中
全写法 + 非写分配	既然每次都要写主存，写不命中时可直接写主存，不必污染 Cache

Note

这两组是常见搭配，不是硬件上唯一可能的组合。若没有特别说明，通常按这两组理解。

平均访问时间

指标	含义
命中率 $H$	访问命中的比例
缺失率 $M$	$M = 1 - H$
缺失代价	未命中后访问下一级并调入块所需的额外时间

若先访问 Cache，未命中后再访问主存：

$$
T = Ht_c + (1-H)(t_c + t_m)
$$

也可写成：

$$
T = t_c + (1-H)t_m
$$

若 Cache 和主存同时访问，命中时立即停止主存访问，则模型会变成：

$$
T = Ht_c + (1-H)t_m
$$

使用公式前要先看清访问模型：是先查 Cache 再查主存，还是 Cache 和主存同时访问。

Cache 容量

Cache 的数据容量：能保存多少主存数据。

Cache 的总容量：Cache 数据容量 + 每行额外保存的控制信息。

位的类型	是否计入 Cache 总容量	计数方式
数据块位	计入	每行 $B \times 8$ 位
`Tag`	计入	每行一份
`Valid`	计入	每行一位
`Dirty`	回写法计入	每行一位
替换控制位	需要替换状态时计入	按每行或每组计算
`Block Offset`	不计入	它只在访问时用于选择块内位置，不作为表项元数据保存

三种替换算法对替换控制位的要求不同：

替换算法	是否需要替换控制位	说明
FIFO	需要	要记录块进入 Cache 的先后顺序，或维护等价的队列/指针状态
LRU	需要	要记录最近使用次序；精确 LRU 的状态通常比 FIFO 更多
Random	通常不按 Cache 行计入	不需要为每行保存进入时间或使用次序；若硬件使用随机数发生器，其开销通常不作为每行容量计算

总容量计算示例

主存地址 32 位，按字节编址；Cache 数据容量 32KB，块大小 64B，4 路组相联，采用随机替换算法和回写法。

Cache 行数：
$$
L = 32KB / 64B = 512
$$

组数：
$$
S = 512 / 4 = 128
$$

块内地址位数：
$$
\log_2 64 = 6
$$

组号位数：
$$
\log_2 128 = 7
$$

标记位数：
$$
32 - 7 - 6 = 19
$$

每行至少需要：
$$
64 \times 8 + 19 + 1 + 1 = 533\ bit
$$

Cache 至少需要：
$$
512 \times 533 = 272896\ bit
$$

这里没有把块内地址的 6 位乘进总容量，因为它不存放在 Cache 行中。