强制性失效Compulsorymiss当第一次访问一个块时该

《强制性失效Compulsorymiss当第一次访问一个块时该》由会员分享，可在线阅读，更多相关《强制性失效Compulsorymiss当第一次访问一个块时该（51页珍藏版）》请在装配图网上搜索。

1、151(1)(1)强制性失效强制性失效(Compulsory miss)(Compulsory miss)当第一次访问一个块时，该块不在当第一次访问一个块时，该块不在 CacheCache中，需从下一级存储器中调入中，需从下一级存储器中调入CacheCache，这就是这就是强制性失效。强制性失效。(冷启动失效，首次访问失效。冷启动失效，首次访问失效。)(2)(2)容量失效容量失效(Capacity miss)(Capacity miss)如果程序执行时所需的块不能全部调如果程序执行时所需的块不能全部调 入入CacheCache中，则当某些块被替换后，若又中，则当某些块被替换后，若又5.3 降低

2、Cache失效率的方法1.三种失效(3C)第五章 存储层次251 重新被访问，就会发生失效。这种失效称重新被访问，就会发生失效。这种失效称 为为容量失效。容量失效。(3)(3)冲突失效冲突失效(Conflict miss)(Conflict miss)在组相联或直接映象在组相联或直接映象CacheCache中，若太多中，若太多 的块映象到同一组的块映象到同一组(块块)中，则会出现该组中，则会出现该组 中某个块被别的块替换中某个块被别的块替换(即使别的组或块有即使别的组或块有 空闲位置空闲位置)，然后又被重新访问的情况。这，然后又被重新访问的情况。这 就是发生了就是发生了冲突失效。冲突失效。(碰

3、撞失效，干扰失效碰撞失效，干扰失效)5.3 降低Cache 失效率的方法3512.三种失效所占的比例(SPEC92)(SPEC92)表表5.55.5 5.3 降低Cache 失效率的方法图示图示I(I(绝对值绝对值)图示图示(相对值相对值)651可以看出：可以看出：(1)(1)相联度越高，冲突失效就越少；相联度越高，冲突失效就越少；(2)(2)强制性失效和容量失效不受相联度的影响；强制性失效和容量失效不受相联度的影响；(3)(3)强制性失效不受强制性失效不受CacheCache容量的影响，但容容量的影响，但容 量失效却随着容量的增加而减少；量失效却随着容量的增加而减少；(4)(4)表中的数据符

4、合表中的数据符合2:12:1的的CacheCache经验规则经验规则，即，即 大小为大小为N N 的直接映象的直接映象CacheCache的失效率约等于的失效率约等于 大小为大小为N N/2/2 的两路组相联的两路组相联CacheCache的失效率。的失效率。751强制性失效：强制性失效：增加块大小，预取增加块大小，预取 (本身很少本身很少)容量失效：容量失效：增加容量增加容量 (抖动现象抖动现象)冲突失效：冲突失效：提高相联度提高相联度 (理想情况：全相联理想情况：全相联)3.减少三种失效的方法4.许多降低失效率的方法会增加命中时间或 失效开销5.3 降低Cache 失效率的方法8515.3

5、.1 增加Cache块大小1.失效率与块大小的关系 (1)(1)对于给定的对于给定的CacheCache容量，当块大小增加容量，当块大小增加 失效率开始是下降，后来反而上升了；失效率开始是下降，后来反而上升了；(2)Cache(2)Cache容量越大，使失效率达到最低的容量越大，使失效率达到最低的 块大小就越大。块大小就越大。5.3 降低Cache 失效率的方法95110512.2.增加块大小会增加失效开销增加块大小会增加失效开销3.3.例题例题1151例例 5.45.4 假定存储系统在延迟假定存储系统在延迟4040个时钟周期后，每个时钟周期后，每2 2个个时钟周期能送出时钟周期能送出1616

6、个字节。即个字节。即:经过经过4242个时钟周期，个时钟周期，它可提供它可提供1616个字节；经过个字节；经过4444个时钟周期，可提供个时钟周期，可提供3232个字节；依此类推。试问对于表个字节；依此类推。试问对于表5-65-6中列出的各种中列出的各种容量的容量的CacheCache，在块大小分别为多少时，平均访存，在块大小分别为多少时，平均访存时间最小？时间最小？解解：解题过程解题过程 1KB1KB、4KB4KB、16KB Cache:16KB Cache:块大小块大小3232字节字节 64KB64KB、256KB Cache:256KB Cache:块大小块大小6464字节字节5.3 降

7、低Cache 失效率的方法块大小块大小（字节）（字节）失效开销失效开销（时钟周期）（时钟周期）Cache容量（字节）容量（字节）1K4K16K64K256K16427.3214.5992.6551.8571.45832446.8704.1862.2631.5941.30864487.6054.3602.2671.5091.2451285610.3185.3572.5511.5711.2742567216.8477.8473.3691.8281.35313515.3.2 提高相联度1.采用相联度超过8的方法实际意义不大2.2:1 Cache经验规则 容量为容量为N N 的直接映象的直接映象Cac

8、heCache 容量为容量为N N/2/2的两路组相联的两路组相联CacheCache3.提高相联度是以增加命中时间为代价 例如：例如：TTLTTL或或ECLECL板级板级CacheCache，两路组相联：，两路组相联：增加增加1010 定制的定制的CMOS Cache,CMOS Cache,两路组相联：两路组相联：增加增加2 25.3 降低Cache 失效率的方法14514.例题 假定提高相联度会按下列比例增大处理器假定提高相联度会按下列比例增大处理器时钟周期：时钟周期：时钟周期时钟周期2 2路路 1.101.10时钟周期时钟周期1 1路路 时钟周期时钟周期4 4路路 1.121.12时钟周

9、期时钟周期1 1路路 时钟周期时钟周期8 8路路 1.141.14时钟周期时钟周期1 1路路 假定命中时间为假定命中时间为1 1个时钟，直接映象情况个时钟，直接映象情况下失效开销为下失效开销为5050个时钟周期，而且假设不必将个时钟周期，而且假设不必将失效开销取整。使用表失效开销取整。使用表5 55 5中的失效率，试问中的失效率，试问当当CacheCache为多大时，以下不等式成立？为多大时，以下不等式成立？例例 5.55.55.3 降低Cache 失效率的方法1551平均访存时间平均访存时间8 8路路 平均访存时间平均访存时间4 4路路平均访存时间平均访存时间4 4路路 平均访存时间平均访存

10、时间2 2路路平均访存时间平均访存时间2 2路路 平均访存时间平均访存时间1 1路路解解：在各种相联度的情况下，平均访存时间分在各种相联度的情况下，平均访存时间分别为：别为：平均访存时间平均访存时间8 8路路 =命中时间命中时间8 8路路 +失效率失效率8 8路路 失效开销失效开销8 8路路 =1.14 1.14失效率失效率8 8路路5050 平均访存时间平均访存时间4 4路路 =1.12 1.12 失效率失效率4 4路路5050 平均访存时间平均访存时间2 2路路 =1.10 1.10 失效率失效率2 2路路5050 平均访存时间平均访存时间1 1路路 =1.00 1.00 失效率失效率1

11、1路路50505.3 降低Cache 失效率的方法1651 在每种情况下的失效开销相同，都是在每种情况下的失效开销相同，都是5050个时钟周期。把相应的失效率代入上式，个时钟周期。把相应的失效率代入上式，即可得平均访存时间。即可得平均访存时间。例如，例如，1KB1KB的直接映象的直接映象CacheCache的平均的平均访存时间为：访存时间为：平均访存时间平均访存时间1 1路路 1.001.00(0.133(0.13350)50)7.657.65 容量为容量为128KB128KB的的8 8路组相联路组相联CacheCache的平均的平均访存时间为：访存时间为：平均访存时间平均访存时间8 8路路

12、1.141.14(0.006(0.00650)50)1.441.44表表5-85-85.3 降低Cache 失效率的方法Cache容量容量（K字节）字节）相联度（路）相联度（路）124817.656.606.225.4425.904.904.624.0944.603.953.573.1983.303.002.872.59162.452.202.122.04322.001.801.771.79641.701.601.571.591281.501.451.421.4418511 1.基本思想 在在CacheCache和它从下一级存储器调数据和它从下一级存储器调数据 的通路之间设置一个全相联的小的通

13、路之间设置一个全相联的小CacheCache，用于存放被替换出去的块用于存放被替换出去的块(称为称为VictimVictim)，以备重用。以备重用。工作过程工作过程5.3.3 Victim Cache5.3 降低Cache 失效率的方法19512051 对于减小冲突失效很有效，特别是对对于减小冲突失效很有效，特别是对于小容量的直接映象数据于小容量的直接映象数据CacheCache，作用尤其，作用尤其明显。明显。例如，项数为例如，项数为4 4的的Victim Cache:Victim Cache:使使4KB Cache4KB Cache的冲突失效减少的冲突失效减少20%20%90%90%2.作用

14、5.3 降低Cache 失效率的方法21511.直接映象 vs组相联5.3.4 伪相联Cache2 2.伪相联Cache优点优点缺点缺点直接映象直接映象组相联组相联命中时间小命中时间小命中时间大命中时间大失效率高失效率高失效率低失效率低取直接映象及组相联两者的优点：取直接映象及组相联两者的优点：命中时间小，失效率低命中时间小，失效率低5.3 降低Cache 失效率的方法2251(1)(1)基本思想及工作原理基本思想及工作原理 (动画演示动画演示)在逻辑上把直接映象在逻辑上把直接映象CacheCache的空间上下的空间上下 平分为两个区。对于任何一次访问，伪相联平分为两个区。对于任何一次访问，伪

15、相联 CacheCache先按直接映象先按直接映象CacheCache的方式去处理。若的方式去处理。若 命中，则其访问过程与直接映象命中，则其访问过程与直接映象CacheCache的情的情 况一样。若不命中，则再到另一区相应的位况一样。若不命中，则再到另一区相应的位 置去查找。若找到，则发生了伪命中，否则置去查找。若找到，则发生了伪命中，否则 就只好访问下一级存储器。就只好访问下一级存储器。(2)(2)快速命中与慢速命中快速命中与慢速命中 要保证绝大多数命中都是快速命中。要保证绝大多数命中都是快速命中。5.3 降低Cache 失效率的方法235124513.例题例例5.65.6 假设当在按直接

16、映象找到的位置处没有发假设当在按直接映象找到的位置处没有发现匹配、而在另一个位置才找到数据现匹配、而在另一个位置才找到数据(伪命中伪命中)需要需要2 2个额外的周期。仍用上个例子中的数据，个额外的周期。仍用上个例子中的数据，问：当问：当CacheCache容量分别为容量分别为2KB2KB和和128KB128KB时，直接时，直接映象、两路组相联和伪相联这三种组织结构中，映象、两路组相联和伪相联这三种组织结构中，哪一种速度最快？哪一种速度最快？5.3 降低Cache 失效率的方法2551首先考虑标准的平均访存时间公式：首先考虑标准的平均访存时间公式：平均访存时间平均访存时间伪相联伪相联 命中时间命

17、中时间伪相联伪相联失效率失效率伪相联伪相联失效开销失效开销伪相联伪相联由于：由于：失效率失效率伪相联伪相联失效率失效率2 2路路 命中时间命中时间伪相联伪相联命中时间命中时间1 1路路伪命中率伪命中率伪相联伪相联2 2；伪命中率伪命中率伪相联伪相联命中率命中率2 2路路命中率命中率1 1路路 (1(1失效率失效率2 2路路)(1(1失效率失效率1 1路路)失效率失效率1 1路路失效率失效率2 2路路解：解：5.3 降低Cache 失效率的方法2651故：故：平均访存时间平均访存时间伪相联伪相联 命中时间命中时间1 1路路(失效率失效率1 1路路失效率失效率2 2路路)2 2 失效率失效率2 2

18、路路失效开销失效开销1 1路路将表将表5 55 5中的数据代入上面的公式，得：中的数据代入上面的公式，得：平均访存时间平均访存时间伪相联，伪相联，2KB2KB 1 1(0.098(0.0980.076)0.076)2 2(0.076(0.07650)50)4.8444.844 平均访存时间平均访存时间伪相联，伪相联，128KB128KB 1 1(0.010(0.0100.007)0.007)2 2(0.007(0.00750)50)1.3561.3565.3 降低Cache 失效率的方法2751根据上一个例子中的表根据上一个例子中的表5 58 8，对于，对于2KB Cache2KB Cache

19、，可得：可得：平均访存时间平均访存时间1 1路路 5.90 5.90 个时钟个时钟 平均访存时间平均访存时间2 2路路 4.90 4.90 个时钟个时钟对于对于128KB128KB的的CacheCache有，可得：有，可得：平均访存时间平均访存时间1 1路路 1.50 1.50 个时钟个时钟 平均访存时间平均访存时间2 2路路 1.45 1.45 个时钟个时钟可见，对于这两种可见，对于这两种CacheCache容量，伪相联容量，伪相联CacheCache都是速度最快的。都是速度最快的。缺点：缺点：多种命中时间多种命中时间5.3 降低Cache 失效率的方法28515.3.5 硬件预取技术1.指

20、令和数据都可以预取2.预取内容既可放入Cache，也可放在 外缓冲器中 例如：指令流缓冲器例如：指令流缓冲器3.预取效果 (1)(1)JoppiJoppi的研究结果的研究结果 指令预取：指令预取：(4KB(4KB，直接映象，直接映象Cache,Cache,块大小块大小1616字节字节)5.3 降低Cache 失效率的方法29511 1个块的指令流缓冲器：个块的指令流缓冲器：捕获捕获15152525 的失效的失效4 4个块的指令流缓冲器：个块的指令流缓冲器：捕获捕获50501616个块的指令流缓冲器：个块的指令流缓冲器：捕获捕获7272 数据预取：数据预取：(4KB,(4KB,直接映象直接映象C

21、ache)Cache)1 1个数据流缓冲器：个数据流缓冲器：捕获捕获2525的失效的失效 还可以采用多个数据流缓冲器还可以采用多个数据流缓冲器(2)Palacharla(2)Palacharla和和KesslerKessler的研究结果的研究结果 流缓冲器：流缓冲器：既能预取指令又能预取数据既能预取指令又能预取数据 对于两个对于两个64KB64KB四路组相联四路组相联CacheCache来说：来说：8 8个流缓冲器能个流缓冲器能捕获捕获50507070的失效。的失效。5.3 降低Cache 失效率的方法30514.例题例例5.75.7 Alpha AXP 21064Alpha AXP 2106

22、4采用指令预取技术，其实际采用指令预取技术，其实际失效率是多少？若不采用指令预取技术，失效率是多少？若不采用指令预取技术，AlphaAlphaAPX 21064APX 21064的指令的指令CacheCache必须为多大才能保持平均访必须为多大才能保持平均访存时间不变？存时间不变？解：解：假设从预取缓冲器中找到所需指令需多花假设从预取缓冲器中找到所需指令需多花1 1个个时钟周期。时钟周期。平均访存时间平均访存时间预取预取 命中时间失效率命中时间失效率预取命中率预取命中率1 1 失效率失效率(1(1预取命中率预取命中率)失效开销失效开销5.3 降低Cache 失效率的方法3151假设：假设：预取

23、命中率预取命中率2525 命中时间命中时间1 1个时钟周期个时钟周期 失效开销失效开销5050个时钟周期个时钟周期 由表由表5.45.4可知，可知，8KB8KB指令指令CacheCache的失效率的失效率1.101.10 故平均访存时间故平均访存时间预取预取 1 1(1.10%(1.10%25%25%1)1)(1.10%(1.10%(1(125%)25%)50)50)1 10.002750.002750.4125 0.4125 1.4151.415 由公式：由公式：平均访问时间命中时间失效率平均访问时间命中时间失效率失效开销失效开销5.3 降低Cache 失效率的方法3251可得相应的失效率为

24、：可得相应的失效率为：失效率失效率(平均访问时间命中时间平均访问时间命中时间)/)/失效开销失效开销 (1.451(1.4511)/501)/500.830.838KB Cache8KB Cache 带预取的带预取的8kB Cache8kB Cache失效率1.101.100.830.8316KB Cache16KB Cache0.640.645.3 降低Cache 失效率的方法33515.3.6 由编译器控制的预取1.预取的类型 寄存器预取：寄存器预取：把数据取到寄存器中把数据取到寄存器中 CacheCache预取：预取：只将数据取到只将数据取到CacheCache中中 故障性预取：故障性预

25、取：预取时，若出现虚地址故障预取时，若出现虚地址故障 或违反访问权限，就会发生异常。或违反访问权限，就会发生异常。非故障性预取：非故障性预取：预取时，若出现虚地址故预取时，若出现虚地址故 障或违反访问权限，并不会导致异常，只障或违反访问权限，并不会导致异常，只 是转变为是转变为“不预取不预取”。由编译器加入预取指令，在数据被用到之前由编译器加入预取指令，在数据被用到之前发出预取请求。发出预取请求。5.3 降低Cache 失效率的方法34514.例题2.在预取数据的同时，处理器应能继续执行 只有这样，预取才有意义。只有这样，预取才有意义。非阻塞非阻塞Cache(Cache(非锁定非锁定Cache

26、)Cache)3.循环是预取优化的主要对象 失效开销小时：失效开销小时：循环体展开循环体展开1 12 2次次 失效开销大时：失效开销大时：循环体展开许多次循环体展开许多次5.3 降低Cache 失效率的方法3551例例 5.85.8 对于下面的程序，判断哪些访问可能会导致对于下面的程序，判断哪些访问可能会导致数据数据CacheCache失效。然后，加入预取指令以减少失失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：过预取避免的失效次数。假定：(1)(1)我们用的是一个容量为我们用的是一个容量为8KB

27、8KB、块大小为、块大小为 16B16B的直接映象的直接映象CacheCache，它采用写回法并，它采用写回法并 且按写分配。且按写分配。(2)a(2)a、b b分别为分别为3 3100(3100(3行行100100列列)和和1011013 3 的双精度浮点数组，每个元素都是的双精度浮点数组，每个元素都是8 8个个 字节。当程序开始执行时，这些数据都字节。当程序开始执行时，这些数据都 不在不在CacheCache内。内。5.3 降低Cache 失效率的方法3651for(ifor(i0;i 3;i0;i 3;ii i1)1)for(j for(j0;j 100;j0;j 100;jj j1)1

28、)aij aijbj0bj0bjbj10;10;解：解：(1)1)计算过程计算过程(2)(2)失效情况失效情况 总的失效次数总的失效次数251251次次 (3)(3)改进后的程序改进后的程序5.3 降低Cache 失效率的方法375138513951for(jfor(j0 0，j j100100；j jj j1)1)prefetch(bj prefetch(bj70);70);/*预取预取7 7次循环后所需的次循环后所需的b(j,0)b(j,0)*/prefetch(a0j prefetch(a0j7);7);/*预取预取7 7次循环后所需的次循环后所需的a(0,j)a(0,j)*/a0j a

29、0jbj 0 bj 0*b jb j1010 for(i for(i1;i 3;i1;i 3;ii i1)1)for(j for(j0;j 100;j0;j 100;jj j1)1)prefetch(aij prefetch(aij7);7);/*预取预取7 7次循环后所需的次循环后所需的a(i,j a(i,j)*/aij aijbj0 bj0*bj bj10;10;5.3 降低Cache 失效率的方法4051例例 5 59 9 在以下条件下，计算例在以下条件下，计算例5.85.8中所节约的时间：中所节约的时间：(1)(1)忽略指令忽略指令CacheCache失效，并假设数据失效，并假设数据C

30、acheCache 无冲突失效和容量失效。无冲突失效和容量失效。(2)(2)假设预取可以被重叠或与假设预取可以被重叠或与CacheCache失效重失效重 叠执行，从而能以最大的存储带宽传送叠执行，从而能以最大的存储带宽传送 数据。数据。(3)(3)不考虑不考虑CacheCache失效时，修改前的循环每失效时，修改前的循环每7 7 个时钟周期循环一次。修改后的程序中，个时钟周期循环一次。修改后的程序中，失效情况失效情况 总的失效次数总的失效次数1919次次5.3 降低Cache 失效率的方法4151解：解：修改前：修改前：循环时间循环时间3003007 7 21002100 失效开销失效开销25

31、1251505012550/1465012550/14650 2100 210012550125501465014650 第一个预取循环每第一个预取循环每9 9个时钟周期循环一次，个时钟周期循环一次，而第二个预取循环每而第二个预取循环每8 8个时钟周期循环一个时钟周期循环一 次次(包括外层包括外层forfor循环的开销循环的开销)。(4)(4)一次失效需一次失效需5050个时钟周期。个时钟周期。5.3 降低Cache 失效率的方法4251 修改后：修改后：循环时间循环时间1001009 92002008 825002500 失效时间失效时间19195050950950 2500 2500950

32、95034503450 加速比加速比14650/345014650/34504.24.25.3 降低Cache 失效率的方法43515.3.7 编译器优化2KB Cache:2KB Cache:降低降低50508KB Cache8KB Cache：降低降低75%75%1.基本思想 在编译时，对程序中的指令和数据进行在编译时，对程序中的指令和数据进行重新组织，以降低重新组织，以降低CacheCache失效率。失效率。2.McFaring 发现：通过对指令进行重新排序，可有效地降低指令Cache的失效率。5.3 降低Cache 失效率的方法44513.数据对存储位置的限制比指令的少，因此 更便于优

33、化。通过把数据重新组织，使得在一块数通过把数据重新组织，使得在一块数 据被从据被从CacheCache替换出去之前，能最大限度替换出去之前，能最大限度 利用其中的数据利用其中的数据(访问次数最多访问次数最多)(1)(1)数组合并数组合并 举例：举例：/*修改前修改前 */int val SIZE;int val SIZE;int key SIZE;int key SIZE;5.3 降低Cache 失效率的方法4551(2)(2)内外循环交换内外循环交换 举例：举例：/*修改前修改前 */for(jfor(j0;j100;j0;j100;jj j1)1)for(i for(i0;i5000;i0

34、;i5000;ii i1)1)xij xij2 2*xij;xij;/*修改后修改后 */struct merge struct merge int val;int val;int key;int key;struct merge merged_arraysize;struct merge merged_arraysize;5.3 降低Cache 失效率的方法4651(3)(3)循环融合循环融合 举例：举例：/*修改前修改前 */for(i for(i0;iN;i0;iN;ii i1)1)for(j for(j0;jN;j0;jN;jj j1)1)aij aij1/bij1/bij*cij;c

35、ij;/*修改后修改后 */for(ifor(i0;i100;i0;i100;ii i1)1)for(j for(j0;j 000;j0;j 000;jj j1)1)xij xij2 2*xij;xij;5.3 降低Cache 失效率的方法4751 /*修改后修改后 */for(i for(i0;i N;i0;i N;ii i1)1)for(j for(j0;j N;j0;j N;jj j1)1)aij aij1/bij1/bij*cij;cij;dij dijaijaijcij;cij;for(i for(i0;iN;i0;iN;ii i1)1)for(j for(j0;jN;j0;jN;j

36、j j1)1)dij dijaijaijcij;cij;(4)(4)分块分块 把对数组的整行或整列访问改为按块进行。把对数组的整行或整列访问改为按块进行。5.3 降低Cache 失效率的方法4851 举例：举例：/*修改前修改前 */for(ifor(i0;i N;i0;i N;ii i1)1)for(j for(j0;j N;j0;j N;jj j1)1)r r0;0;for(k for(k0;k N;k0;k N;kk k1)1)r rr ryikyik*zkj;zkj;xij xijr;r;计算过程计算过程 失效次数：失效次数：2N2N3 3N N2 25.3 降低Cache 失效率的方

37、法49515051/*修改后修改后 */for(jjfor(jj0;jj N;jj0;jj N;jjjjjj1)1)for(kkfor(kk0;kk N;kk0;kk N;kkkkkk1)1)for(ifor(i0;i N;i0;i N;ii i1)1)for(jfor(jjj;j min(jjjj;j min(jjB B1,N);j1,N);jj j1)1)r r0;0;for(k for(kkk;k min(kkkk;k min(kkB B1,N);k1,N);kk k1)1)r rr ryikyik*zkj;zkj;xij xijxijxijr;r;计算过程计算过程 失效次数：失效次数：2N2N3 3/B/B N N2 25.3 降低Cache 失效率的方法5151