门户网站建设 报告,辽宁建设网站首页,哈尔滨专业做网站公司,珠海企业免费建站计基之存储器层次结构
Author#xff1a; Once Day Date#xff1a; 2023年5月9日
长路漫漫#xff0c;而今才刚刚启程#xff01;
本内容收集整理于《深入理解计算机系统》一书。
参看文档:
捋一捋Cache - 知乎 (zhihu.com)iCache和dCache一致性 - 知乎 (zhihu.com)C…计基之存储器层次结构
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];}
}
# 步长为N1000M
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)。
缓存命中当程序需要K1层的某个数据对象d时如果d刚好缓存在第k层中。
缓存不命中如果第K1层中没有缓存数据对象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 M2^m M2m个不同的地址。 然后机器的高速缓存被组织成一个有 S 2 s S2^s S2s个高速缓存组(cache set)的数组每个组包含E个高速缓存行(cache line)。每一个行都是由一个 B 2 b B2^b B2b字节的数据块(block)组成一个有效位(valid bit)指明这个行是否包含有意义的信息还有 t m − ( b s ) tm-(bs) tm−(bs)个标记位(tag bit)是当前块的内存地址的位的一个子集唯一标识存储在这个高速缓存行中的块。
高速缓存的结构一般可以用元组(S, E, B, m)来描述高速缓存的容量指的是所有块的大小的和标记位和有效位不包括在内因此 C S ∗ E ∗ B CS*E*B CS∗E∗B。
高速缓存将m位的地址划分成以下的结构:
|-(高位)--------------m位------------(低位)-|
|--标记(t位)--|--组索引(s位)--|--块偏移(b位)--|一般有以下的符号参数:
参数描述衍生量 S 2 s S2^s S2s组数 s l o g 2 ( S ) slog_2(S) slog2(S)组索引位数量E每个组的行数 B 2 b B2^b B2b块大小(字节) b l o g 2 ( B ) blog_2(B) blog2(B)块偏移位数量 m l o g 2 ( M ) mlog_2(M) mlog2(M)(主存)物理地址位数 t m − ( s b ) tm-(sb) tm−(sb), 标记位数量
2.2 直接映射高速缓存(direct-mapped cache)
根据每个组的高速缓存行数E高速缓存被分为不同的类。每个组只有一行(E1)的高速缓存称为直接映射高速缓存。 对于一个简单的系统如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标记位(t1)索引位(s2)(二进制)偏移位(b1)块号000000100010200101300111401002501012601103701113810004910014101010511101151211006131101614111071511117
从上图可以看出:
标记位和索引位唯一标识了内存中的每个块。一共有8个块但只有4个高速缓存组因此多个块会映射到同一个高速缓存组中这些块具有相同的组索引。映射到同一个高速缓存组的块由标记位唯一标识。
下面执行一次模拟运行: 初始时高速缓存是空的因此四个缓存组情况如下: |---组---|---有效位----|----标记位----|----块[0]----|----块[1]----|0 01 02 03 0读取地址0的字此时发生缓存不命中属于cold cache此时高速缓存从内存中取出块0并把这个块存储在组0中即地址m[0]和m[1]的内容然后返回m[0]的内容。 |---组---|---有效位----|----标记位----|----块[0]----|----块[1]----|0 1 0 m[0] m[1]1 02 03 0读取地址1的字此时命令高速缓存因此直接从高速缓存组[0]的块[1]中拿取m[1]的值。 读取地址13的字由于组[2]中高速缓存行不是有效的所以有缓存不命中高速缓存行把块[6]加载到组[2]中然后从新的高速缓存行组[2]的块[1]中返回m[13]。 |---组---|---有效位----|----标记位----|----块[0]----|----块[1]----|0 1 0 m[0] m[1]1 02 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 02 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 1EC/B 1EC/B称为E路组相连高速缓存。
组相连高速缓存的组选择和直接映射高速缓存没有区别都是使用组索引位标识组。
不同的是组相连高速缓存中每个组有多个行可以将每个组看成一个相连存储器即(key, value)的数组返回对应的value值key即由标记位和有效位组成。
组相连高速缓存的每个组中任何一行都可以包含任何映射到这个组的内存块因此高速缓存必须搜索组中的每一个行寻找一个有效的行其标记与地址中的标记相匹配。
如果CPU请求的字不在组的任何一行中那么就是缓存不命中高速缓存必须从内核中取出包含这个字的块。如果该组中存在空行那么直接替换空行是个不错的选择。
如果该组中没有空行必须从中选择一个非空的行策略一般如下(一般代码编程是无需关心此点):
随机替换策略最不常使用策略(Least-Frequently)最近最少使用策略(Least-Recently-Used, LRU)
2.5 全相联高速缓存
全相联高速缓存(fully associative cache)是由一个包含所有高速缓存行的组( E C / B EC/B EC/B)组成的。
全相联高速缓存中的组选择非常简单因为只有一个组地址中没有组索引位地址只被划分为一个标记和一个块偏移。
全相联高速缓存的行匹配和字选择与组相联高速缓存是一致的但是构建一个又大又快的全相联高速缓存很困难一般来说容量较小。典型的例子是虚拟内存系统中的翻译备用缓冲器(TLB)。
3. 高速缓存性能分析
3.1 写回问题
相比较于读取高速缓存写回的问题会更加复杂一些。
假设写一个已经缓存的字w(写命中write hit)在高速缓存更新了它的w副本以后如何更新更低层次的副本呢如下:
直写(write-through)最简单的方法就是立即将w的高速缓存块写回到紧接着的低一层中。缺点是每次都会引起总线流量。写回(write-back)尽可能推迟更新只有当替换算法要驱逐这个更新过的块时才把它写到紧接着的低一层中。缺点是会增加处理逻辑的复杂性。
当面临写不命中时有以下的处理方法:
写分配(write-allocate)加载相应的低一层块到高速缓存中然后更新这个高速缓存块。该方法试图利用写的空间局部性但是缺点是每次不命中都会导致一个块从低一层传送到高速缓存。非写分配(not-write-allocate)避开高速缓存直接把这个字写到低一层中。
直接高速缓存通常是非写分配的写回高速缓存通常是写分配的。
现代CPU的高速缓存一般使用写回策略。写回策略是指在修改高速缓存中的数据时不立即写回主存而是将修改后的数据标记为“脏数据”并等待下一次需要替换该缓存行时再将脏数据写回主存。这种策略可以减少对主存的写入次数提高系统性能。
相比之下直写策略则是在修改高速缓存中的数据时立即将其写回主存这会导致频繁的主存写入降低系统性能。
因此写回策略通常比直写策略更为常见也更为优秀。但是写回策略也可能会导致数据不一致的问题需要进行合理的缓存一致性协议设计来解决。
一般可以假设现代系统使用写回和写分配的方式这与读取的方式对称(但具体细节仍和处理器细节有关)。
其次可以在高层次开发我们的程序展示良好的空间和时间局部性而不是试图为某个存储器进行优化。
3.2 真实缓存结构的剖析
只保存指令的高速缓存称为i-cache只保存程序数据的高速缓存称为d-cache既保存数据也保存命令的高速缓存称为统一的高速缓存(unified cache)。
i-cache 的优点
加速指令的获取i-cache 可以缓存 CPU 需要执行的指令减少了从主存中获取指令的时间从而提高了程序的执行速度。减少指令访问冲突由于指令通常是按照程序的执行顺序依次执行的因此 i-cache 的访问模式比较规律不容易出现访问冲突。
i-cache 的缺点
浪费一部分缓存容量由于指令通常是按照程序的执行顺序依次执行的因此 i-cache 中存储的指令可能会比较连续这导致了一些缓存行可能存储的是不必要的指令从而浪费了一部分缓存容量。缓存失效对程序的影响较大如果 i-cache 中的缓存行失效CPU 就需要从主存中重新获取指令这会导致较大的性能损失。
d-cache 的优点
加速数据的读写d-cache 可以缓存 CPU 需要读写的数据减少了从主存中获取数据的时间从而提高了程序的执行速度。支持多种访问模式与 i-cache 不同d-cache 中存储的数据可能会被多个线程或者进程同时访问因此 d-cache 支持多种访问模式包括读、写、读写等模式能够更好地适应多线程程序的需求。
d-cache 的缺点
容易出现访问冲突由于数据的访问模式比较随机因此 d-cache 的访问模式比较不规律容易出现访问冲突从而影响程序的执行效率。可能会出现一致性问题由于 d-cache 中存储的是 CPU 需要修改的数据如果多个线程或进程同时访问同一块数据就可能出现一致性问题。为了解决这个问题需要采用一些同步机制例如锁或原子操作等这会增加程序的复杂度和开销。
下面是Intel Core i7处理器的高速缓存层次结构用于参考(来自《深入理解计算机》第六章)。 相关数据总结如下:
高速缓存类型访问时间(周期)高速缓存大小©相联度(E)块大小(B)组数(S)L1 i-cache432KB864B64L1 d-cache432KB864B64L2统一的高速缓存10256KB864B512L3统一的高速缓存40~758MB1664B8192
3.3 高速缓存参数的性能影响
下面是常见的衡量高速缓存性能的指标:
不命中率(miss rate)指在访问高速缓存时所需数据在缓存中找到的次数hits相比于没有找到的次数(不命中数量/引用数量)。命中率(hit rate)命中内存引用比率它等于1 - 不命中率。命中时间(hit time)从高速缓存传送一个字到CPU所需的时间包括组选择、行确认和字选择的时间。对于L1高速缓存来说 命中时间的数量级是几个时钟周期。不命中处罚(miss penalty)由于不命中所需要的额外时间L1不命中需要从L2得到服务的处罚通常是数10个周期从L3得到服务的处罚50个周期从主存得到服务的处罚200个周期。
高速缓存的大小、块大小、相联度和写策略等指标都会对高速缓存的性能产生影响具体如下
高速缓存大小高速缓存大小是指缓存可以存储的数据量。缓存大小越大可以缓存的数据就越多命中率也有可能更高。但是缓存大小也受到制造成本和功耗等因素的限制。块大小块大小是指高速缓存中每个缓存块可以存储的数据量。块大小的选择会影响缓存的命中率和访问延迟。较小的块大小可以提高命中率因为可以更精细地缓存数据但会增加访问延迟和标签存储器的开销。较大的块大小可以减少访问延迟但会降低命中率因为每次缓存块的替换会导致更多的数据失效从而降低命中率。相联度相联度是指高速缓存中每个缓存块可以映射到多少个缓存行中。相联度的选择会影响缓存的命中率和访问延迟。较低的相联度可以减少访问延迟因为每个缓存块只需要查找一个缓存行就可以了但会降低命中率因为如果多个缓存块映射到同一个缓存行中就会发生冲突。较高的相联度可以提高命中率因为每个缓存块可以映射到多个缓存行中从而减少了冲突但会增加访问延迟和标签存储器的开销。写策略写策略是指当 CPU 对缓存进行写操作时缓存如何处理数据的更新。常见的写策略有写回和写直两种。写回策略是指当 CPU 对缓存进行写操作时数据先被写入到缓存中而不是立即写入主存。这样可以减少对主存的访问提高性能。但也会增加缓存的复杂度和一致性问题。写直策略是指当 CPU 对缓存进行写操作时数据会直接被写入到主存中。这样可以保证数据的一致性但会增加对主存的访问降低性能。
3.4 编写对高速缓存友好的代码
高速缓存友好(cache friendly)的代码首先要具备良好的局部性核心原则有两个:
让最常见的情况运行得快忽略一些细枝末节的路径专注于最核心的路径。尽量减少每个循环内部的缓存不命中数量。
编写缓存友好的代码是一种优化技术旨在最大化高速缓存的使用效率从而提高程序的性能。以下是一些编写缓存友好的代码的实践方法
空间局部性高速缓存通常是以缓存块为单位进行管理的因此如果程序中的数据访问模式比较局部即对相邻的数据进行访问就可以提高缓存的命中率。时间局部性高速缓存中存储的数据通常是最近访问过的数据。因此如果程序中的数据访问模式比较重复即对同一块数据进行多次访问就可以提高缓存的命中率。数据对齐高速缓存通常是按照缓存块的大小进行管理的因此如果程序中的数据没有对齐到缓存块的边界就会导致跨越缓存块边界的访问从而降低缓存的命中率和性能。循环展开循环展开是一种优化技术可以将循环中的代码复制多次以减少循环的迭代次数从而提高程序的性能。循环展开可以提高空间局部性和时间局部性从而提高缓存的命中率和性能。编写缓存友好的算法一些算法具有良好的缓存局部性例如矩阵乘法和卷积等算法。避免缓存污染缓存污染是指缓存中存储了不必要的数据从而降低了缓存的命中率和性能。可以使用局部变量和静态变量等技术以减少对全局变量和动态分配内存的访问从而提高缓存的命中率和性能。避免缓存冲突缓存冲突是指多个数据映射到同一个缓存块中从而导致数据的互相替换降低缓存的命中率和性能。可以使用不同的数据结构和算法等技术以减少数据的冲突从而提高缓存的命中率和性能。
3.5 分块(blocking)技术
分块技术Blocking是一种用于提高时间局部性temporal locality的优化技术。时间局部性描述了程序在一段时间内多次访问相同数据的趋势。利用时间局部性可以减少缓存未命中cache miss的数量从而提高程序的执行速度。
分块技术的核心思想是将大的数据结构划分为较小的块block以便它们可以适应缓存的大小。访问这些较小的块时程序会在较短的时间内多次访问相同的数据从而提高缓存利用率。分块技术在许多领域都有应用例如矩阵乘法、图像处理和数据库查询优化等。
下面以矩阵乘法为例介绍如何使用分块技术提高时间局部性。
假设我们有两个矩阵 A 和 B它们的大小分别为 N x N。我们要计算这两个矩阵的乘积 C A x B。传统的矩阵乘法算法如下
for i in range(N):for j in range(N):for k in range(N):C[i][j] A[i][k] * B[k][j]这种实现方式存在缓存未命中的问题因为数据访问的局部性较差。为了提高时间局部性我们可以使用分块技术将矩阵 A、B 和 C 划分为较小的子矩阵。假设我们使用 blockSize x blockSize 的块大小分块后的矩阵乘法算法如下
for i in range(0, N, blockSize):for j in range(0, N, blockSize):for k in range(0, N, blockSize):for ii in range(i, min(i blockSize, N)):for jj in range(j, min(j blockSize, N)):for kk in range(k, min(k blockSize, N)):C[ii][jj] A[ii][kk] * B[kk][jj]通过这种方式我们将大矩阵划分为较小的子矩阵并在子矩阵间进行计算。这样可以提高缓存利用率因为在较短时间内会多次访问相同的数据。同时分块技术可以根据硬件特性调整 blockSize 的大小以适应不同的缓存结构。
需要注意的是分块技术并不总是能提高性能它需要根据特定的程序和硬件环境进行优化。在实际应用中程序员需要对所处理的问题有深入了解并根据具体情况选择适当的优化方法。
