====== 第四章 高速缓冲存储器 ======

===== 4.1 Cache的基本概念 =====

==== 4.1.1 Cache的工作原理 ====

高速缓冲存储器（Cache）是介于CPU和主存之间的高速小容量存储器，用于解决CPU与主存之间速度不匹配的矛盾。

**Cache的基本思想**：

根据程序的局部性原理，将CPU近期最可能访问的数据和指令从主存复制到Cache中。当CPU访问存储器时，首先访问Cache，如果命中则直接访问Cache；如果不命中，则从主存中读取数据并调入Cache。

**Cache的工作流程**：

1. CPU发出访问地址
2. 地址变换机构将主存地址转换为Cache地址
3. 判断数据是否在Cache中（命中判断）
4. 如果命中（Hit），直接从Cache读取数据或向Cache写入数据
5. 如果不命中（Miss），从主存读取数据，同时调入Cache（可能替换某些块），然后访问Cache

**命中率与平均访问时间**：

**命中率（H）**：CPU访问Cache命中的次数占总访问次数的比例
H = Nc / (Nc + Nm)
其中Nc为Cache命中次数，Nm为主存访问次数

**平均访问时间（Ta）**：
Ta = H × Tc + (1-H) × (Tc + Tm) = Tc + (1-H) × Tm
其中Tc为Cache访问时间，Tm为主存访问时间

或者：Ta = H × Tc + (1-H) × Tm（假设命中时只访问Cache）

**Cache的性能提升**：

设主存访问时间为100ns，Cache访问时间为10ns，命中率为95%
平均访问时间 = 0.95 × 10 + 0.05 × 100 = 9.5 + 5 = 14.5ns
加速比 = 100 / 14.5 ≈ 6.9

==== 4.1.2 Cache的地址映射 ====

主存和Cache都划分为大小相等的块（行）。为了将主存块装入Cache，需要建立地址映射关系。

**直接映射**：

每个主存块只能装入Cache中唯一确定的位置。

映射公式：Cache行号 = 主存块号 mod Cache总行数

地址划分：
| 主存标记 | Cache行号 | 块内地址 |

优点：
- 实现简单，只需比较一次标记
- 硬件成本低

缺点：
- 冲突率高，即使Cache有空闲也可能发生冲突
- 可能导致频繁的替换，命中率下降

**全相联映射**：

主存块可以装入Cache的任意位置。

地址划分：
| 主存标记 | 块内地址 |

优点：
- 冲突率低，命中率高
- 空间利用率最高

缺点：
- 查找需要比较所有Cache行的标记
- 硬件复杂，成本高
- 速度慢

**组相联映射**：

直接映射和全相联映射的折中方案。Cache分成若干组，每组包含若干行。主存块映射到特定组，但可以在组内任意位置。

映射公式：组号 = 主存块号 mod 组数

地址划分：
| 主存标记 | 组号 | 块内地址 |

K路组相联：每组包含K个Cache行

优点：
- 冲突率低于直接映射
- 查找范围缩小到组内，硬件复杂度适中
- 是实际应用中最常用的映射方式

**三种映射方式的比较**：

