Notes/计算机科学/计算机专业课程/计算机系统结构/第二章-缓存优化/01_章节关键原文.md

第二章 缓存优化 - 章节关键原文

曲冠南老师（原第2章 缓存优化-曲冠南上课用-20260319（8））

Slide 3

不命中率 （失效率） 平均访存时间 　 ＝ 命中时间＋不命中率×不命中开销

Slide 4

程序执行时间 CPU时间＝（CPU执行周期数+存储器停顿周期数）× 时钟周期时间 其中： 存储器停顿时钟周期数＝访存次数（读/写）×不命中率×不命中开销

Slide 5

例 用一个和Alpha AXP类似的机器作为第一个例子。假设Cache不命中开销为50个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是2.0个时钟周期，访问Cache不命中率为2%，平均每条指令访存1.33次。试分析Cache对性能的影响。

解 CPU时间有cache＝IC ×（CPIexecution＋每条指令的平均访存次数 ×不命中率×不命中开销）× 时钟周期时间 ＝IC ×（2.0＋1.33×2 %×50）× 时钟周期时间 ＝IC × 3.33× 时钟周期时间

考虑Cache的不命中后，性能为： 
    CPU时间有cache  ＝IC×（2.0＋1.33×2 %×50）×时钟周期时间
        ＝IC×3.33×时钟周期时间

　　实际CPI ：3.33 　　　　　3.33/2.0 = 1.67(倍) 　　CPU时间也增加为原来的1.67倍。 　　但若不采用Cache,则： 　　　　　CPI＝2.0＋50×1.33＝68.5

Slide 6

Cache不命中对于一个CPI较小而时钟频率较高的CPU来说，影响是双重的： CPIexecution越低，固定周期数的Cache不命中开销的相对影响就越大。 在计算CPI时，不命中开销的单位是时钟周期数。因此，即使两台计算机的存储层次完全相同，时钟频率较高的CPU的不命中开销较大，其CPI中存储器停顿这部分也就较大。 　 因此Cache对于低CPI、高时钟频率的CPU来说更加重要。

Slide 7

例 考虑两种不同组织结构的Cache：直接映像Cache和两路组相联Cache，试问它们对CPU的性能有何影响？先求平均访存时间，然后再计算CPU性能。分析时请用以下假设： (1)理想Cache（命中率为100%）情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.3次。 (2)两种Cache容量均为64KB，块大小都是32字节。（考虑下这个条件意味着啥） (3)在组相联Cache中，由于多路选择器的存在而使CPU的时钟周期增加到原来的1.10倍。这是因为对Cache的访问总是处于关键路径上，对CPU的时钟周期有直接的影响。 (4) 这两种结构Cache的不命中开销都是70ns。（在实际应用中，应取整为整数个时钟周期） (5) 命中时间为1个时钟周期，64KB直接映像Cache的不命中率为1.4%，相同容量的两路组相联Cache的不命中率为1.0%。

Slide 8

解 平均访存时间为： 平均访存时间＝命中时间＋不命中率×不命中开销

因此，两种结构的平均访存时间分别是： 平均访存时间1路＝2.0＋（0.014×70）＝2.98ns 平均访存时间2路＝2.0×1.10＋（0.010×70）＝2.90ns

两路组相联Cache的平均访存时间比较低。

Slide 9

CPU时间1路 ＝ IC×(2.0×2＋(1.3×0.014×70) ＝ 5.27×IC CPU时间2路 ＝ IC×(2.0×2×1.10＋(1.3×0.010×70))＝ 5.31×IC

直接映像Cache的平均性能好一些。

Slide 11

平均访存时间＝命中时间＋不命中率×不命中开销 可以从三个方面改进Cache的性能： 降低不命中率 减少不命中开销 减少Cache命中时间 下面介绍17种Cache优化技术 8种用于降低不命中率 5种用于减少不命中开销 4种用于减少命中时间

Slide 12

三种类型的不命中(3C) 强制性不命中(Compulsory miss) 当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性不命中。 (冷启动不命中，首次访问不命中） 容量不命中(Capacity miss ) 如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生不命中。这种不命中称为容量不命中。 冲突不命中(Conflict miss) 在组相联或直接映像Cache中，若太多的块映像到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突不命中。 (碰撞不命中，干扰不命中)

Slide 13

三种类型的不命中 强制性不命中不受Cache容量的影响； 强制性不命中不受相联度的影响。

容量不命中不受相联度的影响； 但容量不命中却随着容量的增加而减少。

相联度越高，冲突不命中就越少

具体数据，请见学习通章节2.3 必读资料中的表5.3

Slide 14

2.3.2 降低不命中率的方法 针对三种类型的不命中的直接方法 针对强制不命中 -- 增加块大小 （方法一） 针对容量不命中 -- 增加Cache容量 （方法二） 针对冲突不命中 -- 提高相联度 （方法三）

其他方法 伪相联Cache （方法四） 硬件预取 （方法五） 编译器预取 （方法六） 编译器优化 （方法七） 牺牲Cache （方法八）

Slide 15

方法一：增加块大小

对于给定的Cache容量，当块大小增加时，不命中率开始是下降，后来反而上升了。

Cache容量越大，使不命中率达到最低的块大小就越大。（从上到下，曲线越来越平）

问题一：为什么增加块大小可以降低强制不命中？ 问题二：为什么不命中率先下降后上升？ 问题三：增加块大小还可能带来什么不良后果？

Slide 16

问题一：为什么增加块大小可以降低强制不命中？

问题二：为什么不命中率先下降后上升？ 一方面它减少了强制性不命中；（不命中率总体下降） 另一方面，由于增加块大小会减少Cache中块的数目，所以有可能会增加冲突不命中。（不命中率又升高了）

问题三：增加块大小还可能带来什么不良后果？ 会增加不命中开销。

Slide 17

方法二：增加Cache的容量

最直接的方法是增加Cache的容量 缺点: 增加成本 可能增加命中时间（增加查找时间） 这种方法在片外Cache中用得比较多

Slide 18

方法三：提高相联度

采用相联度超过8的方案的实际意义不大。 2:1Cache经验规则 容量为N的直接映像Cache的不命中率和容量为N/2的两路组相联Cache的不命中率差不多相同。 提高相联度是以增加命中时间为代价。

Slide 19

多路组相联 V.S. 直接映像

方法四：伪相联 Cache (列相联 Cache )

伪相联Cache的优点 命中时间小 不命中率低

Slide 20

基本思想及工作原理 在逻辑上把直接映像Cache的空间上下平分为两个区。 对于任何一次访问，伪相联Cache先按直接映像Cache的方式去处理。 若命中，则其访问过程与直接映像Cache的情况一样。 若不命中，则再到另一区相应的位置去查找。 若找到，则发生了伪命中. 否则就只好访问下一级存储器。

Slide 21

缺点 ：多种命中时间 -- 快速命中与慢速命中 要保证绝大多数命中都是快速命中。

Slide 22

例 假设命中时间为1个周期，按直接映象找到的位置处没有发现匹配，而在另一个位置才找到数据（伪命中）需要2个额外的周期。问：当Cache容量分别为2 KB和128 KB时，直接映象、2路组相联和伪相联这三种组织结构中，哪一种速度最快？

Slide 23

解 平均访存时间伪相联 ＝ 命中时间伪相联＋失效率伪相联×失效开销伪相联

命中时间伪相联＝命中时间1路＋伪命中率伪相联×2

伪相联查找的命中率等于2路组相联Cache的命中率和直接映象Cache命中率之差。

伪命中率伪相联 ＝命中率2路－命中率1路 ＝（1－失效率2路）－（1－失效率1路） ＝失效率1路－失效率2路

② 失效率伪相联＝失效率2路 ③ 失效开销伪相联 = 失效开销1路

Slide 24

将前面表中的数据代入上面的公式，得： 平均访存时间伪相联，2 KB ＝1＋（0.098－0.076）×2＋（0.076×50）＝4.844 对于2 KB Cache，有： 平均访存时间1路 ＝5.90 个时钟 平均访存时间2路 ＝4.90 个时钟

对于128KB的Cache有，可得： 平均访存时间伪相联，128 KB＝1＋（0.010－0.007）×2＋（0.007×50）＝1.356 平均访存时间1路 ＝1.50 个时钟 平均访存时间2路 ＝1.45 个时钟

可见，对于这两种Cache容量，伪相联Cache都是速度最快的。

Slide 25

方法五：硬件预取

指令和数据都可以预取 预取内容既可放入Cache，也可放在外缓冲器中。 例如：指令流缓冲器 指令预取通常由Cache之外的硬件完成 例如：Alpha AXP 21064微处理器在发生指令不命中时取两个块 – 被请求的指令块和顺序的下一指令块。被请求的指令块返回时放入Cache，而预取的指令块放入到缓冲器中。

Slide 26

预取应利用存储器的空闲带宽，不能影响对正常不命中的处理，否则可能会降低性能。

预取效果 Joppi的研究结果 指令预取 (4KB，直接映像Cache，块大小＝16字节) 1个块的指令流缓冲器： 捕获15％～25％的不命中 4个块的指令流缓冲器： 捕获50％ 16个块的指令流缓冲器：捕获72％ 数据预取 (4KB,直接映像Cache) 1个数据流缓冲器，捕获25％的不命中 还可以采用多个数据流缓冲器 Palacharla和Kessler的研究结果 流缓冲器：既能预取指令又能预取数据 对于两个64KB四路组相联Cache来说： 8个流缓冲器能捕获50％～70％的不命中

Slide 27

方法六：编译器控制的预取

主要思想：在编译时加入预取指令，在数据被用到之前发出预取请求。

假定： (1) 使用一个容量为8 KB、块大小为16 B的直接映象Cache，它采用写回法并且按写分配 (2) a、b分别为3×100（3行100列）和101×3的双精度浮点数组，每个元素都是8B。当程序开始执行时，这些数据都不在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）首先，判断哪些访问可能会导致数据Cache失效； （2）其次，加入预取指令以减少失效； （3）最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。

Slide 28

分析可能发生哪种失效

假设数组a和b在内存中连续按行存储； 1块16B，无论是a还是b，一块2个元素； 对于数组a，分布在150块中； 对于数组b，分布在152块中； a和b一共302块，少于Cache总块数，因此，不会发生容量失效； 直接映射，按照假定，a和b连续存储，不会发生冲突失效； 只能发生强制失效。

Slide 29-30

根据运算过程分析不命中和命中

数组a的访问规律 a [0][0] 至 a [0][6]可能产生数据访问失效 数组a: 共150块，失效150次

数组b的访问规律 b [0][0] 至 b [6][0]可能产生数据访问失效 数组b：i=0时，失效101次；i=1和2时，无失效 一共失效次数：150+101 = 251次

Slide 31

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 ]; } / a失效 7/2 = 4, 两次循环共失效8次 */

