计算机组成原理第四章第三节

1、一、概述一、概述二、二、Cache主存结构主存结构三、替换策略三、替换策略第三节第三节 高速缓冲存储器高速缓冲存储器一、概述一、概述1、问题的提出、问题的提出2、Cache 的工作原理的工作原理3、Cache 的基本结构的基本结构4、Cache 的的 读写读写 操作操作5、Cache 的改进的改进避免避免 CPU “空等空等” 现象现象CPU 和主存（和主存（DRAM）的速度差异）的速度差异缓存缓存CPU主存主存容量小容量小速度高速度高容量大容量大速度低速度低程序访问的局部性原理程序访问的局部性原理1、问题的提出、问题的提出2、Cache 的工作原理的工作原理(1) 主存和缓存的编址主存和缓存

2、的编址(2) 命中与未命中命中与未命中(3) Cache 的命中率的命中率(4) Cache 主存系统的效率主存系统的效率主存和缓存按块存储主存和缓存按块存储 块的大小相同块的大小相同B 为块长为块长 主存块号主存块号主存储器主存储器012m1字块字块 0字块字块 1字块字块 M1主存块号主存块号块内地址块内地址m位位b位位n位位M块块B个字个字缓存块号缓存块号块内地址块内地址c位位b位位C块块B个字个字 字块字块 0字块字块 1字块字块 C1012c1标记标记Cache缓存块号缓存块号(1) 主存和缓存的编址主存和缓存的编址缓存共有缓存共有 C 块块主存共有主存共有 M 块块M C主存块主存

3、块 调入调入 缓存缓存主存块与缓存块主存块与缓存块 建立建立 了对应关系了对应关系用用 标记记录标记记录 与某缓存块建立了对应关系的与某缓存块建立了对应关系的 主存块号主存块号命中命中未命中未命中主存块与缓存块主存块与缓存块 未建立未建立 对应关系对应关系主存块主存块 未调入未调入 缓存缓存(2) 命中与未命中命中与未命中与与 Cache 的的 容量容量 与与 块长块长 有关有关 (3) Cache 的命中率的命中率v命中率与命中率与Cache容量容量容量越大，命中率越高；容量越大，命中率越高；当容量达到一定值时，命中率已不因容量增大而明显当容量达到一定值时，命中率已不因容量增大而明显提高；提

4、高；容量是总成本价与命中率的折中值容量是总成本价与命中率的折中值mccNNNhNc为访问为访问Cache的总命中次数的总命中次数Nm为访问主存的总次数为访问主存的总次数v命中率与块长命中率与块长一般每块可取一般每块可取 4 8 个字个字块由小到大增大时，起初会因局部性原理使命中率提高；块由小到大增大时，起初会因局部性原理使命中率提高；若继续增大，则命中率很可能下降；若继续增大，则命中率很可能下降；块长取块长取4、8个可编址的单位即字或字节较好，也可以一个可编址的单位即字或字节较好，也可以一个存取周期内从主存调出的信息长度；个存取周期内从主存调出的信息长度； CRAY_1 16体交叉体交叉 块长

5、取块长取 16 个存储字个存储字 IBM 370/168 4体交叉体交叉 块长取块长取 4 个存储字个存储字（64位位4 = 256位）位）效率效率 e 与与 命中率命中率 有关有关 设设 Cache 命中率命中率 为为 h，访问访问 Cache 的时间为的时间为 tc ， 访问访问 主存主存 的时间为的时间为 tm 则则 e = 100% tc h tc+ (1h) tm 访问访问 Cache 的时间的时间 平均访问时间平均访问时间 e = 100%(4) Cache 主存系统的效率主存系统的效率例例1（书（书4.7）假设）假设CPU执行某段程序时，共访问执行某段程序时，共访问Cache命中

6、命中2000次，访问主存次，访问主存50次。已知次。已知Cache的的存取周期为存取周期为50ns，主存的存取周期为，主存的存取周期为200ns。求。求Cache-主存系统的命中率、效率和平均访问时间。主存系统的命中率、效率和平均访问时间。解：解：1）命中率）命中率 2000/(2000+50)=0.97 2）设访问）设访问Cache时间为时间为t,访问主存时间为访问主存时间为4t e=访问访问Cache时间时间/平均访问时间平均访问时间 =t/(0.97t+0.034t) =0.917 3)平均访问时间平均访问时间 500.97+2000.03=54.5nsCache替换机构替换机构Cach

