高速缓冲存储器（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

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

直接映射：

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

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

地址划分：

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

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

全相联映射：

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

地址划分：

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

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

组相联映射：

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

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

地址划分：

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

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

三种映射方式的比较：

图4-1：Cache三种映射方式示意图

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

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

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

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

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

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

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

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

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

写策略的比较：

写不命中时的策略：

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

非写分配法（No Write Allocate）： 写不命中时，直接写入主存，不调入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为主存访问时间

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

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

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

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

预取方式：

1. 硬件预取：由硬件自动识别访问模式进行预取

1. 顺序预取：预取下一个块
2. 跨步预取：识别固定间隔的访问模式

2. 软件预取：由编译器插入预取指令

1. 非阻塞预取指令：不阻塞处理器执行
2. 可以精确控制预取时机

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

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

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

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

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

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

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

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

不命中的类型：

1. 强制性不命中（冷启动不命中）：

 第一次访问某个块，不可避免
 减少方法：预取、增大块大小

2. 容量不命中：

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

3. 冲突不命中：

 多个块映射到同一Cache位置
 减少方法：提高相联度、增大Cache容量

程序优化：

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 结构体数组：

 根据访问模式选择合适的数据组织方式

在多核处理器中，每个核心有自己的私有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）：

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

例题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

核心概念： - 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. 什么是伪共享？如何避免？