计算机体系结构第五章-2

1、一一. . 三种类型的不命中（三种类型的不命中（3C3C）1. 强制性不命中（强制性失效，强制性不命中（强制性失效，Compulsory miss） 当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性失效。 （也称为冷启动失效或首次访问失效。） 2. 容量不命中（容量失效，容量不命中（容量失效，Capacity miss） 如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。5.3 降低降低CacheCache不命中率不命中率3. 冲突不命中（冲突失效，冲突不命中（冲突失效，Confli

2、ct miss） 在组相联或直接映象Cache中，若太多的块映象到同一组(块)中，则会出现该组中某个块被别的块替换（即使别的组或块有空闲位置），然后又被重新访问的情况。这就是发生了冲突失效。（碰撞失效，干扰失效） 三种失效所占的比例三种失效所占的比例: 表表5.55.3 降低降低CacheCache不命中率不命中率n减少三种失效的方法减少三种失效的方法n强制性失效：强制性失效：增加块大小，预取增加块大小，预取（本身很少）（本身很少）n容量失效：容量失效：增加容量增加容量 （抖动现象）（抖动现象）n冲突失效：冲突失效：提高相联度提高相联度（理想情况：全相联）（理想情况：全相联）n许多降低失效率的

3、方法会增加命中时间或失效开销许多降低失效率的方法会增加命中时间或失效开销5.3 降低降低CacheCache不命中率不命中率二二. 增加增加Cache块大小块大小当Cache的容量一定时，块的大小对命中率的影响非常大。下图表示随着Cache块由小到大的变化，命中率H上升和下降的规律。 最佳最佳 1 初始初始 块大小块大小命中率命中率H增强增强了了空间局部性，空间局部性，减少了强制减少了强制性不命中性不命中 减少了减少了Cache中块中块的数目，可的数目，可能会增加冲能会增加冲突不命中突不命中5.3 降低降低CacheCache不命中率不命中率n措施：措施：适当增加块的大小，但不能增大到使不命中

4、率上升的程度。 各种块大小情况下各种块大小情况下CacheCache的不命中率的不命中率块大小（字节） Cache容量（字节） 1K 4K 16K 64K 256K 16 15.05% 8.57% 3.94% 2.04% 1.09% 32 13.34% 7.24% 2.87% 1.35% 0.70% 64 13.76% 7.00% 2.64% 1.06% 0.51% 128 16.64% 7.78% 2.77% 1.02% 0.49% 256 22.01% 9.51% 3.29% 1.15% 0.49% 负面影响，增加块大小会减少块的数目，可能会增加负面影响，增加块大小会减少块的数目，可能会增

5、加冲突失效。冲突失效。 平均访存时间平均访存时间 命中时间不命中率命中时间不命中率不命中开销不命中开销 当失效开销超过了不命中率下降带来的好处，平均访存时间当失效开销超过了不命中率下降带来的好处，平均访存时间就会增加。就会增加。各种块大小情况下Cache的平均访存时间 块大小（字节） 不命中开销（时钟周期） Cache容量（字节） 1K 4K 16K 64K 256K 16427.321 4.599 2.655 1.857 1.458 32446.870 4.186 2.263 1.594 1.308 64487.605 4.360 2.267 1.509 1.245 1285610.318

