8.Cache

1. Cache是什么

1.1 内存墙

问题：CPU的速度比内存的速度快，且两者差距不断扩大

内存跟不上CPU的斯必得，所以需要Cache（高速缓存）放在二者中间提速。

1.2 基本思路

在使用主存（相对大而慢）之余，添加一块小而快的cache。

• Cache位于CPU和主存之间（也可以集成在CPU内部或作为主板上的一个模块）。
• Cache中存放了主存中的部分信息的副本（未必up-to-date，后面会说）

1.3 工作流程

检查（Check）：当CPU试图访问主存中的某个字时，首先检查这个字是否在 cache中

检查后分两种情况处理：

• 命中（Hit）：如果在cache中，则把这个字直接传送给CPU

• 未命中（Miss）：如果不在cache中, 则将主存中包含这个字固定大小的块（block） 读入cache中，然后再从cache传送该字给CPU

所以未命中的时候会做两件事：

1. 把主存里读相邻一整块数据
2. 把这一整块都塞到Cache里

1.3.1 如何判断命中还是未命中？

CPU通过位置对主存中的内容进行寻址，不关心存储在其中的内容

Cache通过标记、组号、块内地址来标识其内容在主存中具体的对应位置（ppt中只写了标记，然而标记只能确定到某一块，不能具体确定到对应地址，所以我在后面加了组号和块内地址）

1.3.2 为什么这么设计Cache

这个问题也相当于：为什么偏要Cache，不是增加复杂度吗？

1.3.2.1 局部性原理

1. 定义：处理器频繁访问主存中相同位置或者相邻存储位置的现象

2. 类型：

   • 时间局部性：在相对较短的时间周期内，重复访问相同地址的信息
   • 空间局部性：在相对较短的时间周期内，访问相邻地址的数据
     • 顺序局部性：当数据被线性排列和访问时，出现的空间局部性的一种特殊情况（比如遍历一维数组）

3. 对应方案：

   • 对应时间局部性：将未命中的数据在返回给CPU的同时存放在Cache中，下次就能直接从Cache里面拿

   • 对应空间局部性：将包含所访问的字的周围一整块全都存储到 Cache中，下次可以直接从Cache里拿它相邻的数据

这张图有几个要点：

1. 主存里所定义的“块”，是提前划分好的，并且“块”这个概念仅出现在主存里。
2. 主存里的“一块”对应的是Cache里的“一行”，主存的一块会被存放在Cache里的一行。换句话说，Cache里一行的数据，对应到主存里肯定在同一块。

1.3.3 为什么Cache还可以节省时间？

1.3.3.1 平均访问时间

增加命中率p，就需要更大的Cache容量，同时Cache访问时间Tc也会变大。

Cache速度大概是主存的十倍，但是cache容量也远远小于主存，所以这件事比较蛋疼。

不过目前cache在实际生活中，命中率普遍在90%多（似乎是），所以还是很舒服的。

2. Cache的设计要素

2.1 Cache容量

扩大cache容量带来的结果：

• 增大了命中率𝑝
• • 增加了cache的开销和访问时间 𝑇c

2.2 映射功能

实现主存“块”到cache“行”的映射。

2.2.1 直接映射

将主存中的每个块映射到一个固定可用的cache行。

假设𝑖是cache行号，𝑗是主存储器的块号，𝐶是cache的行数

𝑖 = 𝑗 𝑚𝑜𝑑 𝐶（这样就可以像上图右边的映射一样）

2.2.1.1 示例

主存地址是如何像这样划分？见

所以说，直接映射的cache容量会比较多，因为同一块的数据地址会共用用一个标记（也就是主存地址的一部分）

2.2.1.2 总结

优点

• 简单
• 快速映射
• 快速检查

缺点：

• 抖动现象（Thrashing）：如果一个程序重复访问两个需要映射到同一行中且来自不同块的字，则这两个块不断地被交换到cache中，cache的命中率将会降低。

适合大容量的cache

• 行数变多，发生冲突失效的概率降低
• 硬件电路简单，增大容量对𝑇𝐶的影响不明显

2.2.2 关联映射（全相联映射）

一个主存块可以装入cache任意一行

上图的[字]其实不准确，应该是[块内地址]

2.2.2.1 示例

​

2.2.2.2 总结

优点：

• 避免抖动

缺点：

• 实现起来比较复杂
• Cache搜索代价很大，即在检查的时候需要去访问cache的每一行

适合容量较小的cache

• 小容量更容易发生冲突失效
• 小容量检查的时间短

2.2.3 组关联映射（组相联映射）

前面两个太极端了，这个中和一点。

Cache分为若干组，每一组包含相同数量的行，每个主存块被映射到固定组的任意一行。

这里的“组”是组关联映射特有的概念，不是之前的”块”和”行“，而是一组里面有很多行，cache里的每一行是主存里的一块。

注意：K路组关联的意思是，一组里面有几行。

相信你也看出来了，直接映射和关联映射是组关联映射的极端情况。

直接映射：k=1（一组里面只有一行，cache有多少行就有多少组）

关联映射：k=c（cache一共只有一组，一组里面包含了cache里的所有行）

2.2.3.1 实例

2.2.4 如何划分主存地址

首先看cache一行有多少字，这决定了主存里一块包含多少字，需要唯一表达这些字，就需要用数量mod2。

比如cache每行8个字，那就需要3位的块内地址。

其次看cache划分了多少组，需要唯一确定位于哪个组，就需要用组数量mod2（当然，如果只有一组，也就是关联映射，就不需要有组号了）

