一致性失效的分类真共享与伪共享接下来我们将一致性失效进一步分为两个子类真共享失效和伪共享失效。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/35c5eda0ba3a1779c69bfb6adf7a1f6b_3.png以下是这两种失效的定义与对比真共享失效定义即使将缓存块大小减小到机器支持的最小单位例如1字节或1个字运行相同程序时该失效依然会发生。这是因为处理器之间确实在共享和通信真实数据。示例一个缓存写入某数据后另一个处理器需要读取该数据必须将其拉入自己的缓存。这种因实际数据通信引发的失效就是真共享失效。伪共享失效定义如果使用较小的缓存块如1字节运行程序不会发生该失效而使用较大的缓存块时会发生那么这就是伪共享失效。其根本原因在于缓存块尺寸过大导致两个本不相关的数据项被放置在同一个缓存行中。更广泛的含义数据在不同缓存间“弹跳”但触发失效的特定加载/存储序列在缓存行很小时并不会引起失效。它可能发生在数据为后续共享做准备而移动时但触发此次失效的具体操作并非由于实际的数据通信。实例分析让我们通过一个具体例子来区分这两种失效。假设初始条件如下两个数据字X1和X2被存储在同一个缓存行中。处理器 P1 和 P2 的缓存中都拥有该缓存行的可读副本。以下是操作序列及其对应的失效类型分析P1 写入 X1操作P1 需要获得该缓存行的独占权因此必须无效化 P2 缓存中的该行。分析这是真共享失效。因为X1是实际被共享和修改的数据P2 中的副本必须被移除。P2 读取 X2操作P2 需要读取X2但该缓存行已被 P1 独占因此发生失效需要从 P1 或内存获取数据。分析这是伪共享失效。P2 想读的是X2而 P1 修改的是X1两者并无真正的数据依赖。失效的发生仅仅是因为X1和X2位于同一缓存行。P1 再次写入 X1分析同样是伪共享失效。P2 并未触及X1但因其与X2同处一行导致该行状态变化。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/35c5eda0ba3a1779c69bfb6adf7a1f6b_5.pngP2 写入 X2分析伪共享失效。原理同上X1和X2的耦合导致了不必要的通信。P1 读取 X2分析这是真共享失效。P2 写入了X2P1 随后读取它发生了真实的数据通信。这个例子表明伪共享会引入大量不必要的缓存失效和一致性通信损害系统性能。多核扩展性问题https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/35c5eda0ba3a1779c69bfb6adf7a1f6b_7.png现在让我们看看在多核环境下共享失效如何影响系统的可扩展性。首先观察一个在线事务处理数据库工作负载。在四处理器系统上运行并改变缓存大小随着缓存增大指令失效、容量失效、冲突失效冷启动失效会减少因为缓存能容纳更多非共享数据。然而真共享失效和伪共享失效的数量基本不变。因为它们取决于数据共享模式和缓存块大小而非总缓存容量。接着在固定缓存容量下增加处理器核心数量从1到8非共享相关的失效指令、容量、冲突保持不变。但是真共享和伪共享失效均随核心数增加而上升。这引出了一个严峻的问题当核心数量增加到几十甚至上百个时系统的性能很可能被共享和伪共享导致的缓存失效所主导。这迫使我们必须思考如何设计更具可扩展性的一致性协议例如本节开头提到的基于目录的一致性协议它就是为了解决大规模多核系统中监听协议带宽和可扩展性不足的问题而提出的。总结https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/35c5eda0ba3a1779c69bfb6adf7a1f6b_9.pnghttps://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/35c5eda0ba3a1779c69bfb6adf7a1f6b_10.png本节课中我们一起学习了缓存一致性失效的详细分类。我们从经典的“三C”失效模型出发引入了由多核间通信引发的一致性失效并重点区分了其中的真共享失效源于实际数据通信和伪共享失效源于过大的缓存行将不相关数据捆绑在一起。通过实例分析我们看到了伪共享如何导致不必要的性能开销。最后我们探讨了在多核扩展场景下共享失效可能成为性能瓶颈从而引出了对更高效、可扩展的一致性协议如基于目录的协议的需求。理解这些概念是优化并行程序性能和设计下一代多核体系结构的基础。106目录一致性协议入门 在本节课中我们将学习目录一致性协议的基本概念。我们将探讨监听式协议面临的挑战并了解目录协议如何通过将广播通信转变为点对点通信来解决可扩展性问题。最后我们将讨论非统一内存访问架构以及混合协议设计。监听式协议的挑战上一节我们介绍了基于总线的监听式协议。本节中我们来看看其性能和可扩展性方面的挑战。监听式协议的核心挑战在于随着系统处理器数量的增加所有处理器都需要通过一个共享介质如总线进行通信。每当一个核心发生缓存缺失时该事务都需要广播到总线上所有其他核心都必须监听此事务并与自己的本地缓存进行比对以执行必要的操作如使无效或回复数据。这种设计带来的问题是总线带宽需求。为了在增加核心数量的同时保持每个核心的缓存缺失率不变总线的带宽需求将按O(N)增长其中N是处理器数量。当N较小时例如8这可能不是问题。但当N增长到1000甚至百万级别时构建一个如此高带宽且能支持原子事务仲裁的总线将变得极其困难。目录协议的核心思想为了解决上述可扩展性问题我们引入了目录缓存一致性协议。目录协议的关键思想是不再将无效化请求或缓存缺失广播给系统中的所有其他核心而是与一个称为“目录”的特定位置进行通信。这个目录负责追踪哪些缓存拥有特定缓存行的副本。以下是其工作原理当一个核心发生缓存缺失并需要获取数据时它会向目录发送请求。目录检查其记录确定当前有哪些缓存持有该数据行。如果只有一个其他核心持有该数据例如处于只读状态而请求核心需要独占访问例如进行写入那么目录只需向那个特定的核心发送一个无效化消息而不是向所有N个处理器广播。这样我们就将一个广播系统转变为了一个点对点通信系统。虽然我们需要额外的开销来维护目录信息但显著降低了对互联网络带宽的需求。目录协议的系统架构让我们看看目录协议如何融入系统框图。在一个典型的目录协议系统中多个 CPU 通过共享内存进行通信。每个 CPU 首先检查自己的缓存。如果缓存缺失CPU 的缓存控制器会向与该内存地址关联的目录控制器发送一条消息。目录控制器为内存中的每一行维护一个共享者列表记录哪些缓存可能拥有该数据的副本。目录根据此列表仅向相关的缓存发送点对点消息如无效化请求并协调数据的传递。此时的互联网络如 Omega 网络或 Mesh 网络仍然是均匀的所有节点间的通信延迟是固定的因此这仍是一个统一内存访问系统。非统一内存访问架构我们可以进一步优化架构将内存和目录分布到各个 CPU 节点上。在这种设计中每个 CPU 节点都直接连接着一部分本地内存和一个目录控制器。这样做的好处是可扩展性增加 CPU 时也同步增加了内存和目录资源。局部性优势CPU 可以快速访问其本地内存。对于主要被单个核心访问的数据如程序的栈、指令段可以分配在其本地内存中从而获得极低的访问延迟。只有共享数据才需要通过互联网络进行远程访问。这种某些数据“近”、某些数据“远”的架构被称为非统一内存访问架构。现代多路服务器和某些桌面处理器如采用多芯片模块的 AMD 处理器都已采用 NUMA 架构。操作系统如 Linux可以感知 NUMA 拓扑并尝试将进程的内存分配在其本地节点上以优化性能。需要强调的是内存访问延迟不同并不一定意味着系统是基于目录的一致性 NUMA 系统。也存在基于监听协议但内存分布不均的系统。通常文献中提到的CC-NUMA特指基于目录协议实现的缓存一致性 NUMA 系统。混合协议设计在实际系统中经常混合使用不同的协议。一个常见的模式是在单个多核芯片内部使用基于总线的监听协议而在连接多个芯片时使用基于目录的协议。以下是其工作方式在芯片内部各个核心通过高速总线互联并使用监听协议维护一致性。整个芯片对外例如其末级缓存控制器作为一个整体参与到跨芯片的目录协议中。它会响应来自其他芯片目录的请求如无效化并在内部转换为总线事务。这种设计非常普遍。例如一些现代大型系统如基于 Intel 至强处理器的 SGI UV 系统就使用商品化的多核处理器芯片并通过一个目录一致的 NUMA 互联网络将它们连接起来在芯片间实现了可扩展的一致性。总结https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/8d54fecc93a9153d2c36b7147e8a5cf1_1.pnghttps://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/8d54fecc93a9153d2c36b7147e8a5cf1_2.png本节课中我们一起学习了目录一致性协议。我们首先分析了基于总线的监听式协议在可扩展性上面临的带宽挑战。然后我们引入了目录协议其核心思想是通过一个中心目录来追踪数据副本的位置从而将广播通信转变为高效的点对点通信。接着我们探讨了如何将目录与内存分布到各节点形成非统一内存访问架构以利用数据局部性。最后我们了解了在实际系统中目录协议与监听协议可以混合使用例如在芯片内使用总线在芯片间使用目录以兼顾效率与可扩展性。107基于目录的分布式共享内存实现 在本节课中我们将学习如何在实际的硬件中实现基于目录的分布式共享内存系统。我们将探讨如何确定数据在系统中的“家”即目录或主节点深入分析目录内部的数据结构并理解缓存与目录之间如何通过消息传递来协同工作以维护数据的一致性。目录映射策略 ️上一节我们介绍了基于目录的分布式共享内存机器的基本概念本节中我们来看看如何确定一个内存地址对应的目录在哪里。你有一个内存地址。通常在这些系统中映射是基于物理地址进行的而不是虚拟地址。这是因为此时数据是在多个不同系统之间共享的地址已经通过了转换后备缓冲器或内存管理单元的转换成为了物理地址。为了确定目录在分布式共享内存机器中有时也称为“主节点”的位置即应该访问哪个目录有多种方法。其中一种更常见的方法是直接使用地址中的某些位。以下是具体做法取系统中目录的总数计算其以2为底的对数。然后从地址中取出对应数量的位作为主节点编号。因此当你发生缓存未命中并且需要加载该数据时你会发送一条消息。这条消息的目的地标识符就是计算出的主节点编号。希望你的互连网络知道如何将数据路由到那个目录。使用地址的高位进行映射有一些好处。正如我们在非统一内存访问架构中讨论过的操作系统可以控制数据的放置。基于这些高位你可以决定数据将位于系统中的哪个节点或目录。因此操作系统可以基于物理地址来分配内存、分配堆栈、分配指令空间因为操作系统对物理地址的分配拥有绝对控制权。缺点是一个目录或主节点可能成为热点。假设突然之间系统中的所有处理器都试图访问同一页内存例如一个包含所有系统锁的热页。如果你查看这些地址它们都会位于较低的地址区域。即使没有发生伪共享通常也会尝试将所有数据打包到一个页面或结构中很难根据地址的非常高阶位进行交错存放。特别是考虑到程序对由操作系统管理的物理地址高阶位几乎没有控制权。如果采用高位映射所有这些地址都会映射到同一个目录导致所有消息流量都涌向一个节点。这几乎又变回了一种总线结构。虽然情况稍好因为我们不一定需要使所有其他位置的数据失效但目录本身及其带宽开始成为关键瓶颈。另一方面你可以尝试用地址的低位来决定使用哪个目录或主节点。这样你仍然有缓存行内的偏移量但决定主节点的物理地址位是低位。这最终会实现非常好的负载均衡。因为根据不同的缓存行你将几乎是随机地选择不同的主节点。同一个缓存行会去往同一个主节点或目录。如果你有稍微不同的缓存行这很常见因为很难将所有数据争用在一个缓存行内流量就会分散到不同的控制器上从而实现良好的分布。然而缺点是操作系统在这里失去了放置控制能力。这是一个需要权衡的棘手问题。有些人甚至构建了可配置的系统。这涉及到更高级的内容我将在今天讲座的最后一张幻灯片中提及。你可以考虑构建一些系统根据实际的地址和页表输出可能做出不同的映射选择。但系统中的所有组件目录和所有缓存都必须就映射方式达成一致这有点棘手。目录内部结构 现在我们来看看目录内部有什么。我们添加了这个新的硬件结构。每当我们添加一个新的硬件结构时我喜欢查看它内部的所有位。我们添加的这个新硬件结构对于连接到该目录的特定内存中的每一个缓存行都有一个条目。因此纵观整个系统实际上系统中的每一个内存行都会有一个额外的数据条目。以下是其朴素实现方式如果系统中有10TB内存朴素的方法是为系统中每一个块大小的内存块缓存块大小都设置一个目录条目。这些条目通常保存在大表中一般使用SRAM也可能尝试放在DRAM中。目录条目里有什么目录需要知道缓存行处于什么状态。在我们的基本协议中我们将查看三种不同的状态共享、未缓存和独占。一切从未缓存状态开始数据在主存中。当它被读入缓存只读时目录会将其标记为共享。当它被读入缓存读写时目录会将其标记为独占。如果处于共享或独占状态我们需要知道是哪个节点。如果是独占我们需要唯一地知道哪个节点拥有它以便在需要使其失效时能够发送消息。如果是共享我们需要知道所有可能拥有该数据副本的节点列表以便向它们发送消息。这比必须向系统中的所有节点广播或发送消息要好。因此这里会有一个共享者列表。在一个朴素的全映射目录中对于系统中的每个核心或每个缓存都会有1位。该位为1表示该核心拥有数据的只读副本为0则表示没有。当其他缓存试图以可写方式获取该数据时目录将必须使这些设置了1的位的核心的缓存副本失效。如果是独占状态这里不会设置多个位。因为这基本上意味着该核心拥有可写副本。为了保持数据一致性我们不希望有多个可写副本。如果处于未缓存状态我们不需要跟踪任何信息这些位是无关紧要的。这里还有另一个状态挂起。这通常实际上会演变成几个子状态。在目录端有不同的方式来跟踪这一点。这些事务需要多个步骤。例如你想获取数据的可写权限目录将必须使所有其他副本失效。这无法瞬时完成但我们希望提供原子性的表象。通常你实际上会在目录中存储一些子状态例如表示缓存行当前正在从某种状态转换到另一种状态例如从U到E在此期间阻止其他事务对其进行操作。实现方式之一是将状态存储在目录中另一种方式是使用一个全相联的旁路结构来跟踪所有当前正在变化的缓存行。目录足够智能知道当其他请求在该行处于变化状态时到达可以拒绝该请求或告知对方稍后重试。实现方式可以不同但这会变得相当复杂。我们将在高层次上讨论状态转换并假设它们以某种方式是原子的。缓存状态转换MSI协议 现在我们来看看MSI协议如何与此结合。你也可以考虑用MESI或其他协议来实现但MSI更简单一些所以我们先看它。此外在目录协议中像MESI这样的协议的好处会减弱因为如果你以独占状态开始时未修改拉入数据而其他人想要获取只读副本你基本上必须向那个核心发送消息。这在总线上是廉价的因为它可以看到总线上的事务并进行侦听从而从E状态降级到共享状态。但现在这变成了实际的工作目录必须生成消息并且你必须等待来自拥有独占副本的缓存的响应。因此在转向这些分布式共享内存协议时类似MESI的协议就不那么常见了。这是一张我们之前见过的幻灯片展示了总线上的MSI协议。当我们转向基于目录一致性的MSI时情况发生了一些变化。在深入之前我想指出这里实际上有两个不同的状态机在运行一个运行在各个处理器的缓存控制器中另一个运行在目录中。你会看到它们在这里使用了不同的字母表示S、U、E 对比 M、S、I我们特意这样标记以避免混淆。这两个状态机通过相互发送消息进行交互。随着消息在目录和缓存之间流动它们将根据这两个表格经历不同的状态转换。让我们深入了解一下。这是我们总线侦听MSI协议中相同的修改、共享和无效状态规则也相同。如果你处于修改状态可以写入而无需发送任何消息。如果处于共享状态可以读取数据而无需联系任何人。如果处于无效状态并想对其进行任何操作可能需要联系某人在这里是目录就像之前我们必须在总线上发送事务一样。同样从S到M或从M到S的转换也需要通信。可以认为这是相同的状态机在运行只是以前我们通过总线发送事务现在我们将把这些事务转换成发送给目录的消息以及我们从目录接收并必须响应的消息。以前我们侦听总线上的流量这导致我们转换到不同的状态例如其他处理器试图写入我们在总线上看到这一点因此必须将自己转换到无效状态。现在我们实际上会从目录控制器收到一条消息。让我们以一个缓存行在处理器P1中的状态为例从入口点开始。我们从无效状态开始。假设我们想获取该行的只读副本即发生读未命中。处理器1将向目录控制器发送一条读未命中消息。在此期间它没有可读副本无法访问数据实际上仍处于I状态有时人们会在这里设置一个挂起状态具体取决于实现方式。发送读未命中消息后等待响应。这个响应将包含你需要的数据并且是一个同步点表示你可以安全地转换到S状态。类似地对于写未命中如果我们处于无效状态并进行写入我们将向目录控制器发送写未命中请求。它需要做一些处理我们可能必须等待一段时间因为它可能必须使系统中所有其他行的副本失效。然后当我们得到响应时我们就获得了数据并可以转换到修改状态。这些转换弧很简单。我们可以在M状态下由P1进行读取或写入而无需与任何人通信。但现在我们这里有一些不同的消息传入如果我们在共享状态必须响应一条失效消息。这与总线侦听不同以前我们看到另一个处理器试图写入这使我们转换到I现在目录控制器发送一条消息说“使该行失效”这将使我们转换到I。注意这里可能需要回复因为目录控制器想知道系统中的所有缓存行何时已被失效这可能需要可变的时间所以它要等待回复返回。如果我们在修改状态收到来自目录控制器的失效消息我们需要写回数据因为我们有已修改的数据然后回复。还剩下中间的两个转换弧我们在共享状态并想对该缓存行进行写入。在实际写入之前我们必须向目录发送消息说明我们正在进行写未命中希望获取该数据的可写权限。我们必须等待回复才能转换到M状态因为我们必须等待目录控制器与所有其他缓存通信使它们不再拥有只读副本。另一个转换是从修改状态到共享状态。这有点不同但理念相同另一个处理器试图进行读取。我们收到一条读未命中消息不需要使数据失效但需要写回数据因为我们拥有最新的副本。我们将写回数据作为响应然后转换到共享状态因为另一个核心也只拥有只读副本。这里还有两个有趣的转换弧在我们基础的MSI协议中没有。这些对应的情况是如果我们的缓存中有数据但由于冲突未命中或容量未命中而被替换出去最好去更新目录告诉目录将来如果其他缓存想要获取该数据不需要再联系你。如果在修改状态我们可以写回数据因为是脏数据并通知目录我们不再拥有副本目录可以将其转换到未缓存状态。如果在共享状态我们可能希望如果互连有额外带宽在因被替换而失效时发送一条消息通知目录将我们从共享者列表中移除。如果共享者列表因此变空目录可能会将该缓存行从共享状态完全更改为未缓存。但需要指出这些并非严格必要。原因是如果我们构建缓存控制器系统使得当你在某个缓存行处于无效状态时收到一条消息例如本应触发这些转换的消息我们可以直接回复说“我们不再拥有它我们是无效的”。如果你处于I状态唯一可能收到的消息就是一条失效消息而那条消息本就会让你保持在I状态所以我们可以忽略该消息或像回复正常失效消息一样回复。目录状态转换 目录的状态转换看起来有些不同。我们有未缓存、共享和独占状态。如前所述共享意味着系统中可能有多个只读副本独占意味着系统中只有一个缓存拥有该数据。有趣的是如果你实际运行的是MESI协议目录中运行的协议不会改变因为这里的独占状态在目录看来是相同的。让我们看看目录中缓存行状态的几个转换。从未缓存状态开始。假设我们收到来自处理器P的读未命中消息。我们应该转换到S状态给它一个只读副本回复实际数据并将P添加到共享者列表中。这样我们就知道如果有人需要使该行失效我们需要联系P。现在我们在共享状态假设有其他处理器发来读未命中。我们将提供数据并将其添加到共享者列表中共享者列表会增长。回到未缓存状态假设突然收到来自处理器P的写未命中。我们提供数据共享者列表或所有者列表将唯一地添加P并且我们将其置于独占状态因为之前是未缓存不需要联系其他人。现在看另一个转换。假设处理器P0独占拥有数据但突然另一个处理器比如P2要访问该数据。我们已处于独占状态但请求者是不同的缓存。这里需要发生的是我们需要从P0获取数据P0将写回数据并转换到无效状态。然后我们需要将数据提供给新的处理器P2并将P2添加到共享者列表此时是独占所有者。我们可以转换到这个状态。再看这两个状态之间的边。首先看从E到U的边这是写回数据发生的转换。假设你在这里看到一个数据写回发生。一条相当于缓存端可选弧的消息发送给你。数据是可写的在某个缓存中是独占的现在不再可写。最好联系目录写回数据并清空共享者列表这样目录就知道此时没有人拥有它的副本。还有其他几个转换边我们在共享状态有多个只读副本一个缓存发来写未命中消息需要获取可写权限。现在我们必须经历一个相当长的过程遍历整个共享者列表向列表中的所有共享者发送消息说“使这个副本失效并告诉我何时完成”。我们将在目录处收集所有响应。一旦所有响应返回我们知道没有其他人拥有只读副本就可以将数据提供给请求者并将其添加到共享者或所有者列表。最后一条从E到S的橙色边如果我们有一条线在某个缓存中是可写的而另一个缓存现在想读取它。另一个缓存将发送读未命中。拥有独占副本的缓存将从M降级到S。但目录将在这里从E转换到S。我们必须从之前独占拥有它的节点获取最新的数据因此我们将向该节点发送获取请求。一旦我们获得最新的数据就可以将其转发给新的读取者并将该处理器添加到共享者列表。这些开始变得有点复杂因为涉及多个状态机的交互。消息类型总结 我们在这里加快一点速度。我包含了教科书中的这张图表作为示例快速总结了所有不同的消息类型以及它们可以从谁发出、发送给谁。有时消息需要传递地址有时需要传递数据有时需要传递消息来自哪个节点以便将其添加到共享者列表。但我不打算深入讨论细节。我想说的一点是这里列出的消息类型不包括确认消息。当你请求某物时会有回复返回。图表中看到了数据值回复但那只是实际数据不包括来自共享者确认失效等的响应。另一种这里没有绘制的常见消息类型是否定确认。如果有一个缓存行正在转换中目录处于挂起状态此时收到一个请求你可能只需要告诉那个缓存“稍后重试我现在无法处理这个情况”。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/2d2905f0e864c9ab402bd0270fa59892_1.pnghttps://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/2d2905f0e864c9ab402bd0270fa59892_2.png本节课总结在本节课中我们一起学习了基于目录的分布式共享内存系统的关键实现细节。我们探讨了如何通过地址位映射来确定数据的主节点分析了目录内部用于跟踪缓存行状态和共享者列表的数据结构并详细走查了缓存控制器和目录控制器在MSI协议下的状态转换过程。理解这些交互机制是构建高效、可扩展的共享内存系统的核心。108目录一致性协议的可扩展性 在本节课中我们将深入探讨目录一致性协议的可扩展性涵盖多逻辑通信通道、内存排序点、前向进度保证以及目录结构的演进。我们将分析如何避免死锁和活锁并了解现代大规模并行系统中的目录协议实现。多逻辑通信通道与死锁避免 上一节我们介绍了目录协议的基本原理本节中我们来看看如何管理复杂的通信流程以避免死锁。多个逻辑通信通道是必需的。我们之前讨论的所有不同消息类型加上图中未绘制的约10种类型不能同时使用同一个网络。如果只有一个互连网络或一个逻辑网络可能会出现响应消息被排在请求消息之后的情况从而产生更多流量。在这些协议中通信分为多个阶段。消息从A点发送到B点然后从B点到C点再从C点返回B点最后从B点返回A点。如果将这些通信叠加到一个互连网络上并采用队头处理即优先处理队列头部的消息很容易出现新响应消息“插队”的情况该响应可能依赖于系统中其他地方正在进行的其他事务而你正在等待它。例如一个新请求到达排在一个响应之后。一个新请求到达排在一个响应之前。突然之间就可能发生死锁。解决此问题的一种方法是分析所有不同的消息类型并确定哪些类型可以同时共存于网络上。一个很好的例子是在一个相对基本的缓存一致性协议中可能有12种不同的消息类型。可以尝试将其缩减为3或4个不同的流量类别这些类别的流量混合时永远不会引入死锁。如果想确保绝对安全可以建立12个独立的网络或12个不同的逻辑网络但这构建成本高昂。因此人们尝试找出不同流量的等价类然后只建立相应数量的网络。但必须将这些流隔离在不同的逻辑或物理通道上以确保不会发生死锁。内存排序点与仲裁 ⚖️现在我们已经将内存分布开来因此需要开始关注内存排序点。对于给定的内存地址需要确定内存操作的发生顺序。就像在基于总线的协议中会有一个仲裁器来决定谁赢得事务或总线访问权一样在基于目录的系统中通常给定地址的目录是最终的仲裁者。如果两个消息从两个不同的核心同时到达都希望获得对特定地址的写访问权那么先到达目录的那个通常会获胜。有时这可能不公平因此一些系统会尝试采用某种机制防止离目录近的核心总是赢得对争用缓存行的访问。可能会引入某种退避协议。但正是目录保证了原子性它确保在任一时刻特定缓存行只能从一种状态转换到另一种状态。目录就是排序点。可以说先到达主目录的消息获胜。对该行的后续请求将失败。那么失败的请求会怎样目录很可能会发送一个否定确认或一个“重试”消息。它会说“我现在无法处理这个请求该行当前正在转换中其他人已经赢得了转换权请稍后重试该内存事务。”现在回到缓存控制器这边情况变得相当复杂因为它可能会收到一个重试或否定确认。同时它可能还会收到针对同一缓存行的其他消息。在这种情况下它需要优先处理来自目录的消息而不是主处理器的流水线请求因为目录是该内存位置的最终排序点。前向进度保证与活锁避免 ️最后必须考虑前向进度保证。这意味着很容易构建一个这样的内存系统数据被拉入缓存但在能够对该地址实际执行加载或存储操作之前它就被逐出了缓存。突然之间缓存行可能在两个缓存之间来回“弹跳”形成活锁场景。在构建这些基于目录的一致性系统时基于总线的协议中也可能发生但通常可能性较小必须要有某种前向进度保证。可能性较小的原因是在基于目录的系统中通信时间通常更长因此“脆弱窗口期”也更长。前向进度保证意味着一旦数据进入你的缓存你至少需要对其执行一次内存操作以保证在将内存交还给目录控制器之前已经完成了一次操作。例如如果你执行加载操作实际上是将数据以共享状态带入缓存执行一次实际的加载然后才允许放弃它。因此在完成一次内存事务之前你不会回复目录控制器发来的无效化请求。同样如果你以修改状态带入数据在交还数据给内存控制器之前需要先执行一次存储操作。这对于确保系统有前向进度、避免活锁至关重要。目录结构的演进与可扩展性 好的接下来我们将探讨更具前瞻性的内容。我们一直在讨论所谓的全映射目录即为每个处理器核心设置一个位。如果系统中有1000个核心那将是一个非常庞大的位图。而1000个核心同时读取所有数据或某一特定缓存行的情况并不常见。因此这可能造成浪费并且全映射目录的大小以O(N)增长这并不理想。因此人们研究了不同的协议这里只是简要提及。这很大程度上是该领域的研究和未来方向。以下是几种主要的目录结构优化方案有限指针目录其思想是使用基于有限指针的目录。不是使用共享者列表的位掩码而是使用基于2进制编码的数字最多到某个上限。这就是为什么它被称为有限目录或有限指针目录因为无法将系统中的所有节点都列在这个列表中条目数不够。但你可以命名它们因为你有实际数字的二进制编码。如果共享者数量超过了整个列表的容量例如你有5个条目突然出现了第6个共享者需要移除一个通常会有一个溢出位表示共享者数量超过N。当数量超过N且处于共享状态突然需要转换为修改状态时系统将直接向系统中的所有其他缓存发送广播消息或无效化消息。通常这是一个很好的权衡因为极广泛共享的缓存行并不常见这是在存储空间与发送更多消息之间的有趣权衡。无限制目录这里有一个有趣的协议叫做“无限制”目录。思路类似是一个带溢出位的有限目录。但如果发生溢出你开始在软件中、在主内存的一个结构体中维护共享者列表。这要求系统具有非常快速的中断/陷阱机制以便当这种情况发生时因为你正在处理缓存行中断主处理器由主处理器提供共享者列表的其余部分例如当共享者列表溢出时。在这两者之间还有很多研究并且这个领域目前仍有活跃的未来研究。除了简单的目录一致性我们还有一些非常酷的片上一致性协议。这也是当前被大量研究的原因因为人们过去构建了大规模并行的基于目录的机器它们在某些应用中表现很好。但现在我们开始将越来越多的核心集成到单个芯片上因此开始看到片上一致性并研究如何利用快速的片上通信与目录结合来构建更有趣的一致性协议。还有所谓的COMA系统全缓存内存架构其中数据从不驻留在主内存中目录四处移动。这有点超出本课程范围如果想了解可以阅读关于KSR1的资料。此外如何扩展共享者列表也是一个活跃的研究方向。现代系统实例与总结 ️最后简要谈谈这些技术的最新版本。我们有SGI UV 1000它是SGI Origin和Origin 2000机器的后代。它拥有大量核心2560个全部保持缓存一致性。它使用基于目录的一致性协议是非均匀内存访问架构。所有核心通过一个多机箱的2D Torus网络连接在一起。普林斯顿大学的H PCCRC中心就有一台这样的机器。一个片上示例是Tilera Tile 64 Pro它有64个核心每个核心本身就是一个目录主节点并运行基于目录的协议。我之前谈到将通信流量划分为不同的流。在这个芯片上有三个不同的内存网络。因此我们必须设计出三个自身不会死锁的流量类别。还有四个内存控制器直接连接到互连系统。由于这种设计通信延迟各不相同。这里的核心与内存控制器通信非常快而那里的核心则需要更长时间。但这个核心可能离那个内存控制器很近所以存在非均匀性。好的这是本学期的最后一张幻灯片。如果你想在EE 475课程之外继续深入学习可以开始阅读计算机体系结构不同会议的论文。国际计算机体系结构研讨会ISCA的会议录是一个很好的起点它可能是该领域顶级的体系结构会议。国际微体系结构研讨会MICRO是顶级的微体系结构会议。编程语言和操作系统的体系结构支持研讨会ASPLOS涵盖了软件和硬件之间的大量交叉是一个非常棒的会议。高性能计算体系结构会议HPCA过去主要关注高性能大型计算机系统但现在很多普通的计算机体系结构研究也会出现在该会议上。你还应该做什么呢去做研究设计一些芯片在FPGA上测试这些想法学习更多关于并行计算机体系结构的知识。当然你可以在秋季回来选修EE 580 A这是一门研究生级别的主要文献阅读课程更传统的研究生课程你将学习所有不同的并行计算系统我们称之为并行计算因为它既包括并行计算机体系结构也包括一些与体系结构紧密结合的编程模型和并行编程。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/17f98dd68678f5002bed3f79bae63024_1.pnghttps://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/17f98dd68678f5002bed3f79bae63024_3.png本节课中我们一起学习了目录一致性协议的可扩展性挑战与解决方案包括通过多逻辑通道避免死锁、目录作为内存排序点的作用、确保前向进度以避免活锁以及从全映射目录到有限指针目录等可扩展目录结构的演进。我们还了解了SGI UV 1000和Tilera Tile 64 Pro等现代系统的实现并展望了进一步学习并行计算体系结构的途径。
