Cache 的基本原理

2026 大纲 三（六）1 Cache 的基本原理。

几千分之一的容量，凭什么能挡住绝大多数访存

CPU 时钟周期已进入亚纳秒级，DRAM 的访问时间还在百纳秒级——相差约两个数量级。办法是在 CPU 与主存之间插一层容量小、速度快的 SRAM，存放主存中部分内容的副本，这就是 Cache。

但这个方案初看很可疑：Cache 的容量只有主存的几千分之一，凭什么能显著提高命中率？换个比例更直观——把主存比作一整座图书馆，Cache 就是桌上能放几本书的位置。之所以够用，是因为程序访问存储器的行为高度集中：任一时刻真正活跃的地址范围（工作集）远小于整个地址空间。Cache 只需装下工作集，不必装下整个程序。

这就是局部性原理。Cache 同时利用了它的两面：把刚访问过的数据留下（时间局部性），并且一次调入一整块而不是一个字节（空间局部性）。

🔴 两种局部性的判据不同，结论也可能相反——不能因为一种好就推断另一种也好。顺序遍历一个大数组是最典型的"无时间局部性、有空间局部性"；反过来，按列遍历行优先存储的二维数组每次跨过一整行，调入的一整块里只用了一个元素，空间局部性被完全浪费。

后面几节的公式看着多，其实都挂在这一条上：命中率能不能推出来，取决于你能不能说清这段程序的访问模式踩中了哪种局部性、以及它的工作集和 Cache 容量比起来是大是小。

先动手看一眼

加载可视化中...

一、块与行

块（block）在主存一侧，是 Cache 与主存之间的信息交换单位；行（line，也叫槽 slot）在 Cache 一侧，是存放一个主存块的区域。两者空间都被划分成大小相等的区域，于是"以块为单位传输"有了确切含义：一次缺失调入的是一整块。这既是空间局部性的利用方式，也是后续所有地址划分的基础。

Cache 行里不只有数据，完整构成是：

[\underset{有效位}{\underset{⏟}{V}} \underset{标记}{\underset{⏟}{Tag}} \underset{数据块}{\underset{⏟}{Data}} \underset{脏位}{\underset{⏟}{(D)}} \underset{替换算法位}{\underset{⏟}{(\cdot)}}]

字段	为什么必须有	何时存在
有效位 V	系统启动或复位时 Cache 行里是随机内容，有效位标记这一行是否装入过有效数据	总是
标记 Tag	一个 Cache 行在不同时刻会装过不同的主存块，必须记录"现在装的是谁"	总是
数据块	从主存搬来的那一整块	总是
脏位 D	该行被写过、与主存不一致	仅写回策略
替换算法位	如 LRU 位	需要替换决策时

前两个字段合起来给出判命中的完整条件：

🔴 判命中 $=$ 有效位为 1 且标记相符，缺一不可。 上电后 Cache 行里是随机内容，只比标记完全可能碰巧匹配而把垃圾当成命中。反过来用，把某行的有效位清零就等于淘汰该行，称为冲刷（flush）——比真的去擦数据高效得多。

标记字段具体怎么从地址中切出来，见 Cache 和主存之间的映射方式。

二、访存流程

图 7.26　带 cache 的 CPU 的访存操作过程（袁春风《计算机组成与系统结构（第 3 版）》p236）

流程是三步：先判命中（有效位 $+$ 标记）；命中则直接从 Cache 读取、完全不访问主存；缺失则把该地址所在的整个主存块复制到 Cache，同时把所需数据送给 CPU。

图中虚线框内是缺失处理。注意最后一步的"同时"："把数据送 CPU"与"把整块装入 Cache"两条支路是并行的，不是先装满再从 Cache 转发给 CPU。

🔴 Cache 全程由硬件管理、对程序员完全透明。 它与虚拟存储器"缺页由操作系统介入"的分界，落在缺失代价的量级上：Cache 缺失只有几十到上百个时钟周期，软件处理的开销本身就超过缺失代价；缺页约 $10^{5}$ 个周期，多花几百个周期让 OS 做精细决策完全值得。

