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

1、1 1/32/32 计算机系统结构讲义 第5章 存储层次 讲解者：刘东波讲解者：刘东波 联系方式2 2/32/32 计算机系统结构讲义 Cache性能分析 降低Cache不命中率的方法 本讲小结 本讲主要内容 3 3/32/32 计算机系统结构讲义 重点与难点 1. 重点 根据平均访存时间公式和CPU执行时间公式进行 Cache性能分析 降低Cache不命中率的6种方法 2. 难点 Cache性能分析 伪相联Cache工作原理 4 4/32/32 计算机系统结构讲义 5.2.7 Cache的性能分析 1. 不命中率 与硬件速度无关 容易产生一些误导 2. 平均访存时间

2、 平均访存时间 命中时间失效率失效开销 5.2.7 Cache的性能分析 非常重要！ 5 5/32/32 计算机系统结构讲义 程序执行时间 CPUCPU时间（时间（CPUCPU执行周期数执行周期数+ +存储器停顿周期数）存储器停顿周期数） 时钟周期时间时钟周期时间 其中：其中： 存储器停顿时钟周期数存储器停顿时钟周期数“读读”的次数的次数读不命中率读不命中率读不读不 命中开销命中开销“写写”的次数的次数写不命中率写不命中率写不命中开销写不命中开销 存储器停顿时钟周期数访存次数存储器停顿时钟周期数访存次数不命中率不命中率不命中开销不命中开销 CPU时间（CPU执行周期数+访存次数不命中率不命中开

3、销） 时钟周期时间 时钟周期时间不命中开销不命中率 指令数 访存次数 时间 execution CPIICCPU =IC（CPIexecution每条指令的平均访存次数不命中率 不命中开销） 时钟周期时间 6 6/32/32 计算机系统结构讲义 5.2 Cache基本知识 例例5.15.1 用一个和用一个和Alpha AXPAlpha AXP类似的机器作为第一个例子。假类似的机器作为第一个例子。假 设设CacheCache不命中开销为不命中开销为5050个时钟周期，当不考虑存储器停顿时，个时钟周期，当不考虑存储器停顿时， 所有指令的执行时间都是所有指令的执行时间都是2.02.0个时钟周期，访问

4、个时钟周期，访问CacheCache不命中率为不命中率为 2%2%，平均每条指令访存，平均每条指令访存1.331.33次。试分析次。试分析CacheCache对性能的影响。对性能的影响。 解解 CPU时间时间有 有cache IC （CPIexecution每条指令的平均访存次数每条指令的平均访存次数 不命中率不命中率不命中开销）不命中开销） 时钟周期时间时钟周期时间 IC （2.01.332 %50） 时钟周期时间时钟周期时间 IC 3.33 时钟周期时间时钟周期时间 7 7/32/32 计算机系统结构讲义 5.2 Cache基本知识 考虑考虑CacheCache的不命中后，性能为：的不命中

5、后，性能为： CPUCPU时间时间有 有cachecache ICIC（2.02.01.331.332 %2 %5050）时钟周期时间时钟周期时间 ICIC3.333.33时钟周期时间时钟周期时间 实际实际CPI CPI ：3.333.33 3.33/2.0 = 1.67(3.33/2.0 = 1.67(倍倍) ) CPUCPU时间也增加为原来的时间也增加为原来的1.671.67倍。倍。 但若不采用但若不采用Cache,Cache,则：则： CPICPI2.02.050501.331.3368.568.5 8 8/32/32 计算机系统结构讲义 5.2 Cache基本知识 Cache不命中对于

6、一个CPI较小而时钟频率较高的CPU 来说，影响是双重的： CPIexecution越低，固定周期数的Cache不命中开销 的相对影响就越大。 在计算CPI时，不命中开销的单位是时钟周期数。 因此，即使两台计算机的存储层次完全相同，时 钟频率较高的CPU的不命中开销较大，其CPI中存 储器停顿这部分也就较大。 因此Cache对于低CPI、高时钟频率的CPU来 说更加重要。 9 9/32/32 计算机系统结构讲义 例例5.25.2 考虑两种不同组织结构的考虑两种不同组织结构的CacheCache：直接映像：直接映像 CacheCache和两路组相联和两路组相联CacheCache，试问它们对，试

7、问它们对CPUCPU的性能有何影的性能有何影 响？先求平均访存时间，然后再计算响？先求平均访存时间，然后再计算CPUCPU性能。分析时请性能。分析时请 用以下假设：用以下假设： 1010/32/32 计算机系统结构讲义 (1)(1)理想理想CacheCache（命中率为（命中率为100%100%）情况下的）情况下的CPICPI为为2.02.0，时钟周，时钟周 期为期为2ns2ns，平均每条指令访存，平均每条指令访存1.31.3次。次。 (2)(2)两种两种CacheCache容量均为容量均为64KB64KB，块大小都是，块大小都是3232字节。字节。 (3)(3)在组相联在组相联CacheCa

