存储器层次结构.ppt

《存储器层次结构.ppt》由会员分享，可在线阅读，更多相关《存储器层次结构.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、关于存储器层次结构现在学习的是第1页，共43页提纲 导论 存储技术 局部性原理 存储器层次结构 高速缓存存储器 编写高速缓存友好的代码 利用程序中的局部性现在学习的是第2页，共43页存储器(memory)系统 Von Neumann一个线性的字节数组，CPU能够在一个常数时间内访问每个存储器位置 实际一个具有不同容量、成本和访问时间的存储(storage)设备层次结构现在学习的是第3页，共43页存储器层次结构 CPU registerLatency:0 cycle Cache memory(L1,L2,)Latency:1-10 cycle Main memoryLatency:50-100

2、cycle Disk storageLatency:20 000 000 cycle Network storage现在学习的是第4页，共43页计算机程序的局部性(locality)良好局部性的程序重复访问相同的数据项集合倾向于访问临近的数据项集合 优化思想使程序要访问的数据项存储在层次结构中较高的地方，在那里CPU能更快的访问到它们。现在学习的是第5页，共43页提纲 导论 存储技术 局部性原理 存储器层次结构 高速缓存存储器 编写高速缓存友好的代码 利用程序中的局部性现在学习的是第6页，共43页随机访问存储器(RAM)SRAMDRAM描述静态RAM动态RAM每位晶体管数61相对访问时间1X1

3、0X持续的?(刷新)YesNo敏感的?(光电)NoYes相对花费100X1X应用高速缓存主存现在学习的是第7页，共43页访问主存 典型的连接CPU和主存的总线结构现在学习的是第8页，共43页磁盘存储现在学习的是第9页，共43页提纲 导论 存储技术 局部性原理 存储器层次结构 高速缓存存储器 编写高速缓存友好的代码 利用程序中的局部性现在学习的是第10页，共43页局部性 时间局部性(temporal locality)被引用过一次的存储器位置很可能在不远的将来再被多次引用 空间局部性(spatial locality)如果一个存储器位置被引用了一次，那么程序很可能在不远的将来引用附近的一个存储器

4、位置现在学习的是第11页，共43页局部性 有良好局部性的程序运行更快 计算机系统的各个层次都利用了局部性Cache主存 作为虚拟地址空间最近被应用块的高速缓存 缓存磁盘文件系统最近使用的磁盘块Web浏览器将最近被引用的文档放在本地磁盘上Web服务器将最近被请求的文档放在前端磁盘高速缓存中现在学习的是第12页，共43页对程序数据引用的局部性int sumvec(int vN)int i,sum=0;for(i=0;iN;i+)sum+=vi;return sum;变量sum：时间局部性 向量v ：空间局部性现在学习的是第13页，共43页对程序数据引用的局部性 函数sumvec顺序访问一个向量的每

5、个元素，具有步长为1的引用模式 步长为k的引用模式(stride-k reference pattern)访问一个连续向量的每第k个元素 随着步长的增加，空间局部性下降现在学习的是第14页，共43页引用多维数组int sumarraycols(int aMN)int i,j,sum=0;for(j=0;jN;j+)for(i=0;iM;i+)sum+=aij;return sum 按列优先顺序访问(col-major order)步长为N 局部性差现在学习的是第15页，共43页引用多维数组int sumarrayrows(int aMN)int i,j,sum=0;for(i=0;iM;i+)

6、for(j=0;jN;j+)sum+=aij;return sum 按行优先顺序访问(row-major order)步长为1 局部性好现在学习的是第16页，共43页局部性小结 重复引用同一个变量的程序有良好的时间局部性 对于具有步长为k的引用模式的程序，步长越小，空间局部性越好 对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好现在学习的是第17页，共43页提纲 导论 存储技术 局部性原理 存储器层次结构 高速缓存存储器 编写高速缓存友好的代码 利用程序中的局部性现在学习的是第18页，共43页存储器层次结构(memory hierarchy)现在学习的是第1

7、9页，共43页存储器层次结构中的缓存 高速缓存(cache)一个小而快速的存储设备作为存储在更大也更慢的设备中的数据对象的缓冲区域 存储器层次结构的中心思想位于k层的更快更小的存储设备作为位于k+1层的更大更慢的存储设备的缓存现在学习的是第20页，共43页存储器层次结构中的数据传输现在学习的是第21页，共43页缓存命中 当程序需要第k+1层的某个数据对象d时，它首先在当前存储在第k层的一个块中查找d。如果d刚好缓存在第k层中，那么就是我们所说的缓存命中(cache hit)。该程序直接从第k层读取d，根据存储器层次结构的性质，这要比从第k+1层读取d更快。现在学习的是第22页，共43页缓存不命

