存储层次--降低CACHE失效率的方法

1／51(1)强制性失效(Compulsorymiss)当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性失效。(冷启动失效，首次访问失效。)(2)容量失效(Capacitymiss)如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又5.3降低Cache失效率的方法1.三种失效(3C)第五章存储层次虚拟存储器的特点2／51重新被访问，就会发生失效。这种失效称为容量失效。(3)冲突失效(Conflictmiss)在组相联或直接映象Cache中，若太多的块映象到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突失效。(碰撞失效，干扰失效)5.3降低Cache失效率的方法虚拟存储器的特点3／512.三种失效所占的比例(SPEC92)表5.55.3降低Cache失效率的方法虚拟存储器的特点图示I(绝对值)虚拟存储器的特点图示Ⅱ(相对值)6／51可以看出：(1)相联度越高，冲突失效就越少；(2)强制性失效和容量失效不受相联度的影响；(3)强制性失效不受Cache容量的影响，但容量失效却随着容量的增加而减少；(4)表中的数据符合2:1的Cache经验规则，即大小为N的直接映象Cache的失效率约等于大小为N/2的两路组相联Cache的失效率。虚拟存储器的特点7／51强制性失效：增加块大小，预取(本身很少)容量失效：增加容量(抖动现象)冲突失效：提高相联度(理想情况：全相联)3.减少三种失效的方法4.许多降低失效率的方法会增加命中时间或失效开销5.3降低Cache失效率的方法8／515.3.1增加Cache块大小1.失效率与块大小的关系(1)对于给定的Cache容量，当块大小增加失效率开始是下降，后来反而上升了；(2)Cache容量越大，使失效率达到最低的块大小就越大。5.3降低Cache失效率的方法虚拟存储器的特点9／51虚拟存储器的特点10／512.增加块大小会增加失效开销3.例题虚拟存储器的特点11／51例5.4假定存储系统在延迟40个时钟周期后，每2个时钟周期能送出16个字节。即:经过42个时钟周期，它可提供16个字节；经过44个时钟周期，可提供32个字节；依此类推。试问对于表5-6中列出的各种容量的Cache，在块大小分别为多少时，平均访存时间最小？解：解题过程1KB、4KB、16KBCache:块大小＝32字节64KB、256KBCache:块大小＝64字节5.3降低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.35313／515.3.2提高相联度1.采用相联度超过8的方法实际意义不大2.2:1Cache经验规则容量为N的直接映象Cache≈容量为N/2的两路组相联Cache3.提高相联度是以增加命中时间为代价例如：TTL或ECL板级Cache，两路组相联：增加10％定制的CMOSCache,两路组相联：增加2％5.3降低Cache失效率的方法虚拟存储器的特点14／514.例题假定提高相联度会按下列比例增大处理器时钟周期：时钟周期2路＝1.10×时钟周期1路时钟周期4路＝1.12×时钟周期1路时钟周期8路＝1.14×时钟周期1路假定命中时间为1个时钟，直接映象情况下失效开销为50个时钟周期，而且假设不必将失效开销取整。使用表5－5中的失效率，试问当Cache为多大时，以下不等式成立？例5.55.3降低Cache失效率的方法虚拟存储器的特点15／51平均访存时间8路平均访存时间4路平均访存时间4路平均访存时间2路平均访存时间2路平均访存时间1路解：在各种相联度的情况下，平均访存时间分别为：平均访存时间8路=命中时间8路+失效率8路×失效开销8路=1.14＋失效率8路×50平均访存时间4路=1.12＋失效率4路×50平均访存时间2路=1.10＋失效率2路×50平均访存时间1路=1.00＋失效率1路×505.3降低Cache失效率的方法虚拟存储器的特点16／51在每种情况下的失效开销相同，都是50个时钟周期。把相应的失效率代入上式，即可得平均访存时间。例如，1KB的直接映象Cache的平均访存时间为：平均访存时间1路＝1.00＋(0.133×50)＝7.65容量为128KB的8路组相联Cache的平均访存时间为：平均访存时间8路＝1.14＋(0.006×50)＝1.44表5-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.44虚拟存储器的特点18／511.基本思想在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，用于存放被替换出去的块(称为Victim)，以备重用。工作过程5.3.3VictimCache5.3降低Cache失效率的方法虚拟存储器的特点19／51虚拟存储器的特点20／51对于减小冲突失效很有效，特别是对于小容量的直接映象数据Cache，作用尤其明显。例如，项数为4的VictimCache:使4KBCache的冲突失效减少20%～90%2.作用5.3降低Cache失效率的方法21／511.直接映象vs．组相联5.3.4伪相联Cache2.伪相联Cache优点缺点直接映象组相联命中时间小命中时间大失效率高失效率低取直接映象及组相联两者的优点：命中时间小，失效率低5.3降低Cache失效率的方法22／51(1)基本思想及工作原理(动画演示)在逻辑上把直接映象Cache的空间上下平分为两个区。对于任何一次访问，伪相联Cache先按直接映象Cache的方式去处理。若命中，则其访问过程与直接映象Cache的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。(2)快速命中与慢速命中要保证绝大多数命中都是快速命中。5.3降低Cache失效率的方法23／5124／513.例题例5.6假设当在按直接映象找到的位置处没有发现匹配、而在另一个位置才找到数据(伪命中)需要2个额外的周期。仍用上个例子中的数据，问：当Cache容量分别为2KB和128KB时，直接映象、两路组相联和伪相联这三种组织结构中，哪一种速度最快？5.3降低Cache失效率的方法25／51首先考虑标准的平均访存时间公式：平均访存时间伪相联＝命中时间伪相联＋失效率伪相联×失效开销伪相联由于：失效率伪相联＝失效率2路命中时间伪相联＝命中时间1路＋伪命中率伪相联×2；伪命中率伪相联＝命中率2路－命中率1路＝(1－失效率2路)－(1－失效率1路)＝失效率1路－失效率2路解：5.3降低Cache失效率的方法26／51故：平均访存时间伪相联＝命中时间1路＋(失效率1路－失效率2路)×2＋失效率2路×失效开销1路将表5－5中的数据代入上面的公式，得：平均访存时间伪相联，2KB＝1＋(0.098－0.076)×2＋(0.076×50)＝4.844平均访存时间伪相联，128KB＝1＋(0.010－0.007)×2＋(0.007×50)＝1.3565.3降低Cache失效率的方法27／51根据上一个例子中的表5－8，对于2KBCache，可得：平均访存时间1路＝5.90个时钟平均访存时间2路＝4.90个时钟对于128KB的Cache有，可得：平均访存时间1路＝1.50个时钟平均访存时间2路＝1.45个时钟可见，对于这两种Cache容量，伪相联Cache都是速度最快的。缺点：多种命中时间5.3降低Cache失效率的方法28／515.3.5硬件预取技术1.指令和数据都可以预取2.预取内容既可放入Cache，也可放在外缓冲器中例如：指令流缓冲器3.预取效果(1)Joppi的研究结果◆指令预取：(4KB，直接映象Cache,块大小＝16字节)5.3降低Cache失效率的方法29／511个块的指令流缓冲器：捕获15％～25％的失效4个块的指令流缓冲器：捕获50％16个块的指令流缓冲器：捕获72％◆数据预取：(4KB,直接映象Cache)1个数据流缓冲器：捕获25％的失效还可以采用多个数据流缓冲器(2)Palacharla和Kessler的研究结果流缓冲器：既能预取指令又能预取数据对于两个64KB四路组相联Cache来说：8个流缓冲器能捕获50％～70％的失效。5.3降低Cache失效率的方法30／514.例题例5.7AlphaAXP21064采用指令预取技术，其实际失效率是多少？若不采用指令预取技术，AlphaAPX21064的指令Cache必须为多大才能保持平均访存时间不变？解：假设从预取缓冲器中找到所需指令需多花1个时钟周期。平均访存时间预取＝命中时间＋失效率×预取命中率×1＋失效率×(1－预取命中率)×失效开销5.3降低Cache失效率的方法31／51假设：预取命中率＝25％命中时间＝1个时钟周期失效开销＝50个时钟周期由表5.4可知，8KB指令Cache的失效率＝1.10％故平均访存时间预取＝1＋(1.10%×25%×1)＋(1.10%×(1－25%)×50)＝1＋0.00275＋0.4125＝1.415由公式：平均访问时间＝命中时间＋失效率×失效开销5.3降低Cache失效率的方法32／51可得相应的失效率为：失效率＝(平均访问时间－命中时间)/失效开销＝(1.451－1)/50＝0.83％8KBCache带预取的8kBCache失效率1.10％0.83％16KBCache0.64％5.3降低Cache失效率的方法33／515.3.6由编译器控制的预取1.预取的类型◆寄存器预取：把数据取到寄存器中◆Cache预取：只将数据取到Cache中◆故障性预取：预取时，若出现虚地址故障或违反访问权限，就会发生异常。◆非故障性预取：预取时，若出现虚地址故障或违反访问权限，并不会导致异常，只是转变为“不预取”。由编译器加入预取指令，在数据被用到之前发出预取请求。5.3降低Cache失效率的方法34／514.例题2.在预取数据的同时，处理器应能继续执行只有这样，预取才有意义。非阻塞Cache(非锁定Cache)3.循环是预取优化的主要对象失效开销小时：循环体展开1～2次失效开销大时：循环体展开许多次5.3降低Cache失效率的方法35／51例5.8对于下面的程序，判断哪些访问可能会导致数据Cache失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：(1)我们用的是一个容量为8KB、块大小为16B的直接映象Cache，它采用写回法并且按写分配。(2)a、b分别为3×100(3行100列)和101×3的双精度浮点数组，每个元素都是8个字节。当程序开始执行时，这些数据都不在Cache内。5.3降低Cache失效率的方法36／51for(i＝0;i3;i＝i＋1)for(j＝0;j100;j＝j＋1)a[i][j]＝b[j][0]×b[j＋1][0];解：(1)计算过程(2)失效情况总的失效次数＝251次(3)改进后的程序5.3降低Cache失效率的方法37／5138／5139／51for(j＝0，j＜100；j＝j＋1){prefetch(b[j＋7][0]);/*预取7次循环后所需的b(j,0)*/prefetch(a[0][j＋7]);/*预取7次循环后所需的a(0,