1.3 Cache 是怎么工作的

一次访问的完整路径、缺失率怎么算，以及分块为什么能有效

学习目标

读完这一节，你应该能够：

画出一次内存访问从 L1 到主存的完整路径。
说清 Cache 是按"块"而不是按"字节"搬运，以及这带来的副作用。
用缺失率与缺失代价算出平均访问时间（AMAT）。
独立推算出矩阵乘分块前后的大致访存次数差异——这是本节的核心练习。

一、一次访问的完整路径

CPU 要读一个地址，硬件大致这样找：

CPU 发出地址
   │
   ├─→ L1 有吗？ ── 有 → 命中，约 4 个周期返回
   │      │
   │      └─ 没有
   ├─→ L2 有吗？ ── 有 → 约 13 个周期返回，并把块放进 L1
   │      │
   │      └─ 没有
   ├─→ L3 有吗？ ── 有 → 约 50 个周期返回，逐级往上放
   │      │
   │      └─ 没有
   └─→ 去主存取 ─── 约 250 个周期返回，逐级往上放

每往下一级，代价增加几倍到十几倍。所以 Cache 的核心目标只有一个：让尽可能多的访问在靠上的层级就被满足。

二、为什么按"块"搬运

Cache 从不按单个字节搬运，而是按固定大小的块（block，也叫 cache line），典型是 64 字节。

一个块能装 16 个 4 字节的 float。

为什么这么做？因为 1.2 节讲的空间局部性：程序访问了地址 x，很可能马上访问 x+4。既然迟早要用，不如一次搬一整块——搬运的固定开销（寻址、传输启动）就被摊薄了。

但这也带来一个副作用，它非常重要：

即使你只读 1 个字节，硬件也会搬回 64 个字节。

这直接解释了 1.2 节的步长问题：步长为 16（每个块只取 1 个 float）时，你用了 4 字节，却付出了 64 字节的代价——有效带宽只有峰值的十六分之一。

💡 记住这句话：Cache 的收益来自空间局部性，它的浪费也来自空间局部性被破坏。同一个机制，两种情况，方向相反。

三、地址是怎么被拆开的

Cache 需要回答一个问题："这个地址的数据，现在在我这儿吗？在的话在哪个位置？"

为此硬件把地址拆成三段：

字段	作用
标记（tag）	判断是不是我要的那一块
组索引（set index）	决定这块数据可能放在哪一组
块内偏移（block offset）	定位块内的具体字节

根据"一个地址可以放到哪些位置"，Cache 分为三种组织方式：

组织方式	规则	优点	缺点
直接映射	每个地址只能放唯一一个位置	硬件最简单、最快	两个地址抢同一个位置时会互相踢掉对方
组相联（N 路）	每个地址可以放在某组内的 N 个位置里	冲突大幅减少	需要比较 N 个标记、需要替换策略
全相联	可以放在任意位置	冲突最少	硬件最复杂、最贵

现代 CPU 的 L1 通常是 8 路或 16 路组相联。这是一个工程折中：路数越多冲突越少，但比较功耗和面积越高。

实际硬件里还有一个细节：L1 和 L2 常按虚拟地址索引，靠物理地址标记来保证正确性。这个细节对写代码的人基本不可见，知道有这么回事即可。

四、三类缺失，以及它们各自对应什么优化

这是本节最实用的一部分。缺失不是一种，是三种，而且每种对应不同的解法：

缺失类型	什么时候发生	怎么缓解
冷启动缺失（compulsory）	第一次访问某块数据，cache 里必然没有	无法避免，但可以通过预取隐藏
容量缺失（capacity）	工作集太大，cache 装不下，数据被挤出去	分块、降低工作集、压缩数据
冲突缺失（conflict）	工作集其实装得下，但多个地址映射到了同一组，互相踢	改变数据布局、填充（padding）、提高相联度

💡 诊断技巧：看到一个性能问题，先判断它是哪一类缺失。如果是容量缺失，改数据布局没用；如果是冲突缺失，减小数据集也没用。下错药是最常见的时间浪费。

