计算机系统结构-5.ppt

1,5.2Cache基本知识,5.3降低Cache失效率的方法,5.4减少Cache失效开销,5.1存储器的层次结构,5.5减少命中时间,5.6主存,5.7虚拟存储器,5.8进程保护和虚存实例,5.9AlphaAXP21064存储层次,2,5.1.1从单级存储器到多级存储器,1.从用户的角度来看，存储器的三个主要指标是：容量，速度，价格(每位价格)2.人们对这三个指标的期望3.这三个指标相互矛盾4.解决方法采用多种存储器技术，构成存储层次。演示演示(局部性原理),5.1存储器的层次结构,3,5.1.2存储层次的性能参数,C，H，TA假设：S容量TA访问时间C每位价格下面仅考虑由M1和M2构成的两级存储层次：M1的参数：S1，TA1，C1M2的参数：S2，TA2，C2,1.每位价格CC,C1S1C2S2,S1S2,4,3.平均访问时间TATATA1(1H)TM或TATA1FTMTA1命中时间TM失效开销,2.命中率H和失效率FHN1/(N1N2)N1访问M1的次数N2访问M2的次数失效率F1H,5,5.1.3“Cache主存”和“主存辅存”层次,1.从主存的角度来看“Cache主存”层次：弥补主存速度的不足“主存辅存”层次：弥补主存容量的不足,2.“Cache主存”层次主存与CPU的速度差距“Cache-主存”层次,3.“主存辅存”层次两者的比较,6,5.1.4存储层次的四个问题,当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上?(映象规则),当所要访问的块在高一层存储器中时，如何找到该块?(查找算法),3.当发生失效时，应替换哪一块？(替换算法),4.当进行写访问时，应进行哪些操作?(写策略),1.,2.,7,5.2.1映象规则,1.全相联映象全相联：主存中的任一块可以被放置到Cache中的任意一个位置。举例对比：阅览室位置随便坐特点：空间利用率最高，冲突概率最低，实现最复杂。,5.2Cache基本知识,1存储空间分割与地址计算2Cache和主存分块,8,2.直接映象：,直接映象：主存中的每一块只能被放置到Cache中唯一的一个位置。举例(循环分配)对比：阅览室位置只有一个位置可以坐特点：空间利用率最低，冲突概率最高，实现最简单。对于主存的第i块，若它映象到Cache的第j块，则:jimod(M)（M为Cache的块数）,9,组相联：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。举例组相联是直接映象和全相联的一种折衷,设M2m，则当表示为二进制数时，j实际上就是i的低m位：,3.组相联映象：,m位,j,i：,10,上述的j和k通常称为索引,组的选择常采用位选择算法若主存第i块映象到第k组，则:kimod（G）（G为Cache的组数）设G2g，则当表示为二进制数时，k实际上就是i的低g位：,g位,k,i：,11,绝大多数计算机的Cache:n4想一想：相联度一定是越大越好？,n路组相联：每组中有n个块(nM/G)n称为相联度。相联度越高，Cache空间的利用率就越高，块冲突概率就越低，失效率也就越低。,全相联,直接映象,组相联,n(路数),G(组数),M,M,1,1,1nM,1GM,12,5.2.2查找方法,1.如何确定Cache中是否有所要访问的块？若有的话如何确定其位置？,目录表的结构只需查找候选位置所对应的目录表项并行查找与顺序查找提高性能的重要思想：主候选位置(MRU块)前瞻执行,13,并行查找的实现方法：相联存储器单体多字存储器比较器举例：路组相联并行标识比较（比较器的个数及位数）直接映象Cache的查找过程路相联Cache的查找过程,14,15,16,17,18,19,20,21,22,23,24,5.2.3替换算法,所要解决的问题：当新调入一块，而Cache又已被占满时，替换哪一块？,2.FIFO3.LRU优点：失效率低LRU和随机法的失效率的比较,1.随机法优点：实现简单,25,5.2.4写策略,1.“写”操作所占的比例Load指令：26Store指令：9“写”在所有访存操作中所占的比例：9/(100269)7“写”在访问Cache操作中所占的比例：9/(269)25,3“写”访问有可能导致Cache和主存内容的不一致,2.“写”操作必须在确认是命中后才可进行,26,4两种写策略写直达法执行“写”操作时，不仅写入Cache，而且也写入下一级存储器。写回法执行“写”操作时，只写入Cache。仅当Cache中相应的块被替换时，才写回主存。(设置“污染位”),5两种写策略的比较写回法的优点：速度快，所使用的存储器频带较低；写直达法的优点：易于实现，一致性好。,27,6.写缓冲器,8.写策略与调块写回法按写分配写直达法不按写分配,7.“写”操作时的调块按写分配(写时取)写失效时，先把所写单元所在的块调入Cache，再行写入。不按写分配(绕写法)写失效时，直接写入下一级存储器而不调块。,28,5.2.5Cache举例,例子：DEC的AlphaAXP21064中的内部数据Cache。,1.简介容量：8KB块大小：32B块数：256采用不按写分配映象方法：直接映象“写”策略：写直达写缓冲器大小：4个块,29,2.结构图,3.工作过程“读”访问命中“写”访问命中失效情况下的操作,4.写合并当把数据写入写缓冲器时，判断本次所写入单元的块地址是否与写缓冲器中某个有效块的地址相同，若是，则把新数据与该块合并。“采用写合并”与“不采用写合并”的比较,30,5.混合Cache与分离Cache(1)优缺点(2)失效率的比较(3)分离Cache平均失效率的计算：,访问指令Cache的百分比指令Cache的失效率访问数据Cache的百分比数据Cache的失效率,31,LASTLECTUREREVIEW:,层次存储结构：满足三个期望（大容量，高速度，低价格）CACHEMEMORY层次（解决MEMORY速度不足的问题）MEMORY辅存层次（解决MEMORY容量不足的问题）,CACHEMEMORY层次的信息交换以（快）为单位,映象规则：组相联，全相联，直接映射查找算法：目录表（TAG存储器），并行查找替换算法：随机算法，FIFO,LRU等写策略：写直达，写回法按写分配，不按写分配（写失效）写缓冲，写合并技术,层次存储四大问题：,32,5.2.6性能分析,2.平均访问时间（比失效率更好的指标）平均访问时间命中时间失效率失效开销,例5.1假设Cache的命中时间为1个时钟周期，失效开销为50个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加一个时钟周期(因为混合Cache只有一个端口，无法同时满足两个请求。按照前一章中有关流水线的术语，混合Cache会导致结构冲突)，根据表54所列的失效率，试问指令Cache和数据Cache容量均,1.失效率（常用指标）,平均存储器停顿时间,33,解：如前所述，约75%的访存为取指令。因此，分离Cache的总体失效率为：(75%0.64%)(25%6.47%)2.10%根据表54，容量为32KB的混合Cache的失效率略低一些，只有1.99%.,为16KB的分离Cache和容量为32KB的混合Cache相比，哪种Cache的失效率更低？又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？,100%（100%+26%+9%）=75%,34,平均访存时间公式可以分为指令访问和数据访问两部分：平均访存时间指令所占的百分比(指令命中时间指令失效率失效开销)数据所占的百分比(数据命中时间数据失效率失效开销)所以，两种结构的平均访存时间分别为：平均访存时间分离75%(10.64%50)25%(16.47%50)(75%1.32)(25%4.325)0.9901.0592.05,35,平均访存时间混合75%(11.99%50)25%(111.99%50)(75%1.995)(25%2.995)1.4960.7492.24,3.程序执行时间CPU时间CPU执行程序的时钟周期数时钟周期时间(CPU执行周期数存储器停顿周期数)时钟周期时间其中，存储器停顿周期数访存次数失效率失效开销,理想状态下（全部命中）,36,例5.2我们用一个和AlphaAXP类似的机器作为第一个例子。假设Cache失效开销为50个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是2.0个时钟周期，Cache的失效率为2%，平均每条指令访存1.33次。试分析Cache对性能的影响。,CPU时间ICCPIexe每条指令的平均存储器停顿周期数时钟周期时间,CPU时间ICCPIexe访存次数失效率失效开销/指令数时钟周期时间ICCPIexe访存次数/指令数失效率失效开销时钟周期时间,37,考虑Cache的失效后，性能为：CPU时间有cacheIC(2.0(1.332%50)时钟周期时间IC3.33时钟周期时间,CPU时间IC(CPIexe)时钟周期时间,存储器停顿周期数,指令数,解：,实际CPI：3.333.33/2.0=1.67(倍),38,CPU时间也增加为原来的1.67倍。但若不采用Cache,则：CPI2.0+501.3368.5,39,平均访存时间命中时间失效率失效开销可以从三个方面改进Cache的性能：(1)降低失效率(2)减少失效开销(3)减少Cache命中时间下面介绍15种Cache优化技术,5.2.7改进Cache性能,40,(1)强制性失效(Compulsorymiss)当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性失效。(冷启动失效，首次访问失效。)(2)容量失效(Capacitymiss)如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。,5.3降低Cache失效率的方法,1.三种失效(3C),41,(3)冲突失效(Conflictmiss)在组相联或直接映象Cache中，若太多的块映象到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突失效。(碰撞失效，干扰失效),42,2.三种失效所占的比例,(SPEC92)表5.5图示I(绝对值)图示(相对值)可以看出：(1)相联度越高，冲突失效就越少；(2)强制性失效和容量失效不受相联度的影响；(3)强制性失效不受Cache容量的影响，但容量失效却随着容量的增加而减少；,43,(4)表中的数据符合2:1的Cache经验规则，即大小为N的直接映象Cache的失效率约等于大小为N/2的两路组相联Cache的失效率。,强制性失效：增加块大小，预取(本身很少)容量失效：增加容量(抖动现象)冲突失效：提高相联度(理想情况：全相联),3.减少三种失效的方法,4.许多降低失效率的方法会增加命中时间或失效开销,44,5.3.1增加Cache块大小,2.增加块大小会增加失效开销,1.失效率与块大小的关系(1)对于给定的Cache容量，当块大小增加失效率开始是下降，后来反而上升了；(2)Cache容量越大，使失效率达到最低的块大小就越大。,3.例题,45,考虑两种不同组织结构的Cache：直接映象Cache和两路组相联Cache，试问它们对CPU的性能有何影响？先求平均访存时间，然后再计算CPU性能。分析时请用以下假设：理想Cache(命中率为100)情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.3次。两种Cache容量均为64KB，块大小都是32字节。,例5.3,46,图5.8说明，在组相联Cache中，我们必须增加一个多路选择器，用于根据标识匹配结果从相应组的块中选择所需的数据。因为CPU的速度直接与Cache命中的速度紧密相关,所以对于组相联Cache，由于多路选择器的存在而使CPU的时钟周期增加到原来的1.10倍。这两种结构Cache的失效开销都是70ns。在实际应用中，应取整为整数个时钟周期。命中时间为1个时钟周期，64KB直接映象Cache的失效率为1.4%，相同容量的两路组相联Cache的失效率为1.0%。,47,由:平均访存时间命中时间失效率失效开销得:平均访存时间1路2.0(0.01470)2.98ns平均访存时间2路2.01.10(0.01070)2.90ns,由:CPU时间IC(CPIexe每条指令的平均存储器停顿周期数)时钟周期时间IC(CPIexe时钟周期数每条指令的平均存储器停顿时间),解：,48,CPU时间1路IC(2.02(1.30.01470)5.27ICCPU时间2路IC(2.021.10(1.30.01070)5.31IC,得：,5.31IC,CPU时间1路,1.01,5.27IC,CPU时间2路,49,例5.4,假定存储系统在延迟40个时钟周期后，每2个时钟周期能送出16个字节。即:经过42个时钟周期，它可提供16个字节；经过44个时钟周期，可提供32个字节；依此类推。试问对于表5-6中列出的各种容量的Cache，在块大小分别为多少时，平均访存时间最小？,解：平均访存时间为：平均访存时间命中时间失效率失效开销,50,假设命中时间与块大小无关，为1个时钟，那么对于一个块大小为16字节，容量为1KB的Cache来说：平均访存时间1（15.05%42）7.321个时钟周期而对于块大小为256B的大小为256KB的Cache来说，平均访存时间为：平均访存时间1（0.49%76）1.353个时钟周期表5.7列出了在这两种极端情况之间的各种块大小和各种Cache容量的平均访存时间。,52,5.3.2提高相联度,1.采用相联度超过8的方法实际意义不大,2.2:1Cache经验规则容量为N的直接映象Cache容量为N/2的两路组相联Cache,3.提高相联度是以增加命中时间为代价例如：TTL或ECL板级Cache，两路组相联：增加10定制的CMOSCache,两路组相联：增加2,53,4.例题,假定提高相联度会按下列比例增大处理器时钟周期：时钟周期2路1.10时钟周期1路时钟周期4路1.12时钟周期1路时钟周期8路1.14时钟周期1路假定命中时间为1个时钟，直接映象情况下失效开销为50个时钟周期，而且假设不必将失效开销取整。使用表55中的失效率，试问当Cache为多大时，以下不等式成立？,例5.5,54,平均访存时间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路50,55,在每种情况下的失效开销相同，都是50个时钟周期。把相应的失效率代入上式，即可得平均访存时间。例如，1KB的直接映象Cache的平均访存时间为：平均访存时间1路1.00(0.13350)7.65容量为128KB的8路组相联Cache的平均访存时间为：平均访存时间8路1.14(0.00650)1.44,表5-8,57,1.基本思想在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，用于存放被替换出去的块(称为Victim)，以备重用。工作过程,5.3.3VictimCache,58,对于减小冲突失效很有效，特别是对于小容量的直接映象数据Cache，作用尤其明显。例如，项数为4的VictimCache:使4KBCache的冲突失效减少20%90%,2.作用,59,1.直接映象vs组相联,5.3.4伪相联Cache(列相联),2.伪相联Cache,优点,缺点,直接映象,组相联,命中时间小,命中时间大,失效率高,失效率低,取直接映象及组相联两者的优点：命中时间小，失效率低,60,(1)基本思想及工作原理(图示)在逻辑上把直接映象Cache的空间上下平分为两个区。对于任何一次访问，伪相联Cache先按直接映象Cache的方式去处理。若命中，则其访问过程与直接映象Cache的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。,(2)快速命中与慢速命中要保证绝大多数命中都是快速命中。,61,3.例题,例5.6假设当在按直接映象找到的位置处没有发现匹配、而在另一个位置才找到数据(伪命中)需要2个额外的周期。仍用上个例子中的数据，问：当Cache容量分别为2KB和128KB时，直接映象、两路组相联和伪相联这三种组织结构中，哪一种速度最快？,62,首先考虑标准的平均访存时间公式：平均访存时间伪相联命中时间伪相联失效率伪相联失效开销伪相联由于：失效率伪相联失效率2路命中时间伪相联命中时间1路伪命中率伪相联2；伪命中率伪相联命中率2路命中率1路(1失效率2路)(1失效率1路)失效率1路失效率2路,解：,63,故：平均访存时间伪相联命中时间1路(失效率1路失效率2路)2失效率2路失效开销1路,将表55中的数据代入上面的公式，得：平均访存时间伪相联，2KB1(0.0980.076)2(0.07650)4.844平均访存时间伪相联，128KB1(0.0100.007)2(0.00750)1.356,64,根据上一个例子中的表58，对于2KBCache，可得：平均访存时间1路5.90个时钟平均访存时间2路4.90个时钟对于128KB的Cache有，可得：平均访存时间1路1.50个时钟平均访存时间2路1.45个时钟可见，对于这两种Cache容量，伪相联Cache都是速度最快的。,缺点：多种命中时间,65,5.3.5硬件预取技术,1.指令和数据都可以预取,2.预取内容既可放入Cache，也可放在外缓冲器中例如：指令流缓冲器,3.预取效果(1)Joppi的研究结果指令预取：(4KB，直接映象Cache,块大小16字节),66,根据上一个例子中的表58，对于2KBCache，可得：平均访存时间1路5.90个时钟平均访存时间2路4.90个时钟对于128KB的Cache有，可得：平均访存时间1路1.50个时钟平均访存时间2路1.45个时钟可见，对于这两种Cache容量，伪相联Cache都是速度最快的。,67,5.3.5硬件预取技术,1.指令和数据都可以预取,2.预取内容既可放入Cache，也可放在外缓冲器中例如：指令流缓冲器,3.预取效果(1)Joppi的研究结果指令预取：(4KB，直接映象Cache,块大小16字节),68,1个块的指令流缓冲器：捕获1525的失效4个块的指令流缓冲器：捕获5016个块的指令流缓冲器：捕获72,数据预取：(4KB,直接映象Cache)1个数据流缓冲器：捕获25的失效还可以采用多个数据流缓冲器,(2)Palacharla和Kessler的研究结果流缓冲器：既能预取指令又能预取数据对于两个64KB四路组相联Cache来说：8个流缓冲器能捕获5070的失效。,69,4.例题,例5.7AlphaAXP21064采用指令预取技术，其实际失效率是多少？若不采用指令预取技术，AlphaAPX21064的指令Cache必须为多大才能保持平均访存时间不变？,解：假设从预取缓冲器中找到所需指令需多花1个时钟周期。平均访存时间预取命中时间失效率预取命中率1失效率(1预取命中率)失效开销,70,假设：预取命中率25命中时间1个时钟周期失效开销50个时钟周期由表5.4可知，8KB指令Cache的失效率1.10故平均访存时间预取2(1.10%25%1)(1.10%(125%)50)20.002750.41252.415由公式：平均访问时间命中时间失效率失效开销,71,可得相应的失效率为：失效率(平均访问时间命中时间)/失效开销(1.4511)/500.83,8KBCache,带预取的8kBCache,失效率,1.10,0.83,16KBCache,0.64,72,5.3.6由编译器控制的预取,1.预取的类型寄存器预取：把数据取到寄存器中Cache预取：只将数据取到Cache中故障性预取：预取时，若出现虚地址故障或违反访问权限，就会发生异常。非故障性预取：预取时，若出现虚地址故障或违反访问权限，并不会导致异常，只是转变为“不预取”。,由编译器加入预取指令，在数据被用到之前发出预取请求。,73,4.例题,2.在预取数据的同时，处理器应能继续执行只有这样，预取才有意义。非阻塞Cache(非锁定Cache),3.循环是预取优化的主要对象失效开销小时：循环体展开12次失效开销大时：循环体展开许多次,74,例5.8对于下面的程序，判断哪些访问可能会导致数据Cache失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：(1)我们用的是一个容量为8KB、块大小为16B的直接映象Cache，它采用写回法并且按写分配。(2)a、b分别为3100(3行100列)和1013的双精度浮点数组，每个元素都是8个字节。当程序开始执行时，这些数据都不在Cache内。,75,for(i0;i3;ii1)for(j0;j100;jj1)aijbj0bj10;,解：(1)计算过程(2)失效情况数组a数组b总的失效次数251次(3)改进后的程序,76,for(j0，j100；jj1)prefetch(bj70);/*预取7次循环后所需的b(j,0)*/prefetch(a0j7);/*预取7次循环后所需的a(0,j)*/a0jbj0*bj10for(i1;i3;ii1)for(j0;j100;jj1)prefetch(aij7);/*预取7次循环后所需的a(i,j)*/aijbj0*bj10;,77,例59在以下条件下，计算例5.8中所节约的时间：(1)忽略指令Cache失效，并假设数据Cache无冲突失效和容量失效。(2)假设预取可以被重叠或与Cache失效重叠执行，从而能以最大的存储带宽传送数据。(3)不考虑Cache失效时，修改前的循环每7个时钟周期循环一次。修改后的程序中，,失效情况总的失效次数19次,78,解：修改前：循环时间30072100失效开销2515012550/1465021001255014650,第一个预取循环每9个时钟周期循环一次，而第二个预取循环每8个时钟周期循环一次(包括外层for循环的开销)。(4)一次失效需50个时钟周期。,79,修改后：循环时间100920082500失效时间195095025009503450加速比14650/34504.2,80,5.3.7编译器优化,2KBCache:降低508KBCache：降低75%,1.基本思想,在编译时，对程序中的指令和数据进行重新组织，以降低Cache失效率。,2.McFaring发现：通过对指令进行重新排序，可有效地降低指令Cache的失效率。,81,3.数据对存储位置的限制比指令的少，因此更便于优化。通过把数据重新组织，使得在一块数据被从Cache替换出去之前，能最大限度利用其中的数据(访问次数最多)(1)数据合并举例：/*修改前*/intvalSIZE;intkeySIZE;,82,(2)内外循环交换举例：/*修改前*/for(j0;j100;jj1)for(i0;i5000;ii1)xij2*xij;,/*修改后*/structmergeintval;intkey;structmergemerged_arraysize;,83,(3)循环融合举例：/*修改前*/for(i0;iN;ii1)for(j0;jN;jj1)aij1/bij*cij;,/*修改后*/for(i0;i100;ii1)for(j0;j000;jj1)xij2*xij;,84,/*修改后*/for(i0;iN;ii1)for(j0;jN;jj1)aij1/bij*cij;dijaijcij;,for(i0;iN;ii1)for(j0;jN;jj1)dijaijcij;,(4)分块把对数组的整行或整列访问改为按块进行。,85,举例：/*修改前*/for(i0;iN;ii1)for(j0;jN;jj1)r0;for(k0;kN;kk1)rryik*zkj;xijr;,计算过程失效次数：2N3N2,86,/*修改后*/for(jj0;jjN;jjjj1)for(kk0;kkN;kkkk1)for(i0;iN;ii1)for(jjj;jmin(jjB1,N);jj1)r0;for(kkk;kmin(kkB1,N);kk1)rryik*zkj;xijxijr;,计算过程失效次数：2N3N2,87,Review：降低Cache失效率方法总结,CPU时间ICCPIexe访存次数/指令数失效率失效开销时钟周期时间,1.LargerBlockSize(Compulsory)2.HigherAssociativity(Conflict)3.VictimCache(Conflict)4.Pseudo-Associativity(DM+SA)5.HWPrefetchingInstr,Data(空闲带宽)6.SWPrefetchingData(预取指令)7.CompilerOptimizations(改善时间、空间局部性）,3Cs:Compulsory,Capacity,Conflict,88,5.4.1让读失效优先于写,5.4减少Cache失效开销,1.Cache中的写缓冲器导致对存储器访问的复杂化,考虑下列同一块中指令：CACHE采用写直达法，直接映象SW512(R0),R3LWR1,1024(R0)LWR2,512(R0)假设地址1024和512映射到同一块，写缓冲为4个字。,CPU时间ICCPIexe访存次数/指令数失效率失效开销时钟周期时间,89,2.解决问题的方法(读失效的处理)推迟对读失效的处理，直至写缓冲为空(缺点：读失效的开销增加)读失效时检查写缓冲器中的内容，若没有冲突且存储器可访问，就继续处理读失效（优先写处理读失效）,3.在写回法Cache中，也可采用写缓冲器,90,5.4.2子块放置技术,1.为减少标识的位数，可采用增加块大小的方法，但这会增加失效开销，故应采用子块放置技术。,2.子块放置技术：把Cache块进一步划分为更小的块(子块)，并给每个子块赋予一位有效位，用于指明该子块中的数据是否有效。Cache与下一级存储器之间以子块为单位传送数据。但标识仍以块为单位。,3.举例(图示),91,5.4.3请求字处理技术,1.请求字从下一级存储器调入Cache的块中，只有一个字是立即需要的。这个字称为请求字。,2.应尽早把请求字发送给CPU尽早重启动：调块时，从块的起始位置开始读起。一旦请求字到达，就立即发送给CPU，让CPU继续执行。请求字优先：调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU。,92,3.这种技术在以下情况下效果不大：Cache块较小下一条指令正好访问同一Cache块的另一部分。,93,5.4.4非阻塞Cache技术,1.非阻塞Cache：Cache失效时仍允许CPU进行其它的命中访问。即允许“失效下命中”,2.进一步提高性能：“多重失效下命中”，“失效下失效”(存储器必须能够处理多个失效，“多体”),4.重叠失效个数对平均访问时间的影响,采用尽早重启动技术时，请求字到达之前，CPU要等待，乱序执行的机器要求，在CACHE失效时，CPU无需停顿，这就要求CACHE是非阻塞Cache。,3.失效下命中不影响命中时间（潜在优点）,94,非阻塞Cache平均存储器等待时间与阻塞Cache的比值,1,2,浮点程序,76,51,64,39,整数程序,81,78,78,重叠失效个数,95,对于图5.17所描述的Cache，在两路组相联和“一次失效下命中”这两种措施中，哪一种对浮点程序更重要？对整数程序的情况如何？假设8KB数据Cache的平均失效率为：对于浮点程序，直接映象Cache为11.4%，两路组相联Cache为10.7%；对于整数程序，直接映象Cache为7.4%，两路组相联Cache为6.0%。并且假设平均存储器等待时间是失效率和失效开销的积，失效开销为16个时钟周期。,例5.10,96,对于浮点程序，平均存储器等待时间为：失效率直接映象失效开销11.4%161.82失效率两路组相联失效开销10.7%161.711.71/1.820.94,对于整数程序：失效率直接映象失效开销7.4%161.18失效率两路组相联失效开销6.0%160.960.96/1.18=0.81,解：非阻塞Cache平均存储器等待时间与阻塞Cache的比值如下表：,1,2,浮点程序,76,51,64,39,整数程序,81,78,78,重叠失效个数,97,5.4.5两级Cache,1.应把Cache做得更快？还是更大？答案：二者兼顾，再增加一级Cache第一级Cache(L1)小而快-与CPU速度匹配第二级Cache(L2)容量大-降低实际失效开销,2.性能分析平均访问时间命中时间L1失效率L1失效开销L1失效开销L1=命中时间L2失效率L2失效开销L2平均访问时间命中时间L1失效率L1(命中时间L2失效率L2失效开销L2),前几种技术与CPU关系密切，这一种重点是主存与CACHE的接口,98,3.局部失效率与全局失效率局部失效率该级Cache的失效次数/到达该级Cache的访问次数例如：上述式子中的失效率L2全局失效率该级Cache的失效次数/CPU发出的访存的总次数全局失效率L2失效率L1失效率L2评价第二级Cache时，应使用全局失效率这个指标。图5.18,4.当第二级Cache比第一级Cache大得多时，两级Cache的全局失效率与容量和第二级Cache,99,相同的单级Cache的失效率非常接近。,5.第二级Cache的参数第一级Cache的速度会影响CPU的时钟频率，而第二级Cache不会影响CPU的时钟频率，因此其设计有更大的考虑空间。设计中要考虑两个问题：能否降低CPI中的平均访存时间部分？成本是多少？(1)容量第二级Cache的容量一般比第一级的大许多，如512KB图5.19,100,(2)相联度第二级Cache可采用较高的相联度或伪相联方法,例5.12给出有关第二级Cache的以下数据：两路组相联使命中时间增加10%CPU时钟周期对于直接映象，命中时间L210个时钟周期对于直接映象，局部失效率L225%对于两路组相联，局部失效率L220%失效开销L250个时钟周期试问第二级Cache的相联度对失效开销的影响如何？,101,解：对于一个直接映象的第二级Cache来说，第一级Cache的失效开销为：失效开销直接映象，L11025%5022.5个时钟周期对于两路组相联第二级Cache来说，命中时间增加了10%(0.1)个时钟周期，故第一级Cache的失效开销为：失效开销两路组相联，L110.120%5020.1个时钟周期把第二级Cache的命中时间取整，得10或11，则：,102,失效开销两路组相联，L11020%5020.0个时钟周期失效开销两路组相联，L11120%5021.0个时钟周期故对于第二级Cache来说，两路组相联优于直接映象。,(3)块大小第二级Cache可采用较大的块，如64、128、256字节。图5.20为减少平均访存时间，可以让容量较小一的第级Cache采用较小的块，而让容量较大的第二级Cache采用较大的块。,103,5.5减少命中时间,2.应使Cache足够小，以便可以与CPU一起放在同一块芯片上。,命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是Cache的访问时间限制了处理器的时钟频率。,1.硬件越简单，速度就越快；,5.5.1容量小、结构简单的Cache,平均访存时间命中时间失效率失效开销,104,1.虚拟Cache:访问Cache的索引以及Cache中的标识都是虚拟地址(一部分)。,5.5.2虚拟Cache,在虚拟存储器中，CPU发出虚拟地址，需用TLB硬件动态转变成物理地址去访问CACHE，这增加了系统的存取时间。,105,2.并非人人都采用虚拟Cache(为什么?)地址切换时可能需要清空CACHE别名问题I/O问题3.虚拟Cache的清空问题解决方法：在地址标识中增加PID字段(进程标识符)三种情况下失效率的比较：单进程，PIDs，清空PIDs与单进程相比：0.30.6PIDs与PIDs相比：0.64.3%,106,4.同义和别名解决方法：反别名法（硬件）,页着色（软件，UNIX要求别名地址的最后18位相同）5.虚拟索引物理标识优点：兼得虚拟Cache和物理Cache的好处局限性：Cache容量受到限制(页内位移)Cache容量页大小相联度6.举例：IBM3033的Cache页大小4KB相联度16,107,5.5.3将写操作流水化以加快写命中(图5.23),Cache容量164KB64KB7.另一种方法：硬件散列变换,页地址地址标识,页内位移,索引,块内位移,31,1211,0,5.5.4Cache优化技术总结(表5-9),108,表5-9Cache优化技术总结,109,表5-9续Cache优化技术总结,110,5.6.1存储器技术,1.主存的主要性能指标：延迟和带宽2.以往：Cache主要关心延迟，I/O主要关心带宽3.现在：Cache关心两者,5.6主存,1.存储器延迟：访问时间，存储周期2.行选通和列选通,111,3.DRAM与SRAM容量：48：1存储周期：816:1价格：1：816一般来说：主存：DRAMCache：SRAM4.各代DRAM的典型时间参数(表5-10)5.Amdahl经验规则为了保持系统平衡，存储容量应随CPU速度的提高而线性增加。,112,5.6.2提高主存性能的存储器组织结构,为了减少失效开销TM，应该：减少主存延迟提高主存带宽增加Cache块大小能利用主存带宽增加所带来的好处。在以下的讨论中，我们假设基本存储器结构的性能为：送地址需4个时钟周期；每个字的访问时间为24个时钟周期；传送一个字的数据需4个时钟周期。,113,如果Cache大小为4个字，则：失效开销4(4244)432128(时钟周期)带宽16/1280.0125(字节/时钟周期),1.增加存储器的宽度性能举例(参照前面的假设)当宽度为4个字时：失效开销132(周期)带宽0.5(字节/周期),114,缺点：增加CPU和存储器之间的连接通路的宽度CUP和Cache之间有一个多路选择器扩充主存的最小增量增加了相应的倍数写入有可能变得复杂举例：DEC的AlphaAxp21064：256位宽2.采用简单的多体交叉存储器在存储系统中采用多个DRAM，并利用它们潜在的并行性。高位交叉与低位交叉编址,115,存储器的各个体一般是按字交叉的字交叉存储器非常适合于处理：Cache读失效，写回法Cache中的写回,同时启动与分时启动性能举例：(参照前面的假设)失效开销4244444(周期)带宽0.4(字节/周期),例题：,116,假设某台机器的特性及其Cache的性能为：块大小为1个字存储器总线宽度为1个字Cache失效率为3%平均每条指令访存1.2次Cache失效开销为32个时钟周期(和上面相同)平均CPI(忽略Cache失效)为2试问多体交叉和增加存储器宽度对提高性能各有何作用？如果当把Cache块大小变为2个字时，失效率,例5.13,117,降为2%；块大小变为4个字时，失效率降为1%。根据5.6.2小节中给出的访问时间，求在采用2路、4路多体交叉存取以及将存储器和总线宽度增加一倍时，性能分别提高多少？,解：,在改变前的机器中，Cache块大小为一个字，其CPI为2(1.23%32)3.15当将块大小增加为2个字时，在下面三种情况下的CPI分别为：,118,32位总线和存储器，不采用多体交叉：2(1.22%232)3.5432位总线和存储器，采用多体交叉：2(1.22%(4248)2.86性能提高了10%64位总线和存储器，不采用多体交叉：2(1.22%132)2.77性能提高了14%如果将块大小增加到4个字节，则：32位总线和存储器，不采用多体交叉：2(1.21%432)3.54,119,存储体的数目体的数目访问体中一个字所需的时钟周期,32位总线和存储器，采用多体交叉：2(1.21%(42416)2.53性能提高了25%64位总线和存储器，不采用多体交叉：2(1.21%232)2.77性能提高了14%,3.独立存储体设置多个存储控制器，使多个体能独立操作，以便能同时进行多个独立的访存。,120,每个体有独立的地址线(图示)非阻塞Cache与多体结构体和超体,4.避免存储体冲突体冲突：两个请求要访问同一个体减少冲突：采用许多体例如：NECSX/3最多128个体解决体冲突的方法：软件方法(编译器)循环交换优化扩展数组的大小，使之不是2的幂。,121,5.DRAM专用交叉结构三种方式Nibble方式Page方式Staticcolumn方式,硬件方法使体数为素数。当存储体数为素数，且为2的幂减1时，体地址地址mod(存储体中的字数)可以直接载取。举例(表5-11),122,优化后DRAM的访问周期(表5.12)RAMBUS新的接口包交换总线,123,5.7虚拟存储器,2.有关虚拟存储器的四个问题映象规则全相联,1.虚拟存储器的特点多个进程可以共享主存空间程序员不必做存储管理工作采用动态再定位，简化了程序的装入,5.7.1虚拟存储器基本原理,124,查找算法页表，段表，TLB替换算法LRU写策略写回法,125,5.7.2块表TLB,1.TLBTLB是一个专用的高速缓冲器，用于存放近期经常使用的页表项;TLB中的内容是页表部分内容的一个副本;TLB也利用了局部性原理;2.AlphaAxp21064的地址转换过程3.TLB一般比Cache的标识存储器更小、更快,126,5.7.3页面大小的选择,1.大页面和小页面各有优点如何进行权衡?2.大页面的好处：页表的大小与页面大小成反比。较大的页面可以节省实现地址映象所需的存储空间及其它资源；较大的页面可以使快速Cache命中的实现更简单(5.5节)；在主存和辅存之间(也许还通过网络)传送较大的页面比传送较小的页面更有效；,127,TLB的项数有限，对于给定数目的项数，较大的页面意味着可以高效地实现更多存储空间的地址变换，从而减小TLB失效的次数。,3.采用较小的页面可以减少空间的浪费假设每个进程有三个主要的段：文本，堆，堆栈,则平均浪费1.5个页面。,128,5.8.1进程保护,进程：程序呼吸所需的空气及生存的空间。,5.8进程保护和虚存实例,1.界地址寄存器基地址，上界地址检测条件：(基地址地址)上界地址2.虚拟存储器给每个页面增加访问权限标识3.环形保护4.加锁和解锁,129,5.8.2页式虚存举例：AlphaAxp,AlphaAxp体系结构采用段页相结合的方式。1.Alpha的地址空间分为3段：kseg(地址最高两位：10)(内核)sego(最高位：0)(用户)seg1(最高两位：11)(用户)sego和seg1的布局2.Alpha采用三级页表地址变换过程3.Alpha的页表项(PTE),130,4.AlphaAxp21064TLB的参数,参数,描述,块大小,命中时间,平均失效开销,TLB容量,块替换策略,写策略,块映象策略,1PTE(8字节),1个时钟周期,20PTE(8字节),随机,不适用,全相联,指令TLB：8个PTE用于大小为8K字节的页，4个PTE用于大小为4MB的页(共96个字节),数据TLB：32个PTE用于大小为8KB、64KB、512KB何4MB的页(共256个字节),表5-14AlphaAXP21064TLB的存储层次参数,131,5.9AlphaAxp21064存储层次,1.简介2.工作过程,132,5.10小结,1.本章存储层次实例总结,表5-15,133,测试：某台计算机的时钟频率为1GHz，物理地址的长度为32位，按字节编址，使用16KB的数据CACHE和16KB的指令CACHE，块大小都为16B，采用直接映象。数据CACHE的失效率为6.4%，指令CACHE的失效率为1.3%，命中时间均为1个时钟周期，失效开销均为50个时钟周期。试计