受害者缓存 / 路预测
用小容量辅助结构，在不牺牲命中时间的前提下降低冲突缺失
CS152 · 第 8 课
这是本学期第一场客座讲座。官方课程表把这一讲的录像放在 bCourses Media Gallery（需要校内权限，本站无法访问或转载），并注明"前一年度的幻灯片链接在下方"作为公开参考。以下内容忠实依据那份公开可得的替代幻灯片（Krste Asanovic 讲授，涵盖受害者缓存、路预测、非阻塞缓存与预取），覆盖与本讲同一主题范围，但不代表 Spring 2023 客座讲者当场讲述的确切内容。
一条关于资料来源的说明：本地保存的幻灯片文件名为 "Guest_Prefetching"，但其内部标题页实际写着"Lecture 7 – Memory III"，讲者为 Krste Asanovic，并非客座讲者本人的幻灯片。这与官方课程表在第 8 讲一栏的备注完全吻合："Recording on bCourses Media Gallery（slides from previous year are linked below）"——也就是说，官方页面本身就说明了当年客座讲座没有公开幻灯片，只提供前一年度的同主题幻灯片作为参考资料。本页因此如实使用这份可公开获取的替代材料，不臆测客座讲者当场使用的具体表述。
3C 缺失模型（强制性/容量性/冲突性）；写策略（写通/写回 × 按写分配/不按写分配）；流水化缓存写入；多级缓存的局部/全局缺失率与 MPI。
在一个直接映射缓存旁边加一个很小的全相联"受害者缓存"，专门保存最近被换出的行：先查直接映射缓存，缺失则查受害者缓存；如果命中受害者缓存，就把该行与刚刚被换出的行互换位置；如果受害者缓存也缺失，则直接映射缓存换出的行进入受害者缓存（受害者缓存自己换出的行去了哪里，原始幻灯片没有给出答案）。这样既保留了直接映射的快速命中时间，又能吸收一部分冲突性缺失。真实实现例子：HP 7200，配有 4 行的全相联受害者缓存。
用处理器地址索引一张"路预测表"，先只查预测的那一路（快速路径）；如果那一路缺失，再查另一路（较慢的命中，同时更新预测表），仍然缺失才真正向下一级缓存请求数据块。真实例子：MIPS R10000 的二级缓存；类 Alpha 21264 的指令缓存为顺序取指路径和预测跳转路径分别存储独立的预测"路"，从而支持每周期多指令取指且预测正确时"零分支代价"。
非阻塞（lockup-free）缓存允许数据缓存在一次未完成的缺失期间继续响应其他命中请求：命中穿越缺失（hit under miss）降低了有效缺失代价；命中穿越多重缺失 / 缺失穿越缺失（hit/miss under multiple miss）进一步允许多个未完成缺失重叠，但显著增加缓存控制器复杂度（需要支持多个未完成访存请求，可能出现对同一行的"二次缺失"）。真实例子：Pentium Pro 支持 4 个未完成访存缺失；Cray X1E 向量超级计算机支持多达 2,048 个未完成访存缺失——两者相差近 3 个数量级，直观体现了标量与向量机器在访存并行度需求上的巨大差异。
预取指在数据被真正需要之前，就推测性地把指令/数据取入缓存。指令访问通常比数据访问更容易预测。评价预取好坏的三个维度：有效性（是否真的能转化为命中）、时效性（既不能太晚也不能太早）、缓存/带宽污染。
软件预取：程序员/编译器显式插入类似 prefetch(&a[i+1]) 的指令。幻灯片明确指出："时机才是最大的难点，而不是可预测性"——预取太晚等于没用，太早则造成缓存污染；同时还要考虑预取指令本身的执行开销。
真实实验数据（Santhanam et al., 1997, HP PA8000）：随预取距离（1-10 行）变化的加速比曲线，从距离 1 的约 40% 加速，上升到距离 3 附近的峰值约 77%，之后逐渐回落到距离 7-10 附近的约 67%——这条曲线本身就是"预取太近没用、太远也不是越远越好"的实证。更细致的对比表格显示：当数据本来就已经在缓存中命中时，未经精简的预取指令会带来 -55% 的性能损失，而精简预取指令数量后这一损失收窄到 -13%——说明精简预取指令能显著降低（但不能完全消除）"预取了已经在缓存里的数据"这种浪费。
for(j){for(i){x[i][j]=2*x[i][j];}} 改写成 for(i){for(j){x[i][j]=2*x[i][j];}}——对行优先存储的数组而言，让最内层循环连续遍历内存，提升空间局部性a[i]=b[i]*c[i] 和 d[i]=a[i]*c[i] 的循环合并成一个循环体，让 a[i]/c[i] 在仍然驻留缓存时被复用，提升时间局部性（以上三个"这提升了哪种局部性"的问题，原始幻灯片本身没有给出文字答案，以上给出的解释是基于第 6 课局部性定义的合理推断，而非幻灯片原文直接陈述。）
问题 1：根据本讲内容，软件预取最大的难点是什么？
问题 2："Critical Word First"策略具体做了什么？
问题 3：Pentium Pro（4 个未完成缺失）与 Cray X1E 向量超算（2,048 个未完成缺失）之间的巨大差异说明了什么？
用小容量辅助结构，在不牺牲命中时间的前提下降低冲突缺失
不必等整行到齐即可继续执行，降低长行的有效缺失代价
命中穿越缺失、缺失穿越缺失，标量与向量机器需求量级差异巨大
时机是核心难点；硬件跨步预取、软件显式预取各有取舍
sp23/lecture_slides/L08_Guest_Prefetching.pdf（内部标注 "Lecture 7 – Memory III"，Krste Asanovic）