线程级并行

线程级并行性

多处理重要性的增加反映了几个主要因素：

2000 年至 2005 年间，当设计人员试图寻找和利用更多的 ILP 时，硅和能源使用效率急剧下降，但结果证明效率低下，因为功率和硅成本的增长速度快于性能。除了 ILP 之外，我们所知道的唯一可扩展和通用的方法来提高性能的速度比基本技术允许的速度更快（从交换的角度来看）是通过多处理。
随着云计算和软件即服务变得越来越重要，人们对高端服务器的兴趣日益浓厚。
在互联网上提供大量数据的推动下，数据密集型应用程序的增长。
提高桌面性能不那么重要（至少在图形之外），要么是因为当前性能是可以接受的，要么是因为高度计算和数据密集型的应用程序是在云上完成的。
更好地理解如何有效地使用多处理器，特别是在服务器环境中，由于大型数据集（通常以数据并行的形式）、“自然世界”并行（发生在科学和工程代码中）或大量独立请求之间的并行（请求级并行）而产生显著的固有并行性。
通过复制而不是独特设计来利用设计投资的优势;所有多处理器设计都提供这种杠杆作用。

多处理器架构：问题和方法

现有的共享内存多处理器分为两类，

第一组，我们称之为对称（共享内存）多处理器（SMP），或集中式共享内存多处理器，具有少量到中等数量的内核，通常为 32 个或更少。对于处理器数量如此之少的多处理器，处理器可以共享一个集中式内存，所有处理器都可以平等地访问该内存，因此称为对称。在多核芯片中，内存通常以集中方式在内核之间共享;大多数现有的多核是 SMP，但不是全部。

一些多核对最外层缓存具有非一致性访问，这种结构称为 NUCA，用于非一致性缓存访问，因此即使它们具有单个主内存，它们也不是真正的 SMP。

在由多个多核芯片组成的多处理器中，每个多核芯片通常都有单独的存储器。因此，内存是分布式的，而不是集中式的。正如我们将在本章后面看到的，许多具有分布式存储器的设计可以快速访问本地存储器，而访问远程存储器的速度要慢得多;通常，与本地内存和远程内存的访问时间差异相比，各种远程存储器的访问时间差异很小。在此类设计中，程序员和软件系统需要知道访问是对本地存储器还是远程存储器的访问，但可能能够忽略远程存储器之间的访问分布。由于 SMP 方法的吸引力随着处理器数量的增加而降低，因此大多数最大的多处理器都使用某种形式的分布式内存。

SMP 体系结构有时也称为统一内存访问（UMA）多处理器，这是因为所有处理器都具有来自内存的统一延迟，即使内存被组织成多个存储区也是如此。

另一种设计方法由具有物理分布式内存的多处理器组成，称为分布式共享内存（DSM）。图 5.2 显示了这些多处理器的外观。为了支持更大的处理器数量，内存必须在处理器之间分配，而不是集中;否则，内存系统将无法支持大量处理器的带宽需求，而不会产生过长的访问延迟。

在节点之间分配内存既可以增加带宽，又可以减少本地内存的延迟。DSM 多处理器也称为 NUMA（非一致性内存访问），因为访问时间取决于数据字在内存中的位置。DSM 的主要缺点是处理器之间的数据通信变得更加复杂，并且 DSM 需要在软件中投入更多精力才能利用增加的内存带宽

由分布式内存提供。由于大多数具有多个处理器芯片的基于多核的多处理器都使用分布式内存，因此我们将从这个角度解释分布式内存多处理器的操作。

在 SMP 和 DSM 架构中，线程之间的通信通过共享地址空间进行，这意味着任何处理器都可以对任何内存位置进行内存引用，前提是它具有正确的访问权限。与 SMP 和 DSM 关联的术语共享内存是指地址空间是共享的。

相比之下，下一章中的集群和仓库规模的计算机看起来像是通过网络连接的单个计算机，如果没有在两个处理器上运行的软件协议的帮助，另一个处理器的内存就无法访问。在此类设计中，消息传递协议用于在处理器之间通信数据。

并行处理的挑战

多处理器的应用范围从运行基本上没有通信的独立任务到运行线程必须通信才能完成任务的并行程序。两个重要的障碍，都可以用阿姆达尔定律来解释，使并行处理具有挑战性。

集中式共享内存架构

对称共享内存计算机通常支持缓存共享数据和私有数据。私有数据由单个处理器使用，而共享数据由多个处理器使用，本质上是通过读取和写入共享数据来提供处理器之间的通信。缓存私有项时，其位置将迁移到缓存中，从而减少平均访问时间以及所需的内存带宽。由于没有其他处理器使用该数据，因此程序行为与单处理器中的行为相同。缓存共享数据时，共享值可能会在多个缓存中复制。除了减少访问延迟和所需的内存带宽外，此复制还可以减少多个处理器同时读取的共享数据项可能存在的争用。但是，缓存共享数据会带来一个新问题：缓存一致性。

