一致性失效的分类:真共享与伪共享
接下来,我们将一致性失效进一步分为两个子类:真共享失效和伪共享失效。
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同处一行,导致该行状态变化。
- 分析:同样是伪共享失效。P2 并未触及
https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/35c5eda0ba3a1779c69bfb6adf7a1f6b_5.png
P2 写入 X2
- 分析:伪共享失效。原理同上,
X1和X2的耦合导致了不必要的通信。
- 分析:伪共享失效。原理同上,
P1 读取 X2
- 分析:这是真共享失效。P2 写入了
X2,P1 随后读取它,发生了真实的数据通信。
- 分析:这是真共享失效。P2 写入了
这个例子表明,伪共享会引入大量不必要的缓存失效和一致性通信,损害系统性能。
多核扩展性问题
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.png
https://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.png
https://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.png
https://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.png
https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-comp-arch/img/17f98dd68678f5002bed3f79bae63024_3.png
本节课中我们一起学习了目录一致性协议的可扩展性挑战与解决方案,包括通过多逻辑通道避免死锁、目录作为内存排序点的作用、确保前向进度以避免活锁,以及从全映射目录到有限指针目录等可扩展目录结构的演进。我们还了解了SGI UV 1000和Tilera Tile 64 Pro等现代系统的实现,并展望了进一步学习并行计算体系结构的途径。