8、che中，中，由于多路选择器的存在而使由于多路选择器的存在而使CPU的时的时 钟周期增加到原来的钟周期增加到原来的1.10倍。这是因为对倍。这是因为对Cache的访问总是处于的访问总是处于 关键路径上，对关键路径上，对CPU的时钟周期有直接的影响。的时钟周期有直接的影响。 (4) (4) 这两种结构这两种结构CacheCache的不命中开销都是的不命中开销都是70ns70ns。（在实际应。（在实际应 用中，应取整为整数个时钟周期）用中，应取整为整数个时钟周期） (5) (5) 命中时间为命中时间为1 1个时钟周期，个时钟周期，64KB64KB直接映像直接映像CacheCache的不命的不命 中

9、率为中率为1.4%1.4%，相同容量的两路组相联，相同容量的两路组相联CacheCache的不命中率为的不命中率为1.0%1.0%。 1111/32/32 计算机系统结构讲义 5.2 Cache基本知识 解解 平均访存时间为：平均访存时间为： 平均访存时间命中时间不命中率平均访存时间命中时间不命中率不命中开销不命中开销 因此，两种结构的平均访存时间分别是：因此，两种结构的平均访存时间分别是： 平均访存时间平均访存时间1 1路 路 2.02.0（0.0140.0147070）2.98ns2.98ns 平均访存时间平均访存时间2 2路 路 2.02.01.101.10（0.0100.0107070