什么是多处理器缓存一致性？

第一个方面称为coherence，它定义了读取可以返回哪些值。第二个方面称为consistency，它确定读取何时将返回写入值。

如果满足以下条件，则内存系统是相干的：

处理器 P 对位置 X 的读取操作紧跟处理器 P 对 X 的写入操作，并且在写入操作和处理器 P 的读取操作之间没有其他处理器对 X 进行写入操作，则始终返回处理器 P 写入的值。
处理器对位置 X 的读取操作紧跟另一个处理器对 X 的写入操作，如果读取操作和写入操作在时间上足够分开，并且在这两次访问之间没有其他对 X 的写入操作，则返回写入的值。
对同一位置的写入操作是串行的；也就是说，任何两个处理器对同一位置的两次写入操作对所有处理器来说都是按相同顺序进行的。例如，如果将值 1 然后 2 写入到某个位置，则处理器永远不会将该位置的值读为 2，然后稍后又读为 1。

第一个属性只是保留了程序顺序——我们期望即使在单处理器中此属性也是成立的。

第二个属性定义了对内存具有相干视图的含义：如果处理器可以连续读取旧数据值，我们显然会说内存是不相干的。

写序列化需求更为微妙，但同样重要。假设我们没有对写进行序列化，处理器 P1 写入位置 X，然后 P2 写入位置 X。对写进行序列化可确保每个处理器在某个时间点看到 P2 执行的写操作。如果我们没有对写进行序列化，则某些处理器可能会先看到 P2 的写操作，然后看到 P1 的写操作，从而无限期地保留 P1 写入的值。最简单的方法，为了避免这样的困难，确保对同一位置的所有写操作按照相同的顺序被观察到是很重要的；这个属性被称为写序列化。

尽管刚描述的三个属性足以确保一致性，但何时能看到写入值的问题也很重要。要了解原因，请注意，我们不能要求 X 的读取立即看到其他某个处理器为 X 写入的值。例如，如果一个处理器上的 X 写入在另一个处理器上的 X 读取之前很短的时间内发生，则可能无法确保读取返回写入数据的值，因为写入的数据甚至可能还没有在此时离开处理器。写入值必须在何时才能被读取器看到的问题由内存一致性模型定义，

coherence和consistency是互补的：coherence定义了对同一内存位置的读写顺序，而consistency定义了读写行为相对于对其他内存位置的访问的行为。现在，做出以下两个假设。首先，在所有处理器都看到该写的效果之前，写不会完成（并允许进行下一次写）。其次，处理器不会更改任何写相对于任何其他内存访问的顺序。这两个条件意味着，如果处理器按位置 A 然后按位置 B 写入，则看到 B 的新值的任何处理器也必须看到 A 的新值。这些限制允许处理器重新排序读取，但强制处理器按程序顺序完成写入。

强一致性的基本方案

多处理器和 I/O 的一致性问题虽然起源相似，但具有影响适当解决方案的不同特征。与 I/O 不同，在 I/O 中，多个数据副本是罕见的事件（应尽可能避免这种情况），而在多个处理器上运行的程序通常会在多个缓存中具有相同数据的副本。在连贯的多处理器中，缓存提供共享数据项的迁移和复制。

一致性缓存提供迁移，因为数据项可以移动到本地缓存并以透明的方式使用。此迁移既减少了访问远程分配的共享数据项的延迟，又减少了共享内存的带宽需求。

由于缓存在本地缓存中创建数据项的副本，因此一致性缓存还为同时读取的共享数据提供复制。复制可减少访问延迟和读取共享数据项的争用。支持此迁移和复制对于访问共享数据的性能至关重要。因此，多处理器不是试图通过在软件中避免问题来解决问题，而是通过引入协议来维护连贯的缓存来采用硬件解决方案。

为多个处理器保持一致性的协议称为缓存一致性协议。实现缓存一致性协议的关键是跟踪任何数据块共享的状态。任何缓存块的状态都使用与该块关联的状态位来保存，类似于单处理器缓存中保存的有效位和脏位。有两类协议正在使用，每类协议都使用不同的技术来跟踪共享状态：

基于目录 — 特定物理内存块的共享状态保存在一个位置，称为目录。有两种截然不同的基于目录的缓存一致性。在 SMP 中，我们可以使用一个集中式目录，该目录与内存或其他单个序列化点相关联，例如多核中最外层的缓存。在 DSM 中，拥有单个目录是没有意义的，因为这会造成单点争用，并且考虑到具有 8 个或更多内核的多核的内存需求，很难扩展到许多多核芯片。分布式目录比单个目录更复杂，
侦听 - 每个具有物理内存块中数据副本的缓存都可以跟踪该块的共享状态，而不是将共享状态保留在单个目录中。在 SMP 中，缓存通常都可以通过某些广播介质访问（例如，总线将每个内核的缓存连接到共享缓存或内存），并且所有缓存控制器都会监视或窥探介质，以确定它们是否具有在总线或交换机访问上请求的块的副本。侦听也可以用作多芯片多处理器的一致性协议，一些设计支持在每个多核内的目录协议之上的侦听协议。

