我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019跑狗图高清彩图 > 执行开销 >

失效开销( 时钟周期) cache 容量ppt

归档日期:08-15       文本归类:执行开销      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  5.4.3 请求字处理技术 1. 请求字 从下一级存储器调入Cache的块中,只有一个字是立即需要的。这个字称为请求字。 2. 应尽早把请求字发送给CPU ◆ 尽早重启动:调块时,从块的起始位置开始读起。一旦请求字到达,就立即发送给 CPU,让CPU继续执行。 ◆ 请求字优先:调块时,从请求字所在的位置读起。这样,第一个读出的字便是请求字。将之立即发送给CPU。 5.4 减少Cache失效开销 3. 这种技术在以下情况下效果不大: ◆ Cache块较小 ◆ 下一条指令正好访问同一Cache块的另一部分。 5.4 减少Cache失效开销 5.4.4 非阻塞Cache技术 1. 非阻塞Cache:Cache失效时仍允许CPU进行 其它的命中访问。即允许“失效下命中” 2. 进一步提高性能:“多重失效下命中”, “失效下失效” (存储器必须能够处理多个失效) 3. 重叠失效个数对平均访问时间的影响 5.4 减少Cache失效开销 非阻塞Cache平均存储器等待时间与阻塞Cache的比值 1 2 浮点程序 76% 51% 64 39% 整数程序 81% 78% 78% 重叠失效个数 5.4 减少Cache失效开销 对于图5.18所描述的Cache,在两路组相联和 “一次失效下命中”这两种措施中,哪一种对浮 点程序更重要?对整数程序的情况如何? 假设8KB数据Cache的平均失效率为: 对于浮点程序,直接映象Cache为11.4%,两路 组相联Cache为10.7%; 对于整数程序,直接映象Cache为7.4%,两路 组相联Cache为6.0%。并且假设平均存储器等待时 间是失效率和失效开销的积,失效开销为16个时钟 周期。 例 5.11 5.4 减少Cache失效开销 对于浮点程序,平均存储器等待时间为: 失效率直接映象×失效开销=11.4%×16=1.82 失效率两路组相联×失效开销=10.7%×16=1.71 1.71/1.82=0.94 对于整数程序,平均存储器等待时间为: 失效率直接映象×失效开销=7.4 %×16=1.18 失效率两路组相联×失效开销=6.0 %×16 =0.96 0.96/1.18=0.81 结论: 对浮点运算采用“一次失效下命中”措施比采用“两路组相联”技术更有效. 解: 5.4 减少Cache失效开销 5.4.5 两级Cache 1. 应把Cache做得更快?还是更大? 答案:二者兼顾,再增加一级Cache ◆ 第一级Cache(L1)小而快 ◆ 第二级Cache(L2)容量大 2. 性能分析 平均访问时间 =命中时间L1+失效率L1×失效开销L1 =命中时间L1+失效率L1× (命中时间L2+失效率L2×失效开销L2) 5.4 减少Cache失效开销 3. 局部失效率与全局失效率 局部失效率=该级Cache的失效次数/到达 该级Cache的访问次数 全局失效率=该级Cache的失效次数/CPU 发出的访存的总次数 全局失效率L2=失效率L1×失效率L2 局部失效率一般不能反映对提高系统实际运行性能所发挥的作用,因此评价第二级Cache时,一般使用全局失效率这个指标。它指出了在CPU发出的访存中,究竟有多大比例是穿过各级Cache,最终到达存储器的。 5.4 减少Cache失效开销 5.4 减少Cache失效开销 例5.12 假设在1000次访存中,第一级Cache失效40次, 第二级Cache失效20次。试问:在这种情况下,该Cache系统的局部失效率和全局失效率各是多少? 解 第一级Cache的失效率(全局和局部)是 40/1000, 即4%; 第二级Cache的局部失效率是20/40,即50%; 第二级Cache的全局失效率是20/1000,即2%。 4. 当第二级Cache比第一级Cache大得多时,两 级Cache的全局失效率和第二级Cache相同的 单级Cache的失效率非常接近。 5.4 减少Cache失效开销 5. 第二级Cache的参数 第二级Cache不会影响CPU的时钟频率, 因此其设计有更大的考虑空间。 两个问题: ◆ 能否降低CPI中的平均访存时间部分? ◆ 成本是多少? (1) 容量 第二级Cache的容量一般比第一级的 大许多,如512KB 5.4 减少Cache失效开销 (2) 相联度 第二级Cache可采用较高的相联度或伪相联方法 例5.13 给出有关第二级Cache的以下数据: ⑴ 两路组相联使命中时间增加10%×CPU时钟周期 ⑵ 对于直接映象,命中时间L2=10个时钟周期 ⑶ 对于直接映象,局部失效率L2=25% ⑷ 对于两路组相联,局部失效率L2=20% ⑸ 失效开销L2=50个时钟周期 试问第二级Cache的相联度对失效开销的影响如何? 5.4 减少Cache失效开销 解: 对于一个直接映象的第二级Cache来说,第一级Cache的失效开销为: 失效开销直接映象,L1 =10+25%×50=22.5个时钟周期 对于两路组相联第二级Cache来说,命中时间增加了10%(0.1)个时钟周期,故第一级Cache的失效开销为: 失效开销两路组相联,L1 =10.1+20%×50=20.1个时钟周期 故对于第二级Cache来说,两路组相联优于直接映象。 5.4 减少Cache失效开销 (3) 块大小 第二级Cache可采用较大的块, 如 64、128、256字节。 为减少平均访存时间,可以让容量较小 一的第一级Cache采用较小的块,而让容量较大的第二级Cache采用较大的块。 (4) 多级包容性 需要考虑的另一个问题: 第一级Cache中的数据是否总是同时存在于第二级Cache中。 5.4 减少Cache失效开销 5.5 减少命中时间 2. 应使Cache足够小,以便可以与CPU一起放 在同一块芯片上。(某些设计采用了一种折中方案: 把Cache的标识放在片内,而把Cache的数据存储器放在片外) 命中时间直接影响到处理器的时钟频率。在 当今的许多计算机中,往往是Cache的访问时间 限制了处理器的时钟频率。 1. 硬件越简单,速度就越快; 5.5.1 容量小、结构简单的Cache 1. 虚拟Cache 访问Cache的索引以及Cache中的标识都是虚拟地址(一部分)。 2. 并非人人都采用虚拟Cache 原因一:不同进程虚地址空间的相同。 3. 解决方法: (1)进程切换时清空虚拟Cache。 (2)在地址标识中增加PID字段(进程标识符)。 三种情况下失效率的比较: 单进程,PIDs,清空 PIDs与单进程相比:+0.3%~+0.6% PIDs与清空相比: -0.6%~-4.3% 5.5.2 虚拟Cache 5.5 减少命中时间 故: 平均访存时间伪相联 =命中时间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,对于2KB Cache, 可得: 平均访存时间1路 =5.90 个时钟 平均访存时间2路 =4.90 个时钟 对于128KB的Cache有,可得: 平均访存时间1路 =1.50 个时钟 平均访存时间2路 =1.45 个时钟 可见,对于这两种Cache容量,伪相联Cache 都是速度最快的。 缺点:多种命中时间 5.3 降低Cache失效率的方法 5.3.6 硬件预取技术 依据:空间局部性 思想:在Cache访问失效时,不但从内存中取入对应的块,而且将它的邻近块(通常为后继块)取入一个速度快于主存的缓冲器中,这样当对后继块的访问发生时,可通过访问该缓冲器进行块替换。 1. 指令和数据都可以预取 2. 预取内容既可放入Cache,也可放在外缓冲器 (速度快于主存)中 例如:指令流缓冲器 5.3 降低Cache失效率的方法 3. 预取效果 (1) Jouppi的研究结果 ◆ 指令预取:(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.7 Alpha AXP 21064采用指令预取技术,其实际 失效率是多少?若不采用指令预取技术,Alpha APX 21064的指令Cache必须为多大才能保持平均访 存时间不变? 解: 假设从预取缓冲器中找到所需指令(并进行替换)需多花1个时钟周期。 平均访存时间预取 =命中时间+失效率×预取命中率×1 +失效率×(1-预取命中率)×失效开销 5.3 降低Cache失效率的方法 假设: 预取命中率=25% 命中时间=1 个时钟周期 失效开销=50个时钟周期 5.3 降低Cache失效率的方法 由表5-4可知, 8KB指令Cache的失效率=1.10% 平均访存时间预取 =1+(1.10 %×25 %×1)+ (1.10 %×(1-25 %)×50) =1+0.00275+0.4125 =1.415 由公式: 平均访问时间=命中时间+失效率×失效开销 可得相应的失效率为: 失效率=(平均访问时间-命中时间)/失效开销 =(1.451-1)/50=0.83% 8KB Cache 带预取的 8kB Cache 失效率 1.10% 0.83% 16KB Cache 0.64% 关键:预取应建立在存储器的空闲频带 5.3 降低Cache失效率的方法 5.3.7 由编译器控制的预取 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) 失效情况 数组a 数组b 总的失效次数=251次 (3) 改进后的程序(设预取的开销比较大,需提 前 7 次循环进行) 5.3 降低Cache失效率的方法 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失效率的方法 失效情况 总的失效次数=(7+4)+4+4=19次 5.3 降低Cache失效率的方法 例 5.9 在以下条件下,计算例5.8中所节约的时间: (1) 忽略指令Cache失效,并假设数据Cache无冲突失效和容量失效。 (2) 假设预取可以被重叠或与Cache失效重叠执行,从而能以最大的存储带宽传送数据。 (3) 不考虑Cache失效时,修改前的循环每7个时钟周期循环一次。修改后的程序中,第一个预取循环每9个时钟周期循环一次,而第二个预取循环每8个时钟周期循环一次(包括外层for循环的开销)。 (4) 一次失效需50个时钟周期。 5.3 降低Cache失效率的方法 解: 修改前: 循环时间 =300×7 =2100 总失效开销=251×50=12550 总运行时间=2100+12550=14650 5.3 降低Cache失效率的方法 修改后: 循环时间=100×9+200×8=2500 总失效时间=19×50=950 总运行时间=2500+950=3450 加速比=14650/3450=4.2 5.3.8 编译器优化 2KB Cache: 降低50% 8KB Cache:降低75% 1. 基本思想 在编译时,对程序中的指令和数据进行重新组织,以降低Cache失效率。 2. McFaring 发现:通过对指令进行重新排序,可有效地降低指令Cache的失效率。 5.3 降低Cache失效率的方法 3. 数据对存储位置的限制比指令的少,因此更便于优化。通过把数据重新组织,使得在一块数 据被从Cache替换出去之前,能最大限度利用其中的数据(访问次数最多) (1) 数据合并 举例: /* 修改前 */ int val [SIZE]; int key [SIZE]; 5.3 降低Cache失效率的方法 (2) 内外循环交换 举例: /* 修改前 */ for (j=0 ;j100 ;j=j+1) for (i=0 ;i5000 ;i=i+1) x[i][j]=2*x[i][j]; /* 修改后 */ struct merge { int val ; int key ; } ; struct merge merged_array[size]; 5.3 降低Cache失效率的方法 (3) 循环融合 举例: /* 修改前 */ for (i=0 ; iN ;i=i+1) for (j=0 ; jN ; j=j+1) a[i][j]=1/b[i][j]*c[i][j]; /* 修改后 */ for (i=0 ;i100 ;i=i+1) for (j=0 ;j 000 ;j=j+1) x[i][j]=2*x[i][j]; 5.3 降低Cache失效率的方法 /* 修改后 */ for (i=0 ;i N ;i=i+1) for (j=0 ;j N ;j=j+1) { a[i][j]=1/b[i][j]*c[i][j]; d[i][j]=a[i][j]+c[i][j]; } for (i=0 ;iN ;i=i+1) for (j=0 ; jN ;j=j+1) d[i][j]=a[i][j]+c[i][j]; (4)分块 把对数组的整行或整列访问改为按块进行。 5.3 降低Cache失效率的方法 举例: /* 修改前 */ 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; } 5.3 降低Cache失效率的方法 最坏情况下失效次数: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-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; } 失效次数:2N3/B + N2 5.3 降低Cache失效率的方法 5.4.1 让读失效优先于写 5.4 减少Cache失效开销 Cache中的写缓冲器导致对存储器访问的复杂化: 写缓冲器进行的写入操作是滞后进行的,所以该缓冲器也被称为后行写数缓冲器。 例5.10 考虑以下指令序列(写直达、直接映像): SW R3, 512(R0) ;M[512]←R3 (Cache索引为0) LW R1, 1024(R0) ;R1←M[1024] (Cache索引为0) LW R2, 512(R0) ;R2←M[512] (Cache索引为0) 5.4 减少Cache失效开销 2. 解决问题的方法(读失效的处理) ◆ 推迟对读失效的处理 (缺点:读失效的开销增加,如50%) ◆ 检查写缓冲器中的内容 3. 在写回法Cache中,如采用写缓冲器,也可以采用类似方法(检查写缓冲器中的内容) 5.4.2写缓冲合并 5.4 减少Cache失效开销 提高写缓冲器的效率 写直达Cache 依靠写缓冲来减少对下一级存储器写操作的时间。 5.4 减少Cache失效开销 如果写缓冲器为空,就把数据和相应地址写入该缓冲器。 从CPU的角度来看,该写操作就算完成了。 如果写缓冲器中已经有了待写入的数据,就要把这次的写入地址与写缓冲器中已有的所有地址进行比较,看是否有匹配的项。如果有地址匹配而对应的位置又是空闲的,就把这次要写入的数据与该项合并。这就叫写缓冲合并。 如果写缓冲器满且又没有能进行写合并的项,就必须等待。 提高了写缓冲器的空间利用率,而且还能减少因写缓冲器满而要进行的等待时间。 例 考虑两种不同组织结构的Cache:直接映象Cache和两路组相联Cache,试问它们对CPU的性能有何影响?分析时用以下假设: (1)理想Cache(命中率为100%)情况下CPI为2.0,时钟周期为 2ns,平均每条指令访存1.3 次。 (2)两种Cache的容量均为 64KB, 块大小 32 字节 (3)对于组相联Cache,CPU的时钟周期增加到原来的1.1 倍 (4)失效开销都是70ns (5)命中时间为 1 个时钟周期,64KB直接映象Cache的失效率为 1.4%, 64KB两路组相联Cache的失效率为 1.0% 5.2 Cache基本知识 解:平均访存时间 = 命中时间+失效率×失效开销 平均访存时间直接 =2.0+(0.014×70)=2.98ns 平均访存时间组相联=2.0×1.10 +(0.010×70) = 2.90ns CPU时间=IC×[CPIexe+访存次数/指令数× 失效率×失效开销]×时钟周期时间 =IC×[CPIexe×时钟周期时间 +访存次数/指令数×失效率×失效开销 ×时钟周期时间] 5.2 Cache基本知识 CPU时间直接 =IC×(2.0×2+(1.3×0.014×70)) =5.27×IC CPU时间组相联=IC×(2.0×2×1.10 +(1.3×0.010×70)) =5.31×IC 5.2 Cache基本知识 平均访存时间=命中时间+失效率×失效开销 可以从三个方面改进Cache的性能: (1) 降低失效率 (2) 减少失效开销 (3) 减少Cache命中时间 5.2.7 改进 Cache 性能 5.2 Cache基本知识 8 种用于降低失效率 5 种用于减少失效开销 4 种用于减少命中时间 5.2 Cache基本知识 下面介绍 17 种 Cache 优化技术 (1) 强制性失效(Compulsory miss) 当第一次访问一个块时,该块不在Cache 中,需从下一级存储器中调入Cache,这就是强制性失效。 (冷启动失效,首次访问失效。) (2) 容量失效(Capacity miss ) 如果程序执行时所需的块不能全部调入 Cache 中,则当某些块被替换后,若又重新被访问,就会发生失效。这种失效称为容量失效。 5.3 降低Cache失效率的方法 1. 三种失效(3C) (3) 冲突失效(Conflict miss) 在组相联或直接映象Cache中,若太多的块映象到同一组(块)中,则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置),然后又被重新访问的情况。这就是发生了冲突失效。 (碰撞失效,干扰失效) 5.3 降低Cache失效率的方法 2. 三种失效所占的比例 (SPEC92) 5.3 降低Cache失效率的方法 5.3 降低Cache失效率的方法 可以看出: (1) 相联度越高,冲突失效就越少; (2) 强制性失效和容量失效不受相联度的影响; (3) 强制性失效不受 Cache 容量的影响,但容 量失效却随着容量的增加而减少; (4) 表中的数据符合 2:1 的 Cache 经验规则,即 大小为 N 的直接映象Cache的失效率约等于 大小为N/2 的两路组相联Cache的失效率。 5.3 降低Cache失效率的方法 强制性失效:增加块大小,预取 (本身很少) 容量失效:增加容量 (抖动现象) 冲突失效:提高相联度 (理想情况:全相联) 3. 减少三种失效的方法 4. 许多降低失效率的方法会增加命中时间或失效开销 5.3 降低Cache失效率的方法 5.3.1 增加Cache块大小 5.3 降低Cache失效率的方法 5.3 降低Cache失效率的方法 各种块大小情况下Cache的失效率 0.49% 1.15% 3.29% 9.51% 22.01% 256 0.49% 1.02% 2.77% 7.78% 16.64% 128 0.51% 1.06% 2.64% 7.00% 13.76% 64 0.70% 1.35% 2.87% 7.24% 13.34% 32 1.09% 2.04% 3.94% 8.57% 15.05% 16 256K 64K 16K 4K 1K Cache容量(字节) 块大小 (字节) 2. 增加块大小会增加失效开销 1. 失效率与块大小的关系 (1) 对于给定的Cache容量,当块大小增加 失效率开始是下降,后来反而上升了; (2) Cache容量越大,使失效率达到最低的 块大小就越大。 3. 例题 5.3 降低Cache失效率的方法 例 假定存储系统在延迟 40 个时钟周期后,每 2 个时钟周期能送出 16 个字节。即:经过 42 个时钟周期,它可提供 16 个字节;经过 44 个时钟周期,可提供 32 个字节;依此类推。试问对于 表5-6 中列出的各种容量的Cache,在块大小分别为多少时,平均访存时间最小? 解:平均访存时间为: 平均访存时间=命中时间+失效率×失效开销 5.3 降低Cache失效率的方法 假设命中时间与块大小无关,为1个时钟,那么对于一个块大小为16字节,容量为1KB的Cache来说: 平均访存时间 = 1+(15.05 %×42) = 7.321 个时钟周期 而对于块大小为256B的大小为256KB的Cache来说,平均访存时间为: 平均访存时间 = 1+(0.49 %×72) = 1.353 个时钟周期 表5.7 列出了在这两种极端情况之间的各种块大小和各种Cache容量的平均访存时间。 5.3 降低Cache失效率的方法 块大小 (字节) 失效开销 (时钟周期) Cache容量(字节) 1K 4K 16K 64K 256K 16 42 7.321 4.599 2.655 1.857 1.458 32 44 6.870 4.186 2.263 1.594 1.308 64 48 7.605 4.360 2.267 1.509 1.245 128 56 10.318 5.357 2.551 1.571 1.274 256 72 16.847 7.847 3.369 1.828 1.353 5.3.2 提高相联度 1. 采用相联度超过8的方法实际意义不大 2. 2:1 Cache经验规则 容量为N 的直接映象 Cache≈容量为N/2的两路组相联Cache 3. 提高相联度是以增加命中时间为代价 例如: TTL或ECL板级Cache,两路组相联: 增加10% 定制的CMOS Cache, 两路组相联: 增加2% 5.3 降低Cache失效率的方法 4. 例题 假定提高相联度会按下列比例增大处理器 时钟周期: 时钟周期2路 =1.10×时钟周期1路 时钟周期4路 =1.12×时钟周期1路 时钟周期8路 =1.14×时钟周期1路 假定命中时间为1个时钟,失效开销为50个时钟周期,而且假设不必将失效开销取整。使用表5-5中的失效率,试问当Cache为多大时,以下不等式成立? 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.3 降低Cache失效率的方法 Cache容量 (K字节) 相联度(路) 1 2 4 8 1 7.65 6.60 6.22 5.44 2 5.90 4.90 4.62 4.09 4 4.60 3.95 3.57 3.19 8 3.30 3.00 2.87 2.59 16 2.45 2.20 2.12 2.04 32 2.00 1.80 1.77 1.79 64 1.70 1.60 1.57 1.59 128 1.50 1.45 1.42 1.44 5.3 降低Cache失效率的方法 最直接的方法是增加Cache的容量 缺点: 增加成本 可能增加命中时间 这种方法在片外Cache中用得比较多 5.3.3 增加Cache的容量 1. 基本思想 在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache,用于存放被替换出去的块(称为Victim),以备重用。 工作过程 5.3.4 Victim Cache 5.3 降低Cache失效率的方法 5.3 降低Cache失效率的方法 对于减小冲突失效很有效,特别是对于小容量的直接映象数据Cache,作用尤其明显。 例如,项数为4的Victim Cache: 使4KB Cache的冲突失效减少20%~90% 2. 作用 5.3 降低Cache失效率的方法 1. 直接映象 vs.组相联 5.3.5 伪相联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失效率的方法 查找范围:候选位置所对应的目录表项 5.2 Cache基本知识 并行查找与顺序查找 5.2 Cache基本知识 提高性能的重要思想:主候选位置 (MRU块) 5.2 Cache基本知识 并行查找的实现方法: ▲ 相联存储器 ▲ 单体多字存储器+比较器 5.2 Cache基本知识 举例: 4路组相联并行标识比较 5.2 Cache基本知识 直接映象Cache的查找过程 5.2 Cache基本知识 4路相联Cache的查找过程 5.2 Cache基本知识 5.2.3 替换算法 所要解决的问题:当新调入一块,而Cache 又已被占满时,替换哪一块? 2. FIFO 3. LRU 优点: 失效率低 1. 随机法 优点:实现简单 5.2 Cache基本知识 LRU和随机法的失效率的比较 (VAX地址流,块大小16字节) LRU和随机法分别因其失效率低和实现简单而被广泛采用。 5.2.4 写策略 1. “写”操作所占的比例 Load指令:26% Store指令:9% “写”在所有访存操作中所占的比例: 9%/ (100%+26%+9%)≈7% “写”在访问数据Cache操作中所占的比例: 9%/(26%+9%)≈25% 3.“写”访问有可能导致 Cache 和主存内容的不一致 2. “写”操作必须在确认是命中后才可进行 5.2 Cache基本知识 5.2 Cache基本知识 4.两种写策略 ◆ 写直达法 执行“写”操作时,不仅写入Cache,而且 也写入下一级存储器。 ◆ 写回法(也称为拷回法) 执行“写”操作时,只写入Cache。仅当 Cache中相应的块被替换时,才写回主存。 (设置“修改位”) 5.2 Cache基本知识 5.两种写策略的比较 ◆写回法的优点: 写操作速度快,对存储器的 速度要求较低; ◆写直达法的优点:易于实现,一致性好。 5.2 Cache基本知识 采用写直达法时,若在进行“写”操作的过程中CPU必须等待,直到“写”操作结束,则称CPU写停顿。 减少写停顿的一种常用的优化技术: 采用写缓冲器 8. 写策略与调块 写回法 ── 按写分配 写直达法 ── 不按写分配 7. “写”操作时的调块 ◆ 按写分配(写时取) 写失效时,先把所写单元所在的块调入 Cache,再行写入。 ◆ 不按写分配(绕写法) 写失效时,直接写入下一级存储器而不调块。 5.2 Cache基本知识 5.2.5 Cache的结构 例子:DEC的Alpha AXP21064中的内部数据Cache。 1. 简介 容量: 8KB 块大小: 32B 块数: 256 调块: 不按写分配 映象方法: 直接映象 “写”策略: 写直达 写缓冲器大小: 4个块 5.2 Cache基本知识 2. 结构图 5.2 Cache基本知识 5.2 Cache基本知识 5.2 Cache基本知识 3. 失效情况下的操作 读失效: Cache向CPU发出一个暂停信号, 通知它等 待,并从下一级存储器中读如32个字节, 填入对应的Cache块。 写失效: CPU不对Cache进行操作。 5.2 Cache基本知识 4. 混合 Cache 与分离 Cache 访存操作: 指令访问(读指令) 数据访问(读写数据) 分离Cache: 指令Cache + 数据Cache 混合Cache: 单一的Cache 优缺点: (1) 实现成本 (2) 结构冲突 5.2 Cache基本知识 16 KB 容量 1 KB 2 KB 4 KB 8 KB 32 KB 指令 Cache 3.06% 失 效 率 的 比 较 64 KB 128 KB 数据 Cache 混合 Cache 2.26% 1.78% 1.10% 0.64% 0.39% 0.15% 0.02% 24.61% 20.57% 15.94% 10.19% 6.47% 4.82% 3.77% 2.88% 13.34% 9.78% 7.24% 4.57% 2.87% 1.99% 1.36% 0.95% 5.2 Cache基本知识 6. 分离Cache与混合Cache平均失效率的比较 前提:指令Cache容量+数据Cache容量 = 混合Cache容量 5.2 Cache基本知识 分离Cache平均失效率的计算: 访问指令Cache的百分比×指令Cache的失效率 +访问数据Cache的百分比×数据Cache的失效率 访问指令Cache的百分比: 100%/(100%+26%+9%)≈75% 访问数据Cache的百分比: (26%+9%)/(100%+26%+9%)≈25% 5.2 Cache基本知识 5.2.6 Cache性能分析 2. 平均访问时间 平均访问时间=命中时间+失效率×失效开销 1. 失效率 与硬件速度无关 容易产生一些误导 5.2 Cache基本知识 例 假设 Cache 的命中时间为 1 个时钟周期,失效开销为 50 个时钟周期,在混合 Cache 中一次 load 或 store 操作访问 Cache 的命中时间都要增加一个时钟周期 ( 因为混合Cache只有一个端口,无法同时满足两个请求。按照前一章中有关流水线的术语,混合Cache会导致结构冲突 ) ,根据表 5-4 所列的失效率,试问指令 Cache 和数据 Cache 容量均为 16KB 的分离 Cache 和容量为 32KB 的混合 Cache 相比,哪种Cache 的失效率更低?又假设采用写直达策略,且有一个写缓冲器,并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少? 5.2 Cache基本知识 解: 如前所述,约 75% 的访存为取指令。因此, 分离 Cache 的总体失效率为: (75%×0.64%)+(25%×6.47%)=2.10% 根据表5-4,容量为 32KB 的混合 Cache 的失效率略低一些,只有1.99%. 另外: 平均访存时间公式可以分为指令访问和数据 访问两部分: 5.2 Cache基本知识 平均访存时间=指令所占的百分比× (指令命中时间+指令失效率×失效开销)+ 数据所占的百分比× (数据命中时间+数据失效率×失效开销) 所以根据表5-4,两种结构的平均访存时间分别为: 平均访存时间分离=75%×(1+0.64%×50)+ 25%×(1+6.47%×50) =(75%×1.32)+(25%×4.325) =0.990+1.059=2.05 5.2 Cache基本知识 平均访存时间混合=75%×(1+1.99%×50) +25%×(1+1+1.99%×50) =(75%×1.995)+(25%×2.995) =1.496+0.749=2.24 3. 程序执行时间 在考虑存储器对系统性能影响时,可以将系统性能描述为: CPU时间=(CPU执行周期数+存储器停顿周期数) ×时钟周期时间 5.2 Cache基本知识 其中,存储器停顿周期数= “读”的次数×读失效率×读失效开销 +“写”的次数×写失效率×写失效开销 如果读、写失效率以及读、写失效开销相差不大, 存储器停顿周期数=访存次数×失效率×失效开销 于是 CPU时间=IC×[CPIexe+访存次数/指令数× 失效率×失效开销]×时钟周期时间 5.2 Cache基本知识 例 我们用一个和Alpha AXP类似的机器作为第一个例子。假设 Cache 失效开销为 50 个时钟周期,当不考虑存储器停顿时,所有指令的执行时间都是 2.0 个时钟周期, Cache 的失效率为 2%,平均每条指令访存 1.33 次。试分析Cache 对性能的影响。 5.2 Cache基本知识 解:考虑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 5.2 Cache基本知识 5.2 Cache基本知识 Cache失效对于一个CPI较小而时钟频率较高的CPU来说,影响更大: CPI 越低,固定时间的Cache失效开销的相对影响就越大; 时钟频率越高,固定时间的Cache失效开销所对应的时钟周期数越多; Cache低失效率对于低CPI、高时钟频率的CPU来说更加重要。 Computer Architecture * 第五章 存储层次 5.1.1 从单级存储器到多级存储器 从用户的角度来看,存储器的三个主要 指标是: 容量,速度,价格 (每位价格) 5.1 存储器的层次结构 2. 人们对这三个指标的期望: 5.1 存储器的层次结构 速度快 ? 价格高 容量大 ? 价格低 容量大 ? 速度慢 5.1 存储器的层次结构 3. 这三个指标相互矛盾: 4. 解决方法: 采用多种存储器技术,构成存储层次 目标:高速度、低价格(成本)、大容量 5.1 存储器的层次结构 达到目标的依据:指令和数据访问的局部性原理 5.1 存储器的层次结构 5.1.2 存储层次的性能参数 C,S,TA 设: S ── 容量 TA ── 访问时间 C ── 每位价格 下面仅考虑由 M1 和 M2 构成的两级存储层次: M1 的参数:S1,TA1,C1 M2 的参数:S2,TA2,C2 1. 每位价格 C C= ───── 如果 S1 S2,C ? C2 C1S1+C2S2 S1+S2 5.1 存储器的层次结构 2. 命中率 H 和失效率 F 命中率 H :CPU访问存储系统时,在 M1 中找到所 需信息的概率。 H=N1 / (N1+N2) N1 ── 访问 M1 的次数 N2 ── 访问 M2 的次数 失效率F : CPU访问存储系统时,在 M1 中找不到 所需信息的概率。 F=1-H 5.1 存储器的层次结构 3. 平均访问时间 TA 对大部分系统: TM=TA2+TB 5.1 存储器的层次结构 由于 TA= H ?TA1+(1-H )(TA1+TM ) 于是 TA=TA1+(1-H )TM 或 TA=TA1+F TM TA1 ── 命中时间 TM ── 失效开销 5.1 存储器的层次结构 5.1.3 “Cache-主存” 和 “主存-辅存” 层次 5.1 存储器的层次结构 一般来说: “Cache-主存”层次:弥补主存速度的不足 “主存-辅存” 层次: 弥补主存容量的不足 1. “Cache-主存” 层次 5.1 存储器的层次结构 主存与 CPU 的速度差距 5.1 存储器的层次结构 “Cache - 主存”层次的实现:主要借助于辅助硬件。 5.1 存储器的层次结构 2. “主存-辅存”层次 “主存-辅存”层次的实现:主要借助于辅助软硬件。 5.1 存储器的层次结构 存储层次 CPU对第二级的 访问方式 比较项目 目的 存储管理实现 访问速度的比值 (第一级和第二级) 典型的块(页)大小 失效时CPU是否切换 “Cache -主存”层次 “主存-辅存”层次 为了弥补主存速度的不足 为了弥补主存容量的不足 主要由专用硬件实现 主要由软件实现 几比一 几百比一 几十个字节 几百到几千个字节 可直接访问 均通过第一级 不切换 切换到其他进程 两者的比较-----“Cache-主存”与“主存-辅存” 5.1 存储器的层次结构 5.2 Cache基本知识 5.2 Cache基本知识 5.1.4 存储层次的四个问题 当把一个块调入高一层(靠近CPU)存储器时, 可以放在哪些位置上? (映象规则) 当所要访问的块在高一层存储器中时,如何 找到该块? (查找算法) 3. 当发生失效时,应替换哪一块? (替换算法) 4. 当进行写访问时,应进行哪些操作? (写策略) 1. 2. 5.1 存储器的层次结构 5.2.1 映象规则 1. 全相联映象 全相联:主存中的任一块可以被放置到 Cache中的任意一个位置。 特点: 空间利用率最高,冲突概率最低, 实现最复杂。 5.2 Cache基本知识 实际:Cache常包含几百个块,主存常包含几百万个块。 5.2 Cache基本知识 2. 直接映象: 直接映象:主存中的每一块只能被放置到 Cache中唯一的一个位置。 特点: 空间利用率最低,冲突概率最 高,实现最简单。 例如: 对于主存的第 i 块,若它映象到Cache的 第 j 块,则: j=i mod (M ) (M 为Cache的块数) 5.2 Cache基本知识 (循环分配) 5.2 Cache基本知识 组相联:主存中的每一块可以被放置到Cache 中唯一的一个组中的任何一个位置。 设 M=2m,则当表示为二进制数时,j 实际上就是 i 的低 m 位: 3. 组相联映象: m位 j i: 5.2 Cache基本知识 5.2 Cache基本知识 组相联是直接映象和全相联的一种折衷 5.2 Cache基本知识 ◆ 上述的 j (直接映象)和 k (组相联)通 常称为索引 组的选择常采用位选择算法 若主存第 i 块映象到第 k 组,则: k=i mod(G) (G 为Cache的组数) 设 G=2 g,则当表示为二进制数时,k 实际 上就是 i 的低 g 位。 g 位 k 主存块地址 i: 5.2 Cache基本知识 相联度一定是越大越好? ◆ 绝大多数计算机的 Cache: n ≤4 ◆ n 路组相联:每组中有 n 个块 ( n=M /G ) n 称为相联度。 相联度越高,Cache空间的利用率就越高, 块冲突概率就越低,失效率也就越低。 全相联 直接映象 组相联 n (路数) G (组数) M M 1 1 1<n<M 1<G<M 5.2 Cache基本知识 5.2.2 查找方法 所要解决的问题:如何确定Cache中是否有所要访问的块?若有的线 Cache基本知识 目录表的结构:

  ·日粮中大豆异黄酮对环境内分泌干扰物3-甲基 - 南京农业大学学报.pdf

  ·大跨度高速铁路桥梁健康监测系统研发① - 铁道科学与工程学报.pdf

  ·温室气体co 资源化催化转化研究进展 - ingenta connect.pdf

  ·基于光纤光栅偏振特性的横向压力传感器 - 南京师范大学图书馆电子 .pdf

  ·金红石二氧化钛表面二氧化硅纳米膜成膜机理 - 中国有色金属学报.pdf

本文链接:http://guidoon.com/zhixingkaixiao/310.html