五、替换与写策略

替换策略决定"要腾位置时，踢掉谁"。理想的策略是踢掉最久以后才会用到的那个，但硬件无法预知未来，所以用近似：

LRU（最近最少使用）：踢掉最久没被访问的。效果好，但精确实现成本高，实际用近似 LRU。
随机替换：实现简单，效果意外地不差，某些场景下用于避免病态访问模式。

写策略决定"写操作怎么办"：

策略	做法	取舍
写直达（write-through）	同时写 cache 和下一级	简单、一致性好，但写流量大
写回（write-back）	只写 cache，标脏；被踢出时才写回下一级	写流量小，但需要脏位，且一致性更复杂

配套的还有写分配和非写分配：写缺失时要不要先把那块搬进来。

对写代码的人来说，这些细节的实践意义是：写操作通常比读操作代价更高，而且不同硬件对写的行为差异更大。做性能敏感的代码时，读操作的分析更可靠。

六、AMAT：把缺失率变成时间

单个 Cache 的平均访问时间：

\text{AMAT} = t_{\text{命中}} + m \times t_{\text{缺失代价}}

其中 $m$ 是缺失率。多级 Cache 就是把这个式子递归展开：

\text{AMAT} = t_{L1} + m_{L1} \times \left( t_{L2} + m_{L2} \times \left( t_{L3} + m_{L3} \times t_{\text{主存}} \right) \right)

算一个例子（数字取典型量级）：

设 $t_{L1} = 4$ 周期， $m_{L1} = 5\%$ ； $t_{L2} = 12$ 周期， $m_{L2} = 20\%$ ； $t_{L3} = 50$ 周期， $m_{L3} = 50\%$ ； $t_{\text{主存}} = 250$ 周期。

先把从 L2 往下的部分合起来：

\text{AMAT}_{L2} = 12 + 0.2 \times (50 + 0.5 \times 250) = 12 + 0.2 \times 175 = 47 \text{ 周期}

再合进 L1：

\text{AMAT} = 4 + 0.05 \times 47 = 6.35 \text{ 周期}

从这个例子能看出两件事：

L1 缺失率哪怕只有 5%，也会让平均访问时间从 4 涨到 6.35 周期——涨了将近 60%。命中率的小变化会放大成性能的大变化。
靠上的层级权重最高。把 L1 缺失率从 5% 降到 2%，AMAT 降到约 4.94 周期；而在 L3 上做同样的相对改进，影响小得多。

七、分块（blocking）：本节的核心练习

现在把前面的东西用起来，解决一个具体问题：矩阵乘。

先看问题

计算 $C = A \times B$ ，三个矩阵都是 $N \times N$ 的 4 字节浮点数。取 $N = 1024$ ，于是每个矩阵 4 MB，三个一共 12 MB。

最直观的写法是三重循环：

for i in range(N):
    for k in range(N):
        a = A[i][k]
        for j in range(N):
            C[i][j] += a * B[k][j]

（注意这里把 k 放在 j 外面，是为了让最内层循环沿行连续访问——这是 1.2 节的准则一。循环顺序本身已经是一次优化了。）

数一数访存

关注矩阵 $B$ ：它的大小是 4 MB，装不进 L1（通常几十 KB），也常常装不进 L2。

外层每换一个 $i$ ，整行 $k$ 的循环都要把 $B$ 重扫一遍。
所以 $B$ 被从下层存储里重新取回的次数与 $N$ 成正比。

粗略地说， $B$ 的数据搬运量是 $O(N^3)$ 个元素：

1024^3 \times 4 \text{ 字节} \approx 4.3 \text{ GB}

分块之后

把三个矩阵都切成 $T \times T$ 的小块（取 $T = 64$ ，则每块 16 KB，三个块共 48 KB，正好能放进 L1 附近的容量）。

循环变成这样：