监听协议在多处理器中变得流行起来，使用微处理器（单核）和通过总线连接到单个共享内存的缓存。总线为实现监听协议提供了方便的广播介质。多核架构显著改变了这一局面，因为所有多核在芯片上共享一定程度的缓存。因此，一些设计改用目录协议，因为开销很小。为了让读者熟悉这两种类型的协议，我们在这里重点介绍窥探协议，并在谈到 DSM 架构时讨论目录协议。

窥探一致性协议

有两种方法可以保持上一节中描述的一致性要求。一种方法是在写入数据项之前确保处理者对数据项具有独占访问权限。这种协议样式称为写入无效协议，因为它使写入时的其他副本无效。这是迄今为止最常见的协议。独占访问可确保在发生写入时不存在项目的其他可读或可写副本：该项目的所有其他缓存副本都将失效。

访问时，读取处理器持有的任何副本都必须失效（因此协议名称）。因此，当读取发生时，它会在缓存中丢失，并被迫获取数据的新副本。对于写入，我们要求写入处理器具有独占访问权限，以防止任何其他处理器能够同时写入。如果两个处理器尝试同时写入相同的数据，其中一个处理器将赢得比赛（我们将很快看到如何决定谁获胜），从而导致另一个处理器的副本失效。要使另一个处理器完成其写入，它必须获取数据的新副本，该副本现在必须包含更新的值。因此，此协议强制执行写入序列化。

使协议失效的替代方法是在数据项被写入时更新该数据项的所有缓存副本。这种类型的协议称为写更新或写广播协议。由于写更新协议必须将所有写入广播到共享缓存行，因此它消耗的带宽要多得多。出于这个原因，几乎所有最近的多处理器都选择实现写失效协议，在本章的其余部分，我们将只关注失效协议。

基本实现技术

在多核中实现失效协议的关键是使用总线或其他广播介质来执行失效。在较旧的多芯片多处理器中，用于相干的总线是共享内存访问总线。在单芯片多核中，总线可以是专用缓存（Intel i7 中的 L1 和 L2）和共享外部缓存（i7 中的 L3）之间的连接。为了执行失效，处理器只需获取总线访问并在总线上广播要失效的地址。所有处理器都在总线上持续窥探，监视地址。处理器检查总线上的地址是否在其缓存中。如果是这样，缓存中的相应数据将失效。

当对共享块进行写入时，写入处理器必须获取总线访问权限才能广播其失效。如果两个处理器尝试同时写入共享块，则当它们对总线进行仲裁时，它们广播无效操作的尝试将被序列化。第一个获得总线访问的处理器将导致它正在写入的块的任何其他副本失效。如果处理器试图写入相同的块，则总线强制执行的序列化也会序列化它们的写入。此方案的一个含义是，在获得总线访问权限之前，对共享数据项的写入实际上无法完成。所有相干方案都需要某种方法来序列化对同一缓存块的访问，方法是序列化对通信介质或另一个共享结构的访问。

除了使正在写入的缓存块的未完成副本失效外，我们还需要在发生缓存未命中时找到数据项。在直写缓存中，很容易找到数据项的最近值，因为所有写入的数据始终发送到内存，始终可以从内存中获取数据项的最新值。（写入缓冲区可能会导致一些额外的复杂性，必须有效地将其视为额外的缓存条目。

对于回写式缓存，查找最新数据值的问题更难，因为数据项的最新值可以位于专用缓存中，而不是在共享缓存或内存中。幸运的是，回写式缓存可以对缓存未命中和写入使用相同的监听方案：每个处理器都监听放置在共享总线上的每个地址。如果处理器发现它有所请求缓存块的脏副本，它会提供该缓存块以响应读取请求，并导致内存（或 L3）访问中止。额外的复杂性来自必须从另一个处理器的专用缓存（L1 或 L2）中检索缓存块，这通常比从 L3 检索缓存块需要更长的时间。由于回写式缓存对内存带宽的要求较低，因此它们可以支持大量更快的处理器。因此，所有多核处理器都在缓存的最外层使用回写，我们将研究使用回写式缓存实现一致性。

普通的缓存标签可以用来实现窥探的过程，每个区块的有效位使失效易于实现。读取未命中，无论是由失效还是由其他事件生成，也很简单，因为它们仅依赖于侦听功能。对于写入，我们想知道是否缓存了块的任何其他副本，如果没有其他缓存副本，那么在写回缓存中，写入就不需要被放置在总线上。不发送写入既减少了写入所需的时间，也减少了所需的带宽

为了跟踪缓存块是否被共享，我们可以添加一个与每个缓存块关联的额外状态位，就像我们有一个有效位和一个脏位一样。通过添加一个指示块是否被共享的位，我们可以决定写入是否必须生成无效。当写入处于共享状态的块时，缓存会在总线上生成失效，并将该块标记为独占。该核心不会为该块发送进一步的失效。具有缓存块唯一副本的核心通常称为缓存块的所有者。