为什么要把指令 Cache 和数据 Cache 分开

现代 CPU 的 L1 通常是分离的：I-Cache 专给取指用，D-Cache 专给访存用。原因不在命中率，而在流水线：经典 5 段流水线里，IF 阶段要读指令、MEM 阶段要读写数据，而同一个时钟周期里流水线上同时有好几条指令——第 $k$ 周期可能是 I1 在 MEM、I4 在 IF。若只有一个统一 Cache，这两个阶段就要争用同一份 Cache 端口，构成典型的结构冒险（资源冲突），必须让一个等一拍。

拆成两个物理上独立、各有端口的 Cache 之后，IF 与 MEM 可以在同一周期并行访问，结构冒险消失。所以分离的主要目的是"减少指令流水线的资源冲突"，不是"提高命中率"也不是"降低缺失损失"——后两者至多是顺带的副作用。

三、命中率与平均访问时间

H = \frac{N_{c}}{N_{c} + N_{m}}, M = 1 - H

题目给的往往不是命中次数，而是一段访问模式，这时要从块的概念往回推。

顺序遍历：一块能装 $n =$ 块大小 $\div$ 元素大小个元素，每块只有首次访问缺失，所以

H = \frac{n - 1}{n} = 1 - \frac{1}{n}

值得留意的是这个结果完全没有依赖时间局部性——每个元素只读一次，仅靠空间局部性命中率就能到 90% 以上。

⚠️ 访存次数不能一律按 1 次算。 a[k] = a[k] + 32、a[i] = a[i]/x 这类"读改写"语句会编译成一读一写，一个元素访存 2 次。此时缺失率的分母要按访存次数算，不是按元素个数算——每块 4 个元素、每元素访存 2 次，8 次访存里只有 1 次缺失，缺失率是 $1 / 8$ 而不是 $1 / 4$ 。

步长跨块时结论可能变成 $H \approx 0$ ，但判据要说全：

🔴 $H \approx 0$ 的判据是工作集与 Cache 数据容量（行数 $\times$ 块大小）比。步长跨块 $\to$ 工作集大于容量 $\to$ 反复冲突替换 $\to$ 走一圈回来时先前调入的块已被换出。只说"跨步大、空间局部性差"是在描述现象，少了与容量比较这一环——工作集若小于容量，步长再大，第二遍遍历仍然全部命中。

两种模型，按题面描述选

Cache 与主存的配合方式有两种，对应两个公式：

条件的描述方式	模型	公式
"先访 Cache，未命中再访主存""缺失后从主存调入"	串行	$t_{a} = H t_{c} + (1 - H) (t_{c} + t_{m}) = t_{c} + (1 - H) t_{m}$
"同时访问 / 并行启动 Cache 和主存""命中则中止主存访问"	并行	$t_{a} = H t_{c} + (1 - H) t_{m}$
只给出「命中时间」和「缺失损失」	串行的等价形式	$t_{a} =$ 命中时间 $+$ 缺失率 $\times$ 缺失损失

差别在于：串行下缺失时访问 Cache 花掉的时间已经浪费了，还要再花一次主存时间；并行下缺失的代价里不含 Cache 时间。

🔴 第三行那个形式要看清"缺失损失"的定义：它是相对命中而言的额外开销。所以一次缺失的总代价 $=$ 命中时间 $+$ 缺失损失，不是只有缺失损失。

四、效率、加速比与多级 Cache

e = \frac{t_{c}}{t_{a}} (平均访问时间离 Cache 有多近), S = \frac{t_{m}}{t_{a}} (引入 Cache 后快了几倍)

现代 CPU 普遍设置 L1、L2 甚至 L3。多级公式与单级同构，只是把"未命中之后去主存"换成"未命中之后去下一级"。这里有一组记号必须分清：

