每个程序员都应该了解的内存知识-Part2
关于CPU 高速缓存
直接看原文翻译
CPU今天比25年前要复杂得多。在那些日子里，CPU核心的频率与内存总线的水平相当。内存访问速度仅比寄存器访问速度稍慢。但在90年代初，这种情况发生了戏剧性的变化，当时CPU设计师提高了CPU核心的频率，但内存总线和RAM芯片的性能并没有成比例地提高。这并不是因为无法制造更快的RAM，正如前一节所解释的。这是可能的，但并不经济。与当前CPU核心一样快的RAM比任何动态RAM都要贵几个数量级。
如果选择是在拥有非常少但非常快的RAM的机器和拥有大量相对快的RAM的机器之间，鉴于工作集大小超过小RAM大小以及访问次级存储介质（如硬盘）的成本，第二种机器总是会赢。这里的问题是次级存储的速度，通常是硬盘，必须用来存储工作集被交换出去的部分。访问这些磁盘的速度比甚至DRAM访问还要慢几个数量级。
幸运的是，这不必是一个全有或全无的决定。计算机可以拥有少量的高速SRAM，以及大量的DRAM。一种可能的实现方式是将处理器的地址空间的某个区域专门用于包含SRAM，其余部分用于DRAM。然后操作系统的任务就是最佳地分配数据以利用SRAM。基本上，在这种情况下，SRAM作为处理器寄存器集的扩展。
虽然这是一种可能的实现方式，但它并不可行。忽略将这种SRAM支持的内存的物理资源映射到进程的虚拟地址空间的问题（这本身就是非常困难的），这种方法将要求每个进程在软件中管理这个内存区域的分配。内存区域的大小因处理器而异（即，处理器拥有不同数量的昂贵的SRAM支持的内存）。组成程序的每个模块都会要求其快速内存的份额，这通过同步要求引入了额外的成本。简而言之，拥有快速内存的好处将完全被管理资源的开销所抵消。
因此，与其将SRAM置于操作系统或用户的控制之下，不如让它成为处理器透明使用和管理的资源。在这种模式下，SRAM被用来临时复制（换句话说，缓存）处理器可能很快使用的主要内存中的数据。这是可能的，因为程序代码和数据具有时间和空间的局部性。这意味着，在短期内，相同代码或数据被重复使用的可能性很大。对于代码来说，这意味着代码中很可能有循环，因此相同的代码一遍又一遍地执行（空间局部性的完美案例）。数据访问也理想地限于小区域。即使在短期内使用的内存不紧密在一起，相同的数据很快就会被重复使用（时间局部性）。对于代码来说，这意味着，例如，在循环中进行函数调用，该函数位于地址空间的其他地方。该函数可能在内存中很远，但对该函数的调用将在时间上很接近。对于数据来说，这意味着一次使用的内存总量（工作集大小）理想地是有限的，但由于RAM的随机访问特性，使用的内存并不紧密在一起。意识到局部性的存在是当今我们使用的CPU缓存概念的关键。
一个简单的计算可以展示缓存理论上可以有多有效。假设访问主存储需要200个周期，访问缓存存储需要15个周期。那么，如果没有任何缓存，使用100个数据元素各100次的代码将在内存操作上花费2,000,000个周期，如果所有数据都可以被缓存，则只需要168,500个周期。这是一个91.5%的改进。
用于缓存的SRAM的大小比主存储小很多倍。在作者使用带有CPU缓存的工作站的经验中，缓存大小一直是主存储大小的1/1000（今天：4MB缓存和4GB主存储）。这本身并不构成问题。如果工作集的大小（当前正在处理的数据集）小于缓存大小，那就没关系。但是，计算机没有大的主存储是有原因的。工作集的大小肯定会大于缓存。这尤其适用于运行多个进程的系统，其中工作集的大小是所有单独进程和内核的大小之和。
需要应对缓存有限大小的是一套好的策略，以确定任何给定时间应该缓存什么。由于工作集中的所有数据并不完全同时使用，我们可以使用技术暂时用其他数据替换缓存中的一些数据。也许这可以在实际需要数据之前完成。这种预取将通过与程序执行异步发生来消除一些访问主存储的成本。所有这些技术以及更多可以用于使缓存看起来比实际大。我们将在第3.3节中讨论它们。一旦所有这些技术都被利用，就取决于程序员来帮助处理器。这将如何完成将在第6节中讨论。
在深入研究 CPU 缓存实现的技术细节之前，一些读者可能会发现首先了解缓存如何融入现代计算机系统的“大局”的更多细节是有用的。
图3.1展示了最小的缓存配置。它对应于早期部署CPU缓存的系统中可以找到的架构。CPU核心不再直接连接到主存储器。{在更早的系统中，缓存就像CPU和主存储器一样连接到系统总线上。这更像是一种临时解决方案，而不是真正的解决方案。}所有的加载和存储操作都必须通过缓存。CPU核心和缓存之间的连接是特殊的、快速的连接。在简化的表示中，主存储器和缓存连接到系统总线上，该总线也可用于与系统的其他组件通信。我们引入了系统总线作为“FSB”，这是今天使用的名称；见第2.2节。在本节中，我们忽略了北桥；假设它存在是为了促进CPU与主存储器之间的通信。
尽管过去几十年的计算机使用了冯·诺依曼架构，但经验表明，将用于代码和数据的缓存分开是有利的。自1993年以来，英特尔一直使用独立的代码和数据缓存，并且从未回头。代码和数据所需的存储区域在很大程度上是相互独立的，这就是为什么独立缓存工作得更好。近年来，另一个优势出现了：对于最常见的处理器，指令解码步骤是缓慢的；缓存解码后的指令可以加速执行，特别是当由于错误预测或无法预测的分支导致流水线为空时。
缓存引入后不久，系统变得更加复杂。缓存和主存储器之间的速度差异再次增加，以至于增加了另一个级别的缓存，比一级缓存更大、更慢。出于经济原因，仅仅增加一级缓存的大小并不是一个选项。今天，甚至有些机器常规使用三级缓存。具有这样处理器的系统看起来像图3.2。随着单个CPU核心数量的增加，未来缓存级别数量可能会进一步增加。
图3.2展示了三级缓存，并引入了我们在文档其余部分将使用的术语。L1d是一级数据缓存，L1i是一级指令缓存，以此类推。请注意，这是一个示意图；在现实中，从核心到主存储器的数据流不必通过任何更高级别的缓存。CPU设计师在设计缓存接口时有很多自由度。对于程序员来说，这些设计选择是不可见的。
此外，我们还有具有多个核心的处理器，每个核心可以有多个“线程”。核心和线程之间的差异在于，不同的核心拥有各自独立的（几乎所有的硬件资源。核心可以完全独立地运行，除非它们同时使用相同的资源——例如，与外部的连接。另一方面，线程几乎共享了处理器的所有资源。英特尔对线程的实现只有线程的独立寄存器，即便如此也是有限制的，一些寄存器是共享的。因此，现代CPU的完整图景看起来像图3.3。
在这个图中，我们有两个处理器，每个处理器有两个核心，每个核心有两个线程。线程共享一级缓存。核心（深灰色阴影部分）有各自独立的一级缓存。CPU的所有核心共享更高级别的缓存。当然，两个处理器（浅灰色阴影的两个大框）不共享任何缓存。当我们讨论多进程和多线程应用对缓存的影响时，所有这些都将变得非常重要。
3.2 高层次的缓存操作
为了理解使用缓存的成本和节省，我们必须结合第2节中关于机器架构和RAM技术的知识和上一节中描述的缓存结构。
默认情况下，CPU核心读取或写入的所有数据都存储在缓存中。有些内存区域不能被缓存，但这是只有操作系统实现者需要关心的事情；对应用程序程序员来说是不可见的。还有一些指令允许程序员故意绕过某些缓存。这将在第6节中讨论。
如果CPU需要一个数据字，首先搜索缓存。显然，缓存不能包含整个主存储器的内容（否则我们就不需要缓存了），但由于所有内存地址都是可缓存的，每个缓存条目都使用主存储器中数据字的地址进行标记。这样，对一个地址的读写请求可以在缓存中搜索匹配的标记。这里的地址可以是虚拟地址或物理地址，取决于缓存的实现。
由于标记需要占用空间，除了实际的内存外，选择一个字作为缓存的粒度是低效的。在x86机器上的32位字上，标记本身可能需要32位或更多。此外，由于空间局部性是缓存所依赖的原则之一，不考虑这一点将是不利的。由于相邻的内存可能会一起使用，它也应该一起被加载到缓存中。还记得我们在第2.2.1节中学到的：如果RAM模块能够连续传输多个数据字而不需要新的CAS或甚至是RAS信号，它们会更加有效。因此，存储在缓存中的条目不是单个字，而是多个连续字的“行”。在早期的缓存中，这些行长32字节；现在规范是64字节。如果内存总线是64位宽，这意味着每条缓存行需要8次传输。DDR有效地支持这种传输模式。
当处理器需要内存内容时，整个缓存行被加载到L1d中。每个缓存行的内存地址是通过根据缓存行大小掩蔽地址值来计算的。对于一个64字节的缓存行，这意味着低6位被清零。被丢弃的位用作缓存行内的偏移量。在某些情况下，剩余的位被用来在缓存中定位行并作为标记。在实践中，一个地址值被分成三个部分。对于一个32位的地址，它可能看起来如下：
在这个图中我们有两个处理器，每个处理器有两个核心，每个核心有两个线程
线程共享一级缓存。核心（深灰色阴影部分）有各自独立的一级缓存。CPU的所有核心共享更高级别的缓存。当然，两个处理器（浅灰色阴影的两个大框）不共享任何缓存。当我们讨论多进程和多线程应用对缓存的影响时，所有这些都将变得非常重要。
3.2 高层次的缓存操作
为了理解使用缓存的成本和节省，我们必须结合第2节中关于机器架构和RAM技术的知识和上一节中描述的缓存结构。
默认情况下，CPU核心读取或写入的所有数据都存储在缓存中。有些内存区域不能被缓存，但这是只有操作系统实现者需要关心的事情；对应用程序程序员来说是不可见的。还有一些指令允许程序员故意绕过某些缓存。这将在第6节中讨论。
如果CPU需要一个数据字，首先搜索缓存。显然，缓存不能包含整个主存储器的内容（否则我们就不需要缓存了），但由于所有内存地址都是可缓存的，每个缓存条目都使用主存储器中数据字的地址进行标记。这样，对一个地址的读写请求可以在缓存中搜索匹配的标记。这里的地址可以是虚拟地址或物理地址，取决于缓存的实现。
由于标记需要占用空间，除了实际的内存外，选择一个字作为缓存的粒度是低效的。在x86机器上的32位字上，标记本身可能需要32位或更多。此外，由于空间局部性是缓存所依赖的原则之一，不考虑这一点将是不利的。由于相邻的内存可能会一起使用，它也应该一起被加载到缓存中。还记得我们在第2.2.1节中学到的：RAM模块能够连续传输多个数据字而不需要新的CAS或甚至是RAS信号，它们会更加有效。因此，存储在缓存中的条目不是单个字，而是多个连续字的“行”。在早期的缓存中，这些行长32字节；现在规范是64字节。如果内存总线是64位宽，这意味着每条缓存行需要8次传输。DDR有效地支持这种传输模式。
当处理器需要内存内容时，整个缓存行被加载到L1d中。每个缓存行的内存地址是通过根据缓存行大小掩蔽地址值来计算的。对于一个64字节的缓存行，这意味着低6位被清零。被丢弃的位用作缓存行内的偏移量。在某些情况下，剩余的位被用来在缓存中定位行并作为标记。在实践中，一个地址值被分成三个部分。对于一个32位的地址，它可能看起来如下：
缓存行大小为2^O，低O位用作缓存行内的偏移量
- 下一个S位选择“缓存集”。我们很快就会更详细地讨论为什么使用集而不是单个槽来存放缓存行。目前，只需理解有2^S个缓存行集。
- 这留下了顶部的32 - S - O = T位，形成标记。这些T位与每个缓存行相关联的值，用于区分所有在同一缓存集中缓存的别名（所有地址的S部分相同的缓存行都被称为相同的别名）。
- 用于寻址缓存集的S位不需要存储，因为它们对于同一集中的所有缓存行都是相同的。
当指令修改内存时，处理器仍然需要首先加载一个缓存行，因为没有指令会一次性修改整个缓存行（规则的例外：如第6.1节中解释的写入组合）。因此，在写操作之前必须加载缓存行的内容。不可能为缓存持有部分缓存行。一个被写入且尚未回写到主存储器的缓存行被称为“脏”的。一旦写入，脏标志就会被清除。
为了能够在缓存中加载新数据，几乎总是首先需要在缓存中腾出空间。从L1d中逐出会将缓存行推入到L2（使用相同的缓存行大小）。这当然意味着需要在L2中腾出空间。这反过来可能会将内容推入L3和最终推入主存储器。每次逐出的成本都会逐渐增加。这里描述的是现代AMD和VIA处理器更倾向于使用的独占缓存模型。英特尔实现了包容缓存，其中L1d中的每个缓存行也存在于L2中。因此，从L1d中逐出要快得多。有足够的L2缓存，浪费内存存储在两个地方的劣势是最小的，并且在逐出时是值得的。独占缓存的一个可能优势是，加载新的缓存行只需要触及L1d而不需要触及L2，这可能会更快。
CPU可以随意管理缓存，只要处理器架构定义的内存模型没有改变。例如，处理器完全可以利用几乎没有或没有内存总线活动，并主动将脏缓存行写回主存储器。在x86和x86-64处理器中，不同制造商之间，甚至在同一制造商的模型之间，缓存架构的多样性证明了内存模型抽象的强大。
在对称多处理器（SMP）系统中，CPU的缓存不能独立于彼此工作。所有处理器都应该在任何时候看到相同的内存内容。维护这种统一的内存视图被称为“缓存一致性”。如果一个处理器只是简单地查看自己的缓存和主存储器，它将看不到其他处理器中脏缓存行的内容。直接从另一个处理器访问一个处理器的缓存将是非常昂贵的，并且是一个巨大的瓶颈。相反，处理器会检测到另一个处理器想要读取或写入某个特定的缓存行。
如果检测到写入访问，并且处理器在其缓存中有该缓存行的干净副本，则此缓存行被标记为无效。未来的引用将需要重新加载该缓存行。请注意，另一个CPU上的读取访问并不需要使无效，可以保留多个干净的副本。
更复杂的缓存实现允许另一种可能性发生。如果另一个处理器想要读取或写入的缓存行当前在第一个处理器的缓存中被标记为脏，那么就需要采取不同的行动。在这种情况下，主存储器已经过时，请求的处理器必须从第一个处理器那里获取缓存行内容。通过窥探，第一个处理器注意到这种情况并自动向请求的处理器发送数据。这个操作绕过了主存储器，尽管在某些实现中，内存控制器应该注意到这种直接传输，并更新主存储器中的缓存行内容。如果访问是为了写入，第一个处理器随后会使其本地缓存行的副本无效。
随着时间的推移，已经开发出了许多缓存一致性协议。最重要的一个是MESI，我们将在第3.3.4节中介绍。所有这些的结果可以用几个简单的规则概括：
- 脏缓存行不存在于任何其他处理器的缓存中。
- 相同的缓存行的干净副本可以存在于任意多的缓存中。
如果这些规则能够得到维护，即使在多处理器系统中，处理器也可以有效地使用它们的缓存。所有处理器需要做的就是监视彼此的写入访问，并将其地址与它们本地缓存中的地址进行比较。在下一节中，我们将更详细地讨论实现和成本。
最后，我们至少应该给出与缓存命中和未命中相关联的成本的印象。这些是英特尔为Pentium M列出的数字：
- 寄存器：<= 1个周期
- L1d：大约3个周期
- L2：大约14个周期
- 主存储器：大约240个周期
这些是在CPU周期内测量的实际访问时间。值得注意的是，对于片上L2缓存，访问时间的很大一部分（可能甚至是大部分）是由线延迟引起的。这是一种物理限制，随着缓存大小的增加，这种情况只会变得更糟。只有工艺缩小（例如，从Merom的60nm到Penryn的45nm在英特尔的产品线中）才能改善这些数字。
表中的数字看起来很高，但幸运的是，并不是每次缓存加载和未命中都需要支付全部成本。成本的一部分可以被隐藏。今天的处理器都使用不同长度的内部流水线，指令在其中被解码并准备执行。如果内存加载操作可以足够早地在流水线中开始，它可能与其他操作并行发生，并且加载的全部成本可能被隐藏。这通常对L1d是可能的；对于一些具有长流水线的处理器，对L2也是如此。
对于写入操作，CPU不必等到值安全地存储在内存中。只要随后指令的执行看起来与值存储在内存中的效果相同，就没有什么可以阻止CPU走捷径。它可以提前开始执行下一个指令。通过使用可以保存不再在常规寄存器中可用的值的影子寄存器，甚至可以更改将要存储在不完整写入操作中的值。