例对于下面的程序判断哪些访问可能会导致数据Cache失效.ppt
《例对于下面的程序判断哪些访问可能会导致数据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 总的失效
2、次数251次 (3) 改进后的程序,for (j0,j100;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)
3、假设预取可以被重叠或与Cache失效重 叠执行,从而能以最大的存储带宽传送 数据。 (3) 不考虑Cache失效时,修改前的循环每7 个时钟周期循环一次。修改后的程序中,,失效情况 总的失效次数19次,解: 修改前: 循环时间3007 2100 失效开销2515012550/14650 21001255014650,第一个预取循环每9个时钟周期循环一次, 而第二个预取循环每8个时钟周期循环一 次(包括外层for循环的开销)。 (4) 一次失效需50个时钟周期。,修改后: 循环时间100920082500 失效时间1950950 25009503450 加速比14650/34504.2,3.3.
4、7 编译器优化,2KB Cache: 降低50 8KB Cache:降低75%,1. 基本思想,在编译时,对程序中的指令和数据进行 重新组织,以降低Cache失效率。,2. McFaring 发现:通过对指令进行重新排序, 可有效地降低指令Cache的失效率。,3. 数据对存储位置的限制比指令的少,因此 更便于优化。 通过把数据重新组织,使得在一块数 据被从Cache替换出去之前,能最大限度 利用其中的数据(访问次数最多) (1) 数据合并 举例: /* 修改前 */ int val SIZE; int key SIZE;,(2) 内外循环交换 举例: /* 修改前 */ for (j0 ;j
5、100 ;jj1) for (i0 ;i5000 ;ii1) xij2*xij;,/* 修改后 */ struct merge int val ; 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
6、) 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) rryik*zkj; xijr; ,计算过程 失效次数:2N3N2,/* 修改后 */ for (jj0; jj N; jjjj1) for (kk0; kk N; kkkk1) for (i0; i N; ii1) for (jjj; j mi
7、n(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. 在写回法Cache中,也可采用写缓冲器,3.4.2 子块放置技术,1. 为减少标识的位数,可采用增加块大小的 方法,但这会增加失效开销,故应采用子 块放置技术。,2. 子块放置技术:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对于 下面 程序 判断 哪些 访问 可能会 导致 数据 Cache 失效
链接地址:https://www.31doc.com/p-3184108.html