总的失效次数＝4+7+4+4 = 19 次

Slide 32

按照预取数据所放的位置，可把预取分为两种类型： 寄存器预取：把数据取到寄存器中。 Cache预取：只将数据取到Cache中。

按照预取的处理方式不同，可把预取分为： 故障性预取：在预取时，若出现虚地址故障或违反保护权限，就会发生异常。 非故障性预取：在遇到这种情况时则不会发生异常，因为这时它会放弃预取，转变为空操作。本节假定Cache预取都是非故障性的，也叫做非绑定预取。

Slide 33

在预取数据的同时，处理器应能继续执行。 只有这样，预取才有意义。 非阻塞Cache (非锁定Cache)

编译器控制预取的目的 使执行指令和读取数据能重叠执行。 循环是预取优化的主要对象 不命中开销小时：循环体展开1～2次 不命中开销大时：循环体展开许多次 每次预取需要花费一条指令的开销 保证这种开销不超过预取所带来的收益 编译器可以通过把重点放在那些可能会导致不命中的访问上，使程序避免不必要的预取，从而较大程度地减少平均访存时间。

Slide 35

方法七：编译器优化

基本思想：通过对软件进行优化来降低不命中率。 （特色：无需对硬件做任何改动） 程序代码和数据重组 可以重新组织程序而不影响程序的正确性 把一个程序中的过程重新排序，就可能会减少冲突不命中，从而降低指令不命中率。 McFarling研究了如何使用配置文件（profile）来进行这种优化。 把基本块对齐，使得程序的入口点与Cache块的起始位置对齐，就可以减少顺序代码执行时所发生的Cache不命中的可能性。 如果编译器知道一个分支指令很可能会成功转移，那么它就可以通过以下两步来改善空间局部性： 将转移目标处的基本块和紧跟着该分支指令后的基本块进行对调； 把该分支指令换为操作语义相反的分支指令。 数据对存储位置的限制更少，更便于调整顺序。

这两点都是使得大概率执行的代码段放在分支失败处

Slide 36

编译优化技术包括 （1）数组合并 （2）内外循环交换 （3）循环融合 （4）分块

Slide 37

（1）数组合并 基本思想: 将本来相互独立的多个数组合并成为一个复合数组，以提高访问它们的局部性。

举例： /* 修改前 */ int x[100]; int y[100];

/* 修改后 */ struct merge{ int x; int y; }; struct merge merged_array[100];

Slide 38

（2）内外循环交换 基本思想: 提高访问的局部性

举例：
/* 修改前 */ for （ j = 0 ; j < 100 ; j = j+1 ） for （ i = 0 ; i < 5000 ; i = i+1 ） x [ i ][ j ] = 2 * x [ i ][ j ];

/* 修改后 */ for （ i = 0 ; i < 5000 ; i = i+1 ） for （ j = 0 ; j < 100 ; j = j+1 ） x [ i ][ j ] = 2 * x [ i ][ j ];

Slide 39

（3）循环融合 基本思想: 将若干个独立的循环融合为单个的循环。这些循环访问同样的数组，对相同的数据作不同的运算。这样能使得读入Cache的数据在被替换出去之前，能得到反复的使用 。

举例： /* 修改前 */ for（j = 0; j < 100; j = j+1 ） x[i][j] = a[i][j] + b[i][j]； for（j = 0; j < 100; j = j+1 ） y[i][j] = a[i][j] - b[i][j]；

/* 修改后 */ for（j = 0; j < 100; j = j+1 ）{ x[i][j] = a[i][j] + b[i][j]； y[i][j] = a[i][j] - b[i][j]； }

Slide 40

（4）分块 基本思想: 把对数组的整行或整列访问改为按块进行，尽量集中访问，减少替换，提高访问的局部性。

/* 修改前 */ for （ i = 0; i<N; i = i+1 ） for （ j = 0; j < N; j = j+1 ） { r = 0; for （ k = 0; k < N; k = k+1） { r = r + y[ i ][ k ] * z[ k ][ j ]; } x[ i ][ j ] = r; }

Slide 41

/* 修改后 */ for （ jj = 0; jj < N; jj = jj+B ） for （ kk = 0; kk < N; kk = kk+B ） for （ i = 0; i < N; i =i+1 ） for （ j = jj; j < min（jj+B-1, N）; j = j+1 ） { r = 0; for （ k = kk; k < min（kk+B-1, N）; k = k+1） { r = r + y[ i ][ k ] * z[ k ][ j ]; } x[ i ][ j ] = x[ i ][ j ] + r; }

Slide 42

方法八："牺牲"Cache

一种能减少冲突不命中次数而又不影响时钟频率的方法。 基本思想：在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，称为"牺牲"Cache（Victim Cache）。用于存放被替换出去的块(称为牺牲者)，以备重用。 作用 对于减小冲突不命中很有效，特别是对于小容量的直接映像数据Cache，作用尤其明显。 例如项数为4的Victim Cache，能使4KB Cache的冲突不命中减少20%～90%

Slide 43

应把Cache做得更快？还是更大？ 答案：二者兼顾，再增加一级Cache 第一级Cache(L1)小而快 第二级Cache(L2)容量大

性能分析 平均访存时间 ＝ 命中时间L1＋不命中率L1×不命中开销L1 不命中开销L1 ＝ 命中时间L2＋不命中率L2×不命中开销L2

Slide 44

局部不命中率与全局不命中率 局部不命中率＝该级Cache的不命中次数/到达该级Cache的访问次数 例如：上述式子中的不命中率L2 全局不命中率＝该级Cache的不命中次数/CPU发出的访存的总次数 全局不命中率L2＝不命中率L1×不命中率L2 全局不命中率比局部不命中率更有意义，它指出了在CPU发出的访存中，究竟有多大比例是穿过各级Cache，最终到达存储器的。 采用两级Cache时，每条指令的平均访存停顿时间： 每条指令的平均访存停顿时间 ＝ 每条指令的平均不命中次数L1×命中时间L2 ＋每条指令的平均不命中次数L2×不命中开销L2

