08.Cache

回顾 : 内存墙

• 问题 : CPU的速度比内存的速度快, 且两者差距不断扩大

  

• 解决 : CPU和内存之间增加Cache

Cache的基本思路与工作流程

基本思路

• 解决内存墙带来的CPU和主存协作问题

  • 在使用主存 (相对大而慢) 之余, 添加一块小而快的Cache

  • Cache位于CPU和主存之间, 可以集成在CPU内部或作为主板上的一个模块

  • Cache中存放了主存中的部分信息的"副本"

    ​

工作流程

• 检查 : 当CPU试图访问主存中的某个字时, 首先检查这个字是否在cache中

• 检查后分为两种情况处理

  • 命中 : 如果在cache中, 则把这个字传送给CPU

  • 未命中 : 如果不在cache中, 则将主存中包含这个字固定大小的块读入cache中, 如何再从cache传送该字给CPU

    ​

问题

如何判断是否命中?

命中和未命中的判断

• 冯诺依曼体系的设计

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

• Cache通过标记来标识其内容在主存中的对应位置

如果未命中, 为什么不直接把所需要的字从内存传送到CPU?

程序访问的局部性原理

• 定义

  • 处理器频繁访问主存中相同位置或相邻存储位置的现象

• 类型

  • 时间局部性 : 在相对较短的时间周期内, 重复访问特定的信息 (也就是访问相同存储位置的信息)
  • 空间局部性 : 在相对较短的时间周期内, 访问相邻存储位置的数据
    • 顺序局部性 : 当数据被线性排列和访问时, 出现的空间局部性的一种特殊情况
      • 例如 : 遍历一维数组中的元素

局部性原理的示例

向Cache传送内容

• 利用"时间局部性"

  • 将未命中的数据在返回给CPU的同时存放在cache中, 以便再次访问时命中

    

如果未命中, 为什么从内存中读入一个块而不只读入一个字?

传送块而不是传送字

• 利用"空间局部性"

  • 将包含所访问的字的块存储到cache中, 以便在访问相邻数据时命中

    

使用Cache后需要更多的操作, 为什么还可以节省时间?

平均访问时间

• 假设p是命中率, T_c是cache的访问时间, T_m是主存的访问时间, 使用cache时的平均访问时间T_A为

  ​ T_A = p * T_C + (1 - p) * (T_C + T_M)

  ​ = T_C + (1 - p) * T_M

• Cache返回数据的时间忽略不计

• 降低T_C, 提高p, 降低T_M都可以提高T_A

  • 但是, 降低T_C和提高p之间矛盾, 降低T_M(即降低未命中惩罚)很难

• 如果想要T_A < T_M, 必须要求

  ​ p > T_C / T_M

• 难点 : cache的容器远远小于主存的容量 (随机访问时 p = cache容量 / 主存容量)

Cache未命中原因

• 义务失效 / 冷启动失效

  • 第一次访问一个块时
  • 例如 : 第一次访问一个数组, 会发生义务失效

• 容量失效

  • cache无法保护程序访问所需的所有数据块, 则当某数据块被替换后, 又重新被访问, 则发生失效
  • 例如 : cache大小为8KB, 如果需要重复访问一个16KB大小的数组, 数组无法全部放入cache, 会发生容量失效

• 冲突失效

  • 多个存储器位置映射到同一cache位置
  • 例如 : 有两个4KB大小的数组都映射到了相同的地址, 需要来回访问, 则发生冲突失效

Cache的设计要素

Cache容量

• 扩大Cache容量带来的结果

  • 增大了命中率p

  • 增加了Cache的开销和访问时间T_c

映射功能

• 实现主存块到cache行的映射

• 块号, 块内地址

• 映射方式的选择会影响cache的组织结构

直接映射

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

• 假设i是cache行号, j是主存储器的块号, C是cache的行数, 则 i = j mod C

  ​

• 示例

  

怎么映射

• (块)标记

  • 地址中最高n位, n = log₂M - log₂C

    M : 块的数量, C : 行的数量

