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

## 说明

经扫描三位老师（曲冠南、李宏图、谭婧炜佳）的全部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相联度的选择策略**（例题六）

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