Slide 45

例 考虑某一两级Cache：第一级Cache为L1，第二级Cache为L2。 （1）假设在1000次访存中，L1的不命中是40次，L2的不命中是20次。求各种局部不命中率和全局不命中率。 （2）假设L2的命中时间是10个时钟周期，L2的不命中开销是100时钟周期，L1的命中时间是1个时钟周期，平均每条指令访存1.5次，不考虑写操作的影响。问：平均访存时间是多少？每条指令的平均停顿时间是多少个时钟周期？

Slide 46

解 （1）第一级Cache的不命中率（全局和局部）是40/1000，即4%； 第二级Cache的局部不命中率是20/40，即50%； 第二级Cache的全局不命中率是20/1000，即2%。

（2）平均访存时间＝命中时间L1＋不命中率L1×（命中时间L2＋不命中率L2×不命中开销L2） ＝1＋4%×（10＋50%×100） ＝1＋4%×60＝3.4个时钟周期 由于平均每条指令访存1.5次，且每次访存的平均停顿时间为： 3.4－1.0＝2.4 所以： 每条指令的平均停顿时间＝2.4×1.5＝3.6个时钟周期

Slide 47

对于第二级Cache，我们有以下结论： 在第二级Cache比第一级 Cache大得多的情况下，两级Cache的全局不命中率和容量与第二级Cache相同的单级Cache的不命中率非常接近。 局部不命中率不是衡量第二级Cache的一个好指标，因此，在评价第二级Cache时，应用全局不命中率这个指标。 第二级Cache不会影响CPU的时钟频率，因此其设计有更大的考虑空间。 设计第二级Cache时有两个问题需要权衡： 它能否降低CPI中的平均访存时间部分？ 它的成本是多少？ 第二级Cache的参数 容量：第二级Cache的容量一般比第一级的大许多。 大容量意味着第二级Cache可能实际上没有容量不命中，只剩下一些强制性不命中和冲突不命中。 相联度：第二级Cache可采用较高的相联度或伪相联方法。

Slide 48

块大小 第二级Cache可采用较大的块，如 64、128、256字节 为减少平均访存时间，可以让容量较小的第一级Cache采用较小的块，而让容量较大的第二级Cache采用较大的块。 多级包容性 需要考虑的另一个问题： 第一级Cache中的数据是否总是同时存在于第二级Cache中。如果是，就说第二级Cache是具有多级包容性的。

Slide 49

方法二：让读不命中优先于写

Cache中的写缓冲器导致对存储器访问的复杂化 在读不命中时，所读单元的最新值有可能还在写缓冲器中，尚未写入主存。 解决问题的方法(读不命中的处理) 推迟对读不命中的处理，直到写缓冲器清空 （缺点：读不命中的开销增加） 检查写缓冲器中的内容，若无相同，且存储器可用，继续处理读不命中（常用方案） 在写回法Cache中，也可采用写缓冲器。

Slide 50

方法三：写缓冲合并

提高写缓冲器的效率 写直达Cache依靠写缓冲来减少对下一级存储器写操作的时间。 如果写缓冲器为空，就把数据和相应地址写入该缓冲器。从CPU的角度来看，该写操作就算是完成了。 如果写缓冲器中已经有了待写入的数据，就要把这次的写入地址与写缓冲器中已有的所有地址进行比较，看是否有匹配的项。如果有地址匹配而对应的位置又是空闲的，就把这次要写入的数据与该项合并。这就叫写缓冲合并。 如果写缓冲器满且又没有能进行写合并的项，就必须等待。 作用 连续写入多个字的速度快于每次只写入一个字的操作； 提高了写缓冲器的空间利用率，减少因写缓冲器满而要进行的等待时间。

Slide 51

例如 写缓冲区有4项，每项4个64位的字。

Slide 52

方法四：请求字处理技术

请求字 从下一级存储器调入Cache的块中，只有一个字是立即需要的。这个字称为请求字。 应尽早把请求字发送给CPU 尽早重启动：请求字没有到达时，CPU处于等待状态。一旦请求字到达，立即送给CPU，让等待的CPU尽早重启动，继续执行。 请求字优先：调块时，让存储器首先提供CPU所要的请求字。请求字一旦到达，就立即送给CPU，让CPU继续执行，同时从存储器调入该块的其余部分。 在以下情况下，用不用差别不大 Cache块较小 下一条指令正好访问同一Cache块的另一部分

Slide 53

方法五：非阻塞Cache技术

非阻塞Cache：采用记分牌或者Tomasulo类控制方式，允许指令乱序执行，CPU无需在Cache不命中时停顿； 允许多次不命中，进一步提高性能； 可以同时处理的不命中次数越多，所能带来的性能上的提高就越大。

Slide 54

模拟研究 数据Cache的平均存储器等待时间（以周期为单位）与阻塞Cache平均存储器等待时间的比值。 测试条件：8K直接映像Cache，块大小为32字节 测试程序：SPEC92（14个浮点程序，4个整数程序） 结果表明：在重叠不命中个数为1、2和64的情况下 浮点程序的平均比值分别为：76%、51%和39% 整数程序的平均比值则分别为：81%、78%和78%

对于整数程序来说，重叠次数对性能提高影响不大，简

单的"一次不命中下命中"就几乎可以得到所有的好处。

Slide 55

命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是Cache的访问时间限制了处理器的时钟频率。

Slide 56

方法一：使用小容量、结构简单的Cache

硬件越简单，速度就越快； 应使Cache足够小，以便可以与CPU一起放在同一块芯片上。 某些设计采用了一种折衷方案： 把Cache的标识放在片内，而把Cache的数据存储器放在片外。 采用结构简单的Cache，比如直接映像Cache。

Slide 57

物理Cache 使用物理地址进行访问的传统Cache。 标识存储器中存放的是物理地址，进行地址检测也是用物理地址。 缺点：地址转换和访问Cache串行进行，访问速度很慢。

Slide 58

虚拟Cache 可以直接用虚拟地址进行访问的Cache。标识存储器中存放的是虚拟地址，进行地址检测用的也是虚拟地址。 优点：在命中时不需要地址转换，省去了地址转换的时间。即使不命中，地址转换和访问Cache也是并行进行的，其速度比物理Cache快很多。

Slide 59

并非都采用虚拟Cache 清空问题：由于新进程的虚拟地址可能与原进程相同； 解决方法：在地址标识中增加PID(进程标识符)字段； PID相关问题：为了减少位数，PID可能循环使用，所以也可能存在多个进程使用同一个PID，所以此时也需要清空Cache。

Slide 60

虚拟索引＋物理标识 原理：使用虚地址中的页内位移生成Cache索引；虚实转换后的实页地址作为标志tag 优点：兼得虚拟Cache和物理Cache的好处 局限性：Cache容量受到限制 Cache容量≤页大小×相联度 举例：IBM3033的Cache 页大小＝4KB 相联度＝16

Cache容量＝16×4KB＝64KB

Slide 61

方法三：Cache访问流水化

对第一级Cache的访问按流水方式组织 访问Cache需要多个时钟周期才可以完成 例如 Pentium访问指令Cache需要一个时钟周期 Pentium Pro到Pentium Ⅲ需要两个时钟周期 Pentium 4 则需要4个时钟周期

Slide 62

方法四：踪迹Cache

开发指令级并行性所遇到的一个挑战是： 当要每个时钟周期流出超过4条指令时，要提供足够多条彼此互不相关的指令是很困难的。

一个解决方法：采用踪迹 Cache 存放CPU所执行的动态指令序列，包含了由分支预测展开的指令，该分支预测是否正确需要在取到该指令时进行确认。

优缺点 地址映像机制复杂； 相同的指令序列有可能被当作条件分支的不同选择而重复存放； 能够提高指令Cache的空间利用率。

Slide 64

Cache优化技术总结 "＋"号：表示改进了相应指标。 "－"号：表示它使该指标变差。 空格栏：表示它对该指标无影响。 复杂性：0表示最容易，3表示最复杂。

---

李宏图老师（原第2章 缓存优化-李宏图-5.6）

