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

1 强制性失效 Compulsorymiss 当第一次访问一个块时 该块不在Cache中 需从下一级存储器中调入Cache 这就是强制性失效 冷启动失效 首次访问失效 2 容量失效 Capacitymiss 如果程序执行时所需的块不能全部调入Cache中 则当某些块被替换后 若又 5 3降低Cache失效率的方法 1 三种失效 3C 第五章存储层次 虚拟存储器的特点 重新被访问 就会发生失效 这种失效称为容量失效 3 冲突失效 Conflictmiss 在组相联或直接映象Cache中 若太多的块映象到同一组 块 中 则会出现该组中某个块被别的块替换 即使别的组或块有空闲位置 然后又被重新访问的情况 这就是发生了冲突失效 碰撞失效 干扰失效 5 3降低Cache失效率的方法 虚拟存储器的特点 2 三种失效所占的比例 SPEC92 表5 5 5 3降低Cache失效率的方法 虚拟存储器的特点 图示I 绝对值 虚拟存储器的特点 图示 相对值 可以看出 1 相联度越高 冲突失效就越少 2 强制性失效和容量失效不受相联度的影响 3 强制性失效不受Cache容量的影响 但容量失效却随着容量的增加而减少 4 表中的数据符合2 1的Cache经验规则 即大小为N的直接映象Cache的失效率约等于大小为N 2的两路组相联Cache的失效率 虚拟存储器的特点 强制性失效 增加块大小 预取 本身很少 容量失效 增加容量 抖动现象 冲突失效 提高相联度 理想情况 全相联 3 减少三种失效的方法 4 许多降低失效率的方法会增加命中时间或失效开销 5 3降低Cache失效率的方法 5 3 1增加Cache块大小 1 失效率与块大小的关系 1 对于给定的Cache容量 当块大小增加失效率开始是下降 后来反而上升了 2 Cache容量越大 使失效率达到最低的块大小就越大 5 3降低Cache失效率的方法 虚拟存储器的特点 虚拟存储器的特点 2 增加块大小会增加失效开销 3 例题 虚拟存储器的特点 例5 4 假定存储系统在延迟40个时钟周期后 每2个时钟周期能送出16个字节 即 经过42个时钟周期 它可提供16个字节 经过44个时钟周期 可提供32个字节 依此类推 试问对于表5 6中列出的各种容量的Cache 在块大小分别为多少时 平均访存时间最小 解 解题过程1KB 4KB 16KBCache 块大小 32字节64KB 256KBCache 块大小 64字节 5 3降低Cache失效率的方法 虚拟存储器的特点 5 3 2提高相联度 1 采用相联度超过8的方法实际意义不大 2 2 1Cache经验规则容量为N的直接映象Cache 容量为N 2的两路组相联Cache 3 提高相联度是以增加命中时间为代价例如 TTL或ECL板级Cache 两路组相联 增加10 定制的CMOSCache 两路组相联 增加2 5 3降低Cache失效率的方法 虚拟存储器的特点 4 例题 假定提高相联度会按下列比例增大处理器时钟周期 时钟周期2路 1 10 时钟周期1路时钟周期4路 1 12 时钟周期1路时钟周期8路 1 14 时钟周期1路假定命中时间为1个时钟 直接映象情况下失效开销为50个时钟周期 而且假设不必将失效开销取整 使用表5 5中的失效率 试问当Cache为多大时 以下不等式成立 例5 5 5 3降低Cache失效率的方法 虚拟存储器的特点 平均访存时间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 5 3降低Cache失效率的方法 虚拟存储器的特点 在每种情况下的失效开销相同 都是50个时钟周期 把相应的失效率代入上式 即可得平均访存时间 例如 1KB的直接映象Cache的平均访存时间为 平均访存时间1路 1 00 0 133 50 7 65容量为128KB的8路组相联Cache的平均访存时间为 平均访存时间8路 1 14 0 006 50 1 44 表5 8 5 3降低Cache失效率的方法 虚拟存储器的特点 1 基本思想在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache 用于存放被替换出去的块 称为Victim 以备重用 工作过程 5 3 3VictimCache 5 3降低Cache失效率的方法 虚拟存储器的特点 虚拟存储器的特点 对于减小冲突失效很有效 特别是对于小容量的直接映象数据Cache 作用尤其明显 例如 项数为4的VictimCache 使4KBCache的冲突失效减少20 90 2 作用 5 3降低Cache失效率的方法 1 直接映象vs 组相联 5 3 4伪相联Cache 2 伪相联Cache 优点 缺点 直接映象 组相联 命中时间小 命中时间大 失效率高 失效率低 取直接映象及组相联两者的优点 命中时间小 失效率低 5 3降低Cache失效率的方法 1 基本思想及工作原理 动画演示 在逻辑上把直接映象Cache的空间上下平分为两个区 对于任何一次访问 伪相联Cache先按直接映象Cache的方式去处理 若命中 则其访问过程与直接映象Cache的情况一样 若不命中 则再到另一区相应的位置去查找 若找到 则发生了伪命中 否则就只好访问下一级存储器 2 快速命中与慢速命中要保证绝大多数命中都是快速命中 5 3降低Cache失效率的方法 3 例题 例5 6假设当在按直接映象找到的位置处没有发现匹配 而在另一个位置才找到数据 伪命中 需要2个额外的周期 仍用上个例子中的数据 问 当Cache容量分别为2KB和128KB时 直接映象 两路组相联和伪相联这三种组织结构中 哪一种速度最快 5 3降低Cache失效率的方法 首先考虑标准的平均访存时间公式 平均访存时间伪相联 命中时间伪相联 失效率伪相联 失效开销伪相联由于 失效率伪相联 失效率2路命中时间伪相联 命中时间1路 伪命中率伪相联 2 伪命中率伪相联 命中率2路 命中率1路 1 失效率2路 1 失效率1路 失效率1路 失效率2路 解 5 3降低Cache失效率的方法 故 平均访存时间伪相联 命中时间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 356 5 3降低Cache失效率的方法 根据上一个例子中的表5 8 对于2KBCache 可得 平均访存时间1路 5 90个时钟平均访存时间2路 4 90个时钟对于128KB的Cache有 可得 平均访存时间1路 1 50个时钟平均访存时间2路 1 45个时钟可见 对于这两种Cache容量 伪相联Cache都是速度最快的 缺点 多种命中时间 5 3降低Cache失效率的方法 5 3 5硬件预取技术 1 指令和数据都可以预取 2 预取内容既可放入Cache 也可放在外缓冲器中例如 指令流缓冲器 3 预取效果 1 Joppi的研究结果 指令预取 4KB 直接映象Cache 块大小 16字节 5 3降低Cache失效率的方法 1个块的指令流缓冲器 捕获15 25 的失效4个块的指令流缓冲器 捕获50 16个块的指令流缓冲器 捕获72 数据预取 4KB 直接映象Cache 1个数据流缓冲器 捕获25 的失效还可以采用多个数据流缓冲器 2 Palacharla和Kessler的研究结果流缓冲器 既能预取指令又能预取数据对于两个64KB四路组相联Cache来说 8个流缓冲器能捕获50 70 的失效 5 3降低Cache失效率的方法 4 例题 例5 7AlphaAXP21064采用指令预取技术 其实际失效率是多少 若不采用指令预取技术 AlphaAPX21064的指令Cache必须为多大才能保持平均访存时间不变 解 假设从预取缓冲器中找到所需指令需多花1个时钟周期 平均访存时间预取 命中时间 失效率 预取命中率 1 失效率 1 预取命中率 失效开销 5 3降低Cache失效率的方法 假设 预取命中率 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失效率的方法 可得相应的失效率为 失效率 平均访问时间 命中时间 失效开销 1 451 1 50 0 83 8KBCache 带预取的8kBCache 失效率 1 10 0 83 16KBCache 0 64 5 3降低Cache失效率的方法 5 3 6由编译器控制的预取 1 预取的类型 寄存器预取 把数据取到寄存器中 Cache预取 只将数据取到Cache中 故障性预取 预取时 若出现虚地址故障或违反访问权限 就会发生异常 非故障性预取 预取时 若出现虚地址故障或违反访问权限 并不会导致异常 只是转变为 不预取 由编译器加入预取指令 在数据被用到之前发出预取请求 5 3降低Cache失效率的方法 4 例题 2 在预取数据的同时 处理器应能继续执行只有这样 预取才有意义 非阻塞Cache 非锁定Cache 3 循环是预取优化的主要对象失效开销小时 循环体展开1 2次失效开销大时 循环体展开许多次 5 3降低Cache失效率的方法 例5 8对于下面的程序 判断哪些访问可能会导致数据Cache失效 然后 加入预取指令以减少失效 最后 计算所执行的预取指令的条数以及通过预取避免的失效次数 假定 1 我们用的是一个容量为8KB 块大小为16B的直接映象Cache 它采用写回法并且按写分配 2 a b分别为3 100 3行100列 和101 3的双精度浮点数组 每个元素都是8个字节 当程序开始执行时 这些数据都不在Cache内 5 3降低Cache失效率的方法 for i 0 i 3 i i 1 for j 0 j 100 j j 1 a i j b j 0 b j 1 0 解 1 计算过程 2 失效情况总的失效次数 251次 3 改进后的程序 5 3降低Cache失效率的方法 for j 0 j 100 j j 1 prefetch b j 7 0 预取7次循环后所需的b j 0 prefetch a 0 j 7 预取7次循环后所需的a 0 j a 0 j b j 0 b j 1 0 for i 1 i 3 i i 1 for j 0 j 100 j j 1 prefetch a i j 7 预取7次循环后所需的a i j a i j b j 0 b j 1 0 5 3降低Cache失效率的方法 例5 9在以下条件下 计算例5 8中所节约的时间 1 忽略指令Cache失效 并假设数据Cache无冲突失效和容量失效 2 假设预取可以被重叠或与Cache失效重叠执行 从而能以最大的存储带宽传送数据 3 不考虑Cache失效时 修改前的循环每7个时钟周期循环一次 修改后的程序中 失效情况总的失效次数 19次 5 3降低Cache失效率的方法 解 修改前 循环时间 300 7 2100失效开销 251 50 12550 146502100 12550 14650 第一个预取循环每9个时钟周期循环一次 而第二个预取循环每8个时钟周期循环一次 包括外层for循环的开销 4 一次失效需50个时钟周期 5 3降低Cache失效率的方法 修改后 循环时间 100 9 200 8 2500失效时间 19 50 9502500 950 3450加速比 14