记号	名称	含义
$H_{1}$	L1 命中率	在全部访问中 L1 命中的比例
$H_{2}$	L2 的局部命中率	在 L1 未命中的那些访问中，L2 命中的比例
$(1 - H_{1}) H_{2}$	L2 的全局命中率	在全部访问中由 L2 命中的比例

并行： t_{a} = H_{1} t_{c 1} + (1 - H_{1}) [H_{2} t_{c 2} + (1 - H_{2}) t_{m}]

串行： t_{a} = t_{c 1} + (1 - H_{1}) [t_{c 2} + (1 - H_{2}) t_{m}]

差别只在 $t_{c 1}$ 的位置：串行提到括号外（每次访问都先付一遍 L1 时间），并行乘在 $H_{1}$ 上（只有命中才计入）。

🔴 公式里代的一律是局部命中率 $H_{2}$ 。 若题面给的是 L2 的全局命中率 $G_{2}$ ，先还原 $H_{2} = G_{2} / (1 - H_{1})$ 再代。直接把 $G_{2}$ 当 $H_{2}$ 代进去，结果会整体偏小。

四组数字走查：命中率怎么从访问模式推出来、两个模型差的那一点点是什么、多级怎么代（想核对自己套公式会不会代错时展开）

（一）顺序遍历推命中率。 块大小 64 B，数组元素为 int（4 B），按存储顺序遍历：

n = 64 \div 4 = 16 ⟹ H = \frac{15}{16} = 93.75 %

每个元素只读一次，完全没有时间局部性，仅靠空间局部性命中率就有 93.75%。

（二）局部性被破坏。 Cache 8 行、块 64 B，数据容量 $8 \times 64 = 512$ B。某二维数组每行 1024 B，按列访问每次跨 1024 B：

1024 B > 512 B

走完一列回到起点时，先前调入的块早已被后续的块反复替换掉，于是每次访问都缺失， $H \approx 0$ 。关键的一环是与 Cache 数据容量比较——若工作集小于容量，即使步长很大，第二遍遍历仍然全部命中。

（三）两个模型差在哪。 $t_{c} = 10$ ns、 $t_{m} = 100$ ns、 $H = 0.95$ ：

并行： t_{a} = 0.95 \times 10 + 0.05 \times 100 = 14.5 ns; 串行： t_{a} = 10 + 0.05 \times 100 = 15 ns

两者相差 0.5 ns，正好是"缺失时白花的那次 Cache 访问时间" $(1 - H) t_{c} = 0.05 \times 10$ 。并行模型下 $e = 10 / 14.5 \approx 69 %$ 、 $S = 100 / 14.5 \approx 6.9$ 。

再看命中率的敏感性： $t_{c} = 5$ ns、 $t_{m} = 100$ ns、 $H = 0.98$ 时 $t_{a} = 6.9$ ns、 $S \approx 14.5$ ； $H$ 降到 0.90 则 $t_{a} = 14.5$ ns、 $S$ 只剩约 6.9。命中率的微小变化会被缺失代价放大。

（四）多级代入。 $t_{c 1} = 2$ ns、 $t_{c 2} = 10$ ns、 $t_{m} = 200$ ns、 $H_{1} = 0.9$ 、 $H_{2} = 0.8$ （局部），并行模型：

t_{a} = 0.9 \times 2 + 0.1 \times (0.8 \times 10 + 0.2 \times 200) = 1.8 + 4.8 = 6.6 ns

若题面给的是 L2 的全局命中率 $G_{2} = 0.08$ ，必须先还原成 $H_{2} = 0.08 / (1 - 0.9) = 0.8$ 再代入。

考点速记

Cache 存放主存内容的副本，依据是局部性原理；时间局部性看"同一单元是否重访"、空间局部性看"地址是否顺序推进"，两者分开判断、结论可能相反。
块是交换单位、行是 Cache 中存放一块的区域；判命中 $=$ 有效位为 1 且标记相符；缺失时整块调入，且"送 CPU"与"装入 Cache"并行；全过程由硬件管理、对程序员透明。指令 Cache 与数据 Cache 分离是为了消除流水线 IF 与 MEM 的资源冲突。
顺序遍历 $H = 1 - 1 / n$ ；工作集超过 Cache 数据容量则 $H \approx 0$ 。平均访问时间串行 $t_{a} = t_{c} + (1 - H) t_{m}$ 、并行 $t_{a} = H t_{c} + (1 - H) t_{m}$ ；多级公式代入的是局部命中率。

