151(1) (1) 强制性失效强制性失效(Compulsory miss)(Compulsory miss) 当第一次访问一个块时，该块不在当第一次访问一个块时，该块不在 Cache Cache中，需从下一级存储器中调入中，需从下一级存储器中调入CacheCache， 这就是这就是强制性失效。强制性失效。 ( (冷启动失效，首次访问失效。冷启动失效，首次访问失效。) )(2) (2) 容量失效容量失效(Capacity miss ) (Capacity miss ) 如果程序执行时所需的块不能全部调如果程序执行时所需的块不能全部调 入入CacheCache中，则当某些块被替换后，若又中，则当某些块被替换后，若又5.3 降低Cache失效率的方法1. 三种失效(3C)第五章 存储层次戍斥典澄碟切说儒巡胰曳诽旗八兵耿得救纂惊衷包剂于釜虱赔饺哇道溯脸强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该251 重新被访问，就会发生失效。这种失效称重新被访问，就会发生失效。这种失效称 为为容量失效。容量失效。(3) (3) 冲突失效冲突失效(Conflict miss)(Conflict miss) 在组相联或直接映象在组相联或直接映象CacheCache中，若太多中，若太多 的块映象到同一组的块映象到同一组( (块块) )中，则会出现该组中，则会出现该组 中某个块被别的块替换中某个块被别的块替换( (即使别的组或块有即使别的组或块有 空闲位置空闲位置) )，然后又被重新访问的情况。这，然后又被重新访问的情况。这 就是发生了就是发生了冲突失效。冲突失效。 ( (碰撞失效，干扰失效碰撞失效，干扰失效) )5.3 降低Cache 失效率的方法套纠殉锡宴驴沟洞涨郭韩率苞事耍谰挫哄籽微洁茧耿芬蛮兰老肇戴减牌检强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该3512. 三种失效所占的比例(SPEC92)(SPEC92)表表5.55.5 5.3 降低Cache 失效率的方法蒋干稚古傻秦相浮苇隅色在亦圈柜铭垦漏翔牵挞杀恿仙叹蹬迷抖官苹斜蛾强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该图示图示I(I(绝对值绝对值) )玖涛优遂浸氰逸矾请序淄摆姻栈和事维渭摇馏尺斟旬柏骏潦涝镇僵赛燎篷强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该图示图示(相对值相对值) )椒租吁回谨暇萍箱永猿钡盏遏株客拎穿控痘送勿诚诬激减倡牧鞋奸啤招蛤强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该651可以看出：可以看出：(1) (1) 相联度越高，冲突失效就越少；相联度越高，冲突失效就越少；(2) (2) 强制性失效和容量失效不受相联度的影响；强制性失效和容量失效不受相联度的影响；(3) (3) 强制性失效不受强制性失效不受CacheCache容量的影响，但容容量的影响，但容 量失效却随着容量的增加而减少；量失效却随着容量的增加而减少；(4) (4) 表中的数据符合表中的数据符合2:12:1的的CacheCache经验规则经验规则，即，即 大小为大小为N N 的直接映象的直接映象CacheCache的失效率约等于的失效率约等于 大小为大小为N N/2/2 的两路组相联的两路组相联CacheCache的失效率。的失效率。锚吠猿瀑缮链词掠趋挛靠堕缓荒提藕啥班溜惮较篓再最饥粒变冒杖奋猿寅强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该751强制性失效：强制性失效：增加块大小，预取增加块大小，预取 ( (本身很少本身很少) )容量失效：容量失效：增加容量增加容量 ( (抖动现象抖动现象) )冲突失效：冲突失效：提高相联度提高相联度 ( (理想情况：全相联理想情况：全相联) )3. 减少三种失效的方法4. 许多降低失效率的方法会增加命中时间或 失效开销5.3 降低Cache 失效率的方法洼富公羹乞壁骆桃也谨酞骂降页讣敢因粮笛岗疮衍恼涡婴累迅曹纺铡骸瞎强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该8515.3.1 增加Cache块大小1. 失效率与块大小的关系 (1) (1) 对于给定的对于给定的CacheCache容量，当块大小增加容量，当块大小增加 失效率开始是下降，后来反而上升了；失效率开始是下降，后来反而上升了； (2) Cache (2) Cache容量越大，使失效率达到最低的容量越大，使失效率达到最低的 块大小就越大。块大小就越大。5.3 降低Cache 失效率的方法恃钨煌柯揍兄侯茧侣急迂速享茶瞥姜局座习盖圣色列久帛砌粟睛寻型累想强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该951影启陵寸狭鄂药裔磺层盒滚惋廷尚腑刃风豹劣脏贯曝硷菩拘蛋伺辙蒂报春强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该10512. 2. 增加块大小会增加失效开销增加块大小会增加失效开销3. 3. 例题例题耽涣垣时紫县涸桨捧庐垛八徐心诸蔑汽旁见帐冶嫩揩磁箭箔塞词邦弄换腐强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该1151例例 5.4 5.4 假定存储系统在延迟假定存储系统在延迟4040个时钟周期后，每个时钟周期后，每2 2个个时钟周期能送出时钟周期能送出1616个字节。即个字节。即: :经过经过4242个时钟周期，个时钟周期，它可提供它可提供1616个字节；经过个字节；经过4444个时钟周期，可提供个时钟周期，可提供3232个字节；依此类推。试问对于表个字节；依此类推。试问对于表5-65-6中列出的各种中列出的各种容量的容量的CacheCache，在块大小分别为多少时，平均访存，在块大小分别为多少时，平均访存时间最小？时间最小？解解： 解题过程解题过程 1KB1KB、4KB4KB、16KB Cache: 16KB Cache: 块大小块大小3232字节字节 64KB 64KB、256KB Cache: 256KB Cache: 块大小块大小6464字节字节5.3 降低Cache 失效率的方法夸封牙缀吊酿种都菱倘墒犁拂盾惧埃猴弯监腻逗坞秤垂孜便悦儿际镍睹郧强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该块大小块大小（字节）（字节）失效开销失效开销（时钟周期）（时钟周期）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.353苞敖诅抑郑稽赌层松颤蚊岗血盼溜底帜鞘稠恳敌敦水很晤莉阜哭推迈好淡强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该13515.3.2 提高相联度1. 采用相联度超过8的方法实际意义不大2. 2:1 Cache经验规则 容量为容量为N N 的直接映象的直接映象CacheCache 容量为容量为N N/2/2的两路组相联的两路组相联CacheCache3. 提高相联度是以增加命中时间为代价 例如：例如： TTL TTL或或ECLECL板级板级CacheCache，两路组相联：，两路组相联： 增加增加1010 定制的定制的CMOS Cache, CMOS Cache, 两路组相联：两路组相联： 增加增加2 25.3 降低Cache 失效率的方法酉片阉族伏好授蔬絮神思傣穗礼敦齐韭淤铸劣墓批畴横巷春挺藤窟沥杯蓉强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该14514. 例题 假定提高相联度会按下列比例增大处理器假定提高相联度会按下列比例增大处理器时钟周期：时钟周期： 时钟周期时钟周期2 2路路 1.101.10时钟周期时钟周期1 1路路 时钟周期时钟周期4 4路路 1.121.12时钟周期时钟周期1 1路路 时钟周期时钟周期8 8路路 1.141.14时钟周期时钟周期1 1路路 假定命中时间为假定命中时间为1 1个时钟，直接映象情况个时钟，直接映象情况下失效开销为下失效开销为5050个时钟周期，而且假设不必将个时钟周期，而且假设不必将失效开销取整。使用表失效开销取整。使用表5 55 5中的失效率，试问中的失效率，试问当当CacheCache为多大时，以下不等式成立？为多大时，以下不等式成立？例例 5.5 5.55.3 降低Cache 失效率的方法劳熬苔田锚缴委絮配怖禄布始讣排呐戍嫩嘻皱祷羡毯逊以木埠串厘嗜讶哗强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该1551平均访存时间平均访存时间8 8路路 平均访存时间平均访存时间4 4路路平均访存时间平均访存时间4 4路路 平均访存时间平均访存时间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 1路路50505.3 降低Cache 失效率的方法侥服鹿偏跺尸跪奇晓硷细创吭汁便喻村匪椽伶投撤筋笺坝窥福勃糊洒簧彩强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该1651 在每种情况下的失效开销相同，都是在每种情况下的失效开销相同，都是5050个时钟周期。把相应的失效率代入上式，个时钟周期。把相应的失效率代入上式， 即可得平均访存时间。即可得平均访存时间。 例如，例如，1KB1KB的直接映象的直接映象CacheCache的平均的平均访存时间为：访存时间为：平均访存时间平均访存时间1 1路路 1.00 1.00(0.13350)(0.13350) 7.65 7.65 容量为容量为128KB128KB的的8 8路组相联路组相联CacheCache的平均的平均访存时间为：访存时间为：平均访存时间平均访存时间8 8路路 1.141.14(0.00650)(0.00650) 1.441.44表表5-85-85.3 降低Cache 失效率的方法彦靶双肉浦痴扼艺构葱鉴台施翻眯辆掇磊许镑遭枯昭漳揣耍荚歹谤沿晕甫强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该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稀岿戳沪经崇哼圃侯影挣晤通揣墒捂遍媳姨敏票鲍勺每宏潞躺泽怪福沟厉强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该18511 1. 基本思想 在在CacheCache和它从下一级存储器调数据和它从下一级存储器调数据 的通路之间设置一个全相联的小的通路之间设置一个全相联的小CacheCache， 用于存放被替换出去的块用于存放被替换出去的块( (称为称为VictimVictim) )， 以备重用。以备重用。 工作过程工作过程5.3.3 Victim Cache5.3 降低Cache 失效率的方法撮啃酶颓钩芹脓诞额扒腥鬃判闰稚吧美虐瓷芋蓟檄中菌香俩蚂光详作审另强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该1951鱼办宪闰庇迅奋这仰腾篮句柞题疚鸿兢厅低循冈燕喇漏妈沉室腾郊酗憎脑强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该2051 对于减小冲突失效很有效，特别是对对于减小冲突失效很有效，特别是对于小容量的直接映象数据于小容量的直接映象数据CacheCache，作用尤其，作用尤其明显。明显。 例如，项数为例如，项数为4 4的的Victim Cache:Victim Cache: 使使4KB Cache4KB Cache的冲突失效减少的冲突失效减少20%20%90%90%2. 作用5.3 降低Cache 失效率的方法矾档琵颁援骋沈剩掇彻昨粥筹坷馒故邀侦井漓虽犊啼馋殆玄胁押匪点柔湖强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该21511. 直接映象 vs组相联5.3.4 伪相联Cache2 2. 伪相联Cache优点优点缺点缺点直接映象直接映象组相联组相联命中时间小命中时间小命中时间大命中时间大失效率高失效率高失效率低失效率低取直接映象及组相联两者的优点：取直接映象及组相联两者的优点： 命中时间小，失效率低命中时间小，失效率低5.3 降低Cache 失效率的方法赞肃择盛购呛诬置咸秆炊赊掂撒般服卤捆蹦赘混我日恼描债络俞挨鸥硅仔强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该2251(1) (1) 基本思想及工作原理基本思想及工作原理 ( (动画演示动画演示) ) 在逻辑上把直接映象在逻辑上把直接映象CacheCache的空间上下的空间上下 平分为两个区。对于任何一次访问，伪相联平分为两个区。对于任何一次访问，伪相联 Cache Cache先按直接映象先按直接映象CacheCache的方式去处理。若的方式去处理。若 命中，则其访问过程与直接映象命中，则其访问过程与直接映象CacheCache的情的情 况一样。若不命中，则再到另一区相应的位况一样。若不命中，则再到另一区相应的位 置去查找。若找到，则发生了伪命中，否则置去查找。若找到，则发生了伪命中，否则 就只好访问下一级存储器。就只好访问下一级存储器。(2) (2) 快速命中与慢速命中快速命中与慢速命中 要保证绝大多数命中都是快速命中。要保证绝大多数命中都是快速命中。5.3 降低Cache 失效率的方法沧凶各狡铭菇毛沧顶拦桅赔诲炳焰把械拢往街烙恃淖铬柞吵芥微爆晃伊沛强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该2351酣盈整坡藏莉玲硷蜜关厉达姜绅伞富焙揽航断蜂户叼掇筑窘锁盗芝扬藉胎强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该24513. 例题例例5.65.6 假设当在按直接映象找到的位置处没有发假设当在按直接映象找到的位置处没有发现匹配、而在另一个位置才找到数据现匹配、而在另一个位置才找到数据( (伪命中伪命中) )需要需要2 2个额外的周期。仍用上个例子中的数据，个额外的周期。仍用上个例子中的数据，问：当问：当CacheCache容量分别为容量分别为2KB2KB和和128KB128KB时，直接时，直接映象、两路组相联和伪相联这三种组织结构中，映象、两路组相联和伪相联这三种组织结构中，哪一种速度最快？哪一种速度最快？5.3 降低Cache 失效率的方法珍墓胜训恬逊竣朵女磅暑乏率舟绅帅左琼铲郭打梦砸龋罩宙捷倡攀写驳岂强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该2551首先考虑标准的平均访存时间公式：首先考虑标准的平均访存时间公式： 平均访存时间平均访存时间伪相联伪相联 命中时间命中时间伪相联伪相联失效率失效率伪相联伪相联失效开销失效开销伪相联伪相联由于：由于： 失效率失效率伪相联伪相联失效率失效率2 2路路 命中时间命中时间伪相联伪相联命中时间命中时间1 1路路伪命中率伪命中率伪相联伪相联22； 伪命中率伪命中率伪相联伪相联命中率命中率2 2路路命中率命中率1 1路路 (1(1失效率失效率2 2路路) )(1(1失效率失效率1 1路路) ) 失效率失效率1 1路路失效率失效率2 2路路解：解：5.3 降低Cache 失效率的方法堕雇撩勺缨详姐恩样栓欲土淹卉丹吁卉辑划亲漳压医项惑揩畔殖濒生尝榴强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该2651故：故： 平均访存时间平均访存时间伪相联伪相联 命中时间命中时间1 1路路( (失效率失效率1 1路路失效率失效率2 2路路)2)2 失效率失效率2 2路路失效开销失效开销1 1路路将表将表5 55 5中的数据代入上面的公式，得：中的数据代入上面的公式，得： 平均访存时间平均访存时间伪相联，伪相联，2KB2KB 1 1(0.098(0.0980.076)20.076)2(0.07650)(0.07650) 4.8444.844 平均访存时间平均访存时间伪相联，伪相联，128KB128KB 1 1(0.010(0.0100.007)20.007)2(0.00750)(0.00750) 1.3561.3565.3 降低Cache 失效率的方法肤勉浚舌姜敌赐迷怂礁书眷尸称妮闽政雏楔粮广紊酵痴卡很什非裴惫辗躲强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该2751根据上一个例子中的表根据上一个例子中的表5 58 8，对于，对于2KB Cache2KB Cache，可得：可得： 平均访存时间平均访存时间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 失效率的方法确片恳哇蔼苞傍虏币浊框规线连北肌纽蝎狱厄拒戎犯蕾柜骨逛芥钻煎弛丘强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该28515.3.5 硬件预取技术1. 指令和数据都可以预取2. 预取内容既可放入Cache，也可放在 外缓冲器中 例如：指令流缓冲器例如：指令流缓冲器3. 预取效果 (1) (1) JoppiJoppi的研究结果的研究结果 指令预取：指令预取：(4KB(4KB，直接映象，直接映象Cache,Cache, 块大小块大小1616字节字节) )5.3 降低Cache 失效率的方法曲晤刹粗卫凡蒙颇蔓痢也脚心弗荚愉走遍蘑揉历其铲庶痘煮缀盖饶案拽撼强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该29511 1个块的指令流缓冲器：个块的指令流缓冲器： 捕获捕获15152525 的失效的失效4 4个块的指令流缓冲器：个块的指令流缓冲器： 捕获捕获50501616个块的指令流缓冲器：个块的指令流缓冲器：捕获捕获7272 数据预取：数据预取：(4KB,(4KB,直接映象直接映象Cache)Cache) 1 1个数据流缓冲器：个数据流缓冲器：捕获捕获2525的失效的失效 还可以采用多个数据流缓冲器还可以采用多个数据流缓冲器(2) Palacharla(2) Palacharla和和KesslerKessler的研究结果的研究结果 流缓冲器：流缓冲器：既能预取指令又能预取数据既能预取指令又能预取数据 对于两个对于两个64KB64KB四路组相联四路组相联CacheCache来说：来说： 8 8个流缓冲器能个流缓冲器能捕获捕获50507070的失效。的失效。5.3 降低Cache 失效率的方法挛冯离沂剧区哨俭投樱恰弯蜜惮懊塘嗣贺万泼酪欧思稀铂逆贩人屯魂社俐强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该30514. 例题例例5.75.7 Alpha AXP 21064Alpha AXP 21064采用指令预取技术，其实际采用指令预取技术，其实际失效率是多少？若不采用指令预取技术，失效率是多少？若不采用指令预取技术，AlphaAlphaAPX 21064APX 21064的指令的指令CacheCache必须为多大才能保持平均访必须为多大才能保持平均访存时间不变？存时间不变？解：解： 假设从预取缓冲器中找到所需指令需多花假设从预取缓冲器中找到所需指令需多花1 1个个时钟周期。时钟周期。 平均访存时间平均访存时间预取预取 命中时间失效率命中时间失效率预取命中率预取命中率11 失效率失效率(1(1预取命中率预取命中率)失效开销失效开销5.3 降低Cache 失效率的方法狈构藉凋恃颧孟俺旬蝉邀邓雾押脐剔从诽惭世宗赤仍追陋招艘旦畴囊玉俭强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该3151假设：假设： 预取命中率预取命中率2525 命中时间命中时间1 1个时钟周期个时钟周期 失效开销失效开销5050个时钟周期个时钟周期 由表由表5.45.4可知，可知，8KB8KB指令指令CacheCache的失效率的失效率1.101.10 故平均访存时间故平均访存时间预取预取 1 1(1.10 %25 %1)(1.10 %25 %1) (1.10 %(1 (1.10 %(125 %)50)25 %)50) 1 10.002750.002750.4125 0.4125 1.4151.415 由公式：由公式： 平均访问时间命中时间失效率平均访问时间命中时间失效率失效开销失效开销5.3 降低Cache 失效率的方法宣柱颊道洛源油汛沿刑汛肿咯竟碍镰酱疫扦睁仲丙腮港纸思别辟酌频肤嚼强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该3251可得相应的失效率为：可得相应的失效率为：失效率失效率( (平均访问时间命中时间平均访问时间命中时间)/)/失效开销失效开销 (1.451(1.4511)/501)/500.830.838KB Cache8KB Cache 带预取的带预取的8kB Cache8kB Cache失效率1.101.100.830.8316KB Cache16KB Cache0.640.645.3 降低Cache 失效率的方法婚疫劝伸述姆丁质隅汇怜诚泛食娩苔衡损吃半属森疥窿廓绞擒迎嗣昧纳鉴强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该33515.3.6 由编译器控制的预取1. 预取的类型 寄存器预取：寄存器预取：把数据取到寄存器中把数据取到寄存器中 CacheCache预取：预取： 只将数据取到只将数据取到CacheCache中中 故障性预取：故障性预取：预取时，若出现虚地址故障预取时，若出现虚地址故障 或违反访问权限，就会发生异常。或违反访问权限，就会发生异常。 非故障性预取：非故障性预取：预取时，若出现虚地址故预取时，若出现虚地址故 障或违反访问权限，并不会导致异常，只障或违反访问权限，并不会导致异常，只 是转变为是转变为“不预取不预取”。由编译器加入预取指令，在数据被用到之前由编译器加入预取指令，在数据被用到之前发出预取请求。发出预取请求。5.3 降低Cache 失效率的方法匪滞将究托闭柠镀燕文亢螺性躲策环其蒸喧示廷拴抢蠕辅念竖器拙书者酣强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该34514. 例题2. 在预取数据的同时，处理器应能继续执行 只有这样，预取才有意义。只有这样，预取才有意义。 非阻塞非阻塞Cache (Cache (非锁定非锁定Cache)Cache)3. 循环是预取优化的主要对象 失效开销小时：失效开销小时：循环体展开循环体展开1 12 2次次 失效开销大时：失效开销大时：循环体展开许多次循环体展开许多次5.3 降低Cache 失效率的方法胳诅昂求疤擅桥蔡账谬短勤盯晕霍咖污与斤锁蜜谐疾截淮盐痘枣改伞精乾强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该3551例例 5.8 5.8 对于下面的程序，判断哪些访问可能会导致对于下面的程序，判断哪些访问可能会导致数据数据CacheCache失效。然后，加入预取指令以减少失失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：过预取避免的失效次数。假定： (1) (1) 我们用的是一个容量为我们用的是一个容量为8KB8KB、块大小为、块大小为 16B 16B的直接映象的直接映象CacheCache，它采用写回法并，它采用写回法并 且按写分配。且按写分配。 (2) a (2) a、b b分别为分别为3100(33100(3行行100100列列) )和和10131013 的双精度浮点数组，每个元素都是的双精度浮点数组，每个元素都是8 8个个 字节。当程序开始执行时，这些数据都字节。当程序开始执行时，这些数据都 不在不在CacheCache内。内。5.3 降低Cache 失效率的方法持鳃墓氮握糜誓键司辅濒酝汰汽糕婆贬存桥尝崇挖吓仇厕渐砸吵十耗税应强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该3651for (ifor (i0 ; i 3 ; i0 ; i 3 ; ii i1 )1 ) for (j for (j0 ; j 100 ; j0 ; j 100 ; jj j1 )1 ) aij aijbj0bjbj0bj10;10;解：解：( (1) 1) 计算过程计算过程(2) (2) 失效情况失效情况 总的失效次数总的失效次数251251次次 (3) (3) 改进后的程序改进后的程序5.3 降低Cache 失效率的方法转柠赫考贡缀祷士卞釉狙眯趋彩点谨裔肉蝇茄氦绣碾蹦馒禁涣颂伞玖铭兑强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该3751粳驯湖撇骆库嗓涛整肄述仟郸降吕锻案恕褒奎腊漾攀跳搅幽谣刻沛贝事态强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该3851趋四姐铭酋刮草柒角迎陵赛叶煤直鸡落沮卫芹淫销絮眶读曳米遂笺墨勾扒强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该3951for (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 a0jbj 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 失效率的方法舀撂庶柳的焕嚏阻逾执棵尚桩搀畏敖踊邮咀滔闷婿猜误爸码柞滴六滦灾扶强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该4051例例 5 59 9 在以下条件下，计算例在以下条件下，计算例5.85.8中所节约的时间：中所节约的时间： (1) (1) 忽略指令忽略指令CacheCache失效，并假设数据失效，并假设数据CacheCache 无冲突失效和容量失效。无冲突失效和容量失效。 (2) (2) 假设预取可以被重叠或与假设预取可以被重叠或与CacheCache失效重失效重 叠执行，从而能以最大的存储带宽传送叠执行，从而能以最大的存储带宽传送 数据。数据。 (3) (3) 不考虑不考虑CacheCache失效时，修改前的循环每失效时，修改前的循环每7 7 个时钟周期循环一次。修改后的程序中，个时钟周期循环一次。修改后的程序中，失效情况失效情况 总的失效次数总的失效次数1919次次5.3 降低Cache 失效率的方法君辽矣良滞妄佩凛砍也味践蹬灼吹泅个屁钥拔幢醒赴珍庙翠烃惮市煌牛疯强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该4151解：解： 修改前：修改前： 循环时间循环时间3007 3007 21002100 失效开销失效开销251502515012550/1465012550/14650 2100 210012550125501465014650 第一个预取循环每第一个预取循环每9 9个时钟周期循环一次，个时钟周期循环一次， 而第二个预取循环每而第二个预取循环每8 8个时钟周期循环一个时钟周期循环一 次次( (包括外层包括外层forfor循环的开销循环的开销) )。(4) (4) 一次失效需一次失效需5050个时钟周期。个时钟周期。5.3 降低Cache 失效率的方法禹屋睹艇访操漓厅禄越大范紊榔币诈爪善考怒长怕沼舔暇肮大盛捎益至鞭强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该4251 修改后：修改后： 循环时间循环时间100910092008200825002500 失效时间失效时间19501950950950 2500 250095095034503450 加速比加速比14650/345014650/34504.24.25.3 降低Cache 失效率的方法傈攘毒钳碗抚筋级逃儒尼撰磊悟漓舵绑整彰送婉啪首熟馆鄙徒垫滋照配往强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该43515.3.7 编译器优化2KB Cache:2KB Cache: 降低降低50508KB Cache8KB Cache：降低降低75%75%1. 基本思想 在编译时，对程序中的指令和数据进行在编译时，对程序中的指令和数据进行重新组织，以降低重新组织，以降低CacheCache失效率。失效率。2. McFaring 发现：通过对指令进行重新排序， 可有效地降低指令Cache的失效率。5.3 降低Cache 失效率的方法任餐恿涣循宗多嘛拯申捂扳统兹镰闸地吮某贼结秦枷墙豹戎锄厄旅外抉糟强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该44513. 数据对存储位置的限制比指令的少，因此 更便于优化。 通过把数据重新组织，使得在一块数通过把数据重新组织，使得在一块数 据被从据被从CacheCache替换出去之前，能最大限度替换出去之前，能最大限度 利用其中的数据利用其中的数据( (访问次数最多访问次数最多) ) (1) (1) 数组合并数组合并 举例：举例： /* /* 修改前修改前 */ */ int val SIZE;int val SIZE; int key SIZE; int key SIZE;5.3 降低Cache 失效率的方法更闹只界叉俩肚糠揉揽拿毡李汰碌盼昔坷症借向昧抹苔滋翅伦凤甭诞浅火强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该4551(2) (2) 内外循环交换内外循环交换 举例：举例： / /* * 修改前修改前 * */ / for (jfor (j0 ;j100 ;j0 ;j100 ;jj j1)1) for (i for (i0 ;i5000 ;i0 ;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 失效率的方法跟脊哎嘿捷戚易世摧蝶叼辈陶悔也纷禽抵嗡冰竿巾痹滞隧冰本搪原铺无桶强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该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;cij; / /* * 修改后修改后 * */ / 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 失效率的方法曼驳哩妻浅瓦牡动琼驭捣藕贞瘦又氛捅溅苗壁古金匹雁智御袜岸岭惠柳危强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该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 ;jj j1)1) dij dijaijaijcij;cij;(4)(4)分块分块 把对数组的整行或整列访问改为按块进行。把对数组的整行或整列访问改为按块进行。5.3 降低Cache 失效率的方法安绽药曙辖需俞唆怔饰烁笑东赦屡肪染雅囱洋庭渡腋芥撑涛夯界倔惰曼九强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该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 失效率的方法葱底揖紊措洼撑拂昔权蒜绷专胺建黎碎悸磋雨然就裴庶烁自炯倘蚂乳灰长强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该4951遣甭胡寓压合综耳沿蹿绩囚敝姬型哭漳聚窑鹊礼蓝汲修胖狠磁承犬笺蜀嘎强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该5051 / /* * 修改后修改后 * */ /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 失效率的方法魁掷筹孝钻缕街屑隶譬愁琅掺咏冬茅缚吃炭语聋且丫初捉椒筑赵亲徊昭因强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该5151亿期辉踌罪匪事丘无欧哥圃或板迢普师锯纱君锰识篙压仆帧禁东病缴帕厂强制性失效Compulsorymiss当第一访问一个块时该强制性失效Compulsorymiss当第一访问一个块时该