Notes/计算机科学/计算机专业课程/计算机系统结构/第二章-缓存优化/03_章节习题与答案详解.md

第二章 缓存优化 - 章节习题与答案详解

说明

经扫描三位老师（曲冠南、李宏图、谭婧炜佳）的全部PPT幻灯片内容，本章未发现独立的练习题、思考题或课后作业板块。三位老师在授课过程中均以"例题"形式讲解知识点，这些例题融合在教学流程中，具有习题功能。以下整理本章所有典型例题，供复习参考。

---

例题一：Alpha AXP机器Cache性能分析

原文摘抄

曲冠南老师 Slide 5、李宏图老师 Slide 7、谭婧炜佳老师 Slide 18（同一例题）：

例 用一个和Alpha AXP类似的机器作为第一个例子。假设Cache不命中开销为50个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是2.0个时钟周期，访问Cache不命中率为2%，平均每条指令访存1.33次。试分析Cache对性能的影响。

解 CPU时间有cache＝IC ×（CPIexecution＋每条指令的平均访存次数×不命中率×不命中开销）× 时钟周期时间 ＝IC ×（2.0＋1.33×2 %×50）× 时钟周期时间 ＝IC × 3.33× 时钟周期时间

考虑Cache的不命中后，性能为： 

　 CPU时间有cache ＝IC×（2.0＋1.33×2 %×50）×时钟周期时间 　 ＝IC×3.33×时钟周期时间 　　实际CPI ：3.33 　　　　　3.33/2.0 = 1.67(倍) 　　CPU时间也增加为原来的1.67倍。 　　但若不采用Cache,则： 　　　　　CPI＝2.0＋50×1.33＝68.5

参考答案及详细解析

考点： Cache性能对CPU执行时间的影响分析，涉及平均访存时间公式和CPU时间公式的理解与应用。

原理：

• 平均访存时间公式：平均访存时间＝命中时间＋不命中率×不命中开销
• CPU时间公式：CPU时间＝IC×（CPIexecution＋每条指令平均访存次数×不命中率×不命中开销）×时钟周期时间
• CPIexecution＝2.0（不考虑存储器停顿）

解题思路：

1. 已知条件：Cache不命中开销＝50周期，CPIexecution＝2.0，不命中率＝2%，平均每条指令访存1.33次
2. 计算有Cache时的CPI：CPI有cache＝2.0＋1.33×2%×50＝2.0＋1.33＝3.33
3. 计算性能提升倍数：3.33/2.0＝1.67，即CPU时间增为原来的1.67倍
4. 计算无Cache时的CPI：CPI无cache＝2.0＋50×1.33＝68.5（仅受存储器访问影响）

关键结论： Cache使CPI从68.5降到3.33，性能提升效果显著。

---

例题二：直接映像与两路组相联Cache性能对比

原文摘抄

曲冠南老师 Slide 7-9、李宏图老师 Slide 9-11、谭婧炜佳老师 Slide 20-22（同一例题）：

例 考虑两种不同组织结构的Cache：直接映像Cache和两路组相联Cache，试问它们对CPU的性能有何影响？先求平均访存时间，然后再计算CPU性能。分析时请用以下假设： (1)理想Cache（命中率为100%）情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.3次。 (2)两种Cache容量均为64KB，块大小都是32字节。 (3)在组相联Cache中，由于多路选择器的存在而使CPU的时钟周期增加到原来的1.10倍。这是因为对Cache的访问总是处于关键路径上，对CPU的时钟周期有直接的影响。 (4) 这两种结构Cache的不命中开销都是70ns。（在实际应用中，应取整为整数个时钟周期） (5) 命中时间为1个时钟周期，64KB直接映像Cache的不命中率为1.4%，相同容量的两路组相联Cache的不命中率为1.0%。

参考答案及详细解析

考点： 不同Cache组织结构对平均访存时间和CPU性能的影响分析，需要同时考虑不命中率降低和时钟周期增加两个因素。

原理：

• 平均访存时间＝命中时间＋不命中率×不命中开销
• 组相联Cache的时钟周期需乘以增加因子
• CPU时间比较需综合考虑CPI和时钟周期

