《例对于下面的程序判断哪些访问可能会导致数据Cache失效.ppt》由会员分享，可在线阅读，更多相关《例对于下面的程序判断哪些访问可能会导致数据Cache失效.ppt（44页珍藏版）》请在三一办公上搜索。
1、例 对于下面的程序，判断哪些访问可能会导致数据Cache失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：(1)我们用的是一个容量为8KB、块大小为 16B的直接映象Cache，它采用写回法并 且按写分配。(2)a、b分别为3100(3行100列)和1013 的双精度浮点数组，每个元素都是8个 字节。当程序开始执行时，这些数据都 不在Cache内。,for(i0;i 3;ii1)for(j0;j 100;jj1)aijbj0bj10;,解：(1)计算过程(2)失效情况 数组a 数组b 总的失效次数251次(3)改进后的程序,for(j0，j1
2、00；jj1)prefetch(bj70);/*预取7次循环后所需的b(j,0)*/prefetch(a0j7);/*预取7次循环后所需的a(0,j)*/a0jbj 0*b j10 for(i1;i 3;ii1)for(j0;j 100;jj1)prefetch(aij7);/*预取7次循环后所需的a(i,j)*/aijbj0*bj10;,例 在以下条件下，计算例5.8中所节约的时间：(1)忽略指令Cache失效，并假设数据Cache 无冲突失效和容量失效。(2)假设预取可以被重叠或与Cache失效重 叠执行，从而能以最大的存储带宽传送 数据。(3)不考虑Cache失效时，修改前的循环每7 个
3、时钟周期循环一次。修改后的程序中，,失效情况 总的失效次数19次,解：修改前：循环时间3007 2100 失效开销2515012550/14650 21001255014650,第一个预取循环每9个时钟周期循环一次，而第二个预取循环每8个时钟周期循环一 次(包括外层for循环的开销)。(4)一次失效需50个时钟周期。,修改后：循环时间100920082500 失效时间1950950 25009503450 加速比14650/34504.2,3.3.7 编译器优化,2KB Cache:降低508KB Cache：降低75%,1.基本思想,在编译时，对程序中的指令和数据进行重新组织，以降低Cach
4、e失效率。,2.McFaring 发现：通过对指令进行重新排序，可有效地降低指令Cache的失效率。,3.数据对存储位置的限制比指令的少，因此 更便于优化。通过把数据重新组织，使得在一块数 据被从Cache替换出去之前，能最大限度 利用其中的数据(访问次数最多)(1)数据合并 举例：/*修改前*/int val SIZE;int key SIZE;,(2)内外循环交换 举例：/*修改前*/for(j0;j100;jj1)for(i0;i5000;ii1)xij2*xij;,/*修改后*/struct merge int val;int key;struct merge merged_array
5、size;,(3)循环融合 举例：/*修改前*/for(i0;iN;ii1)for(j0;jN;jj1)aij1/bij*cij;,/*修改后*/for(i0;i100;ii1)for(j0;j 000;jj1)xij2*xij;,/*修改后*/for(i0;i N;ii1)for(j0;j N;jj1)aij1/bij*cij;dijaijcij;,for(i0;iN;ii1)for(j0;jN;jj1)dijaijcij;,(4)分块 把对数组的整行或整列访问改为按块进行。,举例：/*修改前*/for(i0;i N;ii1)for(j0;j N;jj1)r0;for(k0;k N;kk1)
6、rryik*zkj;xijr;,计算过程 失效次数：2N3N2,/*修改后*/for(jj0;jj N;jjjj1)for(kk0;kk N;kkkk1)for(i0;i N;ii1)for(jjj;j min(jjB1,N);jj1)r0;for(kkk;k min(kkB1,N);kk1)rryik*zkj;xijxijr;,计算过程 失效次数：2N3/BN2,3.4.1 让读失效优先于写,3.4 减少Cache失效开销,1.Cache中的写缓冲器导致对存储器访问的 复杂化,2.解决问题的方法(读失效的处理)推迟对读失效的处理(缺点：读失效的开销增加，如50)检查写缓冲器中的内容,3.在写
7、回法Cache中，也可采用写缓冲器,3.4.2 子块放置技术,1.为减少标识的位数，可采用增加块大小的 方法，但这会增加失效开销，故应采用子 块放置技术。,2.子块放置技术：把Cache块进一步划分为更 小的块(子块)，并给每个子块赋予一位有 效位，用于指明该子块中的数据是否有效。Cache与下一级存储器之间以子块为单位传 送数据。但标识仍以块为单位。,3.举例(图示),3.4.3 请求字处理技术,1.请求字 从下一级存储器调入Cache的块中，只有 一个字是立即需要的。这个字称为请求字。,2.应尽早把请求字发送给CPU 尽早重启动：调块时，从块的起始位置开 始读起。一旦请求字到达，就立即发送
8、给 CPU，让CPU继续执行。请求字优先：调块时，从请求字所在的位 置读起。这样，第一个读出的字便是请求 字。将之立即发送给CPU。,3.这种技术在以下情况下效果不大：Cache块较小 下一条指令正好访问同一Cache块的另 一部分。,3.4.4 非阻塞Cache技术,1.非阻塞Cache：Cache失效时仍允许CPU进行 其它的命中访问。即允许“失效下命中”,2.进一步提高性能：“多重失效下命中”，“失效下失效”(存储器必须能够处理多个失效),3.重叠失效个数对平均访问时间的影响,非阻塞Cache平均存储器等待时间 与阻塞Cache的比值,1,2,浮点程序,76,51,64,39,整数程序,
9、81,78,78,重叠失效个数,对于图5.17所描述的Cache，在两路组相联和“一次失效下命中”这两种措施中，哪一种对浮点程序更重要？对整数程序的情况如何？假设8KB数据Cache的平均失效率为：对于浮点程序，直接映象Cache为11.4%，两路组相联Cache为10.7%；对于整数程序，直接映象Cache为7.4%，两路组相联Cache为6.0%。并且假设平均存储器等待时间是失效率和失效开销的积，失效开销为16个时钟周期。,例,对于浮点程序，平均存储器等待时间为：失效率直接映象失效开销11.4%161.82 失效率两路组相联失效开销10.7%161.71 1.71/1.820.94,对于整
10、数程序：失效率直接映象失效开销7.4%161.18 失效率两路组相联失效开销6.0%16 0.96 0.96/1.18=0.81,解：,3.4.5 两级Cache,1.应把Cache做得更快？还是更大？答案：二者兼顾，再增加一级Cache 第一级Cache(L1)小而快 第二级Cache(L2)容量大,2.性能分析 平均访问时间 命中时间L1失效率L1失效开销L1 命中时间L1失效率L1(命中时间L2失效率L2失效开销L2),3.局部失效率与全局失效率 局部失效率该级Cache的失效次数/到达 该级Cache的访问次数 例如：上述式子中的失效率L2 全局失效率该级Cache的失效次数/CPU
11、发出的访存的总次数 全局失效率L2失效率L1失效率L2 评价第二级Cache时，应使用全局失效率 这个指标。图 5.18,4.当第二级Cache比第一级Cache大得多时，两 级Cache的全局失效率与容量和第二级Cache,相同的单级Cache的失效率非常接近。,5.第二级Cache的参数 第二级Cache不会影响CPU的时钟频率，因此其设计有更大的考虑空间。两个问题：能否降低CPI中的平均访存时间部分？成本是多少？(1)容量 第二级Cache的容量一般比第一级的 大许多，如512KB 图 5.19,(2)相联度 第二级Cache可采用较高的相联度或伪 相联方法,例5.12 给出有关第二级C
12、ache的以下数据：两路组相联使命中时间增加10%CPU时钟周期 对于直接映象，命中时间L210个时钟周期 对于直接映象，局部失效率L225%对于两路组相联，局部失效率L220%失效开销L250个时钟周期 试问第二级Cache的相联度对失效开销的影响如何？,解：对于一个直接映象的第二级Cache来说，第一级Cache的失效开销为：失效开销直接映象，L1 1025%5022.5个时钟周期 对于两路组相联第二级Cache来说，命中 时间增加了10%(0.1)个时钟周期，故第一级 Cache的失效开销为：失效开销两路组相联，L1 10.120%5020.1个时钟周期 把第二级Cache的命中时间取整
13、，得10或11，则：,失效开销两路组相联，L1 1020%5020.0个时钟周期 失效开销两路组相联，L1 1120%5021.0个时钟周期 故对于第二级Cache来说，两路组相联优于 直接映象。,(3)块大小 第二级Cache可采用较大的块，如 64、128、256字节。图 5.20 为减少平均访存时间，可以让容量较小 一的第级Cache采用较小的块，而让容量较大 的第二级Cache采用较大的块。,3.5 减少命中时间,2.应使Cache足够小，以便可以与CPU一起放 在同一块芯片上。,命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是Cache的访问时间限制了处理器的时钟频率
14、。,1.硬件越简单，速度就越快；,3.5.1 容量小、结构简单的Cache,1.虚拟Cache 访问Cache的索引以及Cache中的标识都 是虚拟地址(一部分)。2.并非人人都采用虚拟Cache(为什么?)3.虚拟Cache的清空问题,3.5.2 虚拟Cache,解决方法：在地址标识中增加PID字段(进程标识符)三种情况下失效率的比较：单进程，PIDs，清空 PIDs与单进程相比：0.30.6 PIDs与PIDs相比：0.64.3%,4.同义和别名 解决方法：反别名法,页着色5.虚拟索引物理标识 优点：兼得虚拟Cache和物理Cache的好处 局限性：Cache容量受到限制(页内位移)Cache容量页大小相联度6.举例：IBM3033的Cache 页大小4KB 相联度16,3.5.3 将写操作流水化以加快写命中(图 5.23),Cache容量164KB64KB7.另一种方法：硬件散列变换,页地址地址标识,页内位移,索 引,块内位移,31,12 11,0,3.5.4 Cache优化技术总结(表 5-9),
