1／51(1) (1) 强制性失效强制性失效( (Compulsory miss)Compulsory miss) 当第一次访问一个块时，该块不在当第一次访问一个块时，该块不在 CacheCache中，需从下一级存储器中调入中，需从下一级存储器中调入CacheCache，， 这就是这就是强制性失效强制性失效 ( (冷启动失效，首次访问失效冷启动失效，首次访问失效) )(2) (2) 容量失效容量失效( (Capacity miss ) Capacity miss ) 如果程序执行时所需的块不能全部调如果程序执行时所需的块不能全部调 入入CacheCache中，则当某些块被替换后，若又中，则当某些块被替换后，若又5.3 降低Cache失效率的方法1. 三种失效(3C)第五章 存储层次 2／51 重新被访问，就会发生失效这种失效称重新被访问，就会发生失效这种失效称 为为容量失效容量失效3) (3) 冲突失效冲突失效( (Conflict miss)Conflict miss) 在组相联或直接映象在组相联或直接映象CacheCache中，若太多中，若太多 的块映象到同一组的块映象到同一组( (块块) )中，则会出现该组中，则会出现该组 中某个块被别的块替换中某个块被别的块替换( (即使别的组或块有即使别的组或块有 空闲位置空闲位置) )，然后又被重新访问的情况。
这，然后又被重新访问的情况这 就是发生了就是发生了冲突失效冲突失效 ( (碰撞失效，干扰失效碰撞失效，干扰失效) )5.3 降低Cache 失效率的方法 3／512. 三种失效所占的比例( (SPEC92)SPEC92)表表5.55.5 5.3 降低Cache 失效率的方法 图示图示I(I(绝对值绝对值) ) 图示图示Ⅱ(Ⅱ(相对值相对值) ) 6／51可以看出：可以看出：(1) (1) 相联度越高，冲突失效就越少；相联度越高，冲突失效就越少；(2) (2) 强制性失效和容量失效不受相联度的影响；强制性失效和容量失效不受相联度的影响；(3) (3) 强制性失效不受强制性失效不受CacheCache容量的影响，但容容量的影响，但容 量失效却随着容量的增加而减少；量失效却随着容量的增加而减少；(4) (4) 表中的数据符合表中的数据符合2:12:1的的CacheCache经验规则经验规则，即，即 大小为大小为N N 的直接映象的直接映象CacheCache的失效率约等于的失效率约等于 大小为大小为N N/2/2 的两路组相联的两路组相联CacheCache的失效率。
的失效率 7／51强制性失效：强制性失效：增加块大小，预取增加块大小，预取 ( (本身很少本身很少) )容量失效：容量失效：增加容量增加容量 ( (抖动现象抖动现象) )冲突失效：冲突失效：提高相联度提高相联度 ( (理想情况：全相联理想情况：全相联) )3. 减少三种失效的方法4. 许多降低失效率的方法会增加命中时间或 失效开销5.3 降低Cache 失效率的方法 8／515.3.1 增加Cache块大小1. 失效率与块大小的关系 (1) (1) 对于给定的对于给定的CacheCache容量，当块大小增加容量，当块大小增加 失效率开始是下降，后来反而上升了；失效率开始是下降，后来反而上升了； (2) (2) CacheCache容量越大，使失效率达到最低的容量越大，使失效率达到最低的 块大小就越大块大小就越大5.3 降低Cache 失效率的方法 9／51 10／512 2. . 增加块大小会增加失效开销增加块大小会增加失效开销3. 3. 例题例题 11／51例例 5.4 5.4 假定存储系统在延迟假定存储系统在延迟4040个时钟周期后，每个时钟周期后，每2 2个个时钟周期能送出时钟周期能送出1616个字节。
即个字节即: :经过经过4242个时钟周期，个时钟周期，它可提供它可提供1616个字节；经过个字节；经过4444个时钟周期，可提供个时钟周期，可提供3232个字节；依此类推试问对于表个字节；依此类推试问对于表5-65-6中列出的各种中列出的各种容量的容量的CacheCache，，在块大小分别为多少时，平均访存在块大小分别为多少时，平均访存时间最小？时间最小？解解： 解题过程解题过程 1 1KBKB、、4KB4KB、、16KB Cache: 16KB Cache: 块大小＝块大小＝3232字节字节 64 64KBKB、、256KB Cache: 256KB Cache: 块大小＝块大小＝6464字节字节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.353 13／515.3.2 提高相联度1. 采用相联度超过8的方法实际意义不大2. 2:1 Cache经验规则 容量为容量为N N 的直接映象的直接映象CacheCache ≈ ≈容量为容量为N N/2/2的两路组相联的两路组相联CacheCache3. 提高相联度是以增加命中时间为代价 例如：例如： TTLTTL或或ECLECL板级板级CacheCache，，两路组相联：两路组相联： 增加增加1010％％ 定制的定制的CMOS Cache, CMOS Cache, 两路组相联：两路组相联： 增加增加2 2％％5.3 降低Cache 失效率的方法 14／514. 例题 假定提高相联度会按下列比例增大处理器假定提高相联度会按下列比例增大处理器时钟周期：时钟周期： 时钟周期时钟周期2 2路路 ＝＝1.10×1.10×时钟周期时钟周期1 1路路 时钟周期时钟周期4 4路路 ＝＝1.12×1.12×时钟周期时钟周期1 1路路 时钟周期时钟周期8 8路路 ＝＝1.14×1.14×时钟周期时钟周期1 1路路 假定命中时间为假定命中时间为1 1个时钟，直接映象情况个时钟，直接映象情况下失效开销为下失效开销为5050个时钟周期，而且假设不必将个时钟周期，而且假设不必将失效开销取整。
使用表失效开销取整使用表5 5－－5 5中的失效率，试问中的失效率，试问当当CacheCache为多大时，以下不等式成立？为多大时，以下不等式成立？例例 5.5 5.55.3 降低Cache 失效率的方法 15／51平均访存时间平均访存时间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路路×50×50 平均访存时间平均访存时间4 4路路 = = 1.12 1.12 ＋失效率＋失效率4 4路路×50×50 平均访存时间平均访存时间2 2路路 = = 1.10 1.10 ＋失效率＋失效率2 2路路×50×50 平均访存时间平均访存时间1 1路路 = = 1.00 1.00 ＋失效率＋失效率1 1路路×50×505.3 降低Cache 失效率的方法 16／51 在每种情况下的失效开销相同，都是在每种情况下的失效开销相同，都是5050个时钟周期。
把相应的失效率代入上式，个时钟周期把相应的失效率代入上式， 即可得平均访存时间即可得平均访存时间 例如，例如，1 1KBKB的直接映象的直接映象CacheCache的平均的平均访存时间为：访存时间为：平均访存时间平均访存时间1 1路路 ＝＝ 1.00 1.00＋＋(0.133×50)(0.133×50) ＝＝ 7.65 7.65 容量为容量为128128KBKB的的8 8路组相联路组相联CacheCache的平均的平均访存时间为：访存时间为：平均访存时间平均访存时间8 8路路 ＝＝1.141.14＋＋(0.006×50)(0.006×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.44 18／511 1. 基本思想 在在CacheCache和它从下一级存储器调数据和它从下一级存储器调数据 的通路之间设置一个全相联的小的通路之间设置一个全相联的小CacheCache，， 用于存放被替换出去的块用于存放被替换出去的块( (称为称为VictimVictim) )，， 以备重用。
以备重用 工作过程工作过程5.3.3 Victim Cache5.3 降低Cache 失效率的方法 19／51 20／51 对于减小冲突失效很有效，特别是对对于减小冲突失效很有效，特别是对于小容量的直接映象数据于小容量的直接映象数据CacheCache，，作用尤其作用尤其明显 例如，项数为例如，项数为4 4的的Victim Cache:Victim Cache: 使使4 4KB CacheKB Cache的冲突失效减少的冲突失效减少20%20%～～90%90%2. 作用5.3 降低Cache 失效率的方法 21／511. 直接映象 vs．组相联5.3.4 伪相联Cache2 2. 伪相联Cache优 点优 点缺 点缺 点直接映象直接映象组相联组相联命中时间小命中时间小命中时间大命中时间大失效率高失效率高失效率低失效率低取直接映象及组相联两者的优点：取直接映象及组相联两者的优点： 命中时间小，失效率低命中时间小，失效率低5.3 降低Cache 失效率的方法 22／51(1) (1) 基本思想及工作原理基本思想及工作原理 ( (动画演示动画演示) ) 在逻辑上把直接映象在逻辑上把直接映象CacheCache的空间上下的空间上下 平分为两个区。
对于任何一次访问，伪相联平分为两个区对于任何一次访问，伪相联 CacheCache先按直接映象先按直接映象CacheCache的方式去处理若的方式去处理若 命中，则其访问过程与直接映象命中，则其访问过程与直接映象CacheCache的情的情 况一样若不命中，则再到另一区相应的位况一样若不命中，则再到另一区相应的位 置去查找若找到，则发生了伪命中，否则置去查找若找到，则发生了伪命中，否则 就只好访问下一级存储器就只好访问下一级存储器2) (2) 快速命中与慢速命中快速命中与慢速命中 要保证绝大多数命中都是快速命中要保证绝大多数命中都是快速命中5.3 降低Cache 失效率的方法 23／51 24／513. 例题例例5.65.6 假设当在按直接映象找到的位置处没有发假设当在按直接映象找到的位置处没有发现匹配、而在另一个位置才找到数据现匹配、而在另一个位置才找到数据( (伪命中伪命中) )需要需要2 2个额外的周期仍用上个例子中的数据，个额外的周期仍用上个例子中的数据，问：当问：当CacheCache容量分别为容量分别为2 2KBKB和和128128KBKB时，直接时，直接映象、两路组相联和伪相联这三种组织结构中，映象、两路组相联和伪相联这三种组织结构中，哪一种速度最快？哪一种速度最快？5.3 降低Cache 失效率的方法 25／51首先考虑标准的平均访存时间公式：首先考虑标准的平均访存时间公式： 平均访存时间平均访存时间伪相联伪相联 ＝命中时间＝命中时间伪相联伪相联＋失效率＋失效率伪相联伪相联××失效开销失效开销伪相联伪相联由于：由于： 失效率失效率伪相联伪相联＝失效率＝失效率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 失效率的方法 26／51故：故： 平均访存时间平均访存时间伪相联伪相联 ＝命中时间＝命中时间1 1路路＋＋( (失效率失效率1 1路路－失效率－失效率2 2路路)×2)×2 ＋失效率＋失效率2 2路路××失效开销失效开销1 1路路将表将表5 5－－5 5中的数据代入上面的公式，得：中的数据代入上面的公式，得： 平均访存时间平均访存时间伪相联，伪相联，2 2KBKB ＝＝1 1＋＋(0.098(0.098－－0.076)×20.076)×2＋＋(0.076×50)(0.076×50) ＝＝4.8444.844 平均访存时间平均访存时间伪相联，伪相联，128128KBKB ＝＝1 1＋＋(0.010(0.010－－0.007)×20.007)×2＋＋(0.007×50)(0.007×50) ＝＝1.3561.3565.3 降低Cache 失效率的方法 27／51根据上一个例子中的表根据上一个例子中的表5 5－－8 8，对于，对于2 2KB CacheKB Cache，，可得：可得： 平均访存时间平均访存时间1 1路路 ＝＝5.90 5.90 个时钟个时钟 平均访存时间平均访存时间2 2路路 ＝＝4.90 4.90 个时钟个时钟对于对于128128KBKB的的CacheCache有，可得：有，可得： 平均访存时间平均访存时间1 1路路 ＝＝1.50 1.50 个时钟个时钟 平均访存时间平均访存时间2 2路路 ＝＝1.45 1.45 个时钟个时钟可见，对于这两种可见，对于这两种CacheCache容量，伪相联容量，伪相联CacheCache都是速度最快的。
都是速度最快的缺点：缺点：多种命中时间多种命中时间5.3 降低Cache 失效率的方法 28／515.3.5 硬件预取技术1. 指令和数据都可以预取2. 预取内容既可放入Cache，也可放在 外缓冲器中 例如：指令流缓冲器例如：指令流缓冲器3. 预取效果 (1) (1) JoppiJoppi的研究结果的研究结果 ◆ 指令预取：指令预取：(4(4KBKB，，直接映象直接映象Cache,Cache, 块大小＝块大小＝1616字节字节) )5.3 降低Cache 失效率的方法 29／511 1个块的指令流缓冲器：个块的指令流缓冲器： 捕获捕获1515％～％～2525％％ 的失效的失效4 4个块的指令流缓冲器：个块的指令流缓冲器： 捕获捕获5050％％1616个块的指令流缓冲器：个块的指令流缓冲器：捕获捕获7272％％◆ 数据预取：数据预取：(4(4KB,KB,直接映象直接映象Cache)Cache) 1 1个数据流缓冲器：个数据流缓冲器：捕获捕获2525％的失效％的失效 还可以采用多个数据流缓冲器还可以采用多个数据流缓冲器(2) (2) PalacharlaPalacharla和和KesslerKessler的研究结果的研究结果 流缓冲器：流缓冲器：既能预取指令又能预取数据既能预取指令又能预取数据 对于两个对于两个6464KBKB四路组相联四路组相联CacheCache来说：来说： 8 8个流缓冲器能个流缓冲器能捕获捕获5050％～％～7070％的失效。
％的失效5.3 降低Cache 失效率的方法 30／514. 例题例例5.75.7 Alpha AXP 21064Alpha AXP 21064采用指令预取技术，其实际采用指令预取技术，其实际失效率是多少？若不采用指令预取技术，失效率是多少？若不采用指令预取技术，AlphaAlphaAPX 21064APX 21064的指令的指令CacheCache必须为多大才能保持平均访必须为多大才能保持平均访存时间不变？存时间不变？解：解： 假设从预取缓冲器中找到所需指令需多花假设从预取缓冲器中找到所需指令需多花1 1个个时钟周期时钟周期 平均访存时间平均访存时间预取预取 ＝命中时间＋失效率＝命中时间＋失效率××预取命中率预取命中率×1×1 ＋失效率＋失效率×(1×(1－预取命中率－预取命中率)×)×失效开销失效开销5.3 降低Cache 失效率的方法 31／51假设：假设： 预取命中率＝预取命中率＝2525％％ 命中时间＝命中时间＝1 1个时钟周期个时钟周期 失效开销＝失效开销＝5050个时钟周期个时钟周期 由表由表5.45.4可知，可知，8 8KBKB指令指令CacheCache的失效率＝的失效率＝1.101.10％％ 故平均访存时间故平均访存时间预取预取 ＝＝1 1＋＋(1.10 %×25 %×1)(1.10 %×25 %×1)＋＋ (1.10 %×(1 (1.10 %×(1－－25 %)×50)25 %)×50) ＝＝1 1＋＋0.002750.00275＋＋0.4125 0.4125 ＝＝1.4151.415 由公式：由公式： 平均访问时间＝命中时间＋失效率平均访问时间＝命中时间＋失效率××失效开销失效开销5.3 降低Cache 失效率的方法 32／51可得相应的失效率为：可得相应的失效率为：失效率＝失效率＝( (平均访问时间－命中时间平均访问时间－命中时间)/)/失效开销失效开销 ＝＝(1.451(1.451－－1)/501)/50＝＝0.830.83％％8KB Cache8KB Cache 带预取的带预取的8 8kBkB Cache Cache失效率1.101.10％％0.830.83％％1616KB CacheKB Cache0.640.64％％5.3 降低Cache 失效率的方法 33／515.3.6 由编译器控制的预取1. 预取的类型 ◆ 寄存器预取：寄存器预取：把数据取到寄存器中把数据取到寄存器中 ◆ CacheCache预取：预取： 只将数据取到只将数据取到CacheCache中中 ◆ 故障性预取：故障性预取：预取时，若出现虚地址故障预取时，若出现虚地址故障 或违反访问权限，就会发生异常。
或违反访问权限，就会发生异常 ◆ 非故障性预取：非故障性预取：预取时，若出现虚地址故预取时，若出现虚地址故 障或违反访问权限，并不会导致异常，只障或违反访问权限，并不会导致异常，只 是转变为是转变为““不预取不预取””由编译器加入预取指令，在数据被用到之前由编译器加入预取指令，在数据被用到之前发出预取请求发出预取请求5.3 降低Cache 失效率的方法 34／514. 例题2. 在预取数据的同时，处理器应能继续执行 只有这样，预取才有意义只有这样，预取才有意义 非阻塞非阻塞Cache (Cache (非锁定非锁定Cache)Cache)3. 循环是预取优化的主要对象 失效开销小时：失效开销小时：循环体展开循环体展开1 1～～2 2次次 失效开销大时：失效开销大时：循环体展开许多次循环体展开许多次5.3 降低Cache 失效率的方法 35／51例例 5.8 5.8 对于下面的程序，判断哪些访问可能会导致对于下面的程序，判断哪些访问可能会导致数据数据CacheCache失效。
然后，加入预取指令以减少失失效然后，加入预取指令以减少失效最后，计算所执行的预取指令的条数以及通效最后，计算所执行的预取指令的条数以及通过预取避免的失效次数假定：过预取避免的失效次数假定： (1) (1) 我们用的是一个容量为我们用的是一个容量为8 8KBKB、、块大小为块大小为 16 16B B的直接映象的直接映象CacheCache，，它采用写回法并它采用写回法并 且按写分配且按写分配 (2) (2) a a、、b b分别为分别为3×100(33×100(3行行100100列列) )和和101×3101×3 的双精度浮点数组，每个元素都是的双精度浮点数组，每个元素都是8 8个个 字节当程序开始执行时，这些数据都字节当程序开始执行时，这些数据都 不在不在CacheCache内5.3 降低Cache 失效率的方法 36／51for (ifor (i＝＝0 ; i < 3 ; i0 ; i < 3 ; i＝＝i i＋＋1 )1 ) for (j for (j＝＝0 ; j < 100 ; j0 ; j < 100 ; j＝＝j j＋＋1 )1 ) a[i][j] a[i][j]＝＝b[j][0]×b[jb[j][0]×b[j＋＋1][0];1][0];解：解：( (1) 1) 计算过程计算过程(2) (2) 失效情况失效情况 总的失效次数＝总的失效次数＝251251次次 (3) (3) 改进后的程序改进后的程序5.3 降低Cache 失效率的方法 37／51 38／51 39／51for (jfor (j＝＝0 0，，j j＜＜100100；；j j＝＝j j＋＋1) 1) { { prefetch prefetch (b[j (b[j＋＋7][0]); 7][0]); / /* * 预取预取7 7次循环后所需的次循环后所需的b(j ,0 ) b(j ,0 ) * */ / prefetch prefetch (a[0][j (a[0][j＋＋7]); 7]); / /* * 预取预取7 7次循环后所需的次循环后所需的a(0,j ) a(0,j ) * */ / a[0][j] a[0][j]＝＝b[j ][0] b[j ][0] * * b [jb [j＋＋1][0]1][0] } } for (i for (i＝＝1; i < 3; i1; i < 3; i＝＝i i＋＋1) 1) { { for (j for (j＝＝0; j < 100; j0; j < 100; j＝＝j j＋＋1)1) prefetch prefetch(a[i][j(a[i][j＋＋7]);7]); / /* * 预取预取7 7次循环后所需的次循环后所需的a(i , j a(i , j ) */) */ a[i][j] a[i][j]＝＝b[j][0] b[j][0] * * b[j b[j＋＋1][0];1][0]; } }5.3 降低Cache 失效率的方法 40／51例例 5 5．．9 9 在以下条件下，计算例在以下条件下，计算例5.85.8中所节约的时间：中所节约的时间： (1) (1) 忽略指令忽略指令CacheCache失效，并假设数据失效，并假设数据CacheCache 无冲突失效和容量失效。
无冲突失效和容量失效 (2) (2) 假设预取可以被重叠或与假设预取可以被重叠或与CacheCache失效重失效重 叠执行，从而能以最大的存储带宽传送叠执行，从而能以最大的存储带宽传送 数据 (3) (3) 不考虑不考虑CacheCache失效时，修改前的循环每失效时，修改前的循环每7 7 个时钟周期循环一次修改后的程序中，个时钟周期循环一次修改后的程序中，失效情况失效情况 总的失效次数＝总的失效次数＝1919次次5.3 降低Cache 失效率的方法 41／51解：解： 修改前：修改前： 循环时间＝循环时间＝300×7 300×7 ＝＝21002100 失效开销＝失效开销＝251×50251×50＝＝12550/1465012550/14650 2100 2100＋＋1255012550＝＝1465014650 第一个预取循环每第一个预取循环每9 9个时钟周期循环一次，个时钟周期循环一次， 而第二个预取循环每而第二个预取循环每8 8个时钟周期循环一个时钟周期循环一 次次( (包括外层包括外层forfor循环的开销循环的开销) )。
4) (4) 一次失效需一次失效需5050个时钟周期个时钟周期5.3 降低Cache 失效率的方法 42／51 修改后：修改后： 循环时间＝循环时间＝100×9100×9＋＋200×8200×8＝＝25002500 失效时间＝失效时间＝19×5019×50＝＝950950 2500 2500＋＋950950＝＝34503450 加速比＝加速比＝14650/345014650/3450＝＝4.24.25.3 降低Cache 失效率的方法 43／515.3.7 编译器优化2 2KB Cache:KB Cache: 降低降低5050％％8 8KB CacheKB Cache：：降低降低75%75%1. 基本思想 在编译时，对程序中的指令和数据进行在编译时，对程序中的指令和数据进行重新组织，以降低重新组织，以降低CacheCache失效率2. McFaring 发现：通过对指令进行重新排序， 可有效地降低指令Cache的失效率5.3 降低Cache 失效率的方法 44／513. 数据对存储位置的限制比指令的少，因此 更便于优化。
通过把数据重新组织，使得在一块数通过把数据重新组织，使得在一块数 据被从据被从CacheCache替换出去之前，能最大限度替换出去之前，能最大限度 利用其中的数据利用其中的数据( (访问次数最多访问次数最多) ) (1) (1) 数组合并数组合并 举例：举例： /* /* 修改前修改前 */ */ int valint val [SIZE]; [SIZE]; int int key [SIZE];key [SIZE];5.3 降低Cache 失效率的方法 45／51(2) (2) 内外循环交换内外循环交换 举例：举例： / /* * 修改前修改前 * */ / for (jfor (j＝＝0 ;j<100 ;j0 ;j<100 ;j＝＝j j＋＋1)1) for (i for (i＝＝0 ;i<5000 ;i0 ;i<5000 ;i＝＝i i＋＋1)1) x[i][j] x[i][j]＝＝2 2* *x[i][j];x[i][j]; / /* * 修改后修改后 * */ / structstruct merge merge { { int val int val ; ; int int key ; key ; } } ; ; struct struct merge merged_array[size]; merge merged_array[size];5.3 降低Cache 失效率的方法 46／51(3) (3) 循环融合循环融合 举例：举例： / /* * 修改前修改前 */ */ for (ifor (i＝＝0 ; i
把对数组的整行或整列访问改为按块进行5.3 降低Cache 失效率的方法 48／51 举例：举例： / /* * 修改前修改前 * */ / for (ifor (i＝＝0; i < N; i0; i < N; i＝＝i i＋＋1)1) for (j for (j＝＝0; j < N; j0; j < N; j＝＝j j＋＋1) 1) { { r r＝＝0;0; for (k for (k＝＝0; k < N; k0; k < N; k＝＝k k＋＋1) 1) { { r r＝＝r r＋＋y[i][k]y[i][k]* *z[k][j];z[k][j]; } } x[i][j] x[i][j]＝＝r;r; } }计算过程计算过程 失效次数：失效次数：2 2N N3 3＋＋N N2 25.3 降低Cache 失效率的方法 49／51 50／51 / /* * 修改后修改后 * */ /for (for (jjjj＝＝0;0; jj jj < N; < N; jjjj＝＝jjjj＋＋1)1)for (for (kkkk＝＝0; 0; kkkk < N; < N; kkkk＝＝kkkk＋＋1)1)for (ifor (i＝＝0; i < N; i0; i < N; i＝＝i i＋＋1)1)for (jfor (j＝＝jjjj; j < min(; j < min(jjjj＋＋B B－－1,N); j1,N); j＝＝j j＋＋1) 1) { { r r＝＝0;0; for (k for (k＝＝kkkk; k < min(; k < min(kkkk＋＋B B－－1,N); k1,N); k＝＝k k＋＋1) 1) { { r r＝＝r r＋＋y[i][k]y[i][k]* *z[k][j];z[k][j]; } } x[i][j] x[i][j]＝＝x[i][j]x[i][j]＋＋r;r;} }计算过程计算过程 失效次数：失效次数：2 2N N3 3 /B/B ＋＋N N2 25.3 降低Cache 失效率的方法 51／51 。