《例 对于下面的程序,判断哪些访问可能会导致数据cache失效》由会员分享，可在线阅读，更多相关《例 对于下面的程序,判断哪些访问可能会导致数据cache失效（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) 改进
2、后的程序for (j0，j100；jj1) prefetch (bj70); /* 预取7次循环后所需的b(j ,0 ) */prefetch (a0j7); /* 预取7次循环后所需的a(0,j ) */a0jbj 0 * b j10for (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、以最大的存储带宽传送数据。(3) 不考虑Cache失效时，修改前的循环每7个时钟周期循环一次。修改后的程序中，失效情况总的失效次数19次解：修改前：循环时间3007 2100失效开销2515012550/1465021001255014650第一个预取循环每9个时钟周期循环一次，而第二个预取循环每8个时钟周期循环一次(包括外层for循环的开销)。(4) 一次失效需50个时钟周期。修改后：循环时间100920082500失效时间195095025009503450加速比14650/34504.23.3.7 编译器优化2KB Cache: 降低50 8KB Cache：降低75%1. 基本思想在编
4、译时，对程序中的指令和数据进行重新组织，以降低Cache失效率。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
5、 ;int key ; ;struct merge merged_arraysize;(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)分块把对数组的整行或整列
6、访问改为按块进行。举例：/* 修改前 */for (i0; i N; ii1)for (j0; j N; jj1) r0;for (k0; k N; kk1) 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/BN23.4.1 让读失效优先于写3.4
7、减少Cache失效开销1. Cache中的写缓冲器导致对存储器访问的复杂化2. 解决问题的方法(读失效的处理) 推迟对读失效的处理(缺点：读失效的开销增加，如50) 检查写缓冲器中的内容3. 在写回法Cache中，也可采用写缓冲器3.4.2 子块放置技术1. 为减少标识的位数，可采用增加块大小的方法，但这会增加失效开销，故应采用子块放置技术。2. 子块放置技术：把Cache块进一步划分为更小的块(子块)，并给每个子块赋予一位有效位，用于指明该子块中的数据是否有效。Cache与下一级存储器之间以子块为单位传送数据。但标识仍以块为单位。3. 举例 (图示)3.4.3 请求字处理技术1. 请求字从下
8、一级存储器调入Cache的块中，只有一个字是立即需要的。这个字称为请求字。 2. 应尽早把请求字发送给CPU 尽早重启动：调块时，从块的起始位置开始读起。一旦请求字到达，就立即发送给CPU，让CPU继续执行。 请求字优先：调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU。3. 这种技术在以下情况下效果不大： Cache块较小 下一条指令正好访问同一Cache块的另一部分。3.4.4 非阻塞Cache技术1. 非阻塞Cache：Cache失效时仍允许CPU进行其它的命中访问。即允许“失效下命中”2. 进一步提高性能：“多重失效下命中”，“失效下失效”(存储器必
9、须能够处理多个失效)3. 重叠失效个数对平均访问时间的影响非阻塞Cache平均存储器等待时间与阻塞Cache的比值12浮点程序76516439整数程序817878重叠失效个数对于图5.17所描述的Cache，在两路组相联和 “一次失效下命中”这两种措施中，哪一种对浮点程序更重要？对整数程序的情况如何？假设8KB数据Cache的平均失效率为：对于浮点程序，直接映象Cache为11.4%，两路组相联Cache为10.7%；对于整数程序，直接映象Cache为7.4%，两路组相联Cache为6.0%。并且假设平均存储器等待时 间是失效率和失效开销的积，失效开销为16个时钟 周期。例对于浮点程序，平均存
10、储器等待时间为：失效率直接映象失效开销11.4%161.82失效率两路组相联失效开销10.7%161.711.71/1.820.94对于整数程序：失效率直接映象失效开销7.4 %161.18失效率两路组相联失效开销6.0 %16 0.960.96/1.18=0.81解：3.4.5 两级Cache1. 应把Cache做得更快？还是更大？答案：二者兼顾，再增加一级Cache 第一级Cache(L1)小而快 第二级Cache(L2)容量大2. 性能分析平均访问时间命中时间L1失效率L1失效开销L1命中时间L1失效率L1(命中时间L2失效率L2失效开销L2)3. 局部失效率与全局失效率局部失效率该级C
11、ache的失效次数/到达该级Cache的访问次数例如：上述式子中的失效率L2全局失效率该级Cache的失效次数/CPU发出的访存的总次数全局失效率L2失效率L1失效率L2评价第二级Cache时，应使用全局失效率这个指标。 图 5.184. 当第二级Cache比第一级Cache大得多时，两级Cache的全局失效率与容量和第二级Cache相同的单级Cache的失效率非常接近。5. 第二级Cache的参数第二级Cache不会影响CPU的时钟频率，因此其设计有更大的考虑空间。两个问题： 能否降低CPI中的平均访存时间部分？ 成本是多少？(1) 容量第二级Cache的容量一般比第一级的大许多，如512K
12、B 图 5.19(2) 相联度第二级Cache可采用较高的相联度或伪相联方法例5.12给出有关第二级Cache的以下数据： 两路组相联使命中时间增加10%CPU时钟周期 对于直接映象，命中时间L210个时钟周期 对于直接映象，局部失效率L225% 对于两路组相联，局部失效率L220% 失效开销L250个时钟周期试问第二级Cache的相联度对失效开销的影响如何？解：对于一个直接映象的第二级Cache来说，第一级Cache的失效开销为：失效开销直接映象，L11025%5022.5个时钟周期对于两路组相联第二级Cache来说，命中时间增加了10%(0.1)个时钟周期，故第一级Cache的失效开销为：
13、失效开销两路组相联，L110.120%5020.1个时钟周期把第二级Cache的命中时间取整，得10或11，则：失效开销两路组相联，L11020%5020.0个时钟周期失效开销两路组相联，L11120%5021.0个时钟周期故对于第二级Cache来说，两路组相联优于直接映象。(3) 块大小第二级Cache可采用较大的块，如 64、128、256字节。 图 5.20为减少平均访存时间，可以让容量较小一的第级Cache采用较小的块，而让容量较大的第二级Cache采用较大的块。3.5 减少命中时间2. 应使Cache足够小，以便可以与CPU一起放在同一块芯片上。命中时间直接影响到处理器的时钟频率。在
14、 当今的许多计算机中，往往是Cache的访问时间 限制了处理器的时钟频率。1. 硬件越简单，速度就越快；3.5.1 容量小、结构简单的Cache1. 虚拟Cache访问Cache的索引以及Cache中的标识都是虚拟地址(一部分)。2. 并非人人都采用虚拟Cache(为什么?) 3. 虚拟Cache的清空问题3.5.2 虚拟Cache解决方法：在地址标识中增加PID字段 (进程标识符) 三种情况下失效率的比较：单进程，PIDs，清空PIDs与单进程相比：0.30.6PIDs与PIDs相比： 0.64.3%4. 同义和别名解决方法：反别名法,页着色5. 虚拟索引物理标识优点：兼得虚拟Cache和物
15、理Cache的好处局限性：Cache容量受到限制(页内位移)Cache容量页大小相联度6. 举例：IBM3033的Cache页大小4KB 相联度163.5.3 将写操作流水化以加快写命中(图 5.23)Cache容量164KB64KB7. 另一种方法：硬件散列变换页地址 地址标识页内位移 索 引块内位移3112 1103.5.4 Cache优化技术总结(表 5-9)优化技术失效 率失效 开销命中 时间硬件复 杂度评价增加块大小+- 0实现容易；RS/6000 550采用了 128字节提高相联度+ -1MIPS R10000为4路组相联Victim Cache+ 2HP7200中采用了类似的技术伪相联Cache+ 2已应用于MIPS R1