Slide 3

不命中率 （失效率）—— 1-H（命中率） 命中率——CPU访问存储系统时，在M1中找到所需信息的概率。

N1 ── 访问M1的次数 N2 ── 访问M2的次数

Slide 4

CPU的一次访存时间： 当命中时，访问时间即为T1（命中时间） 当不命中时，情况比较复杂。 不命中时的访问时间为：T2＋TB＋T1＝T1＋TM
其中：TM ＝T2＋TB 不命中开销TM：从向M2发出访问请求到把整个数据块调入M1中所需的时间。 传送一个信息块所需的时间为TB。

Slide 5

平均访存时间 　 TA＝ HT1＋（1－H）（T1＋TM） ＝ T1＋（1－H）TM 或 TA ＝ T1＋FTM 　　　　 平均访存时间 ＝ 命中时间＋不命中率×不命中开销

Slide 6

CPU时间＝（CPU执行周期数+访存次数×不命中率×不命中开销）× 时钟周期时间 =IC×（CPIexecution＋每条指令的平均访存次数×不命中率×不命中开销）× 时钟周期时间

程序执行时间 CPU时间＝（CPU执行周期数+存储器停顿周期数）× 时钟周期时间 其中： 存储器停顿时钟周期数＝"读"的次数×读不命中率×读不命中开销 ＋"写"的次数×写不命中率×写不命中开销 存储器停顿时钟周期数＝访存次数×不命中率×不命中开销

Slide 7

例 用一个和Alpha AXP类似的机器作为第一个例子。假设Cache不命中开销为50个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是2.0个时钟周期，访问Cache不命中率为2%，平均每条指令访存1.33次。试分析Cache对性能的影响。 解 CPU时间有cache＝IC ×（CPIexecution＋每条指令的平均访存次数 ×不命中率×不命中开销）× 时钟周期时间 ＝IC ×（2.0＋1.33×2%×50）× 时钟周期时间 ＝IC × 3.33× 时钟周期时间

考虑Cache的不命中后，性能为： 　 CPU时间有cache ＝IC×（2.0＋1.33×2%×50）×时钟周期时间 ＝IC×3.33×时钟周期时间 　　实际CPI ：3.33 　　　　　3.33/2.0 = 1.67(倍) 　　CPU时间也增加为原来的1.67倍。 　　但若不采用Cache,则： 　　　　　CPI＝2.0＋50×1.33＝68.5

Slide 8

Cache不命中对于一个CPI较小而时钟频率较高的CPU来说，影响是双重的： CPIexecution越低，固定周期数的Cache不命中开销的相对影响就越大。 在计算CPI时，不命中开销的单位是时钟周期数。因此，即使两台计算机的存储层次完全相同，时钟频率较高的CPU的不命中开销较大，其CPI中存储器停顿这部分也就较大。 　 因此Cache对于低CPI、高时钟频率的CPU来说更加重要。

Slide 14

