存储器层次结构

1、存储器层次结构第1页，共42页，2022年，5月20日，16点4分，星期二提纲导论存储技术局部性原理存储器层次结构高速缓存存储器编写高速缓存友好的代码利用程序中的局部性第2页，共42页，2022年，5月20日，16点4分，星期二存储器(memory)系统Von Neumann一个线性的字节数组，CPU能够在一个常数时间内访问每个存储器位置实际一个具有不同容量、成本和访问时间的存储(storage)设备层次结构第3页，共42页，2022年，5月20日，16点4分，星期二存储器层次结构CPU registerLatency: 0 cycleCache memory (L1, L2, )Latenc

2、y: 1-10 cycleMain memoryLatency: 50-100 cycleDisk storageLatency: 20 000 000 cycleNetwork storage第4页，共42页，2022年，5月20日，16点4分，星期二计算机程序的局部性(locality)良好局部性的程序重复访问相同的数据项集合倾向于访问临近的数据项集合优化思想使程序要访问的数据项存储在层次结构中较高的地方，在那里CPU能更快的访问到它们。第5页，共42页，2022年，5月20日，16点4分，星期二提纲导论存储技术局部性原理存储器层次结构高速缓存存储器编写高速缓存友好的代码利用程序中的局部性

3、第6页，共42页，2022年，5月20日，16点4分，星期二随机访问存储器(RAM)SRAMDRAM描述静态RAM动态RAM每位晶体管数61相对访问时间1X10X持续的?(刷新)YesNo敏感的?(光电)NoYes相对花费100X1X应用高速缓存主存第7页，共42页，2022年，5月20日，16点4分，星期二访问主存典型的连接CPU和主存的总线结构第8页，共42页，2022年，5月20日，16点4分，星期二磁盘存储第9页，共42页，2022年，5月20日，16点4分，星期二提纲导论存储技术局部性原理存储器层次结构高速缓存存储器编写高速缓存友好的代码利用程序中的局部性第10页，共42页，2022

4、年，5月20日，16点4分，星期二局部性时间局部性(temporal locality)被引用过一次的存储器位置很可能在不远的将来再被多次引用空间局部性(spatial locality)如果一个存储器位置被引用了一次，那么程序很可能在不远的将来引用附近的一个存储器位置第11页，共42页，2022年，5月20日，16点4分，星期二局部性有良好局部性的程序运行更快计算机系统的各个层次都利用了局部性Cache主存作为虚拟地址空间最近被应用块的高速缓存缓存磁盘文件系统最近使用的磁盘块Web浏览器将最近被引用的文档放在本地磁盘上Web服务器将最近被请求的文档放在前端磁盘高速缓存中第12页，共42页，2

5、022年，5月20日，16点4分，星期二对程序数据引用的局部性int sumvec(int vN)int i, sum = 0;for(i=0;iN;i+)sum += vi;return sum;变量sum：时间局部性向量v ：空间局部性第13页，共42页，2022年，5月20日，16点4分，星期二对程序数据引用的局部性函数sumvec顺序访问一个向量的每个元素，具有步长为1的引用模式步长为k的引用模式(stride-k reference pattern)访问一个连续向量的每第k个元素随着步长的增加，空间局部性下降第14页，共42页，2022年，5月20日，16点4分，星期二引用多维数组i

6、nt 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页，共42页，2022年，5月20日，16点4分，星期二引用多维数组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局部性好第16页，共42页，2022年，5月

7、20日，16点4分，星期二局部性小结重复引用同一个变量的程序有良好的时间局部性对于具有步长为k的引用模式的程序，步长越小，空间局部性越好对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好第17页，共42页，2022年，5月20日，16点4分，星期二提纲导论存储技术局部性原理存储器层次结构高速缓存存储器编写高速缓存友好的代码利用程序中的局部性第18页，共42页，2022年，5月20日，16点4分，星期二存储器层次结构(memory hierarchy)第19页，共42页，2022年，5月20日，16点4分，星期二存储器层次结构中的缓存高速缓存(cache)一个小

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

