lec06b-Cache Memory.pptVIP

Computer Systems:A Programmer’s Perspective 计算机系统详解Lecture 6b Cache Memory May 20, 2011 Wu junmin (jmwu@ustc.edu.cn) Topics Generic cache memory organization Direct mapped caches Set associative caches Impact of caches on performance 高速缓存（cache） 高速缓存是基于SRAM，容量较小，由硬件自动管理的快速存储器. 保存的是主存中经常被访问到的存储块 CPU 先从L1查找数据，然后到L2，最后到主存中查找数据 典型的总线结构: 在CPU和主存之间插入L1cache 通用的高速缓存结构 高速缓存寻址 直接映射高速缓存 最简单的映射方式 关键性质：每个组只有一行. 访问直接映射高速缓存 组选择 用组索引位决定可能的存储位置. 访问直接映射高速缓存 行匹配和字选择 行匹配: 在选择的组中找到有效（valid）行，并且标记（tag）匹配 字选择: 然后根据块内偏移获取所访问的字 直接映射高级缓存举例 为什么用中间的位作为索引? High-Order Bit Indexing Adjacent memory lines would map to same cache entry Poor use of spatial locality Middle-Order Bit Indexing Consecutive memory lines map to different cache lines Can hold C-byte region of address space in cache at one time 组相联高速缓存 每个组包含多个行 访问组相联高速缓存 组选择 与直接映射一样 组相联映射高速缓存的访问 行匹配和字选择 必须和选中的组中的每个有效的行进行标记比较. 多级高速缓存 Options: 将数据cahce和指令cache分开, 或者一个统一的cache Intel Pentium 高速缓存层次 高速缓存性能参数 缺失率（失效率） 存储器引用在高速缓存中没有找到的比率(不命中数量/引用数量) 典型数据: L1的缺失率约3-10% L2的缺失率可以非常小 (如, 1%), 主要依据大小等因素. 命中时间 从高速缓存传递一个字到CPU的时间(包括确定该字是不是在高速缓存中的时间) 典型数据: L1 要一个时钟周期 L2 要3-8个周期 缺失代价（失效开销） 因为缺失所需要的额外的时间 对主存来说典型时间是25-100个周期 编写高速缓存友好的代码 Good：重复引用变量(时间局部性) Good：步长为1的引用模式 (空间局部性) 举例: cold cache, 4-byte words, 4-word cache blocks 存储器山 读吞吐率(读带宽) 每秒从存储器中读取的字节数 (MB/s) 存储器山 将读吞吐率作为空间和时间局部性函数来测量存储器性能. 紧凑的刻画存储系统性能的方法. 存储器山测试函数 存储器山主函数 存储器山 时间局部性的山脊 步长为1时的一个存储器山的片段 刻画了主存和高级缓存的读吞吐率 空间局部性的斜坡 存储器山中问题大小为256KB时的一个片段 展示了cache块的大小. 矩阵乘法 主要考虑的cache影响因素 cache大小 利用时间局部性，保持工作集较小 (e.g., by using blocking) 块大小 利用空间局部性 描述: N x N大小矩阵乘 O(N3) 的操作次数 访问存储器 每个源操作数要读N次 每个目标都要进行N次的加法 可以保存在寄存器中 矩阵相乘的缺失率分析 假设: 行大小 = 32B (big enough for 4 64-bit words) 矩阵维数 (N) 很大 1/N 大约是 0.0 cache不能同时存储矩阵的多行 分析方法: 查看最内层循环方式 C数组在存储器中的放置 (review) C 数组以行主序放置 每个行分配连续的存储位置 某行中按列序增加访问元素: for (i = 0; i N; i++) sum += a[0][i]; 访问连续的元素 若块大小 4 bytes,开发空间局部性 强制缺失率 = 4 bytes / B 某列中按行序增加访问元素: for (i = 0; i n; i++) sum += a[i][0]; 访问远地的元素 没有空间局部性! 强制缺失率 = 1 (i.e. 100%) 矩阵相乘 (ijk) 矩阵相乘 (jik) 矩阵相乘 (k