三种类型的不命中(3C) 强制性不命中(Compulsory miss) 当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性不命中。 (冷启动不命中，首次访问不命中） 容量不命中(Capacity miss ) 如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生不命中。这种不命中称为容量不命中。 冲突不命中(Conflict miss) 在组相联或直接映像Cache中，若太多的块映像到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突不命中。 (碰撞不命中，干扰不命中)

Slide 15

相联度越高，冲突不命中就越少； 强制性不命中和容量不命中不受相联度的影响； 强制性不命中不受Cache容量的影响，但容量不命中却随着容量的增加而减少。

Slide 16

2.3.2 降低不命中率的方法 针对三种类型的不命中的直接方法 针对强制不命中 -- 增加块大小 （方法一） 针对容量不命中 -- 增加Cache容量 （方法二） 针对冲突不命中 -- 提高相联度 （方法三）

其他方法 伪相联Cache （方法四） 硬件预取 （方法五） 编译器预取 （方法六） 编译器优化 （方法七） 牺牲Cache （方法八）

Slide 17

方法一：增加块大小

对于给定的Cache容量，当块大小增加时，不命中率开始是下降，后来反而上升了。 Cache容量越大，使不命中率达到最低的块大小就越大。（从上到下，曲线越来越平）

Slide 18

原因： 一方面它减少了强制性不命中；（不命中率总体下降） 另一方面，由于增加块大小会减少Cache中块的数目，所以有可能会增加冲突不命中。（不命中率又升高了） 弊端 增加块大小会增加不命中开销

Slide 19

方法二：增加Cache的容量

最直接的方法是增加Cache的容量 缺点: 增加成本 可能增加命中时间 这种方法在片外Cache中用得比较多

Slide 20

方法三：提高相联度

采用相联度超过8的方案的实际意义不大。 2:1Cache经验规则 容量为N的直接映像Cache的不命中率和容量为N/2的两路组相联Cache的不命中率差不多相同。 提高相联度是以增加命中时间为代价。

Slide 21

方法四：伪相联 Cache (列相联 Cache )

伪相联Cache的优点 命中时间小 不命中率低

Slide 22

基本思想及工作原理 在逻辑上把直接映像Cache的空间上下平分为两个区。 对于任何一次访问，伪相联Cache先按直接映像Cache的方式去处理。 若命中，则其访问过程与直接映像Cache的情况一样。 若不命中，则再到另一区相应的位置去查找。 若找到，则发生了伪命中. 否则就只好访问下一级存储器。

Slide 23

缺点 ：多种命中时间 -- 快速命中与慢速命中 要保证绝大多数命中都是快速命中。

Slide 24

方法五：硬件预取

指令和数据都可以预取 预取内容既可放入Cache，也可放在外缓冲器中。 例如：指令流缓冲器 指令预取通常由Cache之外的硬件完成

Slide 25

预取应利用存储器的空闲带宽，不能影响对正常不命中的处理，否则可能会降低性能。

预取效果 Jouppi的研究结果 指令预取 (4KB，直接映像Cache，块大小＝16字节) 1个块的指令流缓冲器： 捕获15％～25％的不命中 4个块的指令流缓冲器： 捕获50％ 16个块的指令流缓冲器：捕获72％ 数据预取 (4KB,直接映像Cache) 1个数据流缓冲器，捕获25％的不命中 还可以采用多个数据流缓冲器 Palacharla和Kessler的研究结果 流缓冲器：既能预取指令又能预取数据 对于两个64KB四路组相联Cache来说： 8个流缓冲器能捕获50％～70％的不命中

Slide 26

方法六：编译器控制的预取

主要思想：在编译时加入预取指令，在数据被用到之前发出预取请求。

假定： (1) 使用一个容量为8KB、块大小为16B的直接映象Cache，它采用写回法并且按写分配。 (2) a、b分别为3×100（3行100列）和101×3的双精度浮点数组，每个元素都是8B。当程序开始执行时，这些数据都不在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）首先，判断哪些访问可能会导致数据Cache失效； （2）其次，加入预取指令以减少失效； （3）最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。

Slide 31

按照预取数据所放的位置，可把预取分为两种类型： 寄存器预取：把数据取到寄存器中。 Cache预取：只将数据取到Cache中。

按照预取的处理方式不同，可把预取分为： 故障性预取：在预取时，若出现虚地址故障或违反保护权限，就会发生异常。 非故障性预取：在遇到这种情况时则不会发生异常，因为这时它会放弃预取，转变为空操作。本节假定Cache预取都是非故障性的，也叫做非绑定预取。

Slide 32

在预取数据的同时，处理器应能继续执行。 只有这样，预取才有意义。 非阻塞Cache (非锁定Cache)

编译器控制预取的目的 使执行指令和读取数据能重叠执行。 循环是预取优化的主要对象 不命中开销小时：循环体展开1～2次 不命中开销大时：循环体展开许多次 每次预取需要花费一条指令的开销 保证这种开销不超过预取所带来的收益 编译器可以通过把重点放在那些可能会导致不命中的访问上，使程序避免不必要的预取，从而较大程度地减少平均访存时间。

Slide 33

方法七：编译器优化

基本思想：通过对软件进行优化来降低不命中率。（特色：无需对硬件做任何改动） 程序代码和数据重组 可以重新组织程序而不影响程序的正确性 把一个程序中的过程重新排序，就可能会减少冲突不命中，从而降低指令不命中率。 McFarling研究了如何使用配置文件（profile）来进行这种优化。 把基本块对齐，使得程序的入口点与Cache块的起始位置对齐，就可以减少顺序代码执行时所发生的Cache不命中的可能性。 如果编译器知道一个分支指令很可能会成功转移，那么它就可以通过以下两步来改善空间局部性： 将转移目标处的基本块和紧跟着该分支指令后的基本块进行对调； 把该分支指令换为操作语义相反的分支指令。 数据对存储位置的限制更少，更便于调整顺序。

Slide 34

编译优化技术包括 （1）数组合并 将本来相互独立的多个数组合并成为一个复合数组，以提高访问它们的局部性。 （2）内外循环交换 （3）循环融合 将若干个独立的循环融合为单个的循环。这些循环访问同样的数组，对相同的数据作不同的运算。这样能使得读入Cache的数据在被替换出去之前，能得到反复的使用 。 （4）分块

Slide 40

方法八："牺牲"Cache

基本思想 在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，称为"牺牲"Cache（Victim Cache）。用于存放被替换出去的块(称为牺牲者)，以备重用。 作用 对于减小冲突不命中很有效，特别是对于小容量的直接映像数据Cache，作用尤其明显。 例如项数为4的Victim Cache，能使4KB Cache的冲突不命中减少20%～90%。

Slide 41

1、采用两级Cache

应把Cache做得更快？还是更大？ 答案：二者兼顾，再增加一级Cache 第一级Cache(L1)小而快 第二级Cache(L2)容量大 性能分析 平均访存时间 ＝ 命中时间L1＋不命中率L1×不命中开销L1 不命中开销L1 ＝ 命中时间L2＋不命中率L2×不命中开销L2

Slide 42

平均访存时间 ＝ 命中时间L1＋不命中率L1× （命中时间L2＋不命中率L2×不命中开销L2）

局部不命中率与全局不命中率 局部不命中率＝该级Cache的不命中次数/到达该 级Cache的访问次数 例如：上述式子中的不命中率L2 全局不命中率＝该级Cache的不命中次数/CPU发 出的访存的总次数

Slide 43

全局不命中率L2＝不命中率L1×不命中率L2 评价第二级Cache时，应使用全局不命中率这个指标。它指出了在CPU发出的访存中，究竟有多大比例是穿过各级Cache，最终到达存储器的。 采用两级Cache时，每条指令的平均访存停顿时间： 每条指令的平均访存停顿时间 ＝ 每条指令的平均不命中次数L1×命中时间L2＋ 每条指令的平均不命中次数L2×不命中开销L2

Slide 44

例 考虑某一两级Cache：第一级Cache为L1，第二级Cache为L2。 （1）假设在1000次访存中，L1的不命中是40次，L2的不命中是20次。求各种局部不命中率和全局不命中率。 （2）假设L2的命中时间是10个时钟周期，L2的不命中开销是100时钟周期，L1的命中时间是1个时钟周期，平均每条指令访存1.5次，不考虑写操作的影响。问：平均访存时间是多少？每条指令的平均停顿时间是多少个时钟周期？

Slide 48

例 给出有关第二级Cache的以下数据： （1）对于直接映像，命中时间L2 ＝ 10个时钟周期 （2）两路组相联使命中时间增加0.1个时钟周期，即为10.1个时钟周期。 （3） 对于直接映像，局部不命中率L2 ＝ 25% （4） 对于两路组相联，局部不命中率L2 ＝ 20% （5） 不命中开销L2 ＝ 50个时钟周期 试问第二级Cache的相联度对不命中开销的影响如何？

Slide 49

解 对一个直接映像的第二级Cache来说，第一级Cache的不命中开销为： 不命中开销直接映像，L1 ＝ 10＋25%×50 ＝ 22.5 个时钟周期 对于两路组相联第二级Cache来说，命中时间增加了10%（0.1）个时钟周期，故第一级Cache的不命中开销为： 不命中开销两路组相联，L1 ＝ 10.1＋20%×50 ＝ 20.1 个时钟周期 把第二级Cache的命中时间取整，得10或11，则： 不命中开销两路组相联，L1 ＝ 10＋20%×50 ＝ 20.0 个时钟周期 不命中开销两路组相联，L1 ＝ 11＋20%×50 ＝ 21.0 个时钟周期 故对于第二级Cache来说，两路组相联优于直接映像。

Slide 50

块大小 第二级Cache可采用较大的块 如 64、128、256字节 为减少平均访存时间，可以让容量较小的第一级Cache采用较小的块，而让容量较大的第二级Cache采用较大的块。 多级包容性 需要考虑的另一个问题： 第一级Cache中的数据是否总是同时存在于第 二级Cache中。

Slide 51

方法二：让读不命中优先于写

Cache中的写缓冲器导致对存储器访问的复杂化 在读不命中时，所读单元的最新值有可能还在写缓冲器中，尚未写入主存。

解决问题的方法(读不命中的处理) 推迟对读不命中的处理 （缺点：读不命中的开销增加） 检查写缓冲器中的内容 在写回法Cache中，也可采用写缓冲器。

Slide 52-53

方法三：写缓冲合并

提高写缓冲器的效率 写直达Cache 依靠写缓冲来减少对下一级存储器写操作的时间。 如果写缓冲器为空，就把数据和相应地址写入该缓冲器。 从CPU的角度来看，该写操作就算是完成了。 如果写缓冲器中已经有了待写入的数据，就要把这次的写入地址与写缓冲器中已有的所有地址进行比较，看是否有匹配的项。如果有地址匹配而对应的位置又是空闲的，就把这次要写入的数据与该项合并。这就叫写缓冲合并。 如果写缓冲器满且又没有能进行写合并的项，就必须等待。

  提高了写缓冲器的空间利用率，而且还能减少因写缓冲

器满而要进行的等待时间。

Slide 55

方法四：请求字处理技术

请求字 从下一级存储器调入Cache的块中，只有一个字 是立即需要的。这个字称为请求字。 应尽早把请求字发送给CPU 尽早重启动：调块时，从块的起始位置开始读起。一旦请求字到达，就立即发送给CPU，让CPU继续执行。 请求字优先：调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU。

Slide 56

这种技术在以下情况下效果不大： Cache块较小 下一条指令正好访问同一Cache块的另一部分

Slide 57

方法五：非阻塞Cache技术

非阻塞Cache：Cache不命中时仍允许CPU进行其他的命中访问。即允许"不命中下命中"。 进一步提高性能： "多重不命中下命中" "不命中下不命中" （存储器必须能够处理多个不命中） 可以同时处理的不命中次数越多，所能带来的性能上的提高就越大。（不命中次数越多越好？）

Slide 58

模拟研究 数据Cache的平均存储器等待时间（以周期为单位）与阻塞Cache平均存储器等待时间的比值 测试条件：8K直接映像Cache，块大小为32字节 测试程序：SPEC92（14个浮点程序，4个整数程序） 结果表明 在重叠不命中个数为1、2和64的情况下浮点程序的平均比值分别为：76%、51%和39% 整数程序的平均比值则分别为：81%、78%和78% 对于整数程序来说，重叠次数对性能提高影响不大，简单的"一次不命中下命中"就几乎可以得到所有的好处。

Slide 60

方法一：使用小容量、结构简单的Cache

硬件越简单，速度就越快； 应使Cache足够小，以便可以与CPU一起放在同一块芯片上。 某些设计采用了一种折衷方案： 把Cache的标识放在片内，而把Cache的数据存储器放在片外。

Slide 61

物理Cache 使用物理地址进行访问的传统Cache。 标识存储器中存放的是物理地址，进行地址检测也是用物理地址。 缺点：地址转换和访问Cache串行进行，访问速度很慢。

Slide 62

虚拟Cache 可以直接用虚拟地址进行访问的Cache。标识存储器中存放的是虚拟地址，进行地址检测用的也是虚拟地址。 优点：在命中时不需要地址转换，省去了地址转换的时间。即使不命中，地址转换和访问Cache也是并行进行的，其速度比物理Cache快很多。

Slide 63

并非都采用虚拟Cache(为什么?) 虚拟Cache的清空问题 解决方法：在地址标识中增加PID字段 (进程标识符) 三种情况下不命中率的比较 单进程，PIDs，清空 PIDs与单进程相比：＋0.3％～＋0.6％ PIDs与清空相比： －0.6％～－4.3% 同义和别名 解决方法：反别名法、页着色

Slide 65

虚拟索引＋物理标识

优点：兼得虚拟Cache和物理Cache的好处 局限性：Cache容量受到限制 (页内位移) Cache容量≤页大小×相联度 举例：IBM3033的Cache 页大小＝4KB 相联度＝16

另一种方法：硬件散列变换

Slide 66

方法三：Cache访问流水化

对第一级Cache的访问按流水方式组织 访问Cache需要多个时钟周期才可以完成 例如 Pentium访问指令Cache需要一个时钟周期 Pentium Pro到Pentium Ⅲ需要两个时钟周期 Pentium 4 则需要4个时钟周期

Slide 67

方法四：踪迹Cache

开发指令级并行性所遇到的一个挑战是： 当要每个时钟周期流出超过4条指令时，要提供足够多条彼此互不相关的指令是很困难的。

一个解决方法：采用踪迹 Cache 存放CPU所执行的动态指令序列，包含了由分支预测展开的指令，该分支预测是否正确需要在取到该指令时进行确认。

优缺点 地址映像机制复杂； 相同的指令序列有可能被当作条件分支的不同选择而重复存放； 能够提高指令Cache的空间利用率。

Slide 69

Cache优化技术总结 "＋"号：表示改进了相应指标。 "－"号：表示它使该指标变差。 空格栏：表示它对该指标无影响。 复杂性：0表示最容易，3表示最复杂。

---

谭婧炜佳老师（原第2章 缓存优化）

Slide 4

存储体系基础知识复习

Cache基本知识： 映像方式：直接映像，全相联，组相连 替换算法：LRU，随机 写策略： 写命中：写直达，写回 写不命中：写分配，写不分配

Slide 5

存储系统的基本知识

计算机系统结构设计中关键的问题之一 ： 如何以合理的价格，设计容量和速度都满足计算机系统要求的存储器系统？

人们对这三个指标的要求 容量大、速度快、价格低

三个要求是相互矛盾的 速度越快，每位价格就越高； 容量越大，每位价格就越低； 容量越大，速度越慢。

Slide 6

多级存储层次结构

解决方法：采用多种存储器技术，构成多级存储层次结构。 程序访问的局部性原理：对于绝大多数程序来说，程序所访问的指令和数据在地址上不是均匀分布的，而是相对簇聚的。

程序访问的局部性包含两个方面 时间局部性：程序将要用到的信息很可能就是现在正在使用的信息。 空间局部性：程序将要用到的信息很可能与现在正在使用的信息在存储空间上是相邻的。

Slide 8

多级存储层次结构

假设第i个存储器Mi的访问时间为Ti，容量为Si，平均每位价格为Ci，则 访问时间： T1 < T2 < … < Tn 容量： S1 < S2 < … < Sn 平均每位价格：C1 > C2 > … > Cn 整个存储系统要达到的目标：从CPU来看，该存储系统的速度接近于M1的，而容量和每位价格都接近于Mn的。 存储器越靠近CPU，则CPU对它的访问频度越高，而且最好大多数的访问都能在M1完成。

Slide 10

Cache的映像规则

全相联映像 全相联：主存中的任一块可以被放置到Cache中的任意一个位置。 特点：空间利用率最高，冲突概率最低，实现最复杂。

Slide 11

直接映像 直接映像：主存中的每一块只能被放置到Cache中唯一的一个位置。 （循环分配） 特点：空间利用率最低，冲突概率最高，实现最简单。 对于主存的第i 块，若它映像到Cache的第j 块，则: 　　　　 j＝i mod (M) （M为Cache的块数） 设M=2m，则当表示为二进制数时，j实际上就是i的低m位:

Slide 13

Cache的映像规则

组相联映像 组相联：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。
组相联是直接映像和全相联的一种折中

Slide 15

平均访存时间

仅考虑由M1和M2构成的两级存储层次： M1的参数：S1，T1，C1 M2的参数：S2，T2，C2

平均访存时间 ＝ 命中时间＋不命中率×不命中开销 命中率：CPU访问存储系统时，在M1中找到所需信息的概率

N1 ── 访问M1的次数 N2 ── 访问M2的次数

Slide 16

平均访存时间：

平均访存时间： TA　　　　　＝ HT1＋（1－H）（T1＋TM） 　　　　＝ T1＋（1－H）TM 或 TA ＝ T1＋FTM

分两种情况来考虑CPU的一次访存： 当命中时，访问时间即为T1 当不命中时，情况比较复杂。 不命中时的访问时间为：T2＋TB＋T1＝T1＋TM
TM ＝T2＋TB

不命中开销(miss penalty)TM：从向M2发出访问请求到把整个数据块调入M1中所需的时间。传送一个信息块所需的时间为TB

Slide 17

程序执行时间

CPU时间＝（CPU执行周期数+存储器停顿周期数）× 时钟周期时间 其中： 存储器停顿时钟周期数＝"读"的次数×读不命中率×读不命中开销 ＋"写"的次数×写不命中率×写不命中开销 存储器停顿时钟周期数＝访存次数×不命中率×不命中开销

CPU时间＝（CPU执行周期数+访存次数×不命中率×不命中开销） × 时钟周期时间 =IC×（CPIexecution＋每条指令的平均访存次数×不命中率 ×不命中开销）× 时钟周期时间

Slide 18

例 假设Cache不命中开销为50个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是2.0个时钟周期，访问Cache不命中率为2%，平均每条指令访存1.33次。试分析Cache对性能的影响。

Slide 19

程序执行时间

Cache不命中对于一个CPI较小而时钟频率较高的CPU来说，影响是双重的： CPIexecution越低，固定周期数的Cache不命中开销的相对影响就越大。 在计算CPI时，不命中开销的单位是时钟周期数。因此，即使两台计算机的存储层次完全相同（访问时间相同），时钟频率较高的CPU的不命中开销较大，其CPI中存储器停顿这部分也就较大。 　 因此Cache对于低CPI、高时钟频率的CPU来说更加重要

Slide 26

三种类型的不命中（3C）

强制性不命中(Compulsory miss) 当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性不命中。 (冷启动不命中，首次访问不命中） 容量不命中(Capacity miss ) 如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生不命中。这种不命中称为容量不命中。 冲突不命中(Conflict miss) 在组相联或直接映像Cache中，若太多的块映像到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突不命中。 (碰撞不命中，干扰不命中)

Slide 27

三种类型的不命中（3C）

相联度越高，冲突不命中就越少； 强制性不命中和容量不命中不受相联度的影响； 强制性不命中不受Cache容量的影响，但容量不命中却随着容量的增加而减少。

容量不命中：采用全相联映像+最优替换策略仍失效

Slide 28

降低不命中率的方法

针对三种类型的不命中的直接方法 针对强制不命中 -- 增加块大小 （方法一） 针对容量不命中 -- 增加Cache容量 （方法二） 针对冲突不命中 -- 提高相联度 （方法三）

其他方法 伪相联Cache （方法四） 硬件预取 （方法五） 编译器预取 （方法六） 编译器优化 （方法七） 牺牲Cache （方法八）

Slide 29-30

方法一：增加块大小

不命中率随块大小变化的曲线

对于给定的Cache容量，当块大小增加时，不命中率开始是下降，后来反而上升了。 Cache容量越大，使不命中率达到最低的块大小就越大。（从上到下，曲线越来越平）

请分析：为什么增加块大小可以降低强制不命中？

请思考：为什么不命中率先下降后上升？ 一方面它减少了强制性不命中；（不命中率总体下降） 另一方面，由于增加块大小会减少Cache中块的数目，所以有可能会增加冲突不命中。（不命中率又升高了）

请考虑：增加块大小还可能带来什么不良后果？ 会增加不命中开销

Slide 31

方法二：增加Cache的容量

最直接的方法是增加Cache的容量 缺点: 增加成本 可能增加命中时间 这种方法在片外Cache中用得比较多

Slide 32

方法三：提高相联度

采用相联度超过8的方案的实际意义不大。 2:1Cache经验规则 容量为N的直接映像Cache的不命中率和容量为N/2的两路组相联Cache的不命中率差不多相同。 提高相联度是以增加命中时间为代价。

Slide 33-35

方法四：伪相联 Cache

伪相联Cache的优点 命中时间小 不命中率低

基本思想及工作原理 在逻辑上把直接映像Cache的空间上下平分为两个区。 对于任何一次访问，伪相联Cache先按直接映像Cache的方式去处理。 若命中，则其访问过程与直接映像Cache的情况一样。 若不命中，则再到另一区相应的位置去查找。 若找到，则发生了伪命中。 否则就只好访问下一级存储器。

缺点 ：多种命中时间 -- 快速命中与慢速命中 要保证绝大多数命中都是快速命中。

Slide 36

例 假设当在按直接映象找到的位置处没有发现匹配，而在另一个位置才找到数据（伪命中）需要2个额外的周期。问：当Cache容量分别为2 KB和128 KB时，直接映象、2路组相联和伪相联这三种组织结构中，哪一种速度最快？

Slide 37

解 首先考虑标准的平均访存时间公式： 平均访存时间伪相联 ＝ 命中时间伪相联＋失效率伪相联×失效开销伪相联

由于： 失效率伪相联＝失效率2路 命中时间伪相联＝命中时间1路＋伪命中率伪相联×2

   伪相联查找的命中率等于2路组相联Cache的命中率和直接映象Cache命中率之差。
   伪命中率伪相联  ＝命中率2路－命中率1路
                  ＝（1－失效率2路）－（1－失效率1路）
                  ＝失效率1路－失效率2路

综合上述分析，有： 平均访存时间伪相联＝命中时间1路＋（失效率1路－失效率2路）×2 ＋失效率2路×失效开销1路

Slide 38

将前面表中的数据代入上面的公式，得： 平均访存时间伪相联，2 KB ＝1＋（0.098－0.076）×2＋（0.076×50）＝4.844 对于2 KB Cache，有： 平均访存时间1路 ＝5.90 个时钟 平均访存时间2路 ＝4.90 个时钟

对于128KB的Cache有，可得： 平均访存时间伪相联，128 KB＝1＋（0.010－0.007）×2＋（0.007×50）＝1.356 平均访存时间1路 ＝1.50 个时钟 平均访存时间2路 ＝1.45 个时钟

可见，对于这两种Cache容量，伪相联Cache都是速度最快的。

Slide 39

方法五：硬件预取

指令和数据都可以预取 预取内容既可放入Cache，也可放在外缓冲器中。 例如：指令流缓冲器 指令预取通常由Cache之外的硬件完成 例如：Alpha AXP 21064微处理器在发生指令不命中时取两个块 – 被请求的指令块和顺序的下一指令块。被请求的指令块返回时放入Cache，而预取的指令块放入到缓冲器中。

Slide 40

预取效果

Jouppi的研究结果 指令预取 (4KB，直接映像Cache，块大小＝16字节) 1个块的指令流缓冲器： 捕获15％～25％的不命中 4个块的指令流缓冲器： 捕获50％ 16个块的指令流缓冲器：捕获72％ 数据预取 (4KB,直接映像Cache) 1个数据流缓冲器，捕获25％的不命中 还可以采用多个数据流缓冲器

Palacharla和Kessler的研究结果 流缓冲器：既能预取指令又能预取数据 对于两个64KB四路组相联Cache来说： 8个流缓冲器能捕获50％～70％的不命中

预取应利用存储器的空闲带宽，不能影响对正常不命中的处理，否则可能会降低性能。

Slide 41

方法六：编译器控制的预取

主要思想：在编译时加入预取指令，在数据被用到之前发出预取请求。

假定：(1) 使用一个容量为8 KB、块大小为16 B的直接映象Cache，它采用写回法并且按写分配。 (2) a、b分别为3×100（3行100列）和101×3的双精度浮点数组，每个元素都是8B。当程序开始执行时，这些数据都不在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）首先，判断哪些访问可能会导致数据Cache失效； （2）其次，加入预取指令以减少失效； （3）最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。

Slide 42

分析可能发生哪种失效

假设数组a和b在内存中连续按行存储； 1块16B，无论是a还是b，一块2个元素； 对于数组a，分布在150块中； 对于数组b，分布在152块中； a和b一共302块，少于Cache总块数，因此，不会发生容量失效； 直接映射，按照假定，a和b连续存储，不会发生冲突失效； 只能发生强制失效。

Slide 43-44

根据运算过程分析不命中和命中

数组a: 共150块，失效150次 数组b：i=0时，失效101次；i=1和2时，无失效 一共失效次数：150+101 = 251次

Slide 45

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 ]; } / a失效 7/2 = 4, 两次循环共失效8次 */