for ii in range(0, N, T):
    for kk in range(0, N, T):
        for jj in range(0, N, T):
            # 只在三个 T×T 的小块上做乘加，
            # 这三块能同时待在快存储里
            for i in range(ii, ii + T):
                for k in range(kk, kk + T):
                    a = A[i][k]
                    for j in range(jj, jj + T):
                        C[i][j] += a * B[k][j]

关键变化：现在 $B$ 的一个块被载入后，会在它被挤出去之前被用满 $T$ 次（外层每个 ii 用一次，共 $N/T$ 次块行迭代，而每次块内被复用 $T$ 遍）。

于是 $B$ 的搬运量变成：

O\left(\frac{N^3}{T}\right) \text{ 个元素} = \frac{4.3 \text{ GB}}{64} \approx 67 \text{ MB}

结论

写法	矩阵 B 的大致搬运量	相对值
三重循环	约 4.3 GB	64×
分块（T = 64）	约 67 MB	1×

运算次数完全没有变，搬运量降了大约 64 倍。

⚠️ 注意这里的模型是简化的：它假设了每级的容量与替换行为、忽略了真实的多级结构与预取。真实的加速比不会是 64 倍（因为瓶颈可能转移到别处，或者 $B$ 的一部分本来就被 L3 留住了）。但这个数量级的关系是真实的，第 1.6 节的实验能让你测到显著的差异。

💡 这就是分块的全部思想：与其反复把大矩阵从慢存储搬进来，不如把它切成能装进快存储的小块，在快存储里把它用够本。

八、与 AI Infra 的连线

1. 分块就是 tiling，就是 blocking，就是矩阵乘优化的全部核心。

你之后会反复看到这个词：GPU 上叫 shared memory tiling，编译器里叫 cache blocking，FlashAttention 里叫分块注意力。它们是同一个思想在不同层级上的实现。

2. FlashAttention 的本质就是"把分块用到注意力上"。

朴素注意力会生成一个 $N \times N$ 的中间矩阵（分数矩阵），并在计算过程中多次把它写回、读回显存。FlashAttention 把它分块，让每一块中间结果只待在片上快速存储里，从不回写到慢存储。用的正是本节第七节的逻辑，只是搬到了 GPU 的存储层次上。

3. 三类缺失给了你一张诊断表。

当你遇到一个"数据量并不大但很慢"的 kernel，先问：是容量缺失（数据放不下）还是冲突缺失（布局不好）？这个判断决定了你接下来改什么。

关键结论

一次访问会逐级往上找：L1 → L2 → L3 → 主存，每下一级代价增加几倍到十几倍。
Cache 按 64 字节的块搬运。这带来空间局部性的收益，也带来步长浪费的代价。
地址被拆成 标记 / 组索引 / 块内偏移；按可放置位置分为直接映射、组相联、全相联。
缺失有三类：冷启动、容量、冲突，各自对应不同的优化手段——先分类，再动手。
$\text{AMAT} = t_{\text{命中}} + m \times t_{\text{缺失代价}}$ ，多级递归展开。靠上层级的权重最高。
分块把 $O(N^3)$ 的搬运量降到 $O(N^3 / T)$ ，而运算次数不变。

自测问题

Cache 为什么按块搬运而不是按字节？这样做的收益和代价分别是什么？
一个步长为 16 的 float 遍历，每个 64 字节块只用掉 4 字节。这属于哪一类缺失？该改什么？
用第六节的数字，如果 $m_{L1}$ 从 5% 升到 10%，AMAT 变成多少？变化的比例是多少？
（核心） 用本节第七节的模型，如果块大小 $T$ 从 64 改成 32，矩阵 $B$ 的搬运量大约变成多少？如果改成 128 呢？为什么 $T$ 不能无限增大？
为什么"两个地址互相踢对方"这个问题在直接映射里更严重，在组相联里更轻？
你的程序处理 100 MB 数据时，改成按块处理就快了 3 倍。这属于哪一类缺失被解决了？