6、5.357 2.551 1.5711.274 2567216.847 7.847 3.369 1.828 1.353 另外，增加块大小同时也会增加不命中开销。另外，增加块大小同时也会增加不命中开销。三三. . 提高相联度提高相联度 1. 相联度（相联度（n值）值） 在组相联映像中，如果每组中有n个块，则称该映像规则为n路组相联。 n的不同取值构成了一系列不同相联度的组相联。5.3 降低降低CacheCache不命中率不命中率n当n=1时，为直接映像。n当n=M（Cache的块数）时，为全相联映像。块块0块块V-1块块V块块2V-1块块(K-1)V块块KV-1组组0组组1组组K-1区区0块块(t

7、-1)KV块块(t-1)KV+V-1块块(t-1)KV+V块块(t-1)KV+2V-1块块(tK-1)V块块tKV-1块块0块块V-1块块V块块2V-1块块(K-1)V块块KV-1组组0组组1组组K-1组组(t-1)K组组(t-1)K+1组组tK-1区区t-1主存储器主存储器Cache 2. 相联度越高（即n值越大）， Cache空间的利用率就越高，块冲突概率就越低，因而Cache的不命中率就越低。n同时，提高相联度则可能以增加命中时间为代价。同时，提高相联度则可能以增加命中时间为代价。5.3 降低降低CacheCache不命中率不命中率例例: : 假定提高相联度会按下列比例增大处理器时钟周期

8、： 时钟周期2路 1.10时钟周期1路 时钟周期4路 1.12时钟周期1路 时钟周期8路 1.14时钟周期1路 假定命中时间为一个时钟周期，直接映象情况下失效开销为50个时钟周期，而且假设不必将失效开销取整。使用表5.5中的失效率，试问当Cache容量一定时，各种相联度下的平均访存时间为多少？（是否相联度越大平均访存时间越短）5.3 降低降低CacheCache不命中率不命中率解解 在各种相联度的情况下，平均访存时间分别为： 平均访存时间8路 = 命中时间8路 + 失效率8路失效开销8路 = 1.14 失效率8路 50 平均访存时间4路 = 1.12 失效率4路 50 平均访存时间2路 = 1

9、.10 失效率2路 50 平均访存时间1路 = 1.00 失效率1路 50 把一定容量Cache相应的失效率代入上式，即可得平均访存时间。 例如，1 KB的直接映象Cache的平均访存时间为： 平均访存时间1路 = 1.000.133507.65 128 KB的8路组相联Cache的平均访存时间为： 平均访存时间8路1.140.006501.445.3 降低降低CacheCache不命中率不命中率Cache容量（KB）相联度（路） 124817.65 6.60 6.22 5.44 25.90 4.90 4.62 4.09 44.60 3.95 3.57 3.19 83.30 3.00 2.87

10、 2.59 162.45 2.20 2.12 2.04 322.00 1.80 1.77 1.79 641.70 1.60 1.57 1.59 1281.50 1.45 1.42 1.44 在各种容量和相联度情况下在各种容量和相联度情况下CacheCache的平均访存时间的平均访存时间 采用采用相联度超过相联度超过8的的方法实际意义方法实际意义不大。不大。 2:1 Cache经验规则：经验规则：容量为容量为N 的直接映象的直接映象Cache失效率失效率 容量为容量为N/2的两路的两路组相联组相联Cache失效率。失效率。 提高提高相联度是以增加相联度是以增加命中时间为代价命中时间为代价 ：n

11、TTL或或ECL板级板级Cache，两路组相联：增加两路组相联：增加10nCMOS Cache, 两路组两路组相联：增加相联：增加2 四四. . 增加增加CacheCache容量容量Cache的容量是影响命中率的主要因素，在地址映象方式确定后，Cache的容量越大，命中率也就越高。根据模拟测试的结果，在一般情况下，命中率H和Cache容量S的关系可近似地表示为: 当当Cache容量比较小时，随着容量比较小时，随着Cache容量的增加，命中率提容量的增加，命中率提高得非常快；高得非常快；但命中率达到一定值后，随着Cache容量的增加，命中率提高的速度渐渐放慢了；当Cache的容量增加到无穷大时，

12、命中率达到100%，但这没有实际意义。SH/ 115.3 降低降低CacheCache不命中率不命中率5.4 减少减少CacheCache不命中开销不命中开销一、采用两级一、采用两级CacheCachen应把Cache做得更快？还是更大？答案：二者兼顾，再增加一级Cachen第一级Cache(L1)足够小而快n第二级Cache(L2)容量足够大n性能分析 平均访存时间 命中时间L1不命中率L1不命中开销L1 不命中开销L1 命中时间L2不命中率L2不命中开销L2平均访存时间 命中时间L1不命中率L1 （命中时间L2不命中率L2不命中开销L2） （L2平均访存时间）平均访存时间）n局部不命中率与