8、中 如果第k层中没有缓存数据对象d，那么就是我们所说的缓存不命中(cache miss)。当发生cache miss时，第k层的缓存从第k+1层中取出包含d的那个块。如果第k层的缓存已经满了的话，可能就会覆盖现存的一个块，由缓存的替换策略来控制。现在学习的是第23页，共43页缓存不命中的种类 冷不命中(cold miss)warmed up之前 容量不命中(capacity miss)working set 冲突不命中(conflict miss)限制性的块放置策略现在学习的是第24页，共43页高速缓存管理寄存器编译器L1,L2 cache内置在缓存中的硬件逻辑DRAM 主存操作系统软件和CP

9、U上的地址翻译硬件本地磁盘缓存网络存储应用程序现在学习的是第25页，共43页提纲 导论 存储技术 局部性原理 存储器层次结构 高速缓存存储器 编写高速缓存友好的代码 利用程序中的局部性现在学习的是第26页，共43页高速缓存存储器 基于L1和L2高速缓存的典型总线结构现在学习的是第27页，共43页高速缓存存储器 直接映射高速缓存(direct-mapped cache)机制比较简单冲突不命中 全相联高速缓存(fully associative cache)成本高，容量小虚拟存储系统翻译备用缓冲器(TLB)组相联高速缓存(set associative cache)现在学习的是第28页，共43页高

10、速缓存替换策略 随机选择 最不常使用(least-frequently-used,LFU)替换在过去某个时间窗口内引用次数最少的那一行 最近最少使用(least-recently-used,LRU)替换最后一次访问时间最久远的那一行现在学习的是第29页，共43页写操作 读操作 很简单 写操作 较复杂写命中(write hit)直写(write-through)立即写到存储器中增加了总线上的写事务 写回(write-back)当替换算法要驱逐已更新块时增加了复杂性写不命中(write miss)写分配(write-allocate)加载存储块到缓存 非写分配(not-write-allocate

11、)现在学习的是第30页，共43页高速缓存性能参数 不命中率(miss rate)不命中数量/引用数量 命中率(hit rate)命中时间(hit time)L1:12个时钟周期 不命中处罚(miss penalty)L2:510个周期主存:25100个周期现在学习的是第31页，共43页高速缓存参数的性能影响 高速缓存大小命中率，命中时间 块大小空间局部性，时间局部性，不命中处罚 相联度冲突不命中，命中时间，成本 写策略高速缓存越往下层，越可能使用写回而不是直写现在学习的是第32页，共43页提纲 导论 存储技术 局部性原理 存储器层次结构 高速缓存存储器 编写高速缓存友好的代码 利用程序中的局部

12、性现在学习的是第33页，共43页编写高速缓存友好(cache friendly)的代码 局部性比较好的程序更低的不命中率运行的更快 基本方法让最常见的情况运行得更快在每个循环内部使缓存不命中数量最小 对局部变量的反复引用 步长为1的应用模式现在学习的是第34页，共43页测量读带宽void test(int elems,int stride)int i,result=0;volatile int sink;for(i=0;ielems;i+=stride)result+=datai;sink=result;double run(int size,int stride,double Mhz)dou

13、ble cycles;int elems=size/sizeof(int);test(elems,stride);cycles=fcyc2(test,elems,stride,0);return(size/stride)/(cycles/Mhz);现在学习的是第35页，共43页重新排列循环以提高空间局部性 NxN矩阵相乘问题 三个嵌套循环，六个版本 对于性能来说，高速缓存命中率是个关键问题，但存储器访问次数也很重要。现在学习的是第36页，共43页使用分块来提高时间局部性 分块(blocking)分块的大致思想是将一个程序中的数据结构组织成块，使得能够将一个块加载到L1高速缓存中，并在这个块中进

14、行所需要的所有的读和写，然后丢掉这个块，加载下一个块，依此类推。增强时间局部性减少容量不命中现在学习的是第37页，共43页分块矩阵乘法111211121112212221222122 CABCCAABBCCAABB现在学习的是第38页，共43页提纲 导论 存储技术 局部性原理 存储器层次结构 高速缓存存储器 编写高速缓存友好的代码 利用程序中的局部性现在学习的是第39页，共43页在程序中利用局部性-小结将你的注意力集中在内部循环上，大部分计算和存储器访问都发生在这里 通过按照数据对象存储顺序来读数据，从而使程序的空间局部性最大 一旦从存储器中读入了一个数据对象，就尽可能地使用它，从而使程序的时间局部性最大不命中率只是确定代码性能的一个因素，存储器访问数量也扮演着重要角色，需要在两者之间做折中现在学习的是第40页，共43页参考文献 Randal E.Bryant,David OHallaron,“Computer Systems A Programmers Perspective”现在学习的是第41页，共43页Thank You!现在学习的是第42页，共43页感谢大家观看感谢大家观看现在学习的是第43页，共43页