总的失效次数＝4+7+4+4 = 19 次

Slide 46

预取分类

按照预取数据所放的位置，可把预取分为两种类型： 寄存器预取：把数据取到寄存器中。 Cache预取：只将数据取到Cache中。

按照预取的处理方式不同，可把预取分为： 故障性预取：在预取时，若出现虚地址故障或违反保护权限，就会发生异常。 非故障性预取：在遇到这种情况时则不会发生异常，因为这时它会放弃预取，转变为空操作。本节假定Cache预取都是非故障性的，也叫做非绑定预取。

Slide 47

编译器控制的预取

在预取数据的同时，处理器应能继续执行。 只有这样，预取才有意义。 非阻塞Cache (非锁定Cache)

编译器控制预取的目的 使执行指令和读取数据能重叠执行。 循环是预取优化的主要对象 不命中开销小时：循环体展开1～2次 不命中开销大时：循环体展开许多次 每次预取需要花费一条指令的开销 保证这种开销不超过预取所带来的收益 编译器可以通过把重点放在那些可能会导致不命中的访问上，使程序避免不必要的预取，从而较大程度地减少平均访存时间。

Slide 48

方法七：编译器优化

基本思想：通过对软件进行优化来降低不命中率。 （特色：无需对硬件做任何改动） 程序代码和数据重组 可以重新组织程序而不影响程序的正确性 把一个程序中的过程重新排序，就可能会减少冲突不命中，从而降低指令不命中率。 把基本块对齐，使得程序的入口点与Cache块的起始位置对齐，就可以减少顺序代码执行时所发生的Cache不命中的可能性。 如果编译器知道一个分支指令很可能会成功转移，那么它就可以通过以下两步来改善空间局部性： 将转移目标处的基本块和紧跟着该分支指令后的基本块进行对调； 把该分支指令换为操作语义相反的分支指令。 数据对存储位置的限制更少，更便于调整顺序。