• 主存地址

  标记	Cache行号	块内地址

• 例

  • 假设cache有4行, 每行包含8个字, 主存中包含128个字, 访问主存的地址长度为7位, 则

    • 最低3位 : 块内地址 (主存中每块有8个字)
    • 中间2位 : 映射时所对应的cache行号 (cache有4行)
    • 最高2位 : 区分映射到同一行的不同块, 记录为cache标记 (共有128 / 8 = 16个块, 则M为16, C为4, 得n为2)

    ​

读数据示例

• 第一次进行第一条指令, 此时cache中为空

​

• 第二次进行第二条指令, 此时cache中第一行被20H占据, 发生冲突, 替换

​

总结

• 优点

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

• 缺点

  • 抖动现象 : 如果一个程序重复访问两个需要映射到同一行中来自不同块的字, 则这两个块不断地被交换到cache中, cache的命中率将会降低, 即发生冲突失效

• 适合大容量的cache

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

关联映射 (全相联映射)

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

  

怎么映射

• (块)标记

  • 地址中最高n位, n = log₂M

• 主存地址

  标记	块内地址

• 例

  • 假设cache有4行, 每行包含8个字, 主存中包含128个字, 访问主存的地址长度为7位, 则
    • 最低3位 : 块内地址 (主存中每块有8个字)
    • 最高4位 : 块号, 记录为cache标记

总结

• 优点

  • 避免抖动

• 缺点

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

• 适合容量较小的cache

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

组关联映射 (组相联映射)

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

• 假设s是cache组号, j是主存块号, S是组数, 则 s = j mod S

• K-路组关联映射, K = C / S

  

怎么映射

• 标记

  • 地址中最高n位, n = log₂M - log₂S

• 主存地址

标记	cache组号	块内地址

• 例

  • 假设cache有4行, 每行包含8个字, 分为2个组, 主存中包含128个字, 访问主存的地址长度为7位, 则
    • 最低3位 : 块内地址
    • 中间1位 : 映射时所对应的cache中的组
    • 最高3位 : 区分映射到同一组的不同块, 记录为cache标记

总结

• 优点

  • 结合了直接映射和关联映射的优点

• 缺点

  • 结合了直接映射和关联映射的缺点

• 面向不同容量的cache做了折中

三种映射方式比较

• 三种方式的相关性

  • 如果 K = 1, 组关联映射等同于直接映射
  • 如果 K = C, 组关联映射等同于关联映射

• 关联度 : 一个主存块映射到cache中可能存放的位置个数

  • 直接映射 : 1
  • 关联映射 : C
  • 组关联映射 : K

• 关联度越低, 命中率越低

  • 直接映射的命中率最低, 关联映射的命中率最高

• 关联度越低, 判断是否命中的时间越短

  • 直接映射的命中时间最短, 关联映射的命中时间最长

• 关联度越低, 标记所占额外空间开销越小

  • 直接映射的标记最短, 关联映射的标记最长

替换算法

• 一旦cache行被占用, 当新的数据块装入cache中时, 原先存放的数据块将会被替换掉

• 对于直接映射, 每个数据块都只有唯一对应的行可以放置, 没有选择的机会

• 对于关联映射和组关联映射, 每个数据块被允许在多个行中选择一个进行放置, 就需要替换算法来决定替换哪一行中的数据块

  • 采用替换算法的情景是, 多行可选且多行均被占
  • 替换算法通过硬件来实现
  • 设计替换算法的目的是提高命中率

最近最少使用算法 (LRU)

• 假设 : 最近使用过的数据块更有可能会被再次使用

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

• 实现 : 对于2路组关联映射

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

  ​

• 示例

  ​

  

  

• LRU位需要额外的硬件实现

  • K路需要 log(K!) ≈ Klog(K) 位, 例如4路时每行需要2位, 共需8位

• LRU会增加cache的访问时间

先进先出算法 (FIFO)