发送失效时，所有者的缓存块的状态将从共享更改为非共享（或独占）。如果另一个处理器稍后请求此缓存块，则必须再次共享状态。因为我们的窥探缓存也会看到任何未命中，所以它知道另一个处理器何时请求了独占缓存块，并且应该共享状态。

每个总线事务都必须检查缓存地址标记，这可能会干扰处理器缓存访问。减少这种干扰的一种方法是复制标签，并将窥探访问定向到重复的标签。另一种方法是使用共享 L3 缓存中的目录;该目录指示给定块是否被共享，以及哪些内核具有副本。使用目录信息，只能将失效者定向到具有缓存块副本的缓存。这要求 L3 必须始终拥有 L1 或 L2 中任何数据项的副本，该属性称为 inclusion。

示例协议

窥探相干协议通常通过在每个内核中加入一个有限域控制器来实现。该控制器响应来自内核中的处理器和总线（或其他广播媒体）的请求，更改所选缓存块的状态，以及使用总线访问数据或使其失效。从逻辑上讲，您可以将一个单独的控制器视为与每个块相关联;也就是说，不同块的窥探操作或缓存请求可以独立进行。在实际实现中，单个控制器允许对不同块的多个操作以交错方式进行（即，一个操作可以在另一个操作完成之前启动，即使一次只允许一个缓存访问或一个总线访问）。另外，请记住，尽管我们在以下描述中提到了总线，但任何支持广播到所有相干控制器及其关联的专用缓存的互连网络都可用于实现窥探。

我们考虑的简单协议有三种状态：无效、共享和修改。

共享状态表示私有缓存中的块可能是共享的，而修改状态表示私有缓存中的块已更新;请注意，修改后的状态意味着该块是独占的。图 5.5 显示了由内核（在表的上半部分）以及来自总线（在表的下半部分）生成的请求。此协议用于回写缓存，但通过将修改后的状态重新解释为独占状态并在写入时更新缓存，可以很容易地更改为适用于直写缓存的正常方式。此基本协议最常见的扩展是添加独占状态，该状态描述了未修改但仅保存在一个专用缓存中的块。我们在第 388 页描述了这一点和其他扩展。

当总线上放置失效或写未命中时，其专用缓存具有缓存块副本的任何内核都会使其失效。对于写回缓存中的写入未命中，如果块仅在一个专用缓存中是独占的，则该缓存也会写回该块;否则，可以从共享缓存或内存中读取数据。

图 5.6 显示了使用写失效协议和回写缓存的单个专用缓存块的有限状态转换图。为简单起见，将协议的三个状态重复以表示基于处理器请求（左侧，对应于图 5.5 中表格的上半部分），而不是基于总线请求的转换（右侧，对应于图 5.5 中表格的下半部分）。粗体字用于区分总线动作，而不是状态转换所依赖的条件。每个节点中的状态表示处理器或总线请求指定的所选专用缓存块的状态。

此缓存协议中的所有状态在单处理器缓存中都是必需的，它们将对应于无效、有效（和干净）和脏状态。图 5.6 左半部分的弧线指示的大多数状态更改在回写单处理器缓存中都需要，但对共享块的写入命中时无效除外。图 5.6 右半部分的弧线所表示的状态变化只是为了实现一致性，根本不会出现在单处理器缓存控制器中。

如前所述，每个缓存只有一个有限状态机，激励来自连接的处理器或总线。图 5.7 显示了图 5.6 右半部分的状态转换如何与图左半部分的状态转换相结合，以形成每个缓存块的单个状态图。

要了解此协议工作的原因，请注意，任何有效的缓存块要么在一个或多个专用缓存中处于共享状态，要么在单个缓存中处于独占状态。任何到独占状态的转换（处理器写入块所必需的）都需要在总线上放置失效或写入未命中，从而导致所有本地缓存使块无效。此外，如果其他某个本地缓存将块置于独占状态，则该本地缓存会生成写回，该写回提供包含所需地址的块。最后，如果在总线上发生独占状态块的读未命中，则具有独占副本的本地缓存会将其状态更改为共享。

图 5.7 中灰色的操作处理总线上的读写未命中，本质上是协议的监听组件。此协议和大多数其他协议中保留的另一个属性是，处于共享状态的任何内存块在外部共享缓存（L2 或 L3，如果没有共享缓存，则为内存）中始终是最新的，这简化了实现。事实上，私有缓存的级别是共享缓存还是内存并不重要;关键是来自内核的所有访问都要经过该级别。