7、e存储体存储体主存主存Cache地址映射地址映射变换机构变换机构3、Cache 的基本结构的基本结构 访问访问Cache取出信息送取出信息送CPU 访问主存访问主存取出信息送取出信息送CPU将新的主存块将新的主存块调入调入Cache中中执行替换算法执行替换算法 腾出空位腾出空位 结束结束命中？命中？Cache满？满？CPU发出访问地址发出访问地址 开始开始是是否否是是否否读读4、Cache 的的 读写读写 操作操作Cache 和主存的一致性和主存的一致性 写直达法写直达法（Write through） 写回法写回法（Write back） 写操作时数据既写入写操作时数据既写入Cache又写入主

8、存又写入主存 写操作时只把数据写入写操作时只把数据写入 Cache 而不写入主存而不写入主存当当 Cache 数据被替换出去时才写回主存数据被替换出去时才写回主存 写操作时间就是访问主存的时间写操作时间就是访问主存的时间，读操作时不，读操作时不涉及对主存的写操作，更新策略比较容易实现涉及对主存的写操作，更新策略比较容易实现写操作时间就是访问写操作时间就是访问 Cache 的时间的时间，读操作读操作 Cache 失效发生数据替换时，失效发生数据替换时，被替换的块需写回主存，增加了被替换的块需写回主存，增加了 Cache 的复杂性的复杂性写写(1) 增加增加 Cache 的级数的级数片载（片内）片

9、载（片内）Cache片外片外 Cache(2) 统一缓存和分立缓存统一缓存和分立缓存指令指令 Cache数据数据 Cache与主存结构有关与主存结构有关与指令执行的控制方式有关与指令执行的控制方式有关是否流水是否流水Pentium 8K 指令指令 Cache 8K 数据数据 CachePowerPC620 32K 指令指令 Cache 32K 数据数据 Cache5、Cache 的改进的改进二、二、Cache 主存的地址映射主存的地址映射1、直接映射、直接映射2、全相联映射、全相联映射3、组相联映射、组相联映射4、小结、小结字块2m1 字块2c+1 字块2c+11 字块2c +1字块2c 字块

10、2c1字块1字块0主存储体主存储体 字块 1 标记 字块 0 标记字块2c1标记Cache存储体存储体t位位012c1 字块字块地址 主存字 块标记t 位位c 位位b 位位主存地址主存地址 比较器（比较器（t位）位）= 未命中未命中有效位有效位=1？*m位位 Cache内地址内地址否否是是命中命中每个缓存块每个缓存块 i 可以和可以和 若干若干 个个 主存块主存块 对应对应每个主存块每个主存块 j 只能和只能和 一一 个个 缓存块缓存块 对应对应i = j mod C字块字块2c+1字块字块2c 字块字块0 字块字块 01、直接映射、直接映射主存地址格式主存地址格式缓存地址格式缓存地址格式主存

11、字块主存字块/ /组标记组标记t t位位CacheCache字块地址字块地址c c位位字块内地址字块内地址b b位位字块内地址字块内地址b b位位CacheCache字块地址字块地址c c位位标记标记t t位位主存主存 中的中的 任一块任一块 可以映射到可以映射到 缓存缓存 中的中的 任一块任一块字块字块2m1字块字块2c1字块字块1 字块字块0字块字块2c1字块字块1字块字块0标记标记标记标记标记标记主存字块标记主存字块标记 字块内地址字块内地址主存地址主存地址m = t + c 位位b位位m = t+cCache 存储器存储器主存储器主存储器 字块字块02、全相联映射、全相联映射主存地址格

12、式主存地址格式缓存地址格式缓存地址格式主存字块标记主存字块标记t+ct+c位位字块内地址字块内地址b b位位字块内地址字块内地址b b位位CacheCache字块地址字块地址c c位位标记标记t+ct+c位位字块字块2m1字块字块2c-r+1 字块字块2c-r + 1 字块字块2c-r字块字块2c-r 字块字块1 字块字块0 字块字块 3标记标记 字块字块 1标记标记字块字块 2c1标记标记 字块字块 2标记标记 字块字块 0标记标记字块字块 2c2标记标记 字块内地址字块内地址组地址组地址主存字块标记主存字块标记s = t + r 位位q = cr 位位b 位位组组012c-r1主存地址主存

