存储器层次结构课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,提纲,导论,存储技术,局部性原理,存储器层次结构,高速缓存存储器,编写高速缓存友好的代码,利用程序中的局部性,存储器,(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),SRAM,DRAM,描述,静态,RAM,动态,RAM,每位晶体管数,6,1,相对访问时间,1X,10X,持续的,?(,刷新,),Yes,No,敏感的,?(,光电,),No,Yes,相对花费,100X,1X,应用,高速缓存,主存,访问主存,典型的连接,CPU,和主存的总线结构,磁盘存储,提纲,导论,存储技术,局部性原理,存储器层次结构,高速缓存存储器,编写高速缓存友好的代码,利用程序中的局部性,局部性,时间局部性,(temporal locality),被引用过一次的存储器位置很可能在不远的将来再被多次引用,空间局部性,(spatial locality),如果一个存储器位置被引用了一次，那么程序很可能在不远的将来引用附近的一个存储器位置,局部性,有良好局部性的程序运行更快,计算机系统的各个层次都利用了局部性,Cache,主存,作为虚拟地址空间最近被应用块的高速缓存,缓存磁盘文件系统最近使用的磁盘块,Web,浏览器将最近被引用的文档放在本地磁盘上,Web,服务器将最近被请求的文档放在前端磁盘高速缓存中,对程序数据引用的局部性,int sumvec(int vN),int i,sum=0;,for(i=0;iN;i+),sum+=vi;,return sum;,变量,sum,：时间局部性,向量,v,：空间局部性,对程序数据引用的局部性,函数,sumvec,顺序访问一个向量的每个元素，具有步长为,1,的引用模式,步长为,k,的引用模式,(stride-k reference pattern),访问一个连续向量的每第,k,个元素,随着步长的增加，空间局部性下降,引用多维数组,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,局部性差,引用多维数组,int sumarrayrows(int aMN),int i,j,sum=0;,for(i=0;iM;i+),for(j=0;jN;j+),sum+=aij;,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,的那个块。,如果第,k,层的缓存已经满了的话，可能就会覆盖现存的一个块，由缓存的替换策略来控制。,缓存不命中的种类,冷不命中,(cold miss),warmed up,之前,容量不命中,(capacity miss),working set,冲突不命中,(conflict miss),限制性的块放置策略,高速缓存管理,寄存器,编译器,L1,L2 cache,内置在缓存中的硬件逻辑,DRAM,主存,操作系统软件和,CPU,上的地址翻译硬件,本地磁盘缓存网络存储,应用程序,提纲,导论,存储技术,局部性原理,存储器层次结构,高速缓存存储器,编写高速缓存友好的代码,利用程序中的局部性,高速缓存存储器,基于,L1,和,L2,高速缓存的典型总线结构,高速缓存存储器,直接映射高速缓存,(direct-mapped cache),机制比较简单,冲突不命中,全相联高速缓存,(fully associative cache),成本高，容量小,虚拟存储系统翻译备用缓冲器,(TLB),组相联高速缓存,(set associative cache),高速缓存替换策略,随机选择,最不常使用,(least-frequently-used,LFU),替换在过去某个时间窗口内引用次数最少的那一行,最近最少使用,(least-recently-used,LRU),替换最后一次访问时间最久远的那一行,写操作,读操作,很简单,写操作,较复杂,写命中,(write hit),直写,(write-through),立即写到存储器中,增加了总线上的写事务,写回,(write-back),当替换算法要驱逐已更新块时,增加了复杂性,写不命中,(write miss),写分配,(write-allocate),加载存储块到缓存,非写分配,(not-write-allocate),高速缓存性能参数,不命中率,(miss rate),不命中数量,/,引用数量,命中率,(hit rate),命中时间,(hit time),L1:12,个时钟周期,不命中处罚,(miss penalty),L2:510,个周期,主存,:25100,个周期,高速缓存参数的性能影响,高速缓存大小,命中率，命中时间,块大小,空间局部性，时间局部性，不命中处罚,相联度,冲突不命中，命中时间，成本,写策略,高速缓存越往下层，越可能使用写回而不是直写,提纲,导论,存储技术,局部性原理,存储器层次结构,高速缓存存储器,编写高速缓存友好的代码,利用程序中的局部性,编写高速缓存友好,(cache friendly),的代码,局部性比较好的程序,更低的不命中率,运行的更快,基本方法,让最常见的情况运行得更快,在每个循环内部使缓存不命中数量最小,对局部变量的反复引用,步长为,1,的应用模式,测量读带宽,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),double cycles;,int elems=size/sizeof(int);,test(elems,stride);,cycles=fcyc2(test,elems,stride,0);,return(size/stride)/(cycles/Mhz);,重新排列循环以提高空间局部性,NxN,矩阵相乘问题,三个嵌套循环，六个版本,对于性能来说，高速缓存命中率是个关键问题，但存储器访问次数也很重要。,使用分块来提高时间局部性,分块,(blocking),分块的大致思想是将一个程序中的数据结构组织成块，使得能够将一个块加载到,L1,高速缓存中，并在这个块中进行所需要的所有的读和写，然后丢掉这个块，加载下一个块，依此类推。,增强时间局部性,减少容量不命中,分块矩阵乘法,提纲,导论,存储技术,局部性原理,存储器层次结构,高速缓存存储器,编写高速缓存友好的代码,利用程序中的局部性,在程序中利用局部性,-,小结,将你的注意力集中在内部循环上，大部分计算和存储器访问都发生在这里,通过按照数据对象存储顺序来读数据，从而使程序的空间局部性最大,一旦从存储器中读入了一个数据对象，就尽可能地使用它，从而使程序的时间局部性最大,不命中率只是确定代码性能的一个因素，存储器访问数量也扮演着重要角色，需要在两者之间做折中,参考文献,Randal E.Bryant,David OHallaron,“Computer Systems A Programmers Perspective”,