缓存工作原理的具体解释

Hacker News Top 新闻

摘要

关于CPU缓存工作原理的详细技术说明,涵盖局部性原理、缓存组织方式、索引以及写操作处理。

暂无内容
查看原文
查看缓存全文

缓存时间: 2026/07/25 05:06

# 缓存工作原理的非常具体的解释 来源: https://parksb.github.io/en/article/29.html ## 硬件实现的哈希表 2019年3月30日 KO (https://parksb.github.io/article/29.html) | EN - 局部性原理 (https://parksb.github.io/en/article/29.html#principle-of-locality) - 缓存 (https://parksb.github.io/en/article/29.html#caches) - 缓存指标 (https://parksb.github.io/en/article/29.html#cache-metrics) - 缓存组织 (https://parksb.github.io/en/article/29.html#cache-organization) - 索引 (https://parksb.github.io/en/article/29.html#indexing) - 标签匹配 (https://parksb.github.io/en/article/29.html#tag-matching) - 标签开销 (https://parksb.github.io/en/article/29.html#tag-overhead) - 相联缓存 (https://parksb.github.io/en/article/29.html#associative-cache) - 组相联缓存组织 (https://parksb.github.io/en/article/29.html#set-associative-cache-organization) - 具体例子 (https://parksb.github.io/en/article/29.html#concrete-example) - 处理缓存写操作 (https://parksb.github.io/en/article/29.html#handling-cache-writes) - 软件重构 (https://parksb.github.io/en/article/29.html#software-restructuring) - 参考文献 (https://parksb.github.io/en/article/29.html#references) 随着技术的进步,处理器速度提升很快,但内存速度却没有跟上。无论处理器有多快,如果内存响应慢,整个系统最终还是会变慢。解决这个问题的设备就是缓存。 缓存是一种位于CPU芯片内部的小型快速存储器(而且价格昂贵)。每次从主存获取数据都很慢,因此缓存保存频繁使用的数据,让处理器从缓存而不是主存中获取数据,从而加快速度。 ### 局部性原理 判断哪些数据是“频繁使用的”遵循局部性原理,它可以分为时间局部性和空间局部性。 时间局部性是指倾向于再次访问最近访问过的数据。例如,作为循环索引的变量`i`在短时间内被多次访问。 `` for (i = 0; i < 10; i += 1) { arr[i] = i; } `` 空间局部性是指倾向于再次访问最近访问过的数据的附近空间。在上面的循环中,当它引用数组`arr`的每个元素时,它会一个接一个地访问附近的内存位置。这是因为数组的元素在内存中是连续分配的。 即使在一个进程内部,有些部分经常使用,有些则不常使用,因此操作系统通过将进程分割成称为页面的单元来管理进程,上图是页面引用的一个跟踪。横轴是执行时间,纵轴是内存地址。水平运行的引用表示相同的内存地址在很长一段时间内被引用,而垂直运行表示紧密间隔的内存地址在同一时间被引用。可以看出,局部性原理也适用于页面访问。 ### 缓存 一个CPU芯片包含多个缓存,每个缓存都有其自身的用途和作用。 `` +-------------+------+------+ +---------------+ +--------+ | | I$ | | <-- | | <-- | | + Processor +------+ L2 | | Main Memory | | Disk | | | D$ | | --> | | --> | | +-------------+------+------+ +---------------+ +--------+ `` - L1缓存:离处理器最近的缓存。为了速度,它分为I$和D$。 - 指令缓存(I$):处理内存中TEXT段数据的缓存。 - 数据缓存(D$):处理除TEXT段外所有数据的缓存。 - L2缓存:容量更大的缓存。为了容量,它不像L1缓存那样分开。 - L3缓存:在多核系统中由多个核心共享的缓存。 Intel Core i7 四核芯片的晶圆图。 如今,缓存占据了CPU芯片面积的30%到70%。1989年制造的单核处理器i486只有一个8KB的I/D缓存。而Intel Core i7四核芯片的晶圆图显示,四个核心中的每一个都有自己256KB的L2缓存,外加一个由所有核心共享的8MB L3缓存。(L2缓存上方的区域看起来像是L1缓存,但我不确定,所以没有标注。) ### 缓存指标 在衡量缓存性能时,命中延迟和未命中延迟被认为是重要因素。 当CPU请求的数据在缓存中时,称为缓存命中。命中延迟是在命中的情况下获取缓存数据所需的时间。当请求的数据不在缓存中时,称为缓存未命中,未命中延迟是在未命中的情况下从更高级别的缓存(例如,当数据不在L1缓存中时,从L2缓存中查找)或内存中获取数据所需的时间。 平均访问时间计算如下: 未命中率=缓存未命中次数缓存访问次数平均访问时间=命中延迟+未命中率×未命中延迟\开始{对齐} \text{未命中率} &= \frac{\text{缓存未命中次数}}{\text{缓存访问次数}} \\ \text{平均访问时间} &= \text{命中延迟} + \text{未命中率} \times \text{未命中延迟} \结束{对齐} 为了提升缓存性能,可以缩小缓存以减少命中延迟,扩大缓存以减少未命中率,或者使用更快的缓存以减少延迟。 ### 缓存组织 缓存由响应快速的SRAM(静态随机存取存储器)构成;给定一个地址作为键,它可以立即访问相应的位置。DRAM(动态随机存取存储器)也具有相同的特性,但从硬件设计上讲,DRAM比SRAM慢。人们通常所说的“主存”通常指的是DRAM。 能够通过地址作为键立即访问一个位置意味着缓存本质上是一个用硬件实现的哈希表。缓存之所以快,部分原因在于它只保存频繁使用的数据,还因为哈希表的时间复杂度是快速的,属于O(1)量级。 缓存由多个块组成。每个块保存数据,并且可以通过地址作为键来访问。块的数量和块大小决定了缓存的容量。 #### 索引 并非使用整个地址作为键,而是只使用其中一部分。例如,有1024个块,块大小为32字节,一个32位地址可以这样索引: 通过索引访问数据。 这里,完整地址的低5位用作偏移量,接下来的10位用作访问块的索引。索引是10位,因为要表示2^n个块的每个索引需要log_2(块数)位。由于这里有2^10 = 1024个块,log_2(1024) = 10,所以使用10位作为索引位。(我稍后会解释偏移位。) 但仅仅这样做会导致不同数据共享相同索引的风险太大。 #### 标签匹配 为了减少索引冲突,使用地址的一部分作为标签。假设有1024个块,块大小为32字节,我们访问32位地址0x000c14B8: 通过索引和标签访问数据。 1. 首先,访问与索引(`0010100101`)对应的标签数组字段。 2. 然后,检查该标签字段的有效位。 3. 如果有效位是`1`,比较标签字段(`00000000000011000`)和地址的标签(`00000000000011000`)是否相等。 4. 将比较结果(`true`,`1`)与有效位(`1`)进行AND操作。 有效位为`1`表示该块中存在正确的值。标签字段与地址的标签匹配,并且有效位为`1`,所以上述示例的结果是命中。命中时,从数据数组中引用索引处的数据。(参考:数据数组和标签数组也都是硬件。) 如果有效位是`0`,表示该块没有值或值无效,因此发生未命中。在这种情况下,将地址的标签写入标签字段,从更高级缓存或内存中获取请求的值并写入数据字段,然后将有效位改为`1`。 即使有效位为`1`,当标签不匹配时也会发生未命中。在这种情况下,如何处理取决于替换策略。如果使用FIFO(先进先出)策略(先进入的数据先被替换),则总是替换现有块。将标签数组的字段改为地址的标签,从更高级缓存或内存中获取请求的数据,用新数据替换数据字段中的值。(实际上,不仅请求的数据,其周围的数据也会被获取。)现有数据被推到更高级缓存。 地址的上15位被用作标签位的原因是标签位数由`地址位数 - (log_2(块大小) + 索引位数)`决定。在这种情况下,使用32 - (5 + 10) = 17位作为标签位,剩下的5位作为偏移位。 #### 标签开销 添加标签数组意味着需要更多空间。但“32KB缓存”仍然意味着一个可以存储32KB数据的缓存。因为标签的空间被视为开销,与块大小无关。 让我们计算一个由1024个32B块组成的32KB缓存的标签开销: 17位标签 + 1位有效位 = 18位 18位 × 1024 = 18Kb 标签 = 2.25KB 换句话说,产生了7%的标签开销。 除了空间成本外还有时间成本。因为需要访问标签数组检查是否命中,然后才访问数据数组获取数据,命中延迟因此增加。 所以两个步骤并行运行:在检查标签数组是否命中的同时,提前访问数据数组。这减少了命中延迟,但必须接受未命中发生时浪费的资源。 ### 相联缓存 当两个不同地址具有相同索引时,会发生冲突,并根据替换策略替换一个块。但每次发生冲突就改变缓存内容会导致更多未命中,并可能引起乒乓问题(单个槽的内容被无限交换)。 这个问题可以通过创建多个标签数组和数据数组来改善。换句话说,索引最终指向多个块。根据索引指向的块数对缓存分类如下: - 直接映射:索引指向单个槽。处理速度快,但冲突频繁。 - 全相联:索引指向所有槽。冲突少,但需要搜索所有块,因此速度慢。 - 组相联:索引指向两个或更多槽。这称为n路组相联缓存。 直接映射和全相联缓存的优缺点都很极端,因此通常使用组相联缓存。 #### 组相联缓存组织 让我们快速看一下2路组相联缓存的工作原理: 2路组相联缓存的工作原理。 通过地址的索引访问块与我们目前看到的直接映射缓存相同。区别在于有两个路,因此检查数据是否被缓存需要检查两个块,而不仅仅是一个。最后,将两路的结果进行OR操作得出最终结果。如果所有路都发生未命中,则根据替换策略将数据写入两个块之一。 与直接映射缓存相比,这提高了命中延迟,但降低了冲突的可能性。 #### 具体例子 假设我们有一个由2字节缓存块组成的8字节2路缓存,给定一个4位地址。 引用0001。 一个引用内存地址`0001`的指令运行。索引位是log_2(2) = 1,标签位是4 - (log_2(2) + 1) = 2。最后,偏移位为1。因此地址`0001`的索引是0,标签是00。这意味着该内存位置的数据可以被缓存在索引为`0`的两个槽之一。 缓存0001和0010。 由于`Way 0`中的块是空的,数据被存储在`Way 0`中索引为`0`的块中。地址`0010`同时被缓存,因为为了提高缓存命中率,内存一次被获取一个完整的缓存块(2B)。(这利用了空间局部性。)这里,被引用数据(`0001`)旁边的空间`0010`被一起缓存。 引用0101。 一个引用内存地址`0101`的指令运行。同样,它可以进入索引为`0`的两个槽之一。 缓存0101和0110。 但由于`Way 0`中索引为`0`的块已经保存了数据,新数据被缓存在空的`Way 1`中。同样,相邻的`0110`数据被一起缓存。`Way 0`中两个块的LRU(最近最少使用)值也增加了。LRU是一种优先替换最近最少使用数据的策略,它也用于操作系统的进程调度(https://parksb.github.io/article/9.html)和页面置换算法中。LRU值越高,表示该块在缓存未命中时更可能被优先替换。 引用1000。发生未命中。 接下来,一个引用内存地址`1000`的指令运行。检查了索引为`0`的两个块,但没有标签为`10`的数据,因此发生了缓存未命中。 缓存0111和1000。 因此缓存数据被替换。在两个槽中,`Way 0`块的LRU值更高,因此`Way 0`中的第一个块被替换,并且由于它被引用,其LRU值被重置为0。(在缓存命中时也会重置LRU值。)同理,被引用数据旁边的`0111`数据也被缓存。`Way 1`中的两个块这次没有被引用,所以它们的LRU值增加了。 ### 处理缓存写操作 当操作是写而不是读,并且要更改数据的地址已经缓存(写命中)时,缓存的块中的数据被更新,而不是内存中的数据。现在出现一个问题:“缓存中更新的数据何时应该写回内存?”有两种写策略。 一种是写直达方法:每次数据写入缓存时,也更新内存中的数据。这会产生大量流量,但能使内存和缓存中的数据保持一致。 另一种是写回方法,仅在块被替换时才更新内存中的数据。为了检查数据是否已更改,需要为每个缓存块添加一个`脏`位,数据更改时置为`1`。之后,当该块被替换时,如果`脏`位为`1`,则更新内存中的数据。 如果要更改数据的地址没有被缓存(写未命中),则使用写分配方法。显而易见,未命中发生时将数据缓存。跳过写分配会暂时节省资源,但无法达到缓存的目的。 ### 软件重构 到目前为止,我们已经从底层了解了缓存的结构和行为,但也可以在代码层面提高缓存效率。看看下面的嵌套循环: `` for (i = 0; i < columns; i += 1) { for (j = 0; j < rows; j += 1) { arr[j][i] = pow(arr[j][i]); } } `` 这个循环求一个二维数组每个元素的平方。看起来没问题,但从空间局部性角度看,它是低效的代码,因为数组`arr`的元素在内存中是连续存储的,但访问不是顺序的。 `` 0 4 8 12 16 20 24 +----------+----------+----------+----------+------

相似文章

每个字节都很重要

Lobsters Hottest

本文通过Java和C语言的示例,阐述了理解CPU缓存行与数据结构布局对编程性能优化的重要性,讨论了多余字节的开销以及结构体数组与数组结构体之间的权衡。

CPU 中的内存排序

Lobsters Hottest

本文解释了CPU乐观地实现内存排序,并依赖回滚机制来处理竞争,同时澄清了关于强排序与弱排序架构的常见误解。