• 假设 : 最近由主存载入cache的数据块更有可能被使用

• 策略 : 替换掉在cache中停留时间最长的块

• 实现 : 时间片轮转发 或 环形缓冲计术

  • 每行包含一个标识位
  • 当同一组中的某行被替换时, 将其标识位设为1, 同时将其下一行的标识位设为0
    • 如果被替换的是该组中的最后一行, 则将该组中的第一行的标识位设为0
  • 当将新的数据块读入该组时, 替换掉标识位为0的行中的数据块

• 示例

  ​

  • FIFO每行1位标识位, 需要额外的硬件实现

  • FIFO仅当替换时, 需要改变标识位

个人理解的LRU和FIFO的区别

• FIFO按固定顺序替换

• LRU在固定顺序的基础上, 会根据最近访问到的动态调整顺序

• 在未命中时, 两种方式一样

• 当命中时, FIFO没有变化, 继续顺序替换; 而LRU则会根据命中的块调整顺序

• 可以自己模拟, 两种方式同时对cache进行存储替换, 当命中时, 两种方式的差异

最不经常使用算法 (LFU)

• 假设 : 访问越频繁的数据块越有可能被再次使用

• 策略 : 替换掉cache中被访问次数最少的数据块

• 实现 : 为每一行设置计数器

随机替换算法 (Random)

• 假设 : 每个数据块被再次使用的可能性是相同的

• 策略 : 随机替换cache中的数据块

• 实现 : 随机替换

• 随机替换算法在性能上只稍逊于使用其他替换算法

写策略

缓存命中时的写策略

• 主存和cache的一致性

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

• 替换时面临的两种情况

  • 如果没被修改, 则该数据块可以直接被替换掉
  • 如果被修改, 则在替换掉该数据块之前, 必须将修改后的数据块写回到主存中对应位置

• 写策略

  • 写直达
  • 写回法

写直达

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

• 优点 : 确保主存中的数据总是和cache中的数据一致, 总是最新的 (例如多CPU同步的场景)

• 缺点 : 产生大量的主存访问, 减慢写操作

写回法

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

• 利用一个脏位或者使用位来表示块是否被修改

• 优点 : 减少了访问主存的次数

• 缺点 : 部分主存数据可能不是最新的 (例如位发生替换但需要读主存的场景)

  • I/O模块存取时可能无法获得最新的数据, 为解决该问题会使得电路设计更加复杂且有可能带来性能瓶颈

缓存未命中时的写策略

写不分配

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

• 优点 : 避免cache和主存中的数据不一致

• 通常搭配 : 写直达

写分配

• 将数据所在的块读入cache后, 在cache中更新内容

• 优点 : 利用了cache的高速特性, 减少写内存次数

• 通常搭配 : 写回法

行大小

• 假设行的大小为一个字开始, 随着行大小的逐步增大, 则cache命中率会增加

  • 数据块中包含了更多周围的数据, 每次会有更多的数据作为一个块装入cache中
  • 利用了空间局部性

• 当行大小变得较大之后, 继续增加行大小, 则cache命中率会下降

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

• 行大小与命中率之间的关系较为复杂

  • 行太小, 行数太多 反时间局部性
  • 行太大, 行数太少 反空间局部性

Cache数目

一级 vs 多级

• 一级

  • 将cache与处理器置于同一芯片 (片内cache)
  • 减少处理器在外部总线上的活动, 从而减少了执行时间

• 多级

  • 当L1未命中时, 减少处理器对总线上DRAM或ROM的访问
  • 使用单独的数据路径, 代替系统总线在L2缓存和处理器之间传输数据, 部分处理器将L2cache结合到处理器芯片上

统一 vs 分立

• 统一

  • 更高的命中率, 在获取指令和数据的复杂之间自动进行平衡
  • 只需要设计和实现一个cache 指令和数据的局部性会相互影响

• 分立

  • 消除cache在指令的取值/译码单元和执行单元之间的竞争, 在任何基于指令流水线的设计中都是重要的