§3 高速缓冲存储器（Cache） 工作原理和基本结构 地址映象与变换 Cache存储器的LRU替换算法的硬件实现

Presentation on theme: "§3 高速缓冲存储器（Cache） 工作原理和基本结构 地址映象与变换 Cache存储器的LRU替换算法的硬件实现"— Presentation transcript:

1 §3 高速缓冲存储器（Cache） 工作原理和基本结构 地址映象与变换 Cache存储器的LRU替换算法的硬件实现

2 为什么要使用Cache? 用以弥补主存速度的不足。 CPU速度与主存速度相差很大（例如，一般的DRAM的工作速度比CPU慢100倍以上。
Cache工作速度很高，可以将其集成到CPU内。高性能CPU通常用两级Cache,一级在CPU内，其容量比较小，速度很快，第二级在主板上，容量比较大，速度比第一级低5倍左右。 Cache全部用硬件调度对所有程序员都是透明的。 Cache与主存储器之间以块为单位进行数据交换。块的大小通常以在主存储器的一个存储周期内可以访问到的数据长度为限。

3 Cache存储系统与虚拟存储系统比较 存储系统 两级存储器速度比 Cache 虚拟存储器 要达到的目标 提高速度 扩大容量 实现方法
全部硬件 软件为主 硬件为辅 3~10倍 105倍 页(块)大小 1~16字 1KB~16KB 等效存储容量 主存储器 透明性 对系统和 应用程序员 仅对应用 程序员 不命中时处理方式 等待主存储器 任务切换

4 主存 块号 块内地址 主存-Cache 地址映象变换机构 Cache 替换 策略 来自处理机 主存地址 地址 访主存 替换Cache
去处理机 直接通路 单字宽 多字宽 已 装 不 进 还 可 入 不命中 命中 高速缓冲存储器Cache

5 基本结构 把主存和Cache机械等分成相同大小的块（行），块比页小得多； 访问Cache的时间时访问主存时间的1/4到1/10；
Cache和CPU是同类型的半导体器件； Cache-主存间的地址映像和变换，以及替换、调度算法用硬件实现，对应用程序员透明，也对系统程序员透明；

6 基本结构（续） Cache在物理位置上靠近CPU，不在主存，减少传输延迟；
除Cache到处理机的通路外，还设有主存到处理机的通路，因此，Cache既是Cache-主存存储层次中的一级，又是处理机和主存的一个旁视存储器； 有Cache的主存系统都采用多体交叉存储器； 应尽量提高Cache的访主存的优先级；

7 地址映象与变换 地址映象：是将每个主存块按某种规则（算法）装入（定位于）Cache,并建立主存地址与Cache地址之间的对应关系。
地址变换：是主存块按照这种映象关系装入Cache后,每次访Cache，如何将主存地址变换成Cache地址。 在选取地址映象方法要考虑的主要因素： 地址变换的硬件容易实现； 地址变换的速度要快； 主存空间利用率要高； 发生块冲突的概率要小

8 四种方式 全相联映象与变换 直接映象与变换 组相联映像与变换 段相联映象

9 全相联映象与变换 定义及规则 映象规则：主存中的任意一块都可以映象到Cache中的任意一块。
如果Cache的块数为Cb，主存的块数为Mb，映象关系共有：Cb×Mb种。 用硬件实现非常复杂 在虚拟存储器中，全部用软件实现

10 相联目录表法 变换过程，如下图。 特点： 冲突概率低 空间利用率高 地址变换复杂

11 块0 Cache 块1 …… 块Cb-1 块i 块Mb-1 主存储器 全相联映象方式

12 有效位 块号B 块内地址 主存地址 目录表（由相联存储器组成，共Cb个字） 主存块号B B 块号b 块内地址w Cache块号b b 相联比较 命中 Cache地址

13 直接映象与变换 定义及规则 映象规则：主存中一块只能映象到Cache的一个特定的块中。 计算公式：
b＝B mod Cb，其中： b为Cache的块号， B是主存的块号， Cb是Cache的块数。 整个Cache地址与主存地址的低位部分完全相同。

14 变换过程，如下图。 特点： 硬件简单 冲突概率高 出现大量空闲块 很少使用。

15 块0 Cache 块1 …… 块Cb-1 主存 储器 直接相联映象方式 块Cb 块2Cb-1 块Mb-Cb 块Mb-1 区0 区1 区Me-1

16 地址变换过程 用主存地址中的块号B去访问区号存储器 把读出来的区号与主存地址中的区号E进行比较
比较结果相等, 且有效位为1, 则Cache命中 比较结果相等, 有效位为0, 表示Cache中的这一块已经作废 比较结果不相等, 有效位为0, 表示Cache中的这一块是空的 比较结果不相等, 有效位为1, 表示原来在Cache中的这一块是有用的