10、）2.90ns2.90ns 两路组相联两路组相联CacheCache的平均访存时间比较低。的平均访存时间比较低。 CPU时间时间IC（CPIexecution每条指令的平均访存次数每条指令的平均访存次数 不命中率不命中率不命中开销）不命中开销） 时钟周期时间时钟周期时间 IC（CPIexecution 时钟周期时间每条指令的时钟周期时间每条指令的 平均访存次数平均访存次数不命中率不命中率不命中开销不命中开销时钟周期时间）时钟周期时间） 1212/32/32 计算机系统结构讲义 5.2 Cache基本知识 因此：因此： CPUCPU时间时间1 1路 路 ICIC(2.0(2.02 2(1.3(1

11、.30.0140.01470)70) 5.275.27ICIC CPUCPU时间时间2 2路 路 ICIC(2.0(2.02 21.101.10(1.3(1.30.0100.01070)70) 5.315.31ICIC 直接映像直接映像CacheCache的平均性能好一些。的平均性能好一些。 1313/32/32 计算机系统结构讲义 5.2 Cache基本知识 1. 平均访存时间命中时间不命中率不命中开销 2. 可以从三个方面改进Cache的性能： 降低不命中率 减少不命中开销 减少Cache命中时间 3. 17种Cache优化技术 q8 8种种用于降低不命中率用于降低不命中率 q5 5种种用

12、于减少不命中开销用于减少不命中开销 q4 4种种用于减少命中时间用于减少命中时间 5.2.8 改进Cache的性能 1414/32/32 计算机系统结构讲义 1. 三种类型的不命中(3C) 强制性不命中(Compulsory miss) q当第一次访问一个块时，该块不在当第一次访问一个块时，该块不在CacheCache中，需从下中，需从下 一级存储器中调入一级存储器中调入CacheCache，这就是强制性不命中。，这就是强制性不命中。 ( (冷启动冷启动不命中，首次访问不命中）不命中，首次访问不命中） 容量不命中(Capacity miss ) q如果程序执行时所需的块不能全部调入如果程序执行

13、时所需的块不能全部调入CacheCache中，则中，则 当某些块被替换后，若又重新被访问，就会发生不命当某些块被替换后，若又重新被访问，就会发生不命 中。这种不命中称为容量不命中。中。这种不命中称为容量不命中。 5.3 降低Cache不命中率 5.3.1 三种类型的不命中 1515/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 冲突不命中(Conflict miss) q在组相联或直接映像在组相联或直接映像CacheCache中，若太多的块映像到中，若太多的块映像到 同一组同一组( (块块) )中，则会出现该组中某个块被别的块替中，则会出现该组中某个块被别的块替 换换( (即

14、使别的组或块有空闲位置即使别的组或块有空闲位置) )，然后又被重新访，然后又被重新访 问的情况。这就是发生了冲突不命中。问的情况。这就是发生了冲突不命中。 ( (碰撞不命中，干扰不命中碰撞不命中，干扰不命中) ) 三种不命中所占的比例 图示I(绝对值) 2.图示(相对值) 1616/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 1717/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 1818/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 可以看出： q相联度越高，冲突不命中就越少；相联度越高，冲突不命中就越少； q强制性不命中和容量不命中不

15、受相联度的影响；强制性不命中和容量不命中不受相联度的影响； q强制性不命中不受强制性不命中不受CacheCache容量的影响，但容量不命中容量的影响，但容量不命中 却随着容量的增加而减少。却随着容量的增加而减少。 1919/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 减少三种不命中的方法 q强制性不命中：强制性不命中：增加块大小，预取增加块大小，预取 （本身很少）（本身很少） q容量不命中：容量不命中：增加容量增加容量 （抖动现象）（抖动现象） q冲突不命中：冲突不命中：提高相联度提高相联度 （理想情况：全相联）（理想情况：全相联） 许多降低不命中率的方法会增加命中时间或不

16、命中 开销 2020/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 1. 不命中率与块大小的关系 对于给定的Cache容量，当块大小增加时，不命 中率开始是下降，后来反而上升了。 原因： q一方面它减少了强制性不命中；一方面它减少了强制性不命中； q另一方面，由于增加块大小会减少另一方面，由于增加块大小会减少CacheCache中块的数目，中块的数目， 所以有可能会增加冲突不命中。所以有可能会增加冲突不命中。 Cache容量越大，使不命中率达到最低的块大小 就越大。 2. 增加块大小会增加不命中开销 5.3.2 增加Cache块大小 2121/32/32 计算机系统结构讲义

17、5.3 降低Cache不命中率 1616 3232 6464 128128 256256 块大小（字节）块大小（字节） 10%10% 5%5% 0%0% 不命中率不命中率 256K256K 64K64K 16K16K 4K4K 不命中率随块大小变化的曲线不命中率随块大小变化的曲线 2222/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 各种块大小情况下Cache的不命中率 块大小 （字节） Cache容量（字节） 1K 4K 16K 64K 256K 16 15.05% 8.57% 3.94% 2.04% 1.09% 32 13.34% 7.24% 2.87% 1.35% 0

18、.70% 64 13.76% 7.00% 2.64% 1.06% 0.51% 128 16.64% 7.78% 2.77% 1.02% 0.49% 256 22.01% 9.51% 3.29% 1.15% 0.49% 2323/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 1. 最直接的方法是增加Cache的容量 缺点: q增加成本增加成本 q可能增加命中时间可能增加命中时间 2. 这种方法在片外Cache中用得比较多 5.3.3 增加Cache的容量 2424/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 1. 采用相联度超过8的方案的实际意义不大。 2.

19、 2:1 Cache经验规则 容量为N的直接映像Cache的不命中率和容量为 N/2的两路组相联Cache的不命中率差不多相同。 提高相联度是以增加命中时间为代价。 5.3.4 提高相联度 2525/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 1. 多路组相联的低不命中率和直接映像的命中速度 2. 伪相联Cache的优点 命中时间小 不命中率低 5.3.5 伪相联 Cache (列相联 Cache ) 优点优点缺点缺点 直接映像直接映像 组相联组相联 命中时间小 命中时间大 不命中率高 不命中率低 2626/32/32 计算机系统结构讲义 基本思想及工作原理 （动画演示）

20、在逻辑上把直接映像在逻辑上把直接映像CacheCache的空间上下平分为两个区。对于任何的空间上下平分为两个区。对于任何 一次访问，伪相联一次访问，伪相联CacheCache先按直接映像先按直接映像CacheCache的方式去处理。若命中，的方式去处理。若命中， 则其访问过程与直接映像则其访问过程与直接映像CacheCache的情况一样。若不命中，则再到另一的情况一样。若不命中，则再到另一 区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下 一级存储器。一级存储器。 索引索引 至至 CPUCPU 取出数据送往取出数据送往 C

21、PUCPU 伪相联组伪相联组 2727/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 缺点： 多种命中时间 快速命中与慢速命中 要保证绝大多数命中都是快速命中。 不命中开销不命中开销 2828/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 1. 指令和数据都可以预取 2. 预取内容既可放入Cache，也可放在外缓冲器中。 例如：指令流缓冲器例如：指令流缓冲器 3. 指令预取通常由Cache之外的硬件完成 4. 预取效果 Joppi的研究结果 q指令预取指令预取 (4KB(4KB，直接映像，直接映像CacheCache，块大小，块大小1616字节字节) n1 1个块的指令流缓冲器：个块的指令流缓冲器： 捕获捕获15152525的不命中的不命中 n4 4个块的指令流缓冲器：个块的指令流缓冲器： 捕获捕获5050 n1616个块的指令流缓冲器：捕获个块的指令流缓冲器：捕获7272 5.3.6 硬件预取 2929/32/32 计算机系统结构讲义 5.3 降低Cache不命中率 q数据预取数据预取 (4KB,(4KB,直接映像直接映像Cache)Cache) n1 1个数据流