局部性、Cache 与主存¶
为什么小 cache 能代表大内存¶
程序访问并非均匀随机：
- 时间局部性：刚访问的数据很可能再次访问，如循环变量；
- 空间局部性：附近地址很可能很快访问，如顺序数组和连续指令。
cache 以块为单位搬运相邻字节，利用空间局部性；把近期块保留在快速层，利用时间局部性。若工作负载完全随机且工作集远大于 cache，命中率会显著下降。
层次结构¶
从程序员视角看，存储层次可排列为寄存器、L1、L2、末级 cache、DRAM 和 SSD，但它们并不是一条由硬件用同一种 miss 机制自动逐层查找的链。寄存器由指令显式访问，cache miss 通常由硬件逐级查到 DRAM；若虚拟页不在主存，则由缺页异常进入操作系统，再从 SSD 等后备存储调页。越靠上通常越快、越小、每位成本越高。
cache 上层保存下层对应块的副本；在写回策略下，dirty 块会暂时比下层副本更新。普通缓存访存先查近处 cache，miss 后再请求下级 cache 或 DRAM。
平均存储访问时间（AMAT）在一层 cache 模型下为：
若命中时间 1 ns、miss 率 5%、miss 惩罚 60 ns，则：
低 miss 率仍可能被巨大惩罚放大。
块、组与 tag¶
一个物理地址通常拆成：
若块大小为 \(B\) 字节，块内偏移位数是 \(\log_2B\)；若有 \(S\) 组，组索引位数是 \(\log_2S\)，其余是 tag。
最小完整例子¶
32 KiB cache、64 B 块、8 路组相联：
因此块内偏移 6 位，组索引 6 位。32 位物理地址剩余 20 位 tag。访问时用 index 选一组，并行比较 8 个 tag；命中 way 再由 offset 选择字节。
映射方式的权衡¶
- 直接映射：每块只能进一个位置，命中快、硬件小，但冲突多；
- 全相联：可放任意位置，冲突少，但要比较所有 tag；
- 组相联：限制在一组的若干 way，折中速度与冲突。
相联度提高会降低一部分冲突 miss，却增加比较器、功耗和命中时间。容量、块大小与相联度都不是越大越好。
三类 miss¶
- 强制 miss：块第一次被访问；
- 容量 miss：工作集超过 cache 总容量；
- 冲突 miss：容量足够，但映射限制让多个热块争同一位置。
增大块可利用空间局部性，却减少可容纳块数并增加无用数据传输。提高相联度缓解冲突，不能解决容量不足。
写策略¶
写直达同时更新 cache 和下层，状态简单但写带宽压力大，常配写缓冲。写回只改 cache 并标记 dirty，替换时才写下层，减少流量但控制更复杂。
发生写 miss 时，写分配先取整块再写，适合后续还会复用；非写分配直接写下层，适合流式写入。策略要和工作负载及一致性协议一起考虑。
替换与预取¶
组满时需选择牺牲块。LRU 试图替换最久未用者，路数大时精确维护昂贵，常用近似 LRU 或随机策略。预取器依据地址模式提前拉取数据，命中未来需求就隐藏延迟；预测错误则浪费带宽、污染 cache，甚至干扰其他核心。
主存并非“平坦数组”¶
DRAM 用电容保存位，需要刷新。访问先激活一整行到行缓冲，再读写列；命中已打开行比切换行更快。多个 bank 可并行处理请求，内存控制器会重排访问以提高吞吐。
因此地址映射和访问顺序会影响 bank 并行与行缓冲命中。顺序访问通常友好，随机大步长访问可能同时破坏 cache 和 DRAM 局部性。
自测¶
- 直接映射 cache 中两个热块反复冲突属于哪类 miss？
- 写回策略为何需要 dirty 位？
- 预取提升性能需要哪些条件，又可能伤害哪些共享资源？