17 有效位 区号E 块内地址w 1 主存 地址 区表存储器 区号E (按地址访问) E 块号b 命中 Cache地址 块号B 相等比较 块失效 比较相等且 有效位为1， 访问Cache

18 提高Cache速度的一种方法： 直接映象方法的主要优点： 直接映象方式的主要缺点: 把区号存储器与Cache合并成一个存储器
硬件实现很简单, 不需要相联访问存储器 访问速度也比较快, 实际上不做地址变换 直接映象方式的主要缺点: 块的冲突率较高

19 有效位 区号E 块内地址w 1 按地址访问的Cache 区号 E 块号b 相等 块号B 相等比较 访主存 数据0 D0 数据1 D1 …… 数据w-1 Dw-1 1/w … 送CPU

20 组相联映像与变换 定义及规则：各组之间是直接映象，组内各块间是全相联映象。 变换过程，如下图。 讨论： S=nv时，全相联映像；
当主存空间和Cache空间确定时，q+s已确定； s值大，组内页数多，冲突概率小，变换复杂； s值小，组内页数少，冲突概率大，变换简单；

21

22 组内块号s’ 区号nd 块内地址W 主存 地址 块表 nd区号，组内块号s 相联比较 (s个块) 块内地址w 相等 Cache地址 组内块号s 相联比较 不等 组号q 组号q’

23 组相联映象方式的缺点： 实现难度和造价要比直接映象方式高 地址变换过程： 用主存地址的组号G按地址访问块表存储器
组相联映象方式的优点： 块的冲突概率比较低 块的利用率大幅度提高 块失效率明显降低 组相联映象方式的缺点： 实现难度和造价要比直接映象方式高 地址变换过程： 用主存地址的组号G按地址访问块表存储器 把读出来的一组区号和块号与主存地址中的区号和块号进行相联比较 如果有相等的，表示Cache命中 如果没有相等的，表示Cache没有命中

24 段相联映象 减少相联目录表的容量，降低成本，提高地址变换速度。 组间全相联，组内直接映象。

25 替换算法的实现 常采用LRU算法，LRU算法是堆栈型算法 由于Cache的调块时间是微秒级，不能采用程序换道 替换算法全部采用硬件途径实现

26 堆栈法 (块号) 近期最近访问 过的块号 近期最久没有 访问的块号 需重新排序的块号 都下推一行 被访问的块号 （经相联比较找到）

27 比较对法 让各个块成对组合，用一个触发器的状态表示该比较对内两块访问的远近次序，再经门电路就可找到LRU块。
适用于组内块数较少的组相联映像Cache。 & TAB TAC TBC 访问B 访问C 访问A 1

28 替换算法的设计要考虑的问题 如何对每次访问进行纪录（适用位法、堆栈法、比较对法所用的记录方法都不同）
如何根据所纪录的信息来判定近期内哪一块是最久没有被访问过的 Cache替换算法的主要特点： 全部用硬件实现

29 Cache存储器的透明性及性能分析 Cache的透明性 Cache的取算法 Cache存储器性能分析

30 Cache的透明性和一致性问题 由于Cache存储器的地址变换和块替换算法全由硬件实现，因此Cache-主存存储层次对应用程序员和系统程序员都是透明的。 本节讨论的内容仅限于单处理机、单存储器 造成Cache与主存的不一致的原因： 由于CPU写Cache，没有立即写主存 由于IO处理机或IO设备写主存

31 CPU X’ I/O X Cache 主存储器 (a) CPU写Cache (b) I/O写主存 Cache与主存不一致的两种情况

32 Cache的透明性 写回法（抵触修改法，WB）：是在CPU执行写操作时，信息只写入Cache，仅当需要被替换时，才将以被写入过的Cache块先送回主存，然后再调入新块。 写直达法（直达法，WT）：利用Cache—主存存储层次在处理机和主存之间的直接通路，每当处理机写入Cache的同时，也通过此通路直接写入主存。

33 写回法与写直达法的优缺点比较 可靠性，写直达法优于写回法 与主存的通信量,写回法少于写直达法
例如：写操作占总访存次数的20％, Cache命中率为99%, 每块4个字。当Cache发生块替换时, 有30%块需要写回主存, 其余的因未被修改过而不必写回主存。则对于WT法, 写主存次数占总访存次数的20%。而WB法为(1-99%) *30%*4=1.2%。因此, WB法与主存的通信量要比WT法少10多倍。

34 写回法与写直达法的优缺点比较 控制的复杂性：写直达法比写回法简单 硬件实现的代价：写回法要比写直达法好 采用何种算法与适用场合有关
单处理机（节省成本）：写回法 共享主存的多处理机（保证信息交换可靠）：写直达法

35 目前，在写回法中采用按写分配法，在写直达法中采用不按写分配法。
写Cache的两种方法： 不按写分配法：在写Cache不命中时，只把所要写的字写入主存。 按写分配法：在写Cache不命中时，还把一个块从主存读入Cache。 目前，在写回法中采用按写分配法，在写直达法中采用不按写分配法。

