计算机组织结构(六) Cache
为什么需要 cache?
- 因为 CPU 比 内存的速度要快得多.`
基本思路
- 使用较小, 较快的 Cache 和相对较大,更为缓慢的 Memory
- Cache 中包含了 Memory 中数据的副本
- Cache 位于中央处理器和存储器之间,并可以被集成在 CPU 或者作为主板上的一个模块.
Cache 工作的原理
- Check :当处理器试图读取内存中的一个字的时候,会先检查该字是否在 Cache 中.
- Hit : 如果确实在, 这个字被传送给处理器.
Miss : 否则,由一定数量的字组成的一块( block )主存中的数据 被读入 Cache ,然后传给处理器.
时间局部性:
未来将要使用的信息(指令和数据), 可能是现在正在使用的信息.- 空间局部性:
未来将要使用的信息, 很可能与正在使用的信息在存储空间上是邻近的(比如遍历一个一维数组).
判断 Hit 与 Miss
- 冯诺依曼计算机的设计:
内存中的内容按位置寻址,而不考虑其中的数据类型. - Cache 中有 标记(tag) 来判断需要读取的信息是否存在于 Cache.
移动”块”而不是字
证明 Cache 机制能够提高性能
- 设命中率为 $p$, $T_C$ 为访问Cache 的时间,$T_M$ 为访问主存的时间,则总时间为(可以认为返回数据不需要时间, 寻找花时间)由上面可以推出,若 $T
Cache 是否越大越好?
Cache 容量变大, 命中率增加会变得缓慢,因为搬来的数据可能关联性弱,对效果提升十分有限.此外,Cache 规模变大会使得 check 的时间变长.
映射功能
- 因为 Cache 的行比主存块要少, 所以需要一个算法将主存中的块映射到 Cache 中的行.
1. 直接映射
- 地址组成：
定义: 内存中的一个块映射到 Cache 中固定的行.
将主存中的每个块映射到固定的可用 Cache 中行.直接映射可以表示为:
其中 i 为 Cache 行号, j 为主存块号, m 为 Cache 行数 .
为了实现访问 Cache 每一个主存地址可以看作由三个域组成：- 低 $w$ 位标识某个块中的唯一一个存储单元(字节或字).
- 剩余 $s$ 位标识了主存 $2^s$ 个块中的一个.
- 其中 $r$ 位标识了 cache 中的行号(cache 的行数为 $m=2^r$)
- $s-r$ 位为 tag 位.用以区分映射到同一行的不同块.
总结:
- 地址长度: $(s+w)$ 位
- 可寻址单元数: $2^{s+w}$
- 块大小=行大小=$2^w$ 个存储单元(字节或字)
- 主存的块数:$\frac{2^{s+w}}{2^w}=2^s$
- cache 行数:$m=2^r$
- cache 容量: $2^{r+w}$ 个字或者字节
- 标记长度: $(s-r)$ 位
举例:
$m=16K=2^{14},i=j\space mod\space 2^{14}$,用 16 进制 表示地址有
| cache 行 | 主存块的起始地址 |
|---|---|
| 0 | 000000,010000,....FF0000 |
| 1 | 000004,010004,...,FF0004 |
| ... | ... |
| 00FFFC,01FFFC,...,FFFFFFC |
地址24位,其中,高8位为 tag 位,若当前存在该行的标记数与地址中的相同,则14位标识 cache 行号, 低2位标识行中的4个字节(或者字);否则,前22位标识为从主存中取一块.取的主存块的地址为22位加两位0(因为块都是以4倍数开始的,每个块有4个单元)
优点:
- check快,从主存中存取的时候快
- tag 短,额外存储少.
- 不会随着容量增大而变慢
- 实现简单
缺点:
- 容易发生抖动:用到的两个块映射到 cache 中的同一行,于是频繁的替换.
- 命中率低
2. 全相联映射
地址图示:
定义: 内存中的块可以映射到 Cache 中的任意一行.
总结:
- 地址长度 s+w 位
- 可寻址单元数 $2^{s+w}$ 个字(字节)
- 块大小=行大小=$2^w$ 个字(字节)
- 主存的块数:$\frac{2^{s+w}}{2^w}=2^s$
- cache 的行数: 不由地址格式决定
- 标记长度=s 位
优点:
- 避免”抖动”.
- 命中率高
缺点:
- check 慢, 从内存中放到 cache 中慢.
- 实现较为复杂
3. 组相联映射
- 图示:
- 定义: Cache 中的行分成组(Set),内存中的块搬到固定的组,组中具体的哪一行不固定.第一步类似直接映射,第二部类似全相联映射. Cache 中分为 $v$ 个组,每组包含 $k$ 个行,则:其中: i 为组号, j 为主存块号,m 为主存块数,v 为组数,k 为每个组中的行数, 即 k路组(K-way Set).
- 总结:
- 地址长度 s+w 位
- 可寻址单元数 $2^{s+w}$ 个字(字节)
- 块大小=行大小=$2^w$ 个字(字节)
- 主存的块数:$\frac{2^{s+w}}{2^w}=2^s$
- cache 中每组行数= k
- 组数 = v = $2^d$
- cache 中的行数 = m = $k\times v=k\times 2^d$
- 标记长度 s-d 位(同一个组中不会出现标记位相同的两个块)
优点:
- 固定组 check ,存取,速度比全相联快
- 命中率比直接映射高
缺点:
- 实现复杂.
- 若反复用的的块很多的话,仍然无法避免抖动.
替换算法
1.最近最少用
2.先进先出
3.使用最少
4.随机
写策略
1.写入
- 每一次改了之后都更新内存
- 好处:提升cache和主存一致性,保证主存中的内容都是最新的
2.写回
- cache 中的行要被替换时不得不写回去,用 dirty bit 来判断数据是否发生过改写,若没有改过无需写回.
块大小(Cache Line Size)
- 由极小变大,根据局部性原理命中率先是提升,因为每个块所能容纳的有用数据增多了.
- 到极大时,且新取信息的概率小于重用信息概率时,命中率会减小.因为较大的块减少了块的个数,少量的块导致装入的数据很快会被改写;当块变大时,每个附加字距离所需字就更远,被使用的概率低.
cache 数目
- 多级 cache 比单一大容量 cache 效率更高
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 极东魔术昼寝结社！
相关推荐
评论