这一节在真题里被考过的形式（下方「真题练习」里属于本篇的那几道）：

给访存总次数与缺失次数，问命中率： $H = (N - N_{miss}) / N$ 。送分题，别把缺失率当命中率填进去。
问指令 Cache 与数据 Cache 分离的主要目的：答减少指令流水线的资源冲突（IF 与 MEM 同周期争用同一 Cache 端口是结构冒险）。"提高命中率""降低缺失损失""降低平均访存时间"都是干扰项。
给一段循环，问访问数组的缺失率：先算一块装几个元素得到"每几次访存缺失一次"，⚠️ a[k]=a[k]+32 是读改写、一个元素访存 2 次，分母要按访存次数算。
挑关于 TLB 与 Cache 的错误叙述：常设的错点是"都由 DRAM 组成"——两者都用 SRAM。
大题里问某程序段的数据访问是否具有时间局部性、为什么：分开判、给依据。只被顺序扫一遍的数组元素没有时间局部性，但按行优先顺序访问时空间局部性很好。
大题里给两个循环嵌套顺序相反的程序，问哪个命中率高：按行优先存储时，内层循环下标应当是变化最快的那一维；按列遍历每次跨一整行，工作集超过 Cache 容量就退化到几乎全缺失。
大题里由缺失率算平均访问时间或 CPU 执行时间：认清题面给的是"命中时间 + 缺失损失"还是" $t_{c}$ 与 $t_{m}$ "，前者用 $t_{a} =$ 命中时间 $+$ 缺失率 $\times$ 缺失损失。

易错：判命中只比标记不看有效位。上电后是随机内容，标记可能碰巧匹配。

易错：读改写语句按 1 次访存算，缺失率算成 2 倍。

易错：把"缺失损失"当成一次缺失的总代价。总代价 $=$ 命中时间 $+$ 缺失损失。

易错：多级 Cache 把全局命中率当局部命中率代入。先用 $H_{2} = G_{2} / (1 - H_{1})$ 还原。

易错：说"空间局部性差所以命中率约等于 0"而不与 Cache 容量比较。工作集小于容量时步长再大也会命中。

教材出处

袁春风《计算机组成与系统结构（第 3 版）》§7.5 高速缓冲存储器：块与行的定义、有效位与冲刷、图 7.26 带 cache 的访存过程（p236）
命中率、平均访问时间与多级 Cache：同上 §7.5.4

Cache 的基本原理

几千分之一的容量，凭什么能挡住绝大多数访存

先动手看一眼

一、块与行

二、访存流程

为什么要把指令 Cache 和数据 Cache 分开

三、命中率与平均访问时间

两种模型，按题面描述选

四、效率、加速比与多级 Cache

考点速记

相关知识

真题练习

相关真题（25题）

Cache 的基本原理 ​

几千分之一的容量，凭什么能挡住绝大多数访存 ​

先动手看一眼 ​

一、块与行 ​

二、访存流程 ​

为什么要把指令 Cache 和数据 Cache 分开 ​

三、命中率与平均访问时间 ​

两种模型，按题面描述选 ​

四、效率、加速比与多级 Cache ​

考点速记 ​

相关知识 ​

真题练习 ​

相关真题（25题）

Cache 的基本原理

几千分之一的容量，凭什么能挡住绝大多数访存

先动手看一眼

一、块与行

二、访存流程

为什么要把指令 Cache 和数据 Cache 分开

三、命中率与平均访问时间

两种模型，按题面描述选

四、效率、加速比与多级 Cache

考点速记

相关知识

真题练习