235 lines
12 KiB
Markdown
235 lines
12 KiB
Markdown
# 第二章 缓存优化 - 章节习题与答案详解
|
||
|
||
## 说明
|
||
|
||
经扫描三位老师（曲冠南、李宏图、谭婧炜佳）的全部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相联度的选择策略**（例题六）
|
||
|
||
这些例题均以"例题"形式出现在授课内容中，体现了理论知识与实际计算的结合，是复习备考的重要参考。 |