Slide 49

编译优化技术包括

数组合并 内外循环交换 循环融合 分块

Slide 50-52

（1）数组合并 基本思想: 将本来相互独立的多个数组合并成为一个复合数组，以提高访问它们的局部性。

举例： /* 修改前 */ int x[100]; int y[100];

/* 修改后 */ struct merge{ int x; int y; }; struct merge merged_array[100];

（2）内外循环交换 基本思想: 提高访问的局部性

（3）循环融合 基本思想: 将若干个独立的循环融合为单个的循环。这些循环访问同样的数组，对相同的数据作不同的运算。这样能使得读入Cache的数据在被替换出去之前，能得到反复的使用 。

Slide 53-54

（4）分块 基本思想: 把对数组的整行或整列访问改为按块进行，尽量集中访问，减少替换，提高访问的局部性。

最坏的情况：所有的访问都不命中 不命中次数：2N3＋N2

/* 修改后 */ for （ jj = 0; jj < N; jj = jj+B ） for （ kk = 0; kk < N; kk = kk+B ） for （ i = 0; i < N; i =i+1 ） for （ j = jj; j < min（jj+B, N）; j = j+1 ） { r = 0; for （ k = kk; k < min（kk+B, N）; k = k+1） { r = r + y[ i ][ k ] * z[ k ][ j ]; } x[ i ][ j ] = x[ i ][ j ] + r; }

Slide 55

方法八："牺牲"Cache

一种能减少冲突不命中次数而又不影响时钟频率的方法。 基本思想：在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，称为"牺牲"Cache（Victim Cache）。用于存放被替换出去的块(称为牺牲者)，以备重用。 作用： 对于减小冲突不命中很有效，特 别是对于小容量的直接映像数据 Cache，作用尤其明显。 例如项数为4的Victim Cache，能 使4KB Cache的冲突不命中减少 20%～90%

Slide 57

方法一：两级Cache

