计算机系统结构-第5章(2016年-second)

1/32▲计算机系统结构讲义第5章存储层次讲解者：刘东波联系方式：155748848452/32▲计算机系统结构讲义1Cache性能分析2降低Cache不命中率的方法3本讲小结本讲主要内容3/32▲计算机系统结构讲义重点与难点1.重点根据平均访存时间公式和CPU执行时间公式进行Cache性能分析降低Cache不命中率的6种方法2.难点Cache性能分析伪相联Cache工作原理4/32▲计算机系统结构讲义5.2.7Cache的性能分析1.不命中率与硬件速度无关容易产生一些误导2.平均访存时间平均访存时间＝命中时间＋失效率×失效开销5.2.7Cache的性能分析非常重要！5/32▲计算机系统结构讲义3.程序执行时间CPU时间＝（CPU执行周期数+存储器停顿周期数）×时钟周期时间其中：存储器停顿时钟周期数＝“读”的次数×读不命中率×读不命中开销＋“写”的次数×写不命中率×写不命中开销存储器停顿时钟周期数＝访存次数×不命中率×不命中开销CPU时间＝（CPU执行周期数+访存次数×不命中率×不命中开销）×时钟周期时间时钟周期时间不命中开销不命中率指令数访存次数时间executionCPIICCPU=IC×（CPIexecution＋每条指令的平均访存次数×不命中率×不命中开销）×时钟周期时间6/32▲计算机系统结构讲义5.2Cache基本知识例5.1用一个和AlphaAXP类似的机器作为第一个例子。假设Cache不命中开销为50个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是2.0个时钟周期，访问Cache不命中率为2%，平均每条指令访存1.33次。试分析Cache对性能的影响。解CPU时间有cache＝IC×（CPIexecution＋每条指令的平均访存次数×不命中率×不命中开销）×时钟周期时间＝IC×（2.0＋1.33×2%×50）×时钟周期时间＝IC×3.33×时钟周期时间7/32▲计算机系统结构讲义5.2Cache基本知识考虑Cache的不命中后，性能为：CPU时间有cache＝IC×（2.0＋1.33×2%×50）×时钟周期时间＝IC×3.33×时钟周期时间实际CPI：3.333.33/2.0=1.67(倍)CPU时间也增加为原来的1.67倍。但若不采用Cache,则：CPI＝2.0＋50×1.33＝68.58/32▲计算机系统结构讲义5.2Cache基本知识4.Cache不命中对于一个CPI较小而时钟频率较高的CPU来说，影响是双重的：CPIexecution越低，固定周期数的Cache不命中开销的相对影响就越大。在计算CPI时，不命中开销的单位是时钟周期数。因此，即使两台计算机的存储层次完全相同，时钟频率较高的CPU的不命中开销较大，其CPI中存储器停顿这部分也就较大。因此Cache对于低CPI、高时钟频率的CPU来说更加重要。9/32▲计算机系统结构讲义例5.2考虑两种不同组织结构的Cache：直接映像Cache和两路组相联Cache，试问它们对CPU的性能有何影响？先求平均访存时间，然后再计算CPU性能。分析时请用以下假设：10/32▲计算机系统结构讲义(1)理想Cache（命中率为100%）情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.3次。(2)两种Cache容量均为64KB，块大小都是32字节。(3)在组相联Cache中，由于多路选择器的存在而使CPU的时钟周期增加到原来的1.10倍。这是因为对Cache的访问总是处于关键路径上，对CPU的时钟周期有直接的影响。(4)这两种结构Cache的不命中开销都是70ns。（在实际应用中，应取整为整数个时钟周期）(5)命中时间为1个时钟周期，64KB直接映像Cache的不命中率为1.4%，相同容量的两路组相联Cache的不命中率为1.0%。11/32▲计算机系统结构讲义5.2Cache基本知识解平均访存时间为：平均访存时间＝命中时间＋不命中率×不命中开销因此，两种结构的平均访存时间分别是：平均访存时间1路＝2.0＋（0.014×70）＝2.98ns平均访存时间2路＝2.0×1.10＋（0.010×70）＝2.90ns两路组相联Cache的平均访存时间比较低。CPU时间＝IC×（CPIexecution＋每条指令的平均访存次数×不命中率×不命中开销）×时钟周期时间＝IC×（CPIexecution×时钟周期时间＋每条指令的平均访存次数×不命中率×不命中开销×时钟周期时间）12/32▲计算机系统结构讲义5.2Cache基本知识因此：CPU时间1路＝IC×(2.0×2＋(1.3×0.014×70))＝5.27×ICCPU时间2路＝IC×(2.0×2×1.10＋(1.3×0.010×70))＝5.31×IC直接映像Cache的平均性能好一些。13/32▲计算机系统结构讲义5.2Cache基本知识1.平均访存时间＝命中时间＋不命中率×不命中开销2.可以从三个方面改进Cache的性能：降低不命中率减少不命中开销减少Cache命中时间3.17种Cache优化技术8种用于降低不命中率5种用于减少不命中开销4种用于减少命中时间5.2.8改进Cache的性能14/32▲计算机系统结构讲义1.三种类型的不命中(3C)强制性不命中(Compulsorymiss)当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性不命中。(冷启动不命中，首次访问不命中）容量不命中(Capacitymiss)如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生不命中。这种不命中称为容量不命中。5.3降低Cache不命中率5.3.1三种类型的不命中15/32▲计算机系统结构讲义5.3降低Cache不命中率冲突不命中(Conflictmiss)在组相联或直接映像Cache中，若太多的块映像到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突不命中。(碰撞不命中，干扰不命中)2.三种不命中所占的比例图示I(绝对值)图示Ⅱ(相对值)16/32▲计算机系统结构讲义5.3降低Cache不命中率17/32▲计算机系统结构讲义5.3降低Cache不命中率18/32▲计算机系统结构讲义5.3降低Cache不命中率可以看出：相联度越高，冲突不命中就越少；强制性不命中和容量不命中不受相联度的影响；强制性不命中不受Cache容量的影响，但容量不命中却随着容量的增加而减少。19/32▲计算机系统结构讲义5.3降低Cache不命中率减少三种不命中的方法强制性不命中：增加块大小，预取（本身很少）容量不命中：增加容量（抖动现象）冲突不命中：提高相联度（理想情况：全相联）许多降低不命中率的方法会增加命中时间或不命中开销20/32▲计算机系统结构讲义5.3降低Cache不命中率1.不命中率与块大小的关系对于给定的Cache容量，当块大小增加时，不命中率开始是下降，后来反而上升了。原因：一方面它减少了强制性不命中；另一方面，由于增加块大小会减少Cache中块的数目，所以有可能会增加冲突不命中。Cache容量越大，使不命中率达到最低的块大小就越大。2.增加块大小会增加不命中开销5.3.2增加Cache块大小21/32▲计算机系统结构讲义5.3降低Cache不命中率163264128256块大小（字节）10%5%0%不命中率256K64K16K4K不命中率随块大小变化的曲线22/32▲计算机系统结构讲义5.3降低Cache不命中率各种块大小情况下Cache的不命中率块大小（字节）Cache容量（字节）1K4K16K64K256K1615.05%8.57%3.94%2.04%1.09%3213.34%7.24%2.87%1.35%0.70%6413.76%7.00%2.64%1.06%0.51%12816.64%7.78%2.77%1.02%0.49%25622.01%9.51%3.29%1.15%0.49%23/32▲计算机系统结构讲义5.3降低Cache不命中率1.最直接的方法是增加Cache的容量缺点:增加成本可能增加命中时间2.这种方法在片外Cache中用得比较多5.3.3增加Cache的容量24/32▲计算机系统结构讲义5.3降低Cache不命中率1.采用相联度超过8的方案的实际意义不大。2.2:1Cache经验规则容量为N的直接映像Cache的不命中率和容量为N/2的两路组相联Cache的不命中率差不多相同。3.提高相联度是以增加命中时间为代价。5.3.4提高相联度25/32▲计算机系统结构讲义5.3降低Cache不命中率1.多路组相联的低不命中率和直接映像的命中速度2.伪相联Cache的优点命中时间小不命中率低5.3.5伪相联Cache(列相联Cache)优点缺点直接映像组相联命中时间小命中时间大不命中率高不命中率低26/32▲计算机系统结构讲义3.基本思想及工作原理（动画演示）在逻辑上把直接映像Cache的空间上下平分为两个区。对于任何一次访问，伪相联Cache先按直接映像Cache的方式去处理。若命中，则其访问过程与直接映像Cache的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。索引至CPU取出数据送往CPU伪相联组……27/32▲计算机系统结构讲义5.3降低Cache不命中率5.缺点：多种命中时间4.快速命中与慢速命中要保证绝大多数命中都是快速命中。不命中开销28/32▲计算机系统结构讲义5.3降低Cache不命中率1.指令和数据都可以预取2.预取内容既可放入Cache，也可放在外缓冲器中。例如：指令流缓冲器3.指令预取通常由Cache之外的硬件完成4.预取效果Joppi的研究结果指令预取(4KB，直接映像Cache，块大小＝16字节)1个块的指令流缓冲器：捕获15％～25％的不命中4个块的指令流缓冲器：捕获50％16个块的指令流缓冲器：捕获72％5.3.6硬件预取29/32▲计算机系统结构讲义5.3降低Cache不命中率数据预取(4KB,直接映像Cache)1个数据流缓冲器：捕获25％的不命中还可以采用多个数据流缓冲器Palacharla和Kessler的研究结果流缓冲器：既能预取指令又能预取数据对于两个64KB四路组相联Cache来说：8个流缓冲器能捕获50％～70％的不命中预取应利用存储器的空闲带宽，不能影响对正常不命中的处理，否则可能会降低性能。30/32▲计算机系统结构讲义5.3降低Cache不命中率1.一种能减少冲突不命中次数而又不影响时钟频率的方法。2.基本思想在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，称为“牺牲”Cache（VictimCache）。用于存放被替换出去的块(称为牺牲者)，以备重用。工作过程5.3.9“牺牲”Cache31/32▲计算机系统结构讲义5.3降低Cache不命中率3.作用对于减小冲突不命中很有效，特别是对于小容量的直接映像数据Cache，作用尤其明显。例如项数为4的VictimCache:能使4KBCache的冲突不命中减少20%～90%32/32▲计算机系统结构讲义本章小结1.掌握Cache性能分析的方法，熟练运用公式计算CPU执行时间和平均访存时间2.掌握Cache不命中的三种类型的产生原因及其相互关联3.掌握常见6种降低Cache不命中率的方法