尽管我们的简单缓存协议是正确的，但它省略了许多使实现更加棘手的复杂性。其中最重要的是，该协议假设操作是原子的，也就是说，操作可以以不会发生干预操作的方式完成。例如，所描述的协议假设可以检测到写入未命中，获取总线，并接收响应作为单个原子动作。实际上，事实并非如此。事实上，即使是读取失误也可能不是原子的;在检测到多核 L2 中的未命中后，内核必须进行仲裁，以便访问连接到共享 L3 的总线。非原子操作引入了协议可能死锁的可能性，这意味着它达到了无法继续的状态。我们将在本节后面以及检查帝斯曼设计时探讨这些复杂情况。

对于多核处理器，处理器内核之间的一致性都是在芯片上实现的，使用监听或简单的中央目录协议。许多多处理器芯片，包括英特尔至强和AMD皓龙，都支持多芯片多处理器，这些处理器可以通过连接芯片中已经集成的高速接口来构建。这些下一级互连不仅仅是共享总线的扩展，而是使用不同的方法来互连多核。

由多个多核芯片构建的多处理器通常具有分布式内存架构，并且需要超越芯片内部的芯片间一致性机制。在大多数情况下，使用某种形式的目录方案。

基本一致性协议的扩展

我们刚才描述的相干协议是一个简单的三态协议，通常用状态的第一个字母来指代，使其成为 MSI（Modified、Shared、Invalid）协议。这个基本协议有许多扩展，我们在本节的图标题中提到。这些扩展是通过添加其他状态和事务来创建的，这些状态和事务可以优化某些行为，从而提高性能。两个最常见的扩展是

MESI 将状态 Exclusive 添加到基本 MSI 协议中，生成四种状态（Modified、Exclusive、Shared 和 Invalid）。独占状态表示缓存块仅驻留在单个缓存中，但已清理。如果一个块处于 E 状态，则可以在不生成任何无效的情况下写入该块，这优化了块在被同一缓存写入之前被单个缓存读取的情况。当然，当发生对处于 E 状态的块的读取未命中时，必须将该块更改为 S 状态以保持一致性。由于所有后续访问都会被窥探，因此可以保持此状态的准确性。具体而言，如果另一个处理器发出读取未命中，则状态将从独占更改为共享。添加此状态的优点是，同一内核对处于独占状态的块的后续写入不需要获取总线访问或生成无效，因为已知该块仅在此本地缓存中;处理器只是将状态更改为“已修改”。通过使用将相干状态编码为排他状态的位，并使用脏位来指示已修改 bock，可以很容易地添加此状态。英特尔 i7 使用 MESI 协议的变体，称为 MESIF，它添加一个状态（转发）来指定哪个共享处理器应该响应请求。它旨在提高分布式内存组织的性能。
MOESI 将状态 Owned 添加到 MESI 协议中，以指示关联的块归该缓存所有，并且在内存中已过期。在 MSI 和 MESI 协议中，当尝试共享处于“已修改”状态的块时，该状态将更改为“共享”（在原始缓存和新共享缓存中），并且必须将该块写回内存。在 MOESI 协议中，可以将块从原始缓存中的“已修改”状态更改为“拥有”状态，而无需将其写入内存。新共享块的其他缓存将块保持在“共享”状态;只有原始缓存保留的 O 状态表示主内存副本已过期，并且指定的缓存是所有者。块的所有者必须在未命中时提供它，因为内存不是最新的，如果块被替换，则必须将块写回内存。

AMD 皓龙处理器系列使用 MOESI 协议。

下一节将研究这些协议在并行和多编程工作负载中的性能;当我们检查性能时，这些扩展对基本协议的价值将很清楚。但是，在我们这样做之前，让我们简要了解一下使用对称内存结构和窥探相干方案的限制。

对称共享内存多处理器和监听协议的局限性

随着多处理器中处理器数量的增加，或者随着每个处理器的内存需求的增长，系统中的任何集中式资源都可能成为瓶颈。对于多核，单个共享总线成为只有几个内核的瓶颈。因此，多核设计采用了更高带宽的互连方案，以及多个独立的存储器，以允许更多的内核。我们在第 5.8 节中检查的多核芯片使用三种不同的方法：

IBM Power8 在单个多核中具有多达 12 个处理器，使用 8 条并行总线连接分布式 L3 缓存和多达 8 个独立的内存通道。
Xeon E7 使用三个环来连接多达 32 个处理器、一个分布式 L3 缓存和两个或四个内存通道（取决于配置）。
Fujitsu SPARC64 X+ 使用横杆将共享 L2 连接到多达 16 个内核和多个内存通道。

SPARC64 X + 是一个具有统一访问时间的对称组织。Power8 的 L3 和内存的访问时间不一致。尽管单个 Power8 多核内存地址之间的无竞争访问时间差异并不大，但随着内存的争用，即使在一个芯片内，访问时间差异也会变得很大。Xeon E7 可以像访问时间一样运行;在实践中，软件系统通常组织内存，以便内存通道与内核的子集相关联。

窥探缓存的带宽也可能成为一个问题，因为每个缓存都必须检查每个未命中，而额外的互连带宽只会将问题推到缓存上。若要了解此问题，请考虑以下示例。