13、全局不命中率n局部不命中率该级Cache的不命中次数/到达该级Cache的访问次数 例如：上述式子中的不命中率L2n全局不命中率该级Cache的不命中次数/CPU发出的访存的总次数第二级Cache的全局不命中率为： 全局不命中率L2不命中率L1不命中率L2 评价第二级Cache时，应使用全局不命中率这个指标。它指出了在CPU发出的访存中，究竟有多大比例是穿过各级Cache，最终到达存储器的。5.4 减少减少CacheCache不命中开销不命中开销 例.假设在1000次访存中，第一级Cache不命中40次， 第二级Cache不命中20次。试问：在这种情况下，该Cache系统的局部不命中率和全局不

14、命中率各是多少？ 解: 第一级Cache的不命中率（全局和局部）是40/1000，即4%； 第二级Cache的局部不命中率是20/40，即50%； 第二级Cache的全局不命中率是20/1000，即2%。 5.4 减少减少CacheCache不命中开销不命中开销n对于第二级Cache，我们有以下结论：n在第二级Cache比第一级 Cache大得多的情况下，两级Cache的全局不命中率和容量与第二级Cache相同的单级Cache的不命中率非常接近。n局部不命中率不是衡量第二级Cache的一个好指标，在评价第二级Cache时，应用全局不命中率这个指标。5.4 减少减少CacheCache不命中开销

15、不命中开销 平均访存时间 命中时间L1不命中率L1不命中开销L1 不命中开销L1 命中时间L2不命中率L2不命中开销L2n考虑第二级考虑第二级CacheCache的参数（可用前面的方法减少第二级的参数（可用前面的方法减少第二级cachecache的失效率）例如：的失效率）例如：n容量容量第二级第二级CacheCache的容量一般比第一级的大许多。的容量一般比第一级的大许多。如如512 KB512 KB，1024 KB1024 KBn相联度相联度第二级第二级CacheCache可采用较高的相联度或伪相联方法。可采用较高的相联度或伪相联方法。（L2平均访存时间）平均访存时间）5.4 减少减少Cac

16、heCache不命中开销不命中开销 例：给出有关第二级Cache的以下数据： （1） 2路组相联使命中时间增加10%10%CPUCPU时钟周期时钟周期 （2） 对于直接映象，命中时间L2 1010个时钟周期 （3） 对于直接映象，局部失效率L2 25%25% （4） 对于2路组相联，局部失效率L2 20%20% （5） 失效开销L2 5050个时钟周期 试问第二级Cache的相联度对失效开销的影响如何？5.4 减少减少CacheCache不命中开销不命中开销 解 对一个直接映象的第二级Cache来说，第一级Cache的失效开销为： 失效开销直接映象，L1 1025%50 22.5 个时钟周期

17、对于2路组相联第二级Cache来说，命中时间增加了10%（0.1）个时钟周期，故第一级Cache的失效开销为： 失效开销2路组相联，L1 10.120%50 20.1 个时钟周期 把第二级Cache的命中时间取整，得10或11，则： 失效开销2路组相联，L1 1020%50 20.0 个时钟周期 失效开销2路组相联，L1 1120%50 21.0 个时钟周期 故对于第二级故对于第二级CacheCache来说，来说，2 2路组相联优于直接映象。路组相联优于直接映象。5.4 减少减少CacheCache不命中开销不命中开销二、请求字处理技术二、请求字处理技术n请求字从下一级存储器调入Cache的块

