12 KiB
第二章 缓存优化 - 各老师章节总结
曲冠南老师
授课主线概述
曲冠南老师的授课以"Cache性能分析与改进"为核心主线，首先回顾存储体系基础知识，奠定基本概念框架，进而深入分析Cache性能的两个关键指标——平均访存时间和程序执行时间，通过公式推导与实例计算帮助学生理解Cache对CPU性能的双重影响。随后系统性地介绍17种Cache优化技术，分别从降低不命中率、减少不命中开销、减少命中时间三个维度展开，形成完整的知识体系。
知识点展开
1. 存储体系基础与Cache性能分析
曲老师首先明确平均访存时间的基本公式：平均访存时间＝命中时间＋不命中率×不命中开销。这一公式是整个Cache优化理论的基础。在此基础上，进一步推导出程序执行时间公式：CPU时间＝（CPU执行周期数+存储器停顿周期数）×时钟周期时间，其中存储器停顿时钟周期数＝访存次数×不命中率×不命中开销。通过Alpha AXP机器的实例，详细计算了Cache命中与不命中情况下的CPI变化，揭示了一个重要结论：Cache对于低CPI、高时钟频率的CPU来说更加重要——因为固定周期数的Cache不命中开销在高时钟频率CPU中实际周期数更大。
在直接映像Cache与两路组相联Cache的对比分析中，曲老师引导同学关注一个容易被忽略的细节：虽然组相联能降低不命中率，但由于多路选择器的存在会使CPU时钟周期增加（本题中增加10%），因此需要综合评估，不能仅看单一指标。
2. 三种类型的不命中（3C）
曲老师详细讲解了三种不命中的产生原因及其特性：
- 强制性不命中：冷启动不命中，首次访问不命中，不受Cache容量和相联度影响
- 容量不命中：程序所需块不能全部调入Cache，受容量影响但不受相联度影响
- 冲突不命中：碰撞不命中，只在组相联或直接映像Cache中发生，相联度越高冲突不命中越少
这一分类为后续针对性优化提供了理论依据。
3. 降低不命中率的方法（8种）
针对三种不命中的直接方法：
- 方法一：增加块大小——可降低强制性不命中，但会增加冲突不命中和不命中开销
- 方法二：增加Cache容量——最直接方法，但增加成本和命中时间
- 方法三：提高相联度——以增加命中时间为代价，相联度超过8意义不大；2:1经验规则表明N容量的直接映像与N/2容量的两路组相联不命中率相当
其他方法：
- 方法四：伪相联Cache——逻辑上把直接映像Cache平分为两区，先按直接映像处理，若不命中再到另一区查找，兼得命中时间小和不命中率低的优点
- 方法五：硬件预取——指令和数据都可预取，需利用存储器空闲带宽，不能影响正常不命中处理
- 方法六：编译器预取——在编译时加入预取指令，以重叠执行；给出了完整的数组访问失效分析案例，详细计算了预取前后的失效次数变化（从251次降至19次）
- 方法七：编译器优化——无需改动硬件，通过软件优化（程序代码和数据重组）降低不命中率，包括数组合并、内外循环交换、循环融合、分块四种技术
- 方法八：牺牲Cache——设置全相联的小Cache存放被替换块，4项Victim Cache能使4KB直接映像Cache冲突不命中减少20%～90%
4. 减少不命中开销的方法（5种）
- 方法一：两级Cache——L1小而快，L2容量大；给出了完整的平均访存时间公式和每条指令平均停顿时间公式；区分局部不命中率与全局不命中率，全局不命中率是更有意义的指标
- 方法二：让读不命中优先于写——解决写缓冲器导致的问题，常用方案是检查写缓冲器内容
- 方法三：写缓冲合并——提高写缓冲器空间利用率，减少等待时间
- 方法四：请求字处理技术——尽早重启动或请求字优先，减少CPU等待时间
- 方法五：非阻塞Cache技术——允许"不命中下命中"，可重叠多次不命中；模拟研究表明对整数程序"一次不命中下命中"就几乎可获得所有好处
5. 减少命中时间的方法（4种）
- 方法一：小容量、结构简单的Cache——硬件越简单速度越快，标识检测和数据传送可同时进行
- 方法二：虚拟Cache——用虚拟地址访问，省去地址转换时间，清空问题和同义别名问题是挑战；虚拟索引＋物理标识可兼得两者好处，但受限于Cache容量≤页大小×相联度
- 方法三：Cache访问流水化——Pentium系列从1周期发展到4周期
- 方法四：踪迹Cache——存放动态指令序列，能提高指令Cache空间利用率，但地址映像机制复杂
李宏图老师
授课主线概述
李宏图老师的授课同样围绕Cache性能分析与改进展开，内容框架与曲冠南老师基本一致，但在部分表述和细节上有所补充和强调。李老师更注重基本概念的清晰界定（如不命中率与命中率的关系、局部不命中率与全局不命中率的区分），并在例题讲解中提供了更详细的中间步骤，便于学生理解计算过程。
知识点展开
1. 基本概念与公式
李老师首先明确命中率和不命中率的定义：不命中率（失效率）＝1-H（命中率），N1为访问M1的次数，N2为访问M2的次数。对于CPU访存时间的分析，当命中时访问时间为T1（命中时间），当不命中时访问时间为T1+TM，其中TM＝T2+TB为不命中开销。
平均访存时间公式：TA＝HT1＋（1－H）（T1＋TM）＝T1＋（1－H）TM＝T1＋FTM
CPU程序执行时间公式强调：存储器停顿时钟周期数＝"读"的次数×读不命中率×读不命中开销＋"写"的次数×写不命中率×写不命中开销。
2. Cache对CPU性能的双重影响
李老师同样通过Alpha AXP实例说明：CPIexecution越低，固定周期数的Cache不命中开销相对影响越大；时钟频率较高的CPU即使存储层次相同，不命中开销的周期数也较大。因此Cache对于低CPI、高时钟频率的CPU更加重要。
3. 三种不命中类型
李老师对3C的讲解与曲老师一致：强制性不命中（冷启动/首次访问）、容量不命中（程序所需块不能全部调入）、冲突不命中（碰撞/干扰）。强调：相联度越高冲突不命中越少；强制性不命中和容量不命中不受相联度影响；容量不命中随容量增加而减少。
4. 降低不命中率方法
李老师对8种方法的概括与曲老师一致，对部分方法提供了更详细的解释：
- 编译器优化中的循环融合：将访问同样数组的独立循环融合为单个循环，使数据在被替换前能得到反复使用
- 牺牲Cache：能减少冲突不命中，特别是对小容量直接映像数据Cache效果明显
5. 两级Cache系统
李老师给出了更系统的两级Cache平均访存时间公式：平均访存时间＝命中时间L1＋不命中率L1×（命中时间L2＋不命中率L2×不命中开销L2）
重点强调了全局不命中率的意义：它指出了CPU访存中最终到达存储器的比例，是评价第二级Cache的好指标。
在例题中，李老师更详细地展示了两种相联度方案下L1不命中开销的计算过程，并指出取整对结果的影响。
6. 写缓冲合并
李老师详细描述了写缓冲合并的工作过程：当写缓冲器已有待写入数据时，将新写入地址与已有地址比较，如有匹配且位置空闲则合并数据。这一机制提高了空间利用率，减少了等待时间。
7. 虚拟Cache
李老师补充了三种情况下不命中率的比较数据：PIDs与单进程相比增加0.3%～0.6%；PIDs与清空相比减少0.6%～4.3%。还提到了同义和别名问题的解决方法：反别名法和页着色。
谭婧炜佳老师
授课主线概述
谭婧炜佳老师的授课在内容上与前两位老师基本一致，但有一个显著特点：她在课程一开始就补充了存储体系的基础知识，包括多级存储层次结构的原理和Cache的三种映像规则（直接映像、全相联、组相联），这为后续内容提供了更完整的知识铺垫。谭老师同样从平均访存时间和程序执行时间出发，系统讲解Cache优化技术。
知识点展开
1. 存储系统基本矛盾与多级存储层次
谭老师开篇即指出存储系统设计的核心矛盾：容量大、速度快、价格低三者相互制约——速度越快每位价格越高，容量越大每位价格越低，容量越大速度越慢。解决方法是采用多级存储层次结构，利用程序访问的局部性原理：时间局部性（即将使用的信息就是现在使用的信息）和空间局部性（即将使用的信息与现在使用的信息在空间上相邻）。
多级存储层次结构的目标：从CPU来看，速度接近M1，容量和每位价格接近Mn。存储器越靠近CPU访问频度越高，最好大多数访问都在M1完成。
2. Cache三种映像规则
谭老师详细讲解了Cache的三种映像方式：
- 全相联映像：主存任一块可放置到Cache任意位置，空间利用率最高，冲突概率最低，实现最复杂
- 直接映像：主存每块只能放到Cache唯一位置（j＝i mod M），空间利用率最低，冲突概率最高，实现最简单
- 组相联映像：折中方案，主存每块放到唯一组的任意位置
3. 平均访存时间
谭老师给出了完整的平均访存时间公式：TA＝HT1＋（1－H）（T1＋TM）＝T1＋（1－H）TM＝T1＋FTM，并明确定义了不命中开销(miss penalty)TM为从向M2发出访问请求到把整个数据块调入M1中所需的时间。
4. 三种不命中类型
谭老师对3C的讲解中特别指出：容量不命中即使采用全相联映像+最优替换策略仍会失效。这一补充说明帮助学生更深入理解容量不命中的本质。
5. 降低不命中率方法
谭老师完整覆盖了8种方法，其中对编译器优化的四种技术（数组合并、内外循环交换、循环融合、分块）都给出了具体的代码示例。特别是分块技术，不仅给出了修改前后的代码，还分析了最坏情况下不命中次数从2N³＋N²降至2N³/B＋N²的变化。
6. 两级Cache系统
谭老师给出了两级Cache的完整性能分析公式，并强调了多级包容性的概念：第一级Cache中的数据是否总是同时存在于第二级Cache中。
7. 虚拟Cache的补充
谭老师补充了同义（synonym）或别名（alias）问题的说明：同一个数据在虚拟Cache中存在两个副本，操作系统或用户对同一物理地址采用两种以上不同形式虚拟地址访问，不允许存在否则会发生错误。
8. 踪迹Cache
谭老师指出踪迹Cache与普通Cache的区别：普通Cache存放静态指令序列，踪迹Cache存放动态指令序列。优缺点包括地址映像机制复杂、相同指令序列可能因条件分支不同选择而重复存放、能够提高指令Cache空间利用率。
三位老师内容对比总结
三位老师的授课内容基本一致，都围绕"Cache性能分析与改进"这一核心主题展开，主要差异体现在：
- 谭婧炜佳老师额外补充了存储体系基础知识（多级存储层次结构原理、三种Cache映像规则），更适合作为课程导入
- 曲冠南老师在伪相联Cache的例题分析中给出了更完整的公式推导
- 李宏图老师在例题中展示了更详细的中间计算步骤，便于学生理解
- 三位老师都给出了几乎相同的17种Cache优化技术列表和相似的总结表格