9、16点4分，星期二缓存不命中如果第k层中没有缓存数据对象d，那么就是我们所说的缓存不命中(cache miss)。当发生cache miss时，第k层的缓存从第k+1层中取出包含d的那个块。如果第k层的缓存已经满了的话，可能就会覆盖现存的一个块，由缓存的替换策略来控制。第23页，共42页，2022年，5月20日，16点4分，星期二缓存不命中的种类冷不命中(cold miss)warmed up之前容量不命中(capacity miss)working set冲突不命中(conflict miss)限制性的块放置策略第24页，共42页，2022年，5月20日，16点4分，星期二高速缓存管理寄存器

10、编译器L1,L2 cache内置在缓存中的硬件逻辑DRAM 主存操作系统软件和CPU上的地址翻译硬件本地磁盘缓存网络存储应用程序第25页，共42页，2022年，5月20日，16点4分，星期二提纲导论存储技术局部性原理存储器层次结构高速缓存存储器编写高速缓存友好的代码利用程序中的局部性第26页，共42页，2022年，5月20日，16点4分，星期二高速缓存存储器基于L1和L2高速缓存的典型总线结构第27页，共42页，2022年，5月20日，16点4分，星期二高速缓存存储器直接映射高速缓存(direct-mapped cache)机制比较简单冲突不命中全相联高速缓存(fully associativ

11、e cache)成本高，容量小虚拟存储系统翻译备用缓冲器(TLB)组相联高速缓存 (set associative cache)第28页，共42页，2022年，5月20日，16点4分，星期二高速缓存替换策略随机选择最不常使用(least-frequently-used, LFU)替换在过去某个时间窗口内引用次数最少的那一行最近最少使用(least-recently-used, LRU)替换最后一次访问时间最久远的那一行第29页，共42页，2022年，5月20日，16点4分，星期二写操作读操作 很简单写操作 较复杂写命中(write hit)直写(write-through)立即写到存储器中增加

12、了总线上的写事务写回(write-back)当替换算法要驱逐已更新块时增加了复杂性写不命中(write miss)写分配(write-allocate)加载存储块到缓存非写分配(not-write-allocate)第30页，共42页，2022年，5月20日，16点4分，星期二高速缓存性能参数不命中率(miss rate)不命中数量/引用数量命中率(hit rate)命中时间(hit time)L1 : 12个时钟周期不命中处罚(miss penalty)L2 : 510个周期主存 : 25100个周期第31页，共42页，2022年，5月20日，16点4分，星期二高速缓存参数的性能影响高速缓存

13、大小命中率，命中时间块大小空间局部性，时间局部性，不命中处罚相联度冲突不命中，命中时间，成本写策略高速缓存越往下层，越可能使用写回而不是直写第32页，共42页，2022年，5月20日，16点4分，星期二提纲导论存储技术局部性原理存储器层次结构高速缓存存储器编写高速缓存友好的代码利用程序中的局部性第33页，共42页，2022年，5月20日，16点4分，星期二编写高速缓存友好(cache friendly)的代码局部性比较好的程序更低的不命中率运行的更快基本方法让最常见的情况运行得更快在每个循环内部使缓存不命中数量最小对局部变量的反复引用步长为1的应用模式第34页，共42页，2022年，5月20日

14、，16点4分，星期二测量读带宽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/strid

15、e)/(cycles/Mhz);第35页，共42页，2022年，5月20日，16点4分，星期二重新排列循环以提高空间局部性NxN矩阵相乘问题三个嵌套循环，六个版本对于性能来说，高速缓存命中率是个关键问题，但存储器访问次数也很重要。第36页，共42页，2022年，5月20日，16点4分，星期二使用分块来提高时间局部性分块(blocking)分块的大致思想是将一个程序中的数据结构组织成块，使得能够将一个块加载到L1高速缓存中，并在这个块中进行所需要的所有的读和写，然后丢掉这个块，加载下一个块，依此类推。增强时间局部性减少容量不命中第37页，共42页，2022年，5月20日，16点4分，星期二分块矩阵乘法第38页，共42页，2022年，5月20日，16点4分，星期二提纲导论存储技术局部性原理存储器层次结构高速缓存存储器编写高速缓存友好的代码利用程序中的局部性第39页，共42页，2022年，5月20日，16点4分，星期二在程序中利用局部性-小结将你的注意力集中在内部循环上，大部分计算和存储器访问都发生在这里通过按照数据对象存储顺序来读数据，从而使程序的空间局部性最大一旦从存储器中读入了一个数据对象，就尽可能地