《例对于下面的程序判断哪些访问可能会导致数据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. 子块放置技术：
8、把Cache块进一步划分为更 小的块(子块)，并给每个子块赋予一位有 效位，用于指明该子块中的数据是否有效。 Cache与下一级存储器之间以子块为单位传 送数据。但标识仍以块为单位。,3. 举例 (图示),3.4.3 请求字处理技术,1. 请求字 从下一级存储器调入Cache的块中，只有 一个字是立即需要的。这个字称为请求字。,2. 应尽早把请求字发送给CPU 尽早重启动：调块时，从块的起始位置开 始读起。一旦请求字到达，就立即发送给 CPU，让CPU继续执行。 请求字优先：调块时，从请求字所在的位 置读起。这样，第一个读出的字便是请求 字。将之立即发送给CPU。,3. 这种技术在以下情况下效
9、果不大： Cache块较小 下一条指令正好访问同一Cache块的另 一部分。,3.4.4 非阻塞Cache技术,1. 非阻塞Cache：Cache失效时仍允许CPU进行 其它的命中访问。即允许“失效下命中”,2. 进一步提高性能：“多重失效下命中”， “失效下失效” (存储器必须能够处理多个失效),3. 重叠失效个数对平均访问时间的影响,非阻塞Cache平均存储器等待时间 与阻塞Cache的比值,1,2,浮点程序,76,51,64,39,整数程序,81,78,78,重叠失效个数,对于图5.17所描述的Cache，在两路组相联和 “一次失效下命中”这两种措施中，哪一种对浮 点程序更重要？对整数程
10、序的情况如何？ 假设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,对于整数程序： 失效率直接映象失效开销7.4 %161.18 失效率两路组相联失效开销6.0 %16 0.96 0.96/1.18=0
11、.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 发出的访存的总次数 全局失效率L2失效率L1失效率L2 评价第二级Cache时，应使用全局失效率 这个指标。 图
12、 5.18,4. 当第二级Cache比第一级Cache大得多时，两 级Cache的全局失效率与容量和第二级Cache,相同的单级Cache的失效率非常接近。,5. 第二级Cache的参数 第二级Cache不会影响CPU的时钟频率， 因此其设计有更大的考虑空间。 两个问题： 能否降低CPI中的平均访存时间部分？ 成本是多少？ (1) 容量 第二级Cache的容量一般比第一级的 大许多，如512KB 图 5.19,(2) 相联度 第二级Cache可采用较高的相联度或伪 相联方法,例5.12 给出有关第二级Cache的以下数据： 两路组相联使命中时间增加10%CPU时钟周期 对于直接映象，命中时间L
13、210个时钟周期 对于直接映象，局部失效率L225% 对于两路组相联，局部失效率L220% 失效开销L250个时钟周期 试问第二级Cache的相联度对失效开销的影响如何？,解： 对于一个直接映象的第二级Cache来说， 第一级Cache的失效开销为： 失效开销直接映象，L1 1025%5022.5个时钟周期 对于两路组相联第二级Cache来说，命中 时间增加了10%(0.1)个时钟周期，故第一级 Cache的失效开销为： 失效开销两路组相联，L1 10.120%5020.1个时钟周期 把第二级Cache的命中时间取整，得10或11， 则：,失效开销两路组相联，L1 1020%5020.0个时钟
14、周期 失效开销两路组相联，L1 1120%5021.0个时钟周期 故对于第二级Cache来说，两路组相联优于 直接映象。,(3) 块大小 第二级Cache可采用较大的块， 如 64、128、256字节。 图 5.20 为减少平均访存时间，可以让容量较小 一的第级Cache采用较小的块，而让容量较大 的第二级Cache采用较大的块。,3.5 减少命中时间,2. 应使Cache足够小，以便可以与CPU一起放 在同一块芯片上。,命中时间直接影响到处理器的时钟频率。在 当今的许多计算机中，往往是Cache的访问时间 限制了处理器的时钟频率。,1. 硬件越简单，速度就越快；,3.5.1 容量小、结构简单
15、的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容量164KB64KB 7. 另一种方法：硬件散列变换,页地址 地址标识,页内位移,索 引,块内位移,31,12 11,0,3.5.4 Cache优化技术总结 (表 5-9),