比如cache分为4个组，就需要2位cache组号

最后剩下的全部都是标记。

标记的本质意思，其实就是块号，主存里每一块都有唯一且独特的块号。

有3位的标记，就可以表达16个块(0-15)。就可以把128个字的主存，以8个字为一块，划分出16个块，每一块都可以用这3位的标记作为块号唯一表示。

2.2.5 三种映射方式比较

关联度（Correlation）：一个主存块映射到cache中可能存放的位置个数

• 直接映射：1
• 关联映射：𝐶 （cache里随便挑一行都可以放）

• 组关联映射：K（cache里固定的某一组里随便挑一行放）

• 关联度越低，命中率越低
• 关联度越低，判断是否命中的时间越短
• 关联度越低，标记所占额外空间开销越小

2.3 替换算法

如果有新的数据块要装入cache中已经有数据的某一行，原先存放的数据块将会被替换掉。

• 对于直接映射，每个数据块都只有唯一对应的行可以放置，没有选择的机会
• 对于关联映射和组关联映射，每个数据块被允许在多个行中选择一个进行放置， 就需要替换算法来决定替换哪一行中的数据块

1. 替换算法通过硬件来实现

2. 设计替换算法的目标是提高命中率

2.3.1 最近最少使用算法（LRU）

替换掉在cache中最长时间未被访问的数据块

实现：

对于2路组关联映射

• 每行包含一个USE（LRU）位 • 当同一组中的某行被访问时，将其USE位设为1，同时将另一行的USE 位设为0
• 当将新的数据块读入该组时，替换掉USE位为0的行中的数据块

LRU位需要额外的硬件实现

LRU会增加cache访问时间

2.3.1.1 示例

2.3.2 先进先出算法（FIFO）

替换掉在Cache中停留时间最长的块(注意：不是最久没有被使用的块，极端地说，有一个块在100年前被存入cache，每秒被hit一亿次，但是因为它太老了，所以还是会被FIFO算法给替换掉)

实现：（可以适用于n路组）

时间片轮转法（环形缓冲技术 ）

• 每行包含一个标识位 • 当同一组中的某行被替换时，将其标识位设为1，同时将其下一行的标识 位设为0
• 如果被替换的是该组中的最后一行，则将该组中的第一行的标识位设 为0

• 当将新的数据块读入该组时，替换掉标识位为0的行中的数据块

• FIFO每行1位标识位，需要额外的硬件实现
• FIFO仅当替换时，需要改变标识位

2.3.3 最不经常使用算法（LFU）

替换掉cache中被访问次数最少的数据块

实现：为每一行设置计数器

2.3.4 随机替换算法（Random）

随机替换cache中的数据块

这个算法和上面三个，在实际应用上，性能其实差不多，只是理论上会稍逊于前三个。

所以很多厂商用的就是随机替换。

2.4 写策略

当cache中的某个数据块被替换时，需要考虑该数据块是否被修改。

如果被修改，则在替换掉该数据块之前，必须将修改后的数据块写回 到主存中对应位置（不然cache和主存不一样就操蛋了）

2.4.1 缓存命中时的写策略

2.4.1.1 写直达

所有写操作都同时对cache和主存进行

优点：

• 确保主存中的数据总是和cache中的数据一致，总是最新的（例如多CPU 同步的场景）

缺点：

• 产生大量的主存访问，减慢写操作

2.4.1.2 写回法

先更新cache中的数据，当cache中某个数据块被替换时，如果它被修改了， 才被写回主存。

利用一个脏位（dirty bit）或者使用位（use bit）来表示块是否被修

优点：

• 减少了访问主存的次数

缺点：

• 部分主存数据可能不是最新的（例如未发生替换但需要读主存的场景）
  • I/O模块存取时可能无法获得最新的数据，为解决该问题会使得电路设计更加复杂且有可能带来性能瓶颈

2.4.2 缓存未命中时的写策略

2.4.2.1 写不分配

直接将数据写入主存，无需读入cache

• 优点：避免cache和主存中的数据不一致
• 通常搭配：写直达

2.4.2.2 写分配

将数据所在的块读入cache后，在cache中更新内容（而不会修改主存）

• 优点：利用了cache的高速特性，减少写内存次数
• 通常搭配：写回法

2.5 行大小

随着行大小的逐步增大，则Cache命中率会增加（有更多的数据作为一个块装入cache）

当行大小变得较大之后，继续增加行大小，则Cache命中率会下降。

• 当Cache容量一定的前提下，较大的行会导致Cache中的行数变少，导致装入 cache中的数据块数量减少，进而造成数据块被频繁替换
• 每个数据块中包含的数据在主存中位置变远，被使用的可能性减

所以命中率大概随着行大小的增加，先上升，后减少。

2.6 Cache数目

2.6.1 一级 vs.多级

• 一级
  • 将cache与处理器置于同一芯片（片内cache）
  • 减少处理器在外部总线上的活动，从而减少了执行时间
• 多级：CPU和主存之间有很多个cache，越靠近CPU的cache越快越小，越靠近主存的cache越慢越大。
  • CPU->L1(cache)->L2(cache)->L3(cache)->主存
  • L1找，去L2找，再去L3找，随后再去主存找。

2.6.2 统一 vs. 分立

• 统一
  • 更高的命中率，在获取指令和数据的负载之间自动进行平衡
  • 只需要设计和实现一个cache
• 分立：（一个称为指令Cache，一个称为数据Cache）
  • 消除cache在指令的取值/译码单元和执行单元之间的竞争