一、替换策略深入分析：LRU vs MRU
1.1 回顾：几种替换策略
常见替换算法：
- FIFO：谁先进来谁先走。
- LRU（Least Recently Used）：通过计数器记录最近使用情况，最近最少使用的被替换。
- MRU（Most Recently Used）：替换掉最近刚使用过的块。
直觉上觉得 LRU 应该总是好的，因为数据有时间局部性和空间局部性。但深入到具体数据的时候，发现所有感觉上对的东西不一定对。
1.2 例题参数设定
| 参数 | 值 |
|---|---|
| 主存大小 | 32K 个字（15 位地址） |
| Cache 容量 | 4K，四路组相联 |
| 每块大小 | 64 字 |
| 主存总块数 | $32\text{K} / 64 = 512$ 块（$2^9$，块号 9 位） |
| 组数 | 16 组，每组 4 行 |
| 地址划分 | 字号 6 位 + 组号 4 位 + 标记 5 位 |
| Cache 比主存快 | 10 倍 |
访问模式：从地址 0 到 4351 顺序访问（共 4352 个字），即前 68 块，连续循环访问 10 次。
1.3 LRU 策略分析
第一次循环（块 0 ~ 67）：Cache 初始为空，所有 68 块全部 miss（冷启动缺失，compulsory miss）。第 0 组的 4 行依次装入块 0、16、32、48。当访问到第 64 块时，第 0 组已满，LRU 选择最久未用的块 0 替换掉。
第二次循环开始：再次访问块 0 时发现已被替换，miss。关键问题：68 块 > 64 行（Cache 容量），每次循环总有 4 块反复被替换。
命中率计算：总访问次数 $4352 \times 10 = 43520$ 字，冷启动 miss 68 次，后续 9 次循环中被替换的块每次第一个字都会 miss。最终命中率约 99.43%，速度提升约 9.5 倍。
1.4 MRU 策略分析
第一次循环同样 68 块全部 miss。关键区别在替换决策：当第 64 块进来时，MRU 替换掉刚用过的块 48（而非最久未用的块 0）。第二次循环访问块 0 时，块 0没有被替换，仍在 Cache 中，命中。访问块 1、2、…、47 都命中，到块 48 时 miss。
命中率更高，速度提升约 9.7 倍。
1.5 结论
别看只是从 9.5 倍提升到 9.7 倍，在明确的循环数据访问模式下，MRU 可能比 LRU 更优。Memory 命中率的微小提升对代码执行效率影响很大。
这个例子说明：直觉不一定靠谱，必须用具体数据验证。替换策略的选择取决于实际访问模式，没有绝对最优。当工作集略大于 Cache 容量时，LRU 会反复替换即将用到的数据，MRU 反而能保留更多有用数据。
二、Cache 写策略
2.1 问题引出
读操作简单——命中就读，不命中就调入。但写操作引发 Cache 与主存的一致性问题：写了 Cache 之后，主存中的数据就”过时”了。
2.2 Write Through（写直达/写穿）
每次写 Cache 时，同时写主存。优点：Cache 和主存始终保持一致，逻辑简单。缺点：写主存速度慢，CPU 每次写都要等主存完成。
Write Buffer 优化
加一个小的写缓冲队列（通常 4 项）：CPU 写数据先写到 Write Buffer，Buffer 告诉 CPU “写好了”，Buffer 在后台慢慢往主存写。如果 Buffer 满了，CPU 必须等待（stall）。怎么解决 Buffer 饱和？加二级 Cache。
2.3 Write Back（写回）
写时只改 Cache，不立即写主存。仅在 Cache 块被替换时，才把修改过的数据写回主存。需要增加 Dirty 位（脏位）：
| Dirty | 含义 | 替换时操作 |
|---|---|---|
| 0 | Cache 与主存一致 | 直接丢弃，用新数据覆盖 |
| 1 | Cache 已被修改 | 必须先写回主存，再加载新数据 |
2.4 写分配 vs 非写分配
当写操作发生 miss 时：
非写分配（No Write Allocate）
写 miss 时不调入 Cache，直接写主存。缺点：刚写的数据后续访问时 Cache 中没有，需要再从主存读入。
写分配（Write Allocate）
写 miss 时先把块调入 Cache，再在 Cache 中写。优点：利用数据局部性，后续访问该数据大概率命中。
对比例子：对同一地址先写后读 5 次——非写分配：4 次 miss + 1 次 hit。写分配：2 次 miss + 3 次 hit。
三、多核 Cache 一致性问题
3.1 问题描述
多个 CPU 各自有 Cache，共享一个主存。当一个 CPU 写了数据后，另一个 CPU 的 Cache 中还是旧数据。
3.2 两个容易混淆的概念
| 概念 | 含义 |
|---|---|
| Consistency（一致性） | Cache 与主存之间数据保持一致 |
| Coherence（一贯性/缓存一致性协议） | 多个 Cache 副本之间数据保持相同 |
解决方案需要设计复杂的一致性协议（如 MESI 协议），后续课程会详细讲解。
3.3 GPU vs CPU 的 Cache 差异
| CPU | GPU | |
|---|---|---|
| Cache | 设计复杂，追求高命中率 | Cache 很小，显存很大 |
| 任务特点 | 控制流复杂，数据依赖多 | 计算简单且高度并行 |
| 数据局部性 | 需要 Cache 支撑 | 流式处理，局部性差 |
| 多核协作 | 需要 Cache 一致性协议 | 主要靠共享显存 |
四、多级 Cache 设计
4.1 L1 Cache：分离式设计
L1 分为 I-Cache（指令缓存）和 D-Cache（数据缓存）。好处：指令和数据访问不冲突，数据带宽翻倍。L1 的设计目标：命中时间（Hit Time）尽可能短。
4.2 L2 Cache：统一式设计
L2 采用联合（统一）设计，指令和数据合并存放。原因：L2 miss 后要访问主存，代价极大，所以 L2 的命中率必须尽可能高。分开存放会使每块的 size 变小，导致命中率下降。L2 的设计目标：命中率（Hit Rate）尽可能高。
4.3 实际处理器 Cache 参数
Intel Core i7：
| 层级 | 容量 | 关联度 | 说明 |
|---|---|---|---|
| L1 | 32KB | 8 路组相联 | 分离式（I-Cache + D-Cache） |
| L2 | 256KB | 8 路组相联 | 每核独享 |
| L3 | 8MB | 16 路组相联 | 多核共享，负责与主存一致性 |
谁连主存谁辛苦——L3 是共享的，和主存之间的接口压力最大。
4.4 多级 Cache 性能计算例题
参数：无 Cache 缺失时 CPI = 1，CPU 频率 5GHz，访问主存时间 100ns = 500 个时钟周期，L1 缺失率 2%，L2 访问时间 5ns = 25 个时钟周期，L2 全局缺失率 0.5%。
只有 L1：有效 CPI = 1 + 0.02 × 500 = 11，性能下降约 11 倍。
加入 L2 后：有效 CPI = 1 + 0.02 × 25 + 0.005 × 500 = 4.0，性能损失降到约 4 倍（相比无 L2 时的 11 倍，大幅改善）。
与其花大力气做指令集并行、数据并行，不如把 Cache 做大一点、命中率提高一点，效果更直接。
五、Cache 大小与块大小的选择
5.1 Cache 容量
越大越好，但存在边际递减效应。从 256KB 到 512KB，成本翻倍但命中率提升很小。要根据性价比选择。
5.2 块大小（Block Size）
| 块大小 | 问题 |
|---|---|
| 太小 | 无法充分利用空间局部性，miss 率高 |
| 太大 | Cache 行数减少，替换频繁，miss 率反而上升 |
| 最佳 | 通常 32 ~ 64 字节（根据实验数据曲线确定） |
六、存储器带宽优化：三种组织方式
6.1 问题背景
Cache miss 后需要从主存读取一个 block（假设 4 个 word）。不同的主存组织方式对 miss penalty 影响很大。
基本参数：CPU 发地址到内存 1 个周期，内存访问时间 10 个周期，传输一个 word 1 个周期。
6.2 方案一：One Word Wide（单字宽）
每次只传 1 个 word，传 4 个 word 需要 4 次完整的访问-传输。Miss Penalty = 1 + 4 × (10 + 1) = 45 个周期。
6.3 方案二：Wide Memory（宽存储器）
把 memory 位宽加大为 4 个 word，一次全部取出。Miss Penalty = 1 + 10 + 1 = 12 个周期。优点：速度快。缺点：需要更宽的总线和更多芯片，花钱多。
6.4 方案三：Interleaved Memory（交叉存储/流水线方式）
利用数据访问的顺序性，在第一个 word 的 memory 准备过程中就开始发第二个 word 的地址，形成流水线式访问。Miss Penalty = 1 + 10 + 3 × 1 + 1 = 15 个周期。优点：代价小（不需要加宽总线），速度快。
| 方案 | Miss Penalty | 硬件成本 | 评价 |
|---|---|---|---|
| 单字宽 | ~45 周期 | 低 | 太慢 |
| 宽存储器 | ~12 周期 | 高 | 太贵 |
| 交叉存储 | ~15 周期 | 低 | 又快又省——最优 |
七、Cache 性能量化分析
7.1 核心公式
平均存储器访问时间（AMAT）： \(\text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}\)
CPU 时间： \(\text{CPU Time} = IC \times (CPI_{\text{execution}} + \text{Memory Stall Cycles per Instruction}) \times T_{\text{clk}}\)
其中： \(\text{Memory Stall} = \text{每条指令的存储器引用次数} \times \text{Miss Rate} \times \text{Miss Penalty}\)
7.2 CPU 时间计算例题
参数：缺失代价 200 个时钟周期，每条指令正常执行 1 个时钟周期，平均缺失率 2%，每条指令平均 1.5 次存储器引用。
Memory Stall per Instruction = 1.5 × 0.02 × 200 = 6 个周期。有效 CPI = 1 + 6 = 7。存储器停顿导致有效 CPI 从理想的 1 膨胀到了 7，性能下降 7 倍。
算法优化的重点不是把 100 次计算变成 80 次，而是提高访问存储器的命中率。
八、程序优化与 Cache 命中率
8.1 二维数组访问顺序的影响
对于按行优先存储的二维数组 A[i][j]：
- 按行访问（外层 i，内层 j）：访问顺序与存储顺序一致，空间局部性好，Cache 命中率高。
- 按列访问（外层 j，内层 i）：每次跳跃整行访问，空间局部性极差，频繁 miss。
8.2 命中率量化计算
参数：32 位机器，256MB 地址空间（$2^{28}$ 字节，按字节编址），指令 Cache 和数据 Cache 各 8 行，主存块大小 64B，直接映射。
地址划分：Block Offset 6 位，Index 3 位，Tag 19 位。
按行访问的命中率：共 64K 次访问，占 4K 个主存块。每个主存块的第一个元素 miss（compulsory miss），块内后续 15 个元素命中。命中率 = 1 - 4K/64K = 93.75%。
按列访问的命中率：如果数组跨越多个 Cache 行的映射范围，每次访问都可能 miss。极端情况下命中率可降至 0%。
代码逻辑完全相同，性能可以差一个数量级。数据布局和访问顺序是 Cache 优化的核心。
能把知识写出来才是真正学会了——会用 < 能给别人讲明白 < 能严谨地写出来。