解题思路：

1. 计算两种结构的平均访存时间：

   • 直接映像：2.0＋（0.014×70）＝2.98ns
   • 两路组相联：2.0×1.10＋（0.010×70）＝2.90ns

2. 计算CPU时间：

   • 直接映像：IC×(2.0×2＋(1.3×0.014×70))＝5.27×IC
   • 两路组相联：IC×(2.0×2×1.10＋(1.3×0.010×70))＝5.31×IC

关键结论： 虽然两路组相联Cache的不命中率更低（1.0% vs 1.4%），但由于时钟周期增加10%，其平均性能反而略差于直接映像Cache。这说明优化不能只看单一指标，需要综合评估。

---

例题三：伪相联Cache速度比较

原文摘抄

曲冠南老师 Slide 22-24、谭婧炜佳老师 Slide 36-38（同一例题）：

例 假设命中时间为1个周期，按直接映象找到的位置处没有发现匹配，而在另一个位置才找到数据（伪命中）需要2个额外的周期。问：当Cache容量分别为2 KB和128 KB时，直接映象、2路组相联和伪相联这三种组织结构中，哪一种速度最快？

参考答案及详细解析

考点： 伪相联Cache的平均访存时间计算，包括伪命中率、命中时间的计算。

原理：

• 伪相联Cache的平均访存时间公式：
  • 命中时间伪相联＝命中时间1路＋伪命中率×2
  • 伪命中率＝失效率1路－失效率2路
  • 失效率伪相联＝失效率2路
• 平均访存时间伪相联＝命中时间1路＋（失效率1路－失效率2路）×2＋失效率2路×失效开销

解题思路：

1. 分别计算2KB和128KB两种容量下三种结构的平均访存时间
2. 对于2KB Cache：
   • 伪相联：1＋（0.098－0.076）×2＋（0.076×50）＝4.844周期
   • 直接映像：5.90周期
   • 两路组相联：4.90周期
3. 对于128KB Cache：
   • 伪相联：1＋（0.010－0.007）×2＋（0.007×50）＝1.356周期
   • 直接映像：1.50周期
   • 两路组相联：1.45周期

关键结论： 伪相联Cache在两种容量下都是速度最快的，兼得了直接映像的快速命中和两路组相联的低失效率。

---

例题四：编译器控制预取分析

原文摘抄

曲冠南老师 Slide 27-31、李宏图老师 Slide 26-30、谭婧炜佳老师 Slide 41-45（同一例题）：

假定： (1) 使用一个容量为8 KB、块大小为16 B的直接映象Cache，它采用写回法并且按写分配 (2) a、b分别为3×100（3行100列）和101×3的双精度浮点数组，每个元素都是8B。当程序开始执行时，这些数据都不在Cache内。 对于下面的程序： for （ i = 0 ; i < 3 ; i = i + 1 ） for （ j = 0 ; j < 100 ; j = j + 1 ） a [ i ][ j ] = b[ j ][ 0 ] * b[ j+1 ][ 0 ];
问： （1）首先，判断哪些访问可能会导致数据Cache失效； （2）其次，加入预取指令以减少失效； （3）最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。

参考答案及详细解析

考点： 编译器控制预取的分析，包括判断失效类型、计算失效次数、设计预取策略。

原理：

• 分析程序访问模式，判断可能发生的失效类型（强制失效/容量失效/冲突失效）
• 预取通过提前将数据调入Cache来减少失效
• 预取指令应至少提前足够的循环次数进行

解题思路：

1. 分析失效类型： a和b共302块，少于Cache总块数，因此不会发生容量失效；直接映射且a和b连续存储，不会发生冲突失效；只能发生强制失效。

2. 分析命中和失效规律： 数组a共150块，每次访问均失效；数组b在i=0时失效101次，i=1和2时无失效；总失效次数为251次。

3. 加入预取后： 假设失效开销很大，预取必须至少提前7次循环进行。通过在循环中加入prefetch指令，总失效次数降至19次。