**图4-1：Cache三种映射方式示意图**
{{https://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Cache_associativity_patterns.svg/800px-Cache_associativity_patterns.svg.png?direct|Cache映射方式：直接映射、组相联、全相联|600}}

| 映射方式 | 查找复杂度 | 命中率 | 硬件成本 |
|----------|------------|--------|----------|
| 直接映射 | 最低 | 较低 | 最低 |
| 全相联映射 | 最高 | 最高 | 最高 |
| 组相联映射 | 中等 | 较高 | 中等 |

===== 4.2 Cache的替换算法与写策略 =====

==== 4.2.1 替换算法 ====

当Cache已满且需要装入新块时，需要选择一个块替换出去。常用的替换算法有：

**随机法（Random）**：
随机选择要替换的块。
- 优点：实现简单
- 缺点：未考虑访问局部性，命中率可能较低

**先进先出法（FIFO）**：
替换最早装入Cache的块。
- 优点：实现简单，符合公平原则
- 缺点：未考虑访问频率，可能替换经常访问的块

**最近最少使用法（LRU）**：
替换最久未被访问的块。
- 优点：符合局部性原理，命中率较高
- 缺点：硬件实现复杂，需要记录访问历史

LRU的近似实现：
- 为每行设置使用位，访问时置1
- 需要替换时，按顺序找第一个为0的项
- 所有位都为1时，全部清零重新开始

**最不经常使用法（LFU）**：
替换访问次数最少的块。
- 需要计数器记录访问次数
- 新装入的块可能很快被淘汰

==== 4.2.2 写策略 ====

Cache的写操作需要保持Cache和主存的一致性，常用的写策略有：

**写直达法（Write Through）**：
写操作时同时写入Cache和主存。
- 优点：数据一致性好，实现简单
- 缺点：写操作速度慢（需要等待主存）
- 优化：使用写缓冲区，CPU只需写入Cache和缓冲区，由缓冲区异步写入主存

**写回法（Write Back）**：
写操作时只写入Cache，当Cache块被替换时才写回主存。
- 优点：写操作速度快，减少主存访问次数
- 缺点：数据一致性差，需要设置脏位（修改位）标记是否修改过
- 脏位：1表示修改过，替换时需写回；0表示未修改，可直接丢弃

**写策略的比较**：

| 特性 | 写直达 | 写回 |
|------|--------|------|
| 可靠性 | 高 | 低 |
| 与主存通信量 | 多 | 少 |
| 控制复杂度 | 简单 | 复杂 |
| 应用 | 单处理器 | 多处理器 |

**写不命中时的策略**：

**写分配法（Write Allocate）**：
写不命中时，先将数据块从主存装入Cache，然后再写入Cache。
通常与写回法配合使用。

**非写分配法（No Write Allocate）**：
写不命中时，直接写入主存，不调入Cache。
通常与写直达法配合使用。

===== 4.3 Cache的改进技术 =====

==== 4.3.1 多级Cache ====

为了进一步提高性能，现代计算机普遍采用多级Cache结构。

**两级Cache结构**：
- L1 Cache：位于CPU芯片内部，速度最快，容量最小（通常32-64KB）
- L2 Cache：可以是片内或片外，容量较大（通常256KB-几MB）

**三级Cache结构**：
- L1 Cache：分指令Cache和数据Cache（哈佛结构），容量16-64KB
- L2 Cache：统一的Cache，容量256KB-512KB
- L3 Cache：多核心共享，容量几MB-几十MB

**多级Cache的平均访问时间**：

对于两级Cache：
Ta = H1 × T1 + (1-H1) × [H2 × T2 + (1-H2) × Tm]
其中H1、H2分别为L1、L2的命中率，T1、T2为访问时间，Tm为主存访问时间

==== 4.3.2 分离Cache与统一Cache ====

**分离Cache（哈佛结构）**：
指令和数据分别存放在不同的Cache中（ICache和DCache）。
- 优点：减少指令和数据访问冲突，支持并行访问，适合流水线
- 缺点：不能动态调整指令和数据的空间分配

**统一Cache**：
指令和数据共享同一个Cache。
- 优点：空间利用率高，可以根据需要动态分配
- 缺点：指令和数据可能产生冲突

现代处理器通常在L1使用分离Cache，L2及以上使用统一Cache。

==== 4.3.3 预取技术 ====

**预取的概念**：
在处理器实际需要数据之前，提前将其装入Cache，减少Cache不命中的延迟。

**预取方式**：

1. **硬件预取**：由硬件自动识别访问模式进行预取
   - 顺序预取：预取下一个块
   - 跨步预取：识别固定间隔的访问模式
   
2. **软件预取**：由编译器插入预取指令
   - 非阻塞预取指令：不阻塞处理器执行
   - 可以精确控制预取时机

**预取的挑战**：
- 预取过早：数据可能在需要前就被替换
- 预取过晚：无法隐藏延迟
- 无用预取：浪费带宽和能量，可能替换有用数据

==== 4.3.4 虚拟Cache ====

**虚拟Cache的概念**：
使用虚拟地址而非物理地址来访问Cache，避免地址转换的开销。

**优点**：
- 命中时无需进行地址转换，速度快
- 减少TLB的压力

**问题**：
- 别名问题：不同虚拟地址可能映射到同一物理地址
- 同义问题：同一虚拟地址在不同进程中的含义不同
- 进程切换时需要清空Cache

**解决方法**：
- 使用物理标记的虚拟Cache
- 增加进程标识符（PID）区分不同进程
- 限制Cache索引使用页内偏移（避免别名）

===== 4.4 Cache的性能优化 =====

==== 4.4.1 影响Cache性能的因素 ====

**Cache容量**：
- 容量越大，命中率越高
- 容量越大，访问时间越长，成本越高
- 需要在性能和成本之间权衡

**块大小**：
- 块越大，空间局部性利用好
- 块过大可能增加不命中惩罚，减少Cache行数
- 存在一个最优块大小（通常为32-128字节）

**相联度**：
- 相联度越高，冲突不命中越少
- 相联度越高，查找时间越长，硬件成本越高
- 实际常用2路、4路、8路组相联

**不命中的类型**：

1. **强制性不命中（冷启动不命中）**：
   第一次访问某个块，不可避免
   减少方法：预取、增大块大小

2. **容量不命中**：
   Cache容量不足以容纳程序所需的所有块
   减少方法：增大Cache容量

3. **冲突不命中**：
   多个块映射到同一Cache位置
   减少方法：提高相联度、增大Cache容量

==== 4.4.2 软件优化技术 ====

**程序优化**：

1. **循环交换**：
   改变循环嵌套顺序，改善空间局部性
   ```c
   // 优化前：按列访问，Cache不友好
   for (i=0; i<n; i++)
       for (j=0; j<n; j++)
           sum += a[j][i];
           
   // 优化后：按行访问，Cache友好
   for (j=0; j<n; j++)
       for (i=0; i<n; i++)
           sum += a[j][i];
   ```

2. **循环分块（Tiling）**：
   将大矩阵分块处理，提高Cache利用率

3. **数据对齐**：
   将数据按Cache行对齐，减少跨行访问

**数据布局优化**：

1. **结构体优化**：
   将一起访问的数据放在一起，减少Cache行占用

2. **数组结构体 vs 结构体数组**：
   根据访问模式选择合适的数据组织方式

===== 4.5 Cache的一致性 =====

==== 4.5.1 多核处理器的Cache一致性 ====

在多核处理器中，每个核心有自己的私有Cache，多个Cache中可能存有同一内存位置的副本，需要保证一致性。

**一致性的要求**：
- 写传播：一个处理器写入的值必须对其他处理器可见
- 写串行化：所有处理器看到的写操作顺序必须一致

**监听协议（Snooping Protocol）**：

所有Cache控制器监听总线上的事务，根据监听结果调整自己的状态。

**MESI协议**：

最常用的Cache一致性协议，定义了四种状态：

- **M（Modified，修改）**：
  Cache行已被修改，与主存不一致，仅在此Cache中存在
  
- **E（Exclusive，独占）**：
  Cache行与主存一致，仅在此Cache中存在
  
- **S（Shared，共享）**：
  Cache行与主存一致，可能在其他Cache中也存在
  
- **I（Invalid，无效）**：
  Cache行无效

状态转换：
- 读命中：保持当前状态
- 读不命中：监听总线，根据其他Cache的状态决定新状态
- 写命中：根据当前状态可能需要发送无效化信号
- 写不命中：需要获取数据并可能无效化其他副本

**目录协议（Directory Protocol）**：

使用集中式或分布式的目录记录每个内存块的共享状态，减少总线流量，适合大规模多处理器系统。

===== 4.6 例题分析 =====

**例题1**：某计算机主存容量为1MB，Cache容量为16KB，块大小为256字节，采用直接映射。问：
（1）Cache共有多少行？
（2）主存地址如何划分？
（3）主存第100块映射到Cache哪一行？

解：
（1）Cache行数 = 16KB / 256B = 64行

（2）块内地址：256B = 2^8，需要8位
Cache行号：64 = 2^6，需要6位
主存标记：20 - 6 - 8 = 6位
地址划分：| 标记6位 | 行号6位 | 块内8位 |

（3）100 mod 64 = 36，映射到第36行

**例题2**：某Cache有8行，主存有32块，采用2路组相联映射。主存地址为5位。问：
（1）Cache共分几组？
（2）主存地址如何划分？
（3）主存第10块映射到Cache哪一组？

解：
（1）2路组相联，8行共分8/2 = 4组

（2）块数32 = 2^5，主存块号5位
组数4 = 2^2，组号2位
每组2行，组内行号不需要在地址中体现
块内地址位数根据块大小确定（题目未给）
地址划分：| 标记 | 组号2位 | 块内地址 |
标记位数 = 5 - 2 = 3位

（3）10 mod 4 = 2，映射到第2组

**例题3**：假设Cache命中时间为1个时钟周期，不命中惩罚为20个周期。执行某程序时，指令Cache不命中率为2%，数据访问占总指令的30%，数据Cache不命中率为5%。求CPI。

解：
指令访问引起的额外周期 = 1 × 2% × 20 = 0.4
数据访问引起的额外周期 = 30% × 5% × 20 = 0.3
CPI = 1 + 0.4 + 0.3 = 1.7

===== 4.7 本章重点总结 =====

**核心概念：**
- Cache的工作原理和命中率
- 三种地址映射方式：直接映射、全相联映射、组相联映射
- 替换算法：FIFO、LRU、随机
- 写策略：写直达、写回

**关键知识点：**
1. 局部性原理：时间局部性和空间局部性
2. 平均访问时间计算
3. 地址映射方式的特点和比较
4. 替换算法的工作原理
5. 写直达与写回的比较
6. 多级Cache结构
7. MESI一致性协议

**重要公式：**
- 平均访问时间：Ta = H × Tc + (1-H) × Tm
- 加速比 = Tm / Ta

**学习要点：**
- 理解Cache解决什么问题
- 掌握三种地址映射的原理和计算
- 了解不同替换算法和写策略的优缺点
- 理解Cache一致性的重要性

**思考题：**
1. 为什么组相联映射在实际应用中最广泛？
2. 写直达和写回各适用于什么场景？
3. 多级Cache相比单级Cache有什么优势？
4. 什么是伪共享？如何避免？