应把Cache做得更快？还是更大？ 答案：二者兼顾，再增加一级Cache 第一级Cache(L1)小而快 第二级Cache(L2)容量大 性能分析 平均访存时间 ＝ 命中时间L1＋不命中率L1×不命中开销L1 不命中开销L1 ＝ 命中时间L2＋不命中率L2×不命中开销L2

Slide 58

局部不命中率与全局不命中率

局部不命中率＝该级Cache的不命中次数/到达该级Cache的访问次数 例如：上述式子中的不命中率L2 全局不命中率＝该级Cache的不命中次数/CPU发出的访存的总次数 全局不命中率L2＝不命中率L1×不命中率L2 全局不命中率比局部不命中率更有意义，它指出了在CPU发出的访存中，究竟有多大比例是穿过各级Cache，最终到达存储器的。 采用两级Cache时，每条指令的平均访存停顿时间： 每条指令的平均访存停顿时间 ＝ 每条指令的平均不命中次数L1×命中时间L2＋每条指令的平均不命中次数L2×不命中开销L2

Slide 60

例 考虑某一两级Cache：第一级Cache为L1，第二级Cache为L2。 （1）假设在1000次访存中，L1的不命中是40次，L2的不命中是20次。求各种局部不命中率和全局不命中率。 （2）假设L2的命中时间是10个时钟周期，L2的不命中开销是100时钟周期，L1的命中时间是1个时钟周期，平均每条指令访存1.5次，不考虑写操作的影响。问：平均访存时间是多少？每条指令的平均停顿时间是多少个时钟周期？

Slide 65

例 给出有关第二级Cache的以下数据： （1）对于直接映像，命中时间L2 ＝ 10个时钟周期 （2）两路组相联使命中时间增加0.1个时钟周期，即为10.1个时钟周期。 （3）对于直接映像，局部不命中率L2 ＝ 25% （4）对于两路组相联，局部不命中率L2 ＝ 20% （5）不命中开销L2 ＝ 50个时钟周期 试问第二级Cache的相联度对不命中开销的影响如何？

Slide 67

块大小 第二级Cache可采用较大的块，如 64、128、256字节 为减少平均访存时间，可以让容量较小的第一级Cache采用较小的块，而让容量较大的第二级Cache采用较大的块。

需要考虑的另一个问题：多级包容性 第一级Cache中的数据是否总是同时存在于第二级Cache中。如果是，就说第二级Cache是具有多级包容性的。

Slide 68

方法二：让读不命中优先于写

Cache中的写缓冲器导致对存储器访问的复杂化 在读不命中时，所读单元的最新值有可能还在写缓冲器中，尚未写入主存。

解决问题的方法(读不命中的处理) 推迟对读不命中的处理，直到写缓冲器清空 （缺点：读不命中的开销增加） 检查写缓冲器中的内容，若无相同，且存储器可用，继续处理读不命中（常用方案）

Slide 69-70

方法三：写缓冲合并

提高写缓冲器的效率：减少对下一级存储器写操作的时间。 如果写缓冲器为空，就把数据和相应地址写入该缓冲器。从CPU的角度来看，该写操作就算是完成了。 如果写缓冲器中已经有了待写入的数据，就要把这次的写入地址与写缓冲器中已有的所有地址进行比较，看是否有匹配的项。如果有地址匹配而对应的位置又是空闲的，就把这次要写入的数据与该项合并。这就叫写缓冲合并。 如果写缓冲器满且又没有能进行写合并的项，就必须等待。

作用 连续写入多个字的速度快于每次只写入一个字的操作； 提高了写缓冲器的空间利用率，减少因写缓冲器满而要进行的等待时间。

例如 写缓冲区有4项，每项4个64位的字。（每个缓冲区和Cache块大小相同）

Slide 71

方法四：请求字处理技术

请求字 从下一级存储器调入Cache的块中，只有一个字是立即需要的。这个字称为请求字。 应尽早把请求字发送给CPU 尽早重启动：请求字没有到达时，CPU处于等待状态。一旦请求字到达，立即送给CPU，让等待的CPU尽早重启动，继续执行。 请求字优先：调块时，让存储器首先提供CPU所要的请求字。请求字一旦到达，就立即送给CPU，让CPU继续执行，同时从存储器调入该块的其余部分。 在以下情况下，用不用差别不大 Cache块较小 下一条指令正好访问同一Cache块的另一部分

Slide 72

方法五：非阻塞Cache技术

非阻塞Cache：采用记分牌或者Tomasulo类控制方式，允许指令乱序执行，CPU无需在Cache不命中时停顿； 允许多次不命中，进一步提高性能； 可以同时处理的不命中次数越多，所能带来的性能上的提高就越大。

Slide 73

问题：重叠不命中次数越多越好？

模拟研究 非阻塞数据Cache的平均存储器等待时间（以周期为单位）与阻塞Cache平均存储器等待时间的比值。 测试条件：8K直接映像Cache，块大小为32字节 测试程序：SPEC92（14个浮点程序，4个整数程序） 结果表明：在重叠不命中个数为1、2和64的情况下 浮点程序的平均等待时间比值分别为：76%、51%和39% 整数程序的平均等待时间比值则分别为：81%、78%和78%

对于整数程序来说，重叠次数对性能提高影响不大，简单的"一次不命中下命中"就几乎可以得到所有的好处。

Slide 75

命中时间

命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是Cache的访问时间限制了处理器的时钟频率。

Slide 76

方法一：使用小容量、结构简单的Cache

硬件越简单，速度就越快； 应使Cache足够小，以便可以与CPU一起放在同一块芯片上。 某些设计采用了一种折衷方案： 把Cache的标识放在片内，而把Cache的数据存储器放在片外。 采用结构简单的Cache，比如直接映像Cache。 标识检测和数据传送可以同时进行

Slide 77

方法二：虚拟Cache

物理Cache 使用物理地址进行访问的传统Cache。 标识存储器中存放的是物理地址，进行地址检测也是用物理地址。 缺点：地址转换和访问Cache串行进行，访问速度很慢。

Slide 78-79

虚拟Cache

虚拟Cache 可以直接用虚拟地址进行访问的Cache。标识存储器中存放的是虚拟地址，进行地址检测用的也是虚拟地址。 优点：在命中时不需要地址转换，省去了地址转换的时间。即使不命中，地址转换和访问Cache也是并行进行的，其速度比物理Cache快很多。

并非都采用虚拟Cache 清空问题：由于新进程的虚拟地址可能与原进程相同； 解决方法：在地址标识中增加PID(进程标识符)字段； PID相关问题：为了减少位数，PID可能循环使用，所以也可能存在多个进程使用同一个PID，所以此时也需要清空Cache。

同义（synonym）或别名（alias）问题：同一个数据在虚拟Cache中存在两个副本 操作系统或用户对同一个物理地址采用两种以上的不同形式的虚拟地址来访问 不允许存在，否则会发生错误

Slide 80

方法二：虚拟Cache

虚拟索引＋物理标识 原理：使用虚地址中的页内位移生成Cache索引；虚实转换后的实页地址作为标志tag 优点：兼得虚拟Cache和物理Cache的好处 局限性：Cache容量受到限制 Cache容量≤页大小×相联度 举例：IBM3033的Cache 页大小＝4KB 相联度＝16

Cache容量＝16×4KB＝64KB

Slide 81

方法三：Cache访问流水化

对第一级Cache的访问按流水方式组织 访问Cache需要多个时钟周期才可以完成 例如 Pentium访问指令Cache需要一个时钟周期 Pentium Pro到Pentium Ⅲ需要两个时钟周期 Pentium 4 则需要4个时钟周期

Slide 82

方法四：踪迹Cache

开发指令级并行性所遇到的一个挑战是： 当要每个时钟周期流出超过4条指令时，要提供足够多条彼此互不相关的指令是很困难的。

一个解决方法：采用踪迹 Cache 存放CPU所执行的动态指令序列，包含了由分支预测展开的指令，该分支预测是否正确需要在取到该指令时进行确认。 普通Cache存放静态指令序列

优缺点 地址映像机制复杂； 相同的指令序列有可能被当作条件分支的不同选择而重复存放； 能够提高指令Cache的空间利用率。

Slide 85-86

Cache优化技术总结 "＋"号：表示改进了相应指标。 "－"号：表示它使该指标变差。 空格栏：表示它对该指标无影响。复杂性：0表示最容易，3表示最复杂。