存储器层次结构（完整版）.ppt

存储器层次结构 张 琦 (Qi Zhang) CS, USTC xiaoga@mail.ustc.edu.cn Dec. 2007 提纲 导论 存储技术 局部性原理 存储器层次结构 高速缓存存储器 编写高速缓存友好的代码 利用程序中的局部性 存储器(memory)系统 Von Neumann 一个线性的字节数组，CPU能够在一个常数时间内访问每个存储器位置 实际 一个具有不同容量、成本和访问时间的存储(storage)设备层次结构 存储器层次结构 CPU register Latency: 0 cycle Cache memory (L1, L2, …) Latency: 1-10 cycle Main memory Latency: 50-100 cycle Disk storage Latency: 20 000 000 cycle Network storage 计算机程序的局部性(locality) 良好局部性的程序 重复访问相同的数据项集合 倾向于访问临近的数据项集合 优化思想 使程序要访问的数据项存储在层次结构中较高的地方，在那里CPU能更快的访问到它们。 提纲 导论 存储技术 局部性原理 存储器层次结构 高速缓存存储器 编写高速缓存友好的代码 利用程序中的局部性 随机访问存储器(RAM) 访问主存 典型的连接CPU和主存的总线结构 磁盘存储 提纲 导论 存储技术 局部性原理 存储器层次结构 高速缓存存储器 编写高速缓存友好的代码 利用程序中的局部性 局部性 时间局部性(temporal locality) 被引用过一次的存储器位置很可能在不远的将来再被多次引用 空间局部性(spatial locality) 如果一个存储器位置被引用了一次，那么程序很可能在不远的将来引用附近的一个存储器位置 局部性 有良好局部性的程序运行更快 计算机系统的各个层次都利用了局部性 Cache 主存 作为虚拟地址空间最近被应用块的高速缓存 缓存磁盘文件系统最近使用的磁盘块 Web浏览器将最近被引用的文档放在本地磁盘上 Web服务器将最近被请求的文档放在前端磁盘高速缓存中 对程序数据引用的局部性 int sumvec(int v[N]) { int i, sum = 0; for(i=0;iN;i++) sum += v[i]; return sum; } 变量sum：时间局部性 向量v ：空间局部性 对程序数据引用的局部性 函数sumvec顺序访问一个向量的每个元素，具有步长为1的引用模式 步长为k的引用模式 (stride-k reference pattern) 访问一个连续向量的每第k个元素 随着步长的增加，空间局部性下降 引用多维数组 int sumarraycols(int a[M][N]) { int i,j,sum = 0; for(j=0;jN;j++) for(i=0;iM;i++) sum += a[i][j]; return sum } 按列优先顺序访问(col-major order) 步长为N 局部性差 引用多维数组 int sumarrayrows(int a[M][N]) { int i,j,sum = 0; for(i=0;iM;i++) for(j=0;jN;j++) sum += a[i][j]; return sum } 按行优先顺序访问(row-major order) 步长为1 局部性好 局部性小结 重复引用同一个变量的程序有良好的时间局部性 对于具有步长为k的引用模式的程序，步长越小，空间局部性越好 对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好 提纲 导论 存储技术 局部性原理 存储器层次结构 高速缓存存储器 编写高速缓存友好的代码 利用程序中的局部性 存储器层次结构(memory hierarchy) 存储器层次结构中的缓存 高速缓存(cache) 一个小而快速的存储设备 作为存储在更大也更慢的设备中的数据对象的缓冲区域 存储器层次结构的中心思想 位于k层的更快更小的存储设备作为位于k+1层的更大更慢的存储设备的缓存 存储器层次结构中的数据传输 缓存命中 当程序需要第k+1层的某个数据对象d时，它首先在当前存储在第k层的一个块中查找d。 如果d刚好缓存在第k层中，那么就是我们所说的缓存命中(cache hit)。该程序直接从第k层读取d，根据存储器层次结构的性质，这要比从第k+1层读取d更快。 缓存不命中 如果第k层中没有缓存数据对象d，那么就是我们所说的缓存不命中(cache miss)。 当发生cache miss时，第k层的缓存从第k+1层中取出包含d的那个块。 如果第