高速缓存(cache)的原理: 了解计算机架构与性能优化 |
您所在的位置：网站首页 › 缓存设备 › 高速缓存(cache)的原理: 了解计算机架构与性能优化 |
高速缓存(cache)的原理: 了解计算机架构与性能优化
|
计基之存储器层次结构
Author： Once Day Date： 2023年5月9日 长路漫漫，而今才刚刚启程！ 本内容收集整理于《深入理解计算机系统》一书。 参看文档: 捋一捋Cache - 知乎 (zhihu.com)iCache和dCache一致性 - 知乎 (zhihu.com)Cache设计总结 - 知乎 (zhihu.com) 文章目录 计基之存储器层次结构1. 概述1.1 随机访问存储器(Random-Access Memory, RAM)1.2 局部性原理(principle of locality)1.3 缓存(caching) 2. 高速缓存存储器2.1 通用高速缓存存储器的组织结构2.2 直接映射高速缓存(direct-mapped cache)2.3 直接映射高速缓存实例分析2.4 组相联高速缓存(set associative cache)2.5 全相联高速缓存 3. 高速缓存性能分析3.1 写回问题3.2 真实缓存结构的剖析3.3 高速缓存参数的性能影响3.4 编写对高速缓存友好的代码3.5 分块(blocking)技术 1. 概述在理想的环境下，存储器系统是一个线性的字节数组，而CPU能够在一个常数时间内访问每个存储器的位置。
但实际上，存储器系统(memory system)是一个具有不同容量、成本和访问时间的存储设备的层次结构： CPU寄存器保存着最常用的数据。接着是小的、快速的高速缓存存储器(cache memory).然后是慢速，但容量较大的主存储器(main memory)，里面存着指令和数据。再往下就是容量更大的磁盘、硬盘、云盘、磁带、网络等等实际或虚拟存储器。
程序一般偏向局部性原理，因此在大多时候，访问的都是某一段位置的内容，这意味这种层次的结构，可以在成本和效率之间取得良好的平衡。 一般而言，存储在寄存器上的数据，0个周期就可以直接访问，存在高速缓存的数据需要4~75个周期，主存的数据需要上百个周期，而在磁盘上的数据，可能需要上百万个周期才能访问。 1.1 随机访问存储器(Random-Access Memory, RAM)随机访问存储器分为两类：静态SRAM和动态DRAM。SRAM一般更贵，因此其容量较小，一般为几兆字节。 静态SRAM将每个位存储在一个双稳态的存储器单元里，每个单元是利用一个晶体管电路实现的，该电路有一个属性，可以无限期地保存在两个不同的电压配置或者状态下，其他任何状态都是不稳定的。即使遭遇电子噪声，也可以恢复到稳定状态。 动态DRAM将每个位使用电容存储，其更加敏感，有很多原因导致其电容电压改变，因此需要周期性刷新每一个位的值(数十毫秒)。 1.2 局部性原理(principle of locality)一个编程良好的计算机程序常常具有良好的局部性(locality)，倾向于引用邻近于其他最近引用过的数据项，或者最近引用过的数据项本身。通常有如下两种形式: 时间局部性(temporal locality)，被引用过一次的内存位置在不远的将来再被多次引用。空间局部性(spatial locality)，一个内存位置被引用了一次，那么程序可能将不远的将来引用附近的位置。局部性原理是一种通用的性能优化技巧，有良好局部性的程序比局部性差的程序运行得快。例如硬件高速缓存，操作系统用DRAM来缓存磁盘内容。 下面是一个数据引用局部性的例子，二维数组求和： # 步长为1 for (int i = 0; i < M; i++){ for (int j = 0; j < N; j++) { sum += g_data[i][j]; } } # 步长为N=1000=M for (int i = 0; i < M; i++){ for (int j = 0; j < N; j++) { sum += g_data[j][i]; } }在测试设备上，步长1的耗费时间仅为步长N的三分之一。 像第一个循环这样的顺序访问一个向量的每个元素，认为其具有步长为1的引用模式(stride-1 reference pattern)，步长为1的引用模式也称为顺序引用模式(sequential reference pattern)。随着步长增加，空间局部性下降。 一般局部性的基本思想如下： 重复引用相同的变量具有良好的时间局部性。对于具有步长为k的引用模式程序，步长越小，空间局部性越好。对于取指令来说，循环有好的时间和空间局部性。 1.3 缓存(caching)一般而言，高速缓存(cache)是一个小而快速的存储设备，作为存储在更大，也更慢的设备中的数据对象的缓冲区域。使用高速缓存的过程称为缓存(caching)。 缓存命中：当程序需要K+1层的某个数据对象d时，如果d刚好缓存在第k层中。 缓存不命中：如果第K+1层中没有缓存数据对象d，那么就是缓存不命中(cache miss)。 当发现缓存不命中时，第K层的缓存会去第K-1层中取出包含d的那个块，如果第k层的缓存已经满了，可能就会覆盖现存的一个块。 覆盖现存块的过程称为替换(replacing)或驱逐(evicting)这个块。被驱逐的块也有时被称为牺牲块(victim block)。 决定替换哪个块是由缓存的替换策略决定的，如随机替换和最少使用替换。 缓存不命中有如下种类: 空缓存一般称为冷缓存(cold cache)，此类不命中称为强制性不命中(compulsory miss)或冷不命中(cold miss)。限制性的放置策略同样会引起不命中，称为冲突不命中(conflict miss)，因此这些数据对象会映射到同一个块中。程序每个阶段访问的缓存块集合是不一样的，即工作集。当工作集大小超过缓存大小时，缓存会经历容量不命中(capacity miss)。一般L1/L2/L3高速缓存都是按照64字节的内存块来缓存。 2. 高速缓存存储器 2.1 通用高速缓存存储器的组织结构假设一个计算机系统，其每个存储器地址有m位，形成 M = 2 m M=2^m M=2m个不同的地址。
然后机器的高速缓存被组织成一个有 S = 2 s S=2^s S=2s个高速缓存组(cache set)的数组，每个组包含E个高速缓存行(cache line)。每一个行都是由一个 B = 2 b B=2^b B=2b字节的数据块(block)组成，一个有效位(valid bit)指明这个行是否包含有意义的信息，还有 t = m − ( b + s ) t=m-(b+s) t=m−(b+s)个标记位(tag bit)，是当前块的内存地址的位的一个子集，唯一标识存储在这个高速缓存行中的块。 高速缓存的结构一般可以用元组(S, E, B, m)来描述，高速缓存的容量指的是所有块的大小的和，标记位和有效位不包括在内，因此 C = S ∗ E ∗ B C=S*E*B C=S∗E∗B。 高速缓存将m位的地址划分成以下的结构: |-(高位)--------------m位------------(低位)-| |--标记(t位)--|--组索引(s位)--|--块偏移(b位)--|一般有以下的符号参数: 参数描述衍生量 S = 2 s S=2^s S=2s组数 s = l o g 2 ( S ) s=log_2(S) s=log2(S)，组索引位数量E每个组的行数 B = 2 b B=2^b B=2b块大小(字节) b = l o g 2 ( B ) b=log_2(B) b=log2(B)，块偏移位数量 m = l o g 2 ( M ) m=log_2(M) m=log2(M)(主存)物理地址位数 t = m − ( s + b ) t=m-(s+b) t=m−(s+b), 标记位数量 2.2 直接映射高速缓存(direct-mapped cache)根据每个组的高速缓存行数E，高速缓存被分为不同的类。每个组只有一行(E=1)的高速缓存称为直接映射高速缓存。
对于一个简单的系统，如cpu+寄存器+L1缓存+DRAM。当CPU执行一个读取内存字w的指令时，它向L1高速缓存请求这个字，如果L1高速缓存有w的一个缓存的副本，那么就得到L1高速缓存命中。 如果高速缓存不命中，此时L1高速缓存会向主存DRAM请求包含w块的一个副本时，CPU必须等待。 最终L1高速缓存里面会包含w块的一个副本，然后从该缓存块中抽出字w，并返回给CPU。 缓存确定一个请求是否命中，然后抽出来被请求字的过程，分为三步: (1) 组选择(2) 行匹配(3) 字抽取如下所示，直接从w的地址中间抽取出s个组索引位，这些位被解释成一个对应于一个组号的无符号整数。
利用s个组索引位组成的索引，即可找到对应的缓存块。对于直接映射高速缓存，因为每组只有一行，因此直接判断有效位和标记是否匹配。如果有效位被设置，且标记匹配，那么这一行中包含w的一个副本。
如上所示，如果(1)(2)两步判断不成立，那么就是缓存不命中。地址的最低几位是块偏移位，其大小受块大小限制，一般的cache line大小是64字节，因此偏移位一般为6位。 直接映射高速缓存不命中时的行替换策略很简单，直接用新取出来的行替换当前行即可。 2.3 直接映射高速缓存实例分析加深对高速缓存运行过程的理解，最好的方式是实际模拟一下具体的情况。 假设一个实例如下: ( S , E , B , m ) = ( 4 , 1 , 2 , 4 ) (S,E,B,m) = (4,1,2,4) (S,E,B,m)=(4,1,2,4) 即高速缓存有4个组，每个组一行，每一行的缓存块有2个字节，地址位有4位，字长(word)为1个字节。下面列出全部情况: 地址m标记位(t=1)索引位(s=2)(二进制)偏移位(b=1)块号000000100010200101300111401002501012601103701113810004910014101010511101151211006131101614111071511117从上图可以看出: 标记位和索引位唯一标识了内存中的每个块。一共有8个块，但只有4个高速缓存组，因此多个块会映射到同一个高速缓存组中，这些块具有相同的组索引。映射到同一个高速缓存组的块由标记位唯一标识。下面执行一次模拟运行: 初始时，高速缓存是空的，因此四个缓存组情况如下: |---组---|---有效位----|----标记位----|----块[0]----|----块[1]----| 0 0 1 0 2 0 3 0读取地址0的字，此时发生缓存不命中，属于cold cache，此时高速缓存从内存中取出块0，并把这个块存储在组0中，即地址m[0]和m[1]的内容，然后返回m[0]的内容。 |---组---|---有效位----|----标记位----|----块[0]----|----块[1]----| 0 1 0 m[0] m[1] 1 0 2 0 3 0读取地址1的字，此时命令高速缓存，因此直接从高速缓存组[0]的块[1]中拿取m[1]的值。 读取地址13的字，由于组[2]中高速缓存行不是有效的，所以有缓存不命中，高速缓存行把块[6]加载到组[2]中，然后从新的高速缓存行组[2]的块[1]中返回m[13]。 |---组---|---有效位----|----标记位----|----块[0]----|----块[1]----| 0 1 0 m[0] m[1] 1 0 2 1 1 m[12] m[13] 3 0读取地址8的字，这会发生缓存不命中，组0中的高速缓存行虽然有效，但标记不匹配，高速缓存将块4加载到组0中，替换原来的数据，然后从新的块[0]中返回m[8]。 |---组---|---有效位----|----标记位----|----块[0]----|----块[1]----| 0 1 1 m[8] m[9] 1 0 2 1 1 m[12] m[13] 3 0读取地址0的字，这又会发生缓存不命中，前面替换过块0。这是典型的容量足够，但由于缓存冲突造成的不命中。 这种高速缓存反复地加载和驱逐相同的高速缓存块的组的现象，一般称为抖动。如下所示: float dotprod(float x[8], float y[8]) { float sum =0.0; int i; for (i = 0; i < 8; i++) { sum += x[i] * y[i]; } return sum; }虽然上面这个函数具有良好的空间局部性，但是如果x地址和y地址之差刚好等于高速缓存大小的整数倍，那么就会映射到同一个缓存组上，容易产生缓存冲突。 2.4 组相联高速缓存(set associative cache)直接映射高速缓存中冲突不命中造成的问题源于每个组只有一行，组相联高速缓存放松了该限制，每个组都保存有多于一个的高速缓存行，即 1 < E < C / B 1 |
【本文地址】