36 Cache的取算法 按需取进法：出现Cache块失效时，才将要访问的字所在的块（行）取进。 预取法 采用预取法并非能提高命中率，其他因素
恒预取：只要访问到主存第i块的某个字，不论Cache是否命中，恒发预取命令。 不命中时预取：近当访问第i块不命中时，才预取命令。 采用预取法并非能提高命中率，其他因素 块的大小 预取开销

37 说明 采用缓冲器技术是减少预取干扰的好办法 模拟结果表明 恒预取法使不命中率降低75%--80%
不命中率时预取法使不命中率降低30%--40% 但前者所引起的Cache、主存间传输量的增加要比后者大得多。

38 Cache存储器性能分析 不命中率与Cache的容量、组的大小和快的大小的关系 Cache-主存存储层次的等效速度与命中率的关系推导

39 块的大小、组的大小与Cache容量对Cache命中的影响
不命中率 1-Hc Cache容量 组的大小一定 块的大小减小 不命中率 1-Hc Cache容量 块的大小一定 组的大小减小 块的大小、组的大小及Cache容量增大时都能提高命中率

40 Cache-主存存储层次的等效速度与命中率的关系推导
设：tc 为Cache的访问时间， tm为主存周期， Hc为访Cache的命中率。 则：Cache的等效存储周期 ta= Hc tc+(1- Hc) tm 因为：主存与CPU之间有直接通路，因此CPU对第二级的访问时间就是tm。

41 （续） 速度提高倍数是： 因为Hc总小于1，可以令

42 分析 由于 因此 不管Cache本身的速度有多高，只要Cache的命中率有限，那么采用Cache-主存存储层次后，速度能提高的最大值是有限的，不会超过

43 举例 Hc=0.5,α=1 ρ的最大值<2 Hc=0.75, α=3 ρ的最大值<4 Hc=1, Hc ρ的期望值 1 0.5
0.25 0.75 2 4 8 Hc=0.5,α=1 ρ的最大值<2 Hc=0.75, α=3 ρ的最大值<4 Hc=1,

44 举例 由于Cache的命中率一般比0.9大的多，可达0.996，因此ρ接近于所期望的tm/tc Hc受Cache容量的影响很大。
容量为4kb时，Hc=0.93 容量为8kb时，Hc=0.97

45 举例 因此在tm/tc=0.12时 4KB的Cache，速度的倍数是 8KB的Cache，速度的倍数是 增加4KB容量，带来层次速度的提高：

46 Cache的容量对机器速度的关系 机器速度的单位是MIPS(每秒执行百万条指令) 主存采用多体交叉存取 机器速度 (MIPS) 10 20
30 200 400 600 800 1000 主存访问 时间(ns) 无Cache 10ns 4k ns 64k ns 16k ns 64k ns 64k ns Cache CPU 容量 拍宽

47 续 主存速度和CPU周期一定时，Cache容量变化，机器速度变化。
Cache容量4KB，CPU拍宽10ns，主存周期1μs，机器速度约为5MPIS 同样条件下，Cache容量增加到64KB，机器速度可能达15MPIS 没有Cache时，机器速度可能只有2MIPS

48 续 Cache容量的增大，可以显著降低对主存速度的要求
要达到机器速度为15MIPS，对于10ns的CPU拍宽、4KB容量的Cache，要求主存访问周期为200ns Cache容量增达到64KB时，主存周期可以降低到1μs

49 §4 Cache--主存--辅存存储层次 在大部分计算机系统中，既有虚拟存储器，也有Cache存储系统。 存储系统可以有多种构成方法
不同的构成只是实现技术不同

50 Cache Ý系统程序员看 主存储器 速度接近Cache 的速度，存储容 量是主存的容量 每位价格接近主 存储器 Cache存储系统

51 主存 储器 Ý应用程序员看 磁盘 存储器 速度接近主存储 器的速度，存储 容量是虚拟地址 空间，每位价格 接近磁盘存储器 虚拟存储系统 Cache 主存储器 磁盘存储器 一种三级存储系统 一种新的二级存储系统

52 存储系统的几种组织方式 CPU 虚拟 地址 MMU Cache 主存 储器 物理 地址 数据或指令 物理地址

53 存储系统的几种组织方式（续） 物理 地址 虚拟地址 MMU CPU 主存 储器 数据 或指令 Cache 数据或指令
一个存储系统组织方式：虚拟地址Cache存储系统；如Intel公司的i860等处理机采用这种组织方式。 CPU 虚拟地址 MMU Cache 主存 储器 数据或指令 物理 地址 数据 或指令 全Cache系统。没有主存储器，Cache－磁盘存储系统。

54 主存保护（选讲）

55 小结 存储系统与存储体系 并行主存频宽的分析 存储体系的性能参数 虚拟存储器的管理方式 四种地址映像与变换的含义与区别 Cache的工作原理