《高速缓冲存储器》由会员分享，可在线阅读，更多相关《高速缓冲存储器（25页珍藏版）》请在金锄头文库上搜索。
1、1,第四章 高速缓冲存储器,2,3,Cache-主存层次层次化存储系统实现的依据是：程序访问的局部性原理。局部性的实质是：根据程序的最近情况，可以较精确地预测出最近的将来将要用到哪些指令和数据。时间局部性：最近访问过的代码可能是不久将被访问的代码。空间局部性：地址相邻的代码可能会被一起访问,4,依据程序访问的局部性原理，可将频繁访问的指令和数据存放在速度较快、容量较小而价格较高的高层存储器中，而将不频繁访问的指令和数据存放在速度较慢、价格较低而容量较大的低层存储器中，以使存储器系统具有较高的平均访存速度。 Cache和主存都划分成相同大小的块。当CPU按主存地址访问信息时，首先查看该信息是否在
2、cache中，若命中则从cache中读取，若没有命中，则从主存中读取该信息，并将包含该信息的整个数据块从主存调入Cache中。这时，如果Cache已满，则要采用某种Cache替换算法把不常用的一块调出，以便腾出空间来存放新调入的块。,5,存储层次设计的四个问题Q1: 信息块可以放在高层的哪里？ (Block placement) 全相联、组相联、直接映射Q2: 如果信息块在高层，那么如何找到它？ (Block identification) 标记/信息块 Q3: 在失效时，应该替换掉哪个信息块？(Block replacement) 随机、LRU、FIFO Q4: 在写操作时，会发生什么情况(
3、Write strategy) 回写（Write Back）或直写（Write Through） (使用写缓冲器,6,7,8,9,Cache性能CPU time = (CPU execution clock cycles + Memory stall clock cycles) clock cycle timeMemory stall clock cycles = (Reads Read miss rate Read miss penalty + Writes Write miss rate Write miss penalty)Memory stall clock cycles = Memo
4、ry accesses Miss rate Miss penalty,10,Cache 性能（续） CPUtime = Instruction Count (CPIexecution + Mem accesses per instruction Miss rate Miss penalty) Clock cycle timeMisses per instruction = Memory accesses per instruction MissrateCPUtime = IC (CPIexecution + Misses per instruction Miss penalty) Clock
5、cycle timeMemory stall cycles per instruction = Misses per instruction (Total miss latency Overlapped miss latency) Average Memory access time = Hit time + Miss rate Miss penalty,11,改进Cache性能Average Memory access time = Hit time + Miss rate Miss penalty 1. 降低失效率 2. 降低失效损失，或者 3. 减少在cache中命中的时间,12,降低失
6、效对失效进行分类： 3 Cs Compulsory 第一次访问一个不在cache中的数据块，该 块必须被调入。也称为cold start misses o或first reference misses。(即使Cache无穷大，也会失效) Capacity 在程序执行中，cache不能存放其所需的所有数 据块，就会先放弃一些块然后再找回，这就出现了capacity misses。（有限大小的全相联Cache也会出现的失效) Conflict 如果采用组相联或直接映射的策略，除了义务 失效和容量失效，还会因为有太多块要同时映射到同一 组中，就会先放弃一些块然后再找回，这就出现了 conflict
7、misses 。也称为collision misses 或interference misses。(有限大小的N路组相联Cache中出现的失效),13,14,15,如何能减少失效? 3 Cs: Compulsory, Capacity, Conflict在所有情况，假设总的cache大小不变： 在下列情况，会发生什么变化：1) 改变块大小： 3Cs中哪些失效会受到明显影响?2) 改变相联度： 3Cs中哪些失效会受到明显影响?3) 改变编译器: 3Cs中哪些失效会受到明显影响?,16,1. 通过增大块大小来减少失效,17,2. 通过增大相联度来减少失效8路组相联实际上在减少Miss rate方面
8、与全相效果接近。 2:1 Cache规律： Miss Rate DM cache size N = Miss Rate 2-way cache size N/2 小心：执行时间是唯一最终度量标准！ 是否时钟周期时间会增加? Hill 1988的研究表明2-way cache的命中时间比1-way 外部cache的时间会+10%, 比内部cache的时间会+ 2% 通过增加Cache容量来减少失效。,18,19,20,4. 通过伪相联减少失效如何结合直接映射的快速命中时间和两路组相联 cache的低冲突失效的优势? 分解cache: 在失效时，检查cache的另一半看是否有所需信息，如果有称为伪
9、命中（pseudo-hit） (慢命中),缺点：如果命中需要1或2个周期，那么CPU难以流水 适用于不与处理器直接连接的cache（二级cache） 用于MIPS R1000和UltraSPARC的二级cache。,21,5. 通过硬件预取指令和数据减少失效 例如，指令预取 Alpha 21064在失效时取2个信息块 额外的块放置在流缓冲器（stream buffer）中 失效时，检测流缓冲器 对于数据块也可使用上述策略 Jouppi 1990 对于4KB cache，1个数据流缓冲器可以减少25%的损失；4个流缓冲器，减少43% Palacharla & Kessler 1994 对于科学计
10、算程序，对于两个64KB，四路组相联cache，8个流缓冲器减少50%至70%的失效,22,6. 通过软件预取数据减少失效 数据预取 将数据装入寄存器(HP PA-RISC loads) Cache预取: 装入cache(MIPS IV, PowerPC, SPARC v. 9) 发射预取指令需要时间 发射预取指令的开销是否小于减少失效的收 益？,23,7. 通过编译优化减少失效 McFarling 1989 对于块大小为4字节的8KB直接映射cache，软件可以75% 的失效 指令 对存储访问重排序，因而可以减少冲突失效 数据 合并数组(data merge)：通过将两个独立数组合并为一个复
11、合元素的数组来改进空间局部性 循环交换(loop interchange): 通过改变循环嵌套来按序访问存储器中存储的数据 循环合并(loop fusion): 将两个具有相同循环类型且有一些变量重叠的独立循环合并 块化(blocking): 通过不断使用一些数据块（而不是完整地遍历一行和一列）来改进时间局部性,24,合并数据的示例 /* Before: 2 sequential arrays */ int valSIZE; int keySIZE; /* After: 1 array of stuctures */ struct merge int val; int key; ; struc
12、t merge merged_arraySIZE; 减少val和key之间的冲突 改进空间局部性,25,总结 CPUtime = IC CPI Execution + Memory accesses Instruction Miss rate Miss penalty Clock cycle time 3 Cs: Compulsory, Capacity, Conflict 降低失效率 1. 通过增大块大小减少失效 2.通过增大相联度减少失效 3.通过Victim Cache减少失效 4.通过伪-相联减少失效 5.通过硬件预取指令或数据减少失效 6.通过软件预取数据减少失效 7.通过编译优化减少失效 注意：在评价性能时仅仅侧重于某一个参数是危险的,
