第三章-（六）高速缓冲存储器(Cache)

1.Cache基本原理基本概念

1.1程序访问的局部性原理

空间局部性：在最近的未来要用到的信息(指令和数据)，很可能与现在正在使用的信息在存储空间上是邻近的

时间局部性：在最近的未来要用到的信息，很可能是现在正在使用的信息

基于局部性原理，不难想到，可 以把CPU目前访问的地址“周围” 的部分数据放到Cache中（使下次访问的速度更快）

1.2.性能分析

设tc为访问一次Cache所需时间，tm为访问一次主存所需时间

命中率H：CPU欲访问的信息已在Cache中的比率

1.先访问Cache，若Cache未命中再访问主存

Cache—主存系统的平均访问时间t为：

2.同时访问Cache和主存，若Cache命中则立即停止访问主存

 例题：

当Cache与主存一一对应时，就会出现Cache被占满的现象

有待解决的问题

• 如何区分Cache与 主存的数据块对应关系？ ——Cache和主存的映射方式

• Cache很小，主存很大。如果Cache满了怎么办？ ——替换算法

• CPU修改了Cache中的数据副本，如何确保主存中数据母本的一致性？ ——Cache写策略

1.3 Cache的基本工作原理

Cache通常集成在CPU中，在CPU和主存之间设置Cache，把主存中被频繁访问的地址信息所在块调入Cache，CPU就可以在Cache中更快地访问到这个块内的信息。

考虑到局部性原理，假设我们以内存中64B作为一个块，当访问这个块的某个地址时就把它写入Cache。具体对应关系如下：

主存块大小=cache块大小

Cache的 “块” 也可称 “行”。

关于命中率和缺失率问题主要有两个要点:

1. 是否为cache和主存同时访问。
2. A[x]=A[x]+32。这个操作涉及读和写操作各一次，计算命中率时需注意。 

 2.Cache和主存的映射方式

 2.1总览

2.2全相邻映射

储存方式：主存块可以放在Cache的任意位置

如何区分Cache中存 放的是哪个主存块？

给每个Cache块增加一 个“标记”，记录对应的主存块号。

有“标记”就够了？—不行因为，如果存的是985则后面有五位的自动为0，而主存不是0号为对应的后五位的Cache中，所以为了避免歧义就加上有效位，有效的表示1，无效的表示0.

 因为Cache快对应主存块的大小相等，故要2的28次除以2的6次，块号如上，块内地址如上。

CPU 访问主存地址1…1101001110（判断步骤）：

1. 主存地址的前22位
2. 对比Cache中所有块的标记，若标记匹配且有效位=1，则Cache命中，访问块内地址为001110 的单元。
3. 若未命中或有效位=0，则正常访问主存

2.3直接映射（只能放固定位置）

储存方式：直接映射，主存块在Cache中的位置=主存块号%Cache总块数

在存储的时候有被覆盖的缺点。

因为主存块号%2的3次 ， 相当于留下最后三位二进制数，故直接在Cache后面对应，三位

 故储存地址的方式：

CPU 访问主存地址0…01000 001110（检查步骤） ：

1. 根据主存块号的后3位确定Cache行
2. 若主存块号的前19位与Cache标记匹配且有效位=1，则Cache命中，访问块内地址为 001110的单元。
3. 若未命中或有效位=0，则正常访问主存

2.3组相邻映射

存储方式：组相联映射，所属分组=主存块号%分组数

因为主存块号%22 ，相当于留下最后两位相当于留下最后两位位二进制数，故直接在Cache后面对应，两位

CPU 访问主存地址1…1101001110 ：

①根据主存块号的后2位确定所属分组号

②若主存块号的前20位与分组内的某个标记匹配且有效位=1，则Cache命中，访问块内地址为 001110的单元。

③若未命中或有效位=0，则正常访问主存

2.4三种方式的优缺点

3.Cache中主存块的替换算法

3.1知识点总览

3.2随机算法（RAND） 

 特点：随机算法——实现简单，但完全没考虑局部性原理，命中率低，实际效果很不稳定

3.3先进先出算法（FIFO）

先进先出算法——实现简单，最开始按#0#1#2#3放入Cache，之后轮流替换 #0#1#2#3 FIFO依然没考虑局部性原理，最先被调入Cache的块也有可能是被频繁访问的

抖动现象： 频繁的换入换出现象（刚被替换的块很快又被调入）

3.4近期最少使用算法（LRU）

说明：LRU算法——基于“局部性原理” ，近期被访问过的主存块，在不久的将来也很有可能被再次访问，因此淘汰最久没被访问过的块是合理的。LRU算法的实际运行效果优秀，Cache命中率高。 若被频繁访问的主存块数量 > Cache行的数量，则有可能发生“抖动”{1,2,3,4,5,1,2,3,4,5,1,2…}

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

此处优先淘汰行号更小的

LFU算法——曾经被经常访问的主存块在未来不一定会用到（如：微信视频聊天相关的块）， 并没有很好地遵循局部性原理，因此实际运行效果不如 LRU 

4.Cache写策略

4.1总览

为何不讨论读命中、读不命中的情况？ 读操作不会导致Cache和主存的数据不一致

4.2写命中

写回法(write-back) —— 当CPU对Cache写命中时，只修改Cache的内容，而不立即写入主存，只有当此块被换出时才写回主存 

减少了访存次数，但存在数据不一致的隐患。-为此引入脏位来表示是否被修改过。

4.3全写法

全写法(写直通法，write-through) —— 当CPU对Cache写命中时，必须把数据同时写入Cache

和主存，一般使用写缓冲(write buffer)：为了使CPU使用更高效

使用写缓冲，CPU写的速度很快，若写操作不频繁，则效果很好。若写操作很频繁，可能会因为写缓冲饱和而发生阻塞

4.4写不命中

写分配法(write-allocate)——当CPU对Cache写不命中时，把主存中的块调入Cache，在Cache

中修改。通常搭配写回法使用。主存不动，只是修改了Cache中的副本。

非写分配法(not-write-allocate)——当CPU对Cache写不命中时只写入主存，不调入Cache。 搭配全写法使用。（只写主存，不调用Cache）

多级Cache