考虑一个 8 处理器多核，其中每个处理器都有自己的 L1 和 L2 缓存，并且在 L2 缓存之间的共享总线上执行监听。假设平均 L2 请求（无论是相干未命中还是其他未命中）为 15 个周期。假设时钟速率为 3.0 GHz，CPI 为 0.7，加载/存储频率为 40%。如果我们的目标是一致性流量消耗不超过 50% 的 L2 带宽，那么每个处理器的最大一致性未命中率是多少？

从可以使用的缓存周期数的公式开始（其中 CMR 是相干未命中率）：

这意味着相干未命中率必须为 0.73% 或更低。在下一节中，我们将看到几个相干未命中率超过 1% 的应用程序。或者，如果我们假设 CMR 可以是 1%，那么我们可以支持不到 6 个处理器。显然，即使是小型多核也需要一种扩展窥探带宽的方法。

有几种技术可以增加侦听带宽：

如前所述，标签可以复制。这使有效的缓存级侦听带宽增加了一倍。如果我们假设一半的一致性请求不会命中 snoop 请求，并且 snoop 请求的成本仅为 10 个周期（而不是 15 个周期），那么我们可以将 CMR 的平均成本降低到 12.5 个周期。这种降低允许相干未命中率为 0.88，或者支持一个额外的处理器（7 对 6）。
如果多核（通常为 L3）上的最外层缓存是共享的，我们可以分配该缓存，以便每个处理器都有一部分内存并处理该部分地址空间的窥探。IBM 12 核 Power8 使用的这种方法导致了 NUCA 设计，但有效地将 L3 的 snoop 带宽按处理器数量扩展。如果 L3 中存在窥探命中，那么我们仍然必须广播到所有 L2 缓存，而 L2 缓存必须反过来窥探它们的内容。

由于 L3 充当窥探请求的过滤器，因此 L3 必须具有包容性。

我们可以将目录放在最外层的共享缓存（例如 L3）的级别。L3 充当窥探请求的过滤器，并且必须具有包容性。在 L3 上使用目录意味着我们不需要窥探或广播到所有 L2 缓存，而只需要目录指示的那些缓存可能具有块的副本。正如 L3 可以分发一样，关联的目录条目也可以分发。这种方法用于 Intel Xeon E7 系列，它支持 8 到 32 个内核。

图 5.8 显示了具有分布式缓存系统（例如方案 2 或 3 中使用的系统）的多核的外观。如果添加额外的多核芯片以形成更大的多处理器，则需要一个片外网络，以及一种扩展相干机制的方法（我们将在第 5.8 节中看到）。

AMD皓龙代表了窥探协议和目录协议之间的另一个中间点。内存直接连接到每个多核芯片，最多可以连接四个多核芯片。该系统是 NUMA，因为本地内存速度更快。Opteron使用点对点链路实现其相干协议，以广播多达三个其他芯片。由于处理器间链路不共享，因此处理器可以知道无效操作何时完成的唯一方法是显式确认。因此，相干协议使用广播来查找潜在的共享副本，就像窥探协议一样，但使用确认来对操作进行排序，就像目录协议一样。由于在 Opteron 实现中，本地内存仅比远程内存快一些，因此某些软件将 Opteron 多处理器视为具有统一的内存访问。

在第 5.4 节中，我们研究了基于目录的协议，这些协议消除了在未命中时广播到所有缓存的需要。某些多核设计使用目录在多核（Intel Xeon E7）中，而其他人则在扩展到多核之外时添加目录。分布式目录消除了对单个点序列化所有访问的需要（通常是侦听方案中的单个共享总线），并且任何删除单点序列化的方案都必须处理许多与分布式目录方案相同的挑战。

实现侦听缓存一致性

在一个没有单一中央总线的系统中，我们必须找到一些其他方法来使原子失误中的步骤。特别是，我们必须确保两个试图同时写入同一块的处理器（这种情况称为争用）是严格有序的：一个写入被处理，并在下一个写入开始之前进行。一场比赛中两个写作中的哪一个赢得比赛并不重要，只是只有一个获胜者的连贯动作首先完成。在使用多条总线的多核中，如果每个内存块仅与一条总线相关联，则可以消除争用，从而确保访问同一块的两次尝试必须由该公共总线进行序列化。此属性以及在比赛中重新启动失败者未命中处理的能力，是在没有总线的情况下实现窥探缓存一致性的关键。

可以将窥探和目录结合起来，并且一些设计在多核和多个芯片之间的目录或一个缓存级别的目录和另一个级别的窥探组合中使用监听。

对称共享内存多处理器的性能

在使用侦听相干协议的多核中，几种不同的现象结合在一起决定了性能。具体而言，整体缓存性能是单处理器缓存未命中流量和通信引起的流量行为的组合，这会导致失效和后续缓存未命中。更改处理器计数、缓存大小和块大小可能会以不同的方式影响未命中率的这两个组成部分，从而导致整体系统行为是这两种影响的结合。