18、中，只有一个字是立即需要的。这个字称为请求字请求字。 n应尽早把请求字发送给CPUn尽早重启动：尽早重启动：调块时，从块的起始位置开始读起。一旦请求字到达，就立即发送给CPU，让CPU继续执行。n请求字优先：请求字优先：调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU。5.4 减少减少CacheCache不命中开销不命中开销 平均访存时间 命中时间不命中率不命中开销 命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是Cache的访问时间限制了处理器时钟频率的提高。 一一. 容量小、结构简单的容量小、结构简单的Cache n小容量Cache有利于

19、减少命中时间。n应使Cache足够小，以便可以与CPU一起放在同一块芯片上。n硬件越简单，速度就越快。5.5 减少命中时间减少命中时间二、虚拟二、虚拟Cache 1.将Cache、主存储器、磁盘存储器组织成“Cache-主存”和“主存-磁盘”两个独立的存储系统，又称为：物理地址物理地址CacheCache存储系统。存储系统。 CPU 虚拟地址虚拟地址 物理地址物理地址 MMU数据或指令数据或指令 高速缓冲高速缓冲 Cache 主存储器主存储器存储管存储管理部件理部件5.5 减少命中时间减少命中时间 2.将Cache、主存和磁盘三个存储器组织在一起，构成一个“Cache-主存-磁盘”存储系统。又

20、称为：虚虚拟地址拟地址CacheCache存储系统。存储系统。 如如IntelIntel公司的公司的i860i860等处理机采用这种组织方式等处理机采用这种组织方式 主存储器主存储器 CPU 虚拟地址虚拟地址数据或指令数据或指令MMUCache物理地址物理地址数据或指令数据或指令 能够接受虚能够接受虚拟地址的访问拟地址的访问5.7 虚拟存储器虚拟存储器一一. . 基本工作原理基本工作原理 1. 基本概念基本概念 虚拟存储器是对物理主存的扩展,由软件来实现。这样，从程序员的角度来看，存储空间扩大了。在虚拟存储结构方式下，程序员编制程序时所使用的地址与主存地址是不同的。n通常，把程序使用的地址称为

21、虚拟地址虚拟地址，或称为逻辑地址逻辑地址，这些地址的集合称为虚存空间虚存空间；n实际主存的地址称为实地址实地址，或物理地址物理地址。所有实地址的集合称为存储空间存储空间，其范围就是整个主存的容量。n在采用虚拟存储器的计算机中，程序是与虚存空间相联系的，而执行程序的CPU则是和主存所用的存储空间相联系的。系统为了让CPU执行程序，必须要把虚存空间变换成存储空间，也就是要把程序的逻辑地址变为CPU可以寻址的主存地址。n虚拟存储器根据地址映象方式的不同分为段式段式、页式页式和段页段页式式虚拟存储器。5.7 虚拟存储器虚拟存储器2. 虚拟存储器的地址构成虚拟存储器的地址构成n以页式虚拟存储器为例，在页

22、式虚拟存储器中，把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的块（称为页页），每一页中包含有固定长度的存储单元。n主存储器的页称为实页实页，虚拟存储器的页称为虚页虚页。5.7 虚拟存储器虚拟存储器n地址构成：地址构成：（a） 主存地址主存地址A的组成的组成实页号实页号p页内偏移页内偏移d 用户号用户号U 虚页号虚页号P 页内偏移页内偏移D磁盘号磁盘号磁头号磁头号磁道号磁道号记录号记录号页内偏移页内偏移D（b） 多用户虚拟存储器地址多用户虚拟存储器地址Av的组成的组成（c） 磁盘存储器物理地址的组成磁盘存储器物理地址的组成5.7 虚拟存储器虚拟存储器3.页式虚拟存储器工作原理页式虚拟存储器

