Cache存储器

1. 为什么使用Cache？

1. 内存墙的存在（内存性能严重限制CPU性能的发挥）

2. 解决内存墙问题的方法

1. 同时使用速度快容量小的Cache与速度慢容量大的存储块
2. cache包含主存一部分内存的副本
3. cache位于CPU和主存之间，或者位于CPU内部

3. Cache如何工作得？

• check：当处理器需要读取一个数据时，先去cache里检查一下是否在cache里
• hit：如果在，直接将这个数据传给处理器
• miss：如果不在，从主存中将包括这个数据的固定大小的块写进cache，并把需要的数据传给处理器

4. cache工作流程的一些问题

• 如何确定一个数据是否在cache里？
  • 冯诺依曼计算机结构确定“无论什么数据都是以相同的方式寻址”
  • cache包含一个tag用来确定cache的某一行对应主存的那一部分
  • 内存中的数据是由标签来进行指向的，而不是依据数据类型进行访问
• 为什么在cache-miss时是从主存中读取一个块而不是一个字？
  • 因为程序的局部性原理
  • 在程序执行过程中，处理器会倾向于向一块地方集中的访问数据
  • 局部性分为：
    • 时间局部性
    • 空间局部性
    • 顺序访问（数组之类的）

5. 把数据搬到Cache

• 使用时间局部性
• 经典的cache组织

6. 一次搬用一整块内容而不是一个字

• 使用空间局部性原理
• cache结构

7. 同比起来，使用cache会多更多的操作，为什么能节省时间呢？

• 访问cache的速度比访问内存的速度快很多
• 由于局部性原理的存在，cache的命中率会比较高
• 一次搬用一个块的数据比多次搬用一个字的时间少

8. 平均访问时间

• 假设命中率为$p$，$T_{c}$为访问cache的时间，$T_{m}$是访问存储器的时间，那么平均访问时间为：$T_{A} = pT_{c} + (1-p)(T_{c} + T_{M}) = T_{c} + (1-p)T_{M}$

• 当$p > T_{c} / T_{M}$时，$T_{A} < T_{M}$

• 问题：cache的容量远小于存储器的容量

9. cache设计考虑因素

• 大小
• 映射策略
• 替换策略
• 写策略
• 行大小
• 数量

10. Cache Size

• 增加行大小 -> 增加命中率$p$, 同时也会增加cache的访问时间
• 

11. Mapping Function

• 用来将主中的块映射到cache行的策略/算法
• 一种覆盖cache中哪一行的策略
• 映射函数的选择决定了cache行的组织
• 类型：
  • 直接映射
  • 全相关映射
  • 组相关映射

1. 直接映射

• 将存储器中的块固定的对应于cache中可以用的行中
• $i = j mod C$, $i$:cache行号，$j$:数据块的块号, $C$:cache总行数
• tag：前n位，$n = log_{2}M - log_{2}C$

1. 优点：

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

2.缺点：

• 抖动大：当一个程序需要多次交替的访问两个映射在同一行的块，会发生多次的块替换

comment：适用于大容量的cache

2. 全相关映射

• 允许将存储器中的块映射到cache的任意行
• tag：前n位， $n = log_{2}M$

1. 优点：

• 避免了抖动

2.缺点：

• 复杂的实现
• cache的查询消耗大

comment：是用于小容量的cache

3. 组相关映射

• cache被分为$s$个组，每组$k$行。
• $j$为块号，$i = j mod s$，第j块被映射到第i组。
• 称为k-路组
• tag：前n位，$n = log_{2}M - log_{2}S$

1. 优点：

• 集成了直接映射和全相关映射的优点

2. 缺点：

• 同时也集成了直接映射和全相关映射的缺点

comment：对任意容量的cache在性能上进行了很好的权衡

12. 映射策略的对比

1. 相关性：每个块可能在cache中的行数

• 直接映射：1
• 全相关映射：C
• 组相关映射：k

2. 相关性与性能

• 相关性越低，命中率越低
• 相关性越低，检查速度越快
• 相关性越低，tag长度越短

13. 替换策略

1. 当cache的行被填充时，一个新的块需要插入cache，那么此时就可能将cache中已有的块丢弃，也就是替换掉

2. 对于直接映射：一个确定的块有且只有一个对应的cache行可以装填

3. 对于全相关和组相关映射而言，替换策略是必需的，并且必须通过硬件来实现。

4. 最常用的集中替换算法

   • least recently use（LRU）-- 最近最少使用
   • first in first out（FIFO）-- 先进先出
   • least frequently used（LFU）-- 最不经常被使用
   • random – 随机

   1. LRU

   • 根据最近一次被用到的时间进行排序
     • 以二路组为例，我们将一位置为1，则另一位被置为0
   • 替换cache中当前最长时间没被使用的块
   • 将设最近被使用的块不久还将会被使用
   • 特别适合二路组关联映射

   2. FIFO

   • 和使用时间关系不大，根据进入cache的时间来排序
   • 假设越靠后的数据越容易被再次使用到
   • 实现：循环/循环缓冲技术
   • 通过计数器来时间（时间戳）

   3.Random

   • 随机的替换对应的行
   • 假设每个存储位置都等概率被再次访问到

14. 写策略

• 内存与cache的一致性要求
  • 当一个块在cache中被替换时，需要考虑块是否被个别更改可
• 两种情况：
  • 如果没有更改，可以直接替换
  • 如果更改了，对应在内存中的块需要被更新
• 两种策略：
  • 写入法（write through）
  • 写回法（write back）

1. 写入法

• 当cache中的行发生改变时，立即对内存中对应的块进行更新

• 优点：确保了内存中的数据始终被更新过了

• 缺点：

  • 产生大量的内存访问，出现时间瓶颈

  • 减慢了写操作

2. 写回法

• 只更新cache中的数据，当这个快被替换或者遇到I/O操作需要对主存这块区域读取数据时，才发生更新
• 使用dirty bit/ use bit，来代表是否被修改了
• 优点：减少了对内存的写操作
• 缺点：内存中对应的内容时过时的，因此当存在I/O操作时，只能允许通过cache进行，因此会造成复杂的电路以及潜在的瓶颈

15. 行大小

• 当行大小从很小的容量增加到比较大的容量时：
  • 命中率提高
  • 更多有用的数据可以被带入cache
• 当行大小变的非常大时：
  • 命中率提高，但提高的速度明显减慢
    • 更大的行，导致cache的行数减少，这将导致频繁的替换
    • 每个额外的字都会离被需要的字更远，因此更小的可能性会在不久的将来被访问在
• 块大小和命中率之间的关系更加复杂

16. cache行数量

• unified（统一）：
  • 提高指令与数据负载自动平衡的命中率
  • 只有一个cache需要被设计和实现
• split（分隔）：
  • 消除指令获取/解码单元和执行单元之间对缓存的争用，这对指令的流水线很重要