附录 B 将单处理器未命中率分解为三个 C 分类（容量、强制和冲突），并深入了解应用程序行为和缓存设计的潜在改进。同样，处理器间通信产生的未命中（通常称为相干未命中）可以分为两个独立的来源。

第一个来源是通过缓存一致性机制进行数据通信而产生的真正共享失误。在基于失效的协议中，处理器对共享缓存块的第一次写入会导致失效，从而建立该块的所有权。此外，当另一个处理器尝试读取该缓存块中的修改字时，会发生未命中，并且会传输生成的块。这两种未命中都归类为真正的共享未命中，因为它们直接源于处理者之间的数据共享。

第二种效应称为错误共享，源于使用基于失效的一致性算法，每个缓存块只有一个有效位。当一个块失效（并且后续引用导致未命中）时，就会发生错误共享，因为块中的某些单词（而不是正在读取的单词）被写入其中。如果写入的单词实际上被接收无效的处理器使用，则该引用是真正的共享引用，并且会导致与块大小无关的未命中。但是，如果写入的单词和读取的单词不同，并且失效不会导致传达新值，而只会导致额外的缓存未命中，则为错误共享未命中。在错误共享未命中中，块是共享的，但缓存中实际上没有字被共享，如果块大小为单个字，则不会发生未命中。以下示例使共享模式更加清晰。

商业工作负载

在本节中，我们将研究 4 处理器共享内存多处理器在运行联机事务处理工作负载时的内存系统行为。我们研究的研究是在 1998 年使用 4 处理器 Alpha 系统完成的，但它仍然是对此类工作负载的多处理器性能的最全面和最有见地的研究。我们将重点了解多处理器缓存活动，尤其是 L3 中的行为，其中大部分流量都与一致性相关。

结果在 AlphaServer 4100 上或使用以 AlphaServer 4100 为模型的可配置模拟器收集。AlphaServer 4100 中的每个处理器都是 Alpha 21164，每个时钟最多发出 4 条指令，运行频率为 300 MHz。尽管该系统中 Alpha 处理器的时钟速率比 2017 年设计的系统中的处理器慢得多，但该系统的基本结构（由四问题处理器和三级缓存层次结构组成）与多核 Intel i7 和其他处理器非常相似，如图 5.9 所示。我们不关注性能细节，而是考虑查看每个处理器 2 到 8 MiB 不等的 L3 缓存的模拟 L3 行为的数据。

尽管最初的研究考虑了三种不同的工作负载，但我们还是将注意力集中在以 TPC-B（其内存行为类似于其较新的表亲 TPC-C，在第 1 章中描述）并为底层数据库建模的在线事务处理（OLTP）工作负载上。工作负载由一组生成请求的客户端进程和一组处理请求的服务器组成。服务器进程消耗了 85% 的用户时间，其余时间将转到客户端。尽管 I/O 延迟通过仔细调整和足够的请求来保持处理器繁忙而隐藏，但服务器进程通常会在大约 25,000 条指令后阻塞 I/O。总体而言，71% 的执行时间是在用户模式下度过的，18% 是在操作系统中度过的，11% 的执行时间是空闲的，主要是等待 I/O。在所研究的商业应用中，OLTP 应用对内存系统的压力最大，即使使用更大的 L3 缓存进行评估，也显示出重大挑战。例如，在 AlphaServer 上，处理器停滞不前在大约 90% 的周期中，内存访问占用了几乎一半的失速时间，而 L2 错过了 25% 的失速时间。

我们首先研究改变 L3 缓存大小的影响。在这些研究中，每个处理器的 L3 缓存从 1 到 8 MiB 不等;每个处理器 2 MiB，L3 的总大小等于 Intel i7 6700 的总大小。然而，在 i7 的情况下，缓存是共享的，这提供了一些优点和缺点。共享的 8 MiB 缓存不太可能优于总大小为 16 MiB 的单独 L3 缓存。图 5.10 显示了使用双向集关联缓存增加缓存大小的效果，这减少了大量的冲突未命中。由于 L3 未命中次数减少，执行时间随着 L3 缓存的增长而缩短。令人惊讶的是，几乎所有的增益都发生在 1 到 2 MiB（或四个处理器的总缓存的 4 到 8 MiB）中。除此之外，几乎没有额外的收益，尽管缓存未命中仍然是导致 2 MiB 和 4 MiB 缓存性能显著损失的原因。问题是，为什么？

为了更好地理解这个问题的答案，我们需要确定哪些因素会影响 L3 未命中率，以及它们如何随着 L3 缓存的增长而变化。图 5.11 显示了这些数据，显示了来自五个来源的每条指令贡献的内存访问周期数。具有 1 MiB L3 的 L3 内存访问周期的两个最大来源是指令和容量/冲突未命中。随着 L3 的扩大，这两个来源缩小为次要贡献者。不幸的是，