23、工作原理U P D内部地址变换内部地址变换 虚拟页号虚拟页号主存实地址主存实地址p d二二. 虚拟存储器的地扯映象和地址变换虚拟存储器的地扯映象和地址变换n虚拟存储器中有三种地址空间： 存储器地址空间、虚拟地址空间和磁盘存储器地址空间。存储器地址空间、虚拟地址空间和磁盘存储器地址空间。n地址映象：地址映象： 虚拟存储器的地址映象是把虚拟地址空间映象到主存储器地址空间，也就是在程序的虚拟地址与主存储器实地址间建立对应关系。n地址变换：地址变换： 地址变换是在程序装入主存储器后，在实际运行时，把程序的虚拟地址变换成主存储器的实地址（内部地址变换）或磁盘存储器地址（外部地址变换）。5.7 虚拟存储器

24、虚拟存储器1. 段式虚拟存储器段式虚拟存储器n段式虚拟存储器地址映象关系段式虚拟存储器地址映象关系段表段表 起始地址起始地址 段号段号 段长段长0124K2K8K0K12K20K0主程序主程序（0段）段）004K2K8K1段段2段段程序空间程序空间0K2K12K4K20K8K主存储器主存储器程序按逻辑关系分程序按逻辑关系分为大小不同的段为大小不同的段5.7 虚拟存储器虚拟存储器n段式虚拟存储器地址变换过程段式虚拟存储器地址变换过程 多用户虚地址多用户虚地址 用户号用户号U 段号段号S 段内偏移段内偏移D 主存实地址主存实地址段表基地址寄存器堆段表基地址寄存器堆 0 N 7 段表基地址段表基地址

25、 段表长度段表长度 B 段号段号 起始地址起始地址 装入位装入位 段长段长 访问方式访问方式 段表（每个用户或作业）段表（每个用户或作业） B 0 1 2 3 4 5 6 若为若为 “0”,表表示要访问的段不示要访问的段不在主存里在主存里,其他其他项可用来存放该项可用来存放该段在磁盘存储器段在磁盘存储器中的起始地址等中的起始地址等信息信息。5.7 虚拟存储器虚拟存储器n段式虚拟存储器优点：段式虚拟存储器优点： 适宜于编制相对独立的模块化程序。 便于实现程序和数据的共享。 程序的动态链接和调度比较容易。 便于实现信息保护。n段式虚拟存储器缺点：段式虚拟存储器缺点： 调入调出时容易产生碎片，使主存

26、储器空间利用不充分。 对磁盘存储器的管理比较困难。 地址变换所花费的开销比较大。5.7 虚拟存储器虚拟存储器2. 页式虚拟存储器页式虚拟存储器n页式虚拟存储器把虚拟地址空间等分成大小相同的块，每块大小相同的块，每块称为一页称为一页，相应地，也把主存储器的地址空间等分成和页大小相同的块（页）。5.7 虚拟存储器虚拟存储器n页式虚拟存储器地址变换过程页式虚拟存储器地址变换过程 装入位装入位 修改位修改位 主存页号主存页号 各种标志各种标志 页内偏移页内偏移d 实页号实页号p主存主存实地址实地址p 用户号用户号U 虚页号虚页号P 页内偏移页内偏移D 虚地址虚地址 多用户多用户PaPa1页表基址寄存器

27、页表基址寄存器页表页表5.7 虚拟存储器虚拟存储器n 与段式虚拟存储器相比，页式虚拟存储器的主要优缺点：n优点：优点： 主存储器的利用率比较高。 与段表相比，页表相对比较简单。 地址映象和变换的速度比较快。 因为页的大小为磁盘存储器物理块大小的整数倍，对磁盘存储器的管理和操作比较容易。n缺点：缺点： 程序的模块化性能不好。 页表太大，要占用很大的存储空间。5.7 虚拟存储器虚拟存储器3.3.段页式虚拟存储器段页式虚拟存储器n基本思想是：基本思想是： 对用户用来编写程序的虚拟存储空间采用分段的方法管理，而对主存储器的实地址空间采用分页的方法管理。 在段页式虚拟存储器中，主存储器按固定大小分成页，称为实页；用户仍然按照逻辑的段来编写程序，但每一个段又被分成若干个固定大小的页