关键结论： 预取将失效次数从251次降至19次，避免了232次失效。但需注意预取指令本身也有开销，需保证开销不超过收益。

---

例题五：两级Cache性能分析

原文摘抄

曲冠南老师 Slide 45-46、李宏图老师 Slide 44-45、谭婧炜佳老师 Slide 60-62（同一例题）：

例 考虑某一两级Cache：第一级Cache为L1，第二级Cache为L2。 （1）假设在1000次访存中，L1的不命中是40次，L2的不命中是20次。求各种局部不命中率和全局不命中率。 （2）假设L2的命中时间是10个时钟周期，L2的不命中开销是100时钟周期，L1的命中时间是1个时钟周期，平均每条指令访存1.5次，不考虑写操作的影响。问：平均访存时间是多少？每条指令的平均停顿时间是多少个时钟周期？

参考答案及详细解析

考点： 两级Cache系统的性能分析，包括局部不命中率与全局不命中率的概念及平均访存时间计算。

原理：

• 局部不命中率＝该级Cache不命中次数/到达该级Cache的访问次数
• 全局不命中率＝该级Cache不命中次数/CPU发出的访存总次数
• 两级Cache平均访存时间＝命中时间L1＋不命中率L1×（命中时间L2＋不命中率L2×不命中开销L2）
• 每条指令平均停顿时间＝每条指令平均不命中次数L1×命中时间L2＋每条指令平均不命中次数L2×不命中开销L2

解题思路：

1. 计算不命中率：

   • L1不命中率（全局和局部）＝40/1000＝4%
   • L2局部不命中率＝20/40＝50%
   • L2全局不命中率＝20/1000＝2%

2. 计算平均访存时间：

   • 平均访存时间＝1＋4%×（10＋50%×100）＝1＋4%×60＝3.4时钟周期

3. 计算每条指令平均停顿时间：

   • 每次访存平均停顿＝3.4－1.0＝2.4时钟周期
   • 每条指令平均停顿时间＝2.4×1.5＝3.6时钟周期

关键结论： 全局不命中率比局部不命中率更有意义，它反映了最终到达存储器的访问比例。

---

例题六：第二级Cache相联度选择

原文摘抄

李宏图老师 Slide 48-49、谭婧炜佳老师 Slide 65-66（同一例题）：

例 给出有关第二级Cache的以下数据： （1）对于直接映像，命中时间L2 ＝ 10个时钟周期 （2）两路组相联使命中时间增加0.1个时钟周期，即为10.1个时钟周期。 （3）对于直接映像，局部不命中率L2 ＝ 25% （4）对于两路组相联，局部不命中率L2 ＝ 20% （5） 不命中开销L2 ＝ 50个时钟周期 试问第二级Cache的相联度对不命中开销的影响如何？

参考答案及详细解析

考点： 第二级Cache相联度选择对不命中开销的影响分析。

原理：

• 不命中开销L1＝命中时间L2＋不命中率L2×不命中开销L2
• 相联度增加会同时影响命中时间和不命中率

解题思路：

1. 直接映像第二级Cache的L1不命中开销：10＋25%×50＝22.5时钟周期
2. 两路组相联第二级Cache的L1不命中开销：10.1＋20%×50＝20.1时钟周期
3. 取整后再计算：10＋20%×50＝20.0 或 11＋20%×50＝21.0时钟周期

关键结论： 对于第二级Cache，两路组相联优于直接映像，因为不命中率的降低（25%→20%）带来的收益超过了命中时间的轻微增加（0.1周期）。

---

总结

本章共包含6道典型例题，覆盖了以下核心考点：

1. Cache性能对CPU执行时间的影响（例题一）
2. 不同Cache组织结构的综合性能评估（例题二）
3. 伪相联Cache的性能优势分析（例题三）
4. 编译器控制预取的原理与应用（例题四）
5. 两级Cache系统的性能分析（例题五）
6. 第二级Cache相联度的选择策略（例题六）

这些例题均以"例题"形式出现在授课内容中，体现了理论知识与实际计算的结合，是复习备考的重要参考。