哪家高端网站建设好,理财平台网站建设,网页生成app在线,wordpress redis 插件这篇写一下计算机系统中的缓存Cache应用场景和实现方式介绍。
Memory hierarchy
在讲缓存之前#xff0c;首先要了解计算机中的内存结构层次Memory hierarchy。也就是下图金字塔形状的结构。 从上到下#xff0c;内存层次结构如下#xff1a; 寄存器#xff1a;这是计算机…这篇写一下计算机系统中的缓存Cache应用场景和实现方式介绍。
Memory hierarchy
在讲缓存之前首先要了解计算机中的内存结构层次Memory hierarchy。也就是下图金字塔形状的结构。 从上到下内存层次结构如下 寄存器这是计算机中最快速的存储区域。它们位于处理器内用于存储即将被处理器执行的指令和数据。 高速缓存Cache位于处理器和主内存之间用于存储最近或频繁访问的数据和指令。高速缓存有多级L1、L2、L3其中L1最接近处理器且速度最快但也最小。 主内存RAM当计算机运行程序时程序的代码和数据被加载到主内存中。 硬盘驱动器HDD或固态硬盘SSD这些是非易失性的存储设备用于长期存储数据和程序。 网络存储和云存储这些存储设备位于本地计算机之外数据通常通过网络进行访问。
从上到下离CPU就越来越远越往下的部分容量往往越大价格也越便宜而越靠近CPU的部分速度越快但是价格高且容量小。
Locality
局部性原理 (Locality of Reference) 是设计内存层次结构时需要考虑的重要因素也是后面缓存为什么能够起作用的原因。 时间局部性Temporal Locality如果一个数据或指令在某个时间点被访问那么在未来的一段时间内这个数据或指令可能会被再次访问。这是由于程序的执行往往具有重复性例如循环和递归。高速缓存就是基于时间局部性设计的将最近访问过的数据和指令存储在快速访问的缓存中。 空间局部性Spatial Locality如果一个数据或指令被访问那么在未来的一段时间内其附近的数据或指令也可能会被访问。这是由于程序的执行通常具有连续性例如顺序执行的指令和数组的元素。内存管理系统会将整个块包含了访问数据或指令的附近地址加载到高速缓存或主内存中以利用空间局部性。
缓存Cache
如果我们把用过地址放在CPU里的存储单元或者说一个更接近CPU、更能快速获取的地方就有了我们广义概念上的“Cache”了。虽然这个地方很小但基于locality的原理程序倾向于使用之前的地址或者之前地址附近地址每次CPU像访问数据它都会优先从cache里查找因为离得更近如果是那种多次反复需要的数据就可以直接让cache来提前处理了提高数据获取速度。 当然毕竟cache的位置有限如果请求的数据没有在cache里这叫做cache miss就只能把cache中的数据删掉比如最久没用的那个然后把新数据从下面更慢的内存结构中获取后替换上去。
几种Cache miss
Cache miss主要有以下三种 冷强制未命中Cold or Compulsory Miss 冷未命中是因为缓存开始时是空的而这是对该块的第一次引用。换句话说这是无法避免的未命中因为当你第一次访问一个数据块时它不可能已经在缓存中。 容量未命中Capacity Miss 当活动的缓存块集合工作集大于缓存的容量时就会发生容量未命中。即使数据块之前已在缓存中但由于缓存空间有限可能已经被其他更近期访问的数据块替换出去。 冲突未命中Conflict Miss 前两个都比较好理解这个冲突未命中比较复杂我用通俗的语言讲大概是这样比如我们教室有三排学生每排都有一个椅子当作cache那么我们cache一共有3个学生有3排。这个时候如果规定每排学生只能用对应的一把椅子就会发生conflict miss。比如第一排第一个同学有了一个行为他被存储在了第一个椅子上这个时候第一排第二个同学又有一个行为我们只会用第二个同学去换下第一个同学——即使这个时候还有两把椅子是空的。当最后再次访问第一个同学时你会发现明明第一个同学之前访问过明明cache里有空位但就是在cache里找不到他这种情况下的miss就叫做conflict miss。
Cache的参数和大小表示
高速缓存Cache的总大小可以由以下三个参数描述
S缓存的集数Set。E每个集中的线数Line也就是每个集中的缓存块数量Cache blocks per set。B每个缓存块的大小Size of each block。
而Cache set就等于 S × E × B。 Cache的结构看起来这么麻烦如何存储数据呢对于一个数据如cache会根据它的地址来划分和存储。 如上图所示通常地址会被划分成3部分块偏移量block offset、集索引set index和标签tag。 块偏移量Block Offset这部分的位数取决于每个cache块或行的大小。例如如果一个块的大小是16字节那么块偏移量就需要4位因为2^4 16用于确定一个字节在其块中的位置。 集索引Set Index这部分的位数取决于cache的集数。例如如果有64个集集索引就需要6位因为2^6 64用于确定一个块应该存储在哪个集中。 标签Tag地址中剩下的位被用作标签用于在cache查找过程中区分不同的内存块。
所以对于一个地址大致的查找流程是这样的首先进行地址分割就像上面说的那样分成三部分其次拿着集索引去cache中找到对应的集拿到了这个集可以理解成图里的一整行蓝色背景包含很多line我们查找所有line通常会并行查找来提高速度找到那个linewhich有效位valid bit是1以及tag标签和地址划分出来的tag部分一样如果找到了则使用块偏移量从这个集中取出所需的数据。 再举个例子在上面这个图中 block块大小是8因此我们需要3个位作为block offset这里offset是100也就是4那么数据到时候会从第4位开始也就是图中绿色块部分集的个数不知道集索引的位数也不确定但这里0...01不管中间几个0都是1表示对应第一个集。在剩下的部分就是两个红色部分的tag比较了。
用这句话来检查一下你是否理解这里虽然得到的块偏移量是4但是你可以发现我们把4往后的部分也都放在cache里了绿色部分。因为这样的话如果下次访问这个同样的地址1按找那套流程算下来其实直接就对应块偏移量为5的部分直接就在cache里了这就是cache对Spatial Locality也友好的地方——不止是之前访问过的我有之前访问过的邻居我也有
Cache的写操作
当我们讨论写操作write operations在缓存系统中的行为时我们需要考虑两种基本的情况写命中write hit和写未命中write miss。在处理这两种情况时有几种常见的策略 1 写命中Write Hit当我们试图写入的数据已在缓存中时我们有两种基本策略 写直达Write-Through这种策略立即将更改写入到主存储器和缓存中。这种策略的优点是它保持了主存储器和缓存中的数据一致性但缺点是每次写操作都需要访问主存储器这可能会带来较大的性能开销。 写回Write-Back这种策略仅将更改写入到缓存中并将缓存行标记为dirty通过设置一个dirty bit。只有当缓存行被替换出缓存时更改才会被写回到主存储器。这里的dirty bit就是替换时用来判断的如果是1那么就需要把整个缓存行包含2^b字节的数据块写回write-back到主内存。这种策略的优点是减少了对主存储器的访问次数从而提高了性能。但是这也可能会导致主存储器与缓存之间的数据不一致。 2 写未命中Write Miss当我们试图写入的数据不在缓存中时我们有两种基本策略 不写分配No-Write-Allocate这种策略直接将数据写入主存储器而不将其加载到缓存中。这种策略适用于不希望单次写操作污染缓存的情况。 写分配Write-Allocate这种策略在写入数据之前先将相关的缓存行加载到缓存中再将新的写操作应用到这个缓存行。如果预计将来会有更多对同一位置的写操作这种策略可能会很有用。
在实际的系统中可能会组合使用这些策略。比如一种常见的组合是使用写直达和不写分配策略这种组合可以保持数据的一致性而且适合处理散列的、非连续的写操作。另一种常见的组合是使用写回和写分配策略这种组合可以减少对主存储器的访问次数从而提高性能尤其是在处理连续的、集中的写操作时。
小结
这篇文章写了下cache的概念以及读写过程中的读取策略。cache的缓存命中是非常有用和关键的可以为程序或许数据节省下非常多时间。一个有趣的观点是99%的命中率可能比97%的命中率好两倍。比如假设缓存命中的时间为1个周期未命中的惩罚为100个周期。那么
对于97%的命中率平均访问时间为1个周期命中时间 0.03未命中率 * 100个周期未命中惩罚 4个周期。对于99%的命中率平均访问时间为1个周期命中时间 0.01未命中率 * 100个周期未命中惩罚 2个周期。
因此尽管两者的命中率只相差2%但是平均访问时间却差了一倍。
所以对于程序员来说尽量写出“缓存友好”的代码也是能很好提升程序的效率。通过理解缓存的工作方式我们可以编写出更有效地利用缓存的代码一些常见方式有 重复引用变量这是好的利用时间局部性Temporal Locality如果一个变量被反复引用它可能会留在缓存中这样每次引用都会命中缓存从而提高性能。 使用跨度为1的引用模式这是好的利用空间局部性Spatial Locality。如果你的代码按顺序访问数据例如遍历数组那么缓存系统可能会预先加载你即将访问的数据从而提高缓存命中率。这就是为什么我们一行一行地遍历二维数组要比一列一列地遍历快很多因为数组在内存中是按行存储缓存可以帮助我们提前加载到接下来的数据。
结束