强制共享、错误共享和真实共享未命中不受较大 L3 的影响。因此，在 4 MiB 和 8 MiB 时，真正的共享未命中数占未命中数的主导部分;当将 L3 缓存大小增加到 2 MiB 以上时，真实共享未命中率的更改会导致总体未命中率的降低有限。

增加缓存大小可以消除大多数单处理器未命中，同时保持多处理器未命中。增加处理器计数如何影响不同类型的未命中？图 5.12 显示了这些数据，假设基本配置具有 2 MiB、双向集关联 L3 缓存（每个处理器缓存大小的有效值与 i7 相同，但关联性较低）。正如我们所预料的那样，真正共享未命中率的增加（单处理器未命中率的任何减少都无法弥补）导致每条指令的内存访问周期总体增加。

我们研究的最后一个问题是，增加块大小（这应该会降低指令和冷未命中率，并在限制范围内降低容量/冲突未命中率，并可能降低真正的共享未命中率）是否有助于此工作负载。图 5.13 显示了当块大小从 32 字节增加到 256 字节时，每 1000 条指令的未命中次数。将块大小从 32 字节增加到 256 字节会影响以下四个未命中率分量：

真实共享未命中率下降了 2 倍以上，表明真实共享模式存在一些局部性。
正如我们预期的那样，强制失误率显着降低。
冲突/容量未命中显示小幅下降（1.26 倍，而块大小增加 8 倍），表明大于 2 MiB 的 L3 缓存发生的单处理器未命中空间局部性不高。
错误共享失误率虽然绝对值很小，但几乎翻了一番。

对指令失误率缺乏显着影响是令人吃惊的。如果存在具有此行为的纯指令缓存，我们将得出结论，空间局部性非常差。在混合 L2 和 L3 缓存的情况下，指令数据冲突等其他影响也可能导致较大块的指令缓存未命中率较高。其他研究已经记录了大型数据库和 OLTP 工作负载的指令流中的低空间局部性，这些工作负载具有许多短的基本块和专用代码序列。根据这些数据，较大块大小 L3 的未命中损失以及 32 字节块大小 L3 的未命中损失可以表示为 32 字节块大小损失的乘数。

借助能够快速访问块的现代 DDR SDRAM，这些数字是可以实现的，尤其是在 64 字节（i7 块大小）和 128 字节块大小时。当然，我们还必须担心内存流量增加的影响，以及可能与其他内核争夺内存的影响。后一种效应很容易抵消通过提高单个处理器的性能而获得的收益。

进程并发和操作系统工作负载

我们的下一个研究是一个由用户活动和操作系统活动组成的多程序工作负载。使用的工作负载是 Andrew 基准测试编译阶段的两个独立副本，该基准测试模拟软件开发环境。编译阶段由使用八个处理器执行的 UNIX“make”命令的并行版本组成。工作负载在 8 个处理器上运行 5.24 秒，在 3 个不同的文件系统上创建 203 个进程并执行 787 个磁盘请求。工作负载使用 128 MiB 内存运行，并且不会发生分页活动。

工作负载有三个不同的阶段：编译基准，这涉及大量的计算活动;在库中安装目标文件;并删除对象文件。最后一个阶段完全由 I/O 主导，只有两个进程处于活动状态（每个运行一个）。在中间阶段，I/O 也起着重要作用，处理器基本上处于闲置状态。总体工作负载比 OLTP 工作负载占用更多系统和 I/O 密集型。

对于工作负载测量，我们假设以下内存和 I/O 系统：

1 级指令缓存 — 32 KB，双向集关联，具有 64 字节块，1 个时钟周期命中时间。
1 级数据缓存 — 32 KB，双向集关联，具有 32 字节块，1 个时钟周期命中时间。我们的重点是检查 1 级数据缓存中的行为，这与 OLTP 研究相反，后者侧重于 L3 缓存。
2 级缓存 — 1 MiB 统一的双向集关联，具有 128 字节块、10 个时钟周期的命中时间。
主存储器 — 总线上的单个存储器，访问时间为 100 个时钟周期。
磁盘系统 - 固定访问延迟为 3 毫秒（低于正常值以减少空闲时间）。

图 5.14 显示了如何使用刚才列出的参数分解 8 个处理器的执行时间。执行时间分为四个部分：

空闲 - 在内核模式空闲循环中执行
用户 - 在用户代码中执行
同步 - 执行或等待同步变量
内核 - 在既不处于空闲状态也不处于同步访问状态的操作系统中执行

这种进程并发工作负载会显著降低指令缓存性能，至少对于操作系统而言是这样。操作系统中 64 字节块大小的指令缓存未命中率，双向集关联缓存的 32 KB 从 1.7% 不等

对于 256 KB 缓存，缓存为 0.2%。在各种缓存大小中，用户级指令缓存未命中率大约是操作系统速率的六分之一。这在一定程度上解释了这样一个事实，即尽管用户代码执行的指令数量是内核的 9 倍，但这些指令所花费的时间仅为内核执行的较少指令数量的 4 倍。