13、地址Cache主存储器主存储器m 位位共共 Q 组组，每组内两块（，每组内两块（r = 1)1某一主存块某一主存块 j 按模按模 Q 映射到映射到 缓存缓存 的第的第 i 组组中的中的 任一块任一块i = j mod Q直接映射直接映射全相联映射全相联映射 字块0 字块 1 字块 0 字块2c-r 字块2c-r+13、组相联映射、组相联映射主存地址格式主存地址格式缓存地址格式缓存地址格式主存字块标记主存字块标记t+rt+r位位组地址组地址c-rc-r位位字块内地址字块内地址b b位位字块内地址字块内地址b b位位CacheCache组地址组地址c-rc-r位位标记标记t+rt+r位位组内字组内

14、字块地址块地址r r位位某一某一 主存块主存块 只能固定只能固定 映射到映射到 某一某一 缓存块缓存块直接直接全相联全相联组相联组相联某一某一 主存块主存块 能能 映射到映射到 任一任一 缓存块缓存块某一某一 主存块主存块 只能只能 映射到映射到 某一某一 缓存缓存 组组 中的中的 任一块任一块不灵活，命中率低不灵活，命中率低成本高成本高r=0时是直接映射方式；时是直接映射方式；r=c 是全相联；是全相联；4、小结小结例例1（4.32）某主机主存容量为）某主机主存容量为4MB，Cache容量为容量为16KB，每字块有，每字块有8个字，每个字个字，每个字32位，设计一个四位，设计一个四路组组相联

15、映射的路组组相联映射的Cache组织。组织。 1）画出主存地址字段中各段的位数；）画出主存地址字段中各段的位数； 2）设）设Cache的初态为空，的初态为空，CPU依次从主存第依次从主存第0, 1, 2，。，。，89号单元读出号单元读出90个字（主存一次读出一个字），并重复按此个字（主存一次读出一个字），并重复按此次序读次序读8次，问命中率是多少？次，问命中率是多少？ 3）若）若Cache的速度是主存的的速度是主存的6倍，试问有倍，试问有Cache和无和无Cache相相比，速度约提高多少倍？比，速度约提高多少倍？解：解：1） 字块长度：字块长度： Cache块数：块数： 四路组组：四路组组：

16、Cache组数：组数： 主存容量：主存容量：主存字块标记：主存字块标记：主存字块标记主存字块标记t+rt+r位位1010组地址组地址c-rc-r位位7 7字块内地址字块内地址b b位位5 5832/8=32=25B地址地址5位位16KB/25B=29地址地址9位位2r=4r=229B/22B=27地址地址7位位4MB=222B地址地址22位位22-7-5=10位位2）Cache初态为空初态为空 读第读第0号单元时，没有命中，必须访问主存，号单元时，没有命中，必须访问主存，同时将该字所在的主存块调入同时将该字所在的主存块调入Cache第第0组中的任组中的任一块内，接着读一块内，接着读1-7号单元

17、时均命中；号单元时均命中； 同理读第同理读第8、16、24、。、。、88号单元时均号单元时均未命中，可见未命中，可见CPU在连续读在连续读90个字时有个字时有12个未命个未命中；而后中；而后7次循环读次循环读90个字均命中，命中率为：个字均命中，命中率为：983. 0890128903）设主存存取周期为）设主存存取周期为6t，Cache周期为周期为t； 没有没有Cache的访问时间：的访问时间：6t720 有有Cache的访问时间：的访问时间： 6t12+t(720-12) 速度提高倍数：速度提高倍数：538. 41)12720(1267206ttt例例2 主存容量主存容量4M16位，位，Cache容量容量16K16位，块长位，块长416位，访存地址为字地址。位，访存地址为字地址。1）在直接映射方式下，设计主存地址；）在直接映射方式下，设计主存地址；2）在全相联映射方式下，设计主存的地址；）在全相联映射方式下，设计主存的地址；3）在二路组相联方式下，设计主存地址；）在二路组相联方式下，设计主存地址；主存字块标记主存字块标记8 8CacheCache字块地址字块地址1212字块内地址字块内地址2 2主存字块标记主存字块标记2020字块内地址字块内地址2