第八章 目录一致性协议 A Primer on Memory Consistency and Cache Coherence - 2nd Edition

第八章 目录一致性协议
 

      在本章中，我们将介绍目录一致性协议。目录协议最初是为解决窥探协议可扩展性不足的问题而开发的。传统窥探系统在全序互连网络上广播所有请求，且所有一致性控制器都会监听这些请求。相比之下，目录协议通过间接层避免了有序广播网络，也避免了每个缓存控制器处理所有请求的情况。

        我们首先从高层介绍目录协议（8.1 节），然后展示一个完整但简单的三状态（MSI）目录协议系统（8.2 节）。该系统和协议作为基线，后续我们将在此基础上添加系统特性和协议优化。接着解释如何在基线 MSI 协议中添加独占状态（8.3 节）和拥有状态（8.4 节），随后讨论如何表示目录状态（8.5 节）以及如何设计和实现目录本身（8.6 节）。然后描述提升性能和降低实现成本的技术（8.7 节），再讨论采用目录协议的商用系统（8.8 节），最后以目录协议及其未来的讨论结束本章（8.9 节）。

        仅希望学习目录一致性协议基础知识的读者可以略读或跳过 8.3 节至 8.7 节，尽管这些章节的部分内容有助于读者更好地理解 8.8 节的案例研究。

8.1 目录协议简介

        目录协议的核心创新在于建立一个目录，用于维护每个块的一致性状态的全局视图。目录跟踪哪些缓存持有每个块以及块的状态。想要发出一致性请求（如 GetS）的缓存控制器会将请求直接发送到目录（即单播消息），目录查询块的状态以确定后续操作。例如，目录状态可能表明请求的块由核心 C2 的缓存拥有，因此请求应转发给 C2（如使用新的 Fwd-GetS 请求）以获取块的副本。当 C2 的缓存控制器收到转发请求时，会向请求缓存控制器单播响应。

        对比目录协议和窥探协议的基本操作具有启发性。在目录协议中，目录维护每个块的状态，缓存控制器将所有请求发送到目录。目录要么响应请求，要么将请求转发给一个或多个其他一致性控制器，由后者响应。一致性事务通常涉及两步（单播请求 + 单播响应）或三步（单播请求 + K≥1 个转发请求 + K 个响应，K 为共享者数量）。有些协议甚至有第四步，原因可能是响应通过目录间接传递，或请求者在事务完成时通知目录。相反，窥探协议将块的状态分布在所有可能的一致性控制器中。由于没有这种分布式状态的中央汇总，一致性请求必须广播到所有一致性控制器。因此，窥探一致性事务始终涉及两步（广播请求 + 单播响应）。

        与窥探协议类似，目录协议需要定义一致性事务相对于其他事务的排序时机和方式。在大多数目录协议中，一致性事务在目录处排序。多个一致性控制器可能同时向目录发送一致性请求，事务顺序由请求在目录处的序列化顺序决定。如果两个请求同时到达目录，互连网络实际上会选择目录先处理哪个请求。第二个到达的请求的处理方式取决于目录协议和竞争请求的类型：可能（a）在第一个请求后立即处理，（b）在目录中等待第一个请求完成，或（c）被否定确认（NACK）。在后一种情况下，目录向请求者发送否定确认消息（NACK），请求者必须重新发出请求。本章不考虑使用 NACK 的协议，但会在 9.3.2 节讨论 NACK 的可能用途及其如何导致活锁问题。

        将目录作为排序点是目录协议与窥探协议的另一个关键区别。传统窥探协议通过在有序广播网络上序列化所有事务来创建全序。窥探的全序不仅确保每个块的请求按块顺序处理，还便于实现内存一致性模型。回想一下，传统窥探协议使用全序广播来序列化所有请求；因此，当请求者观察到自己的一致性请求时，这表示其一致性周期可以开始。具体来说，当窥探控制器看到自己的 GetM 请求时，可以推断其他缓存将使它们的 S 块失效。我们在表 7.4 中证明，这种序列化通知足以支持强 SC 和 TSO 内存一致性模型。

        相比之下，目录协议在目录处对事务排序，以确保冲突请求被所有节点按块顺序处理。然而，缺乏全序意味着目录协议中的请求者需要另一种策略来确定其请求何时被序列化，从而确定其一致性周期何时可以安全开始。由于（大多数）目录协议不使用全序广播，因此没有全局序列化概念。相反，请求必须相对于所有可能拥有块副本的缓存单独序列化。需要显式消息通知请求者其请求已被每个相关缓存序列化。特别是对于 GetM 请求，每个拥有共享（S）副本的缓存控制器在序列化无效消息后必须发送显式确认（Ack）消息。

        目录协议与窥探协议的对比凸显了它们之间的根本权衡。目录协议以间接层为代价（即某些事务需要三步而非两步）实现了更高的可扩展性（即所需带宽更少）。这种额外的间接层增加了某些一致性事务的延迟。

8.2 基线目录系统

        本节将介绍一个具有直接且适度优化的目录协议的基线系统。该系统在揭示后续章节中特性和优化的动机的同时，提供了对目录协议关键特性的洞察。

8.2.1 目录系统模型

        我们在图 8.1 中说明了目录系统模型。与窥探协议不同，互连网络的拓扑结构故意模糊，可能是网格、环面或架构师希望使用的任何其他拓扑。本章假设互连网络的一个限制是它强制点到点排序，即如果控制器 A 向控制器 B 发送两条消息，消息将按发送顺序到达控制器 B。点到点排序降低了协议的复杂性，我们将无排序网络的讨论推迟到 8.7.3 节。

        该目录系统模型与图 2.1 中的基线系统模型的唯一区别是添加了目录，并将内存控制器重命名为目录控制器。目录的大小和组织方式有很多种，目前我们假设最简单的模型：内存中的每个块对应一个目录项。8.6 节将研究和比较更实际的目录组织选项。我们还假设一个具有单个目录控制器的整体式 LLC；8.7.1 节将解释如何将此功能分布到 LLC 的多个存储体和多个目录控制器。

8.2.2 高层协议规范

        基线目录协议仅有三种稳定状态：MSI。除非块在缓存中处于 M 状态，否则块由目录控制器拥有。每个块的目录状态包括稳定的一致性状态、所有者标识（如果块处于 M 状态）以及以独热位向量编码的共享者标识（如果块处于 S 状态）。图 8.2 展示了一个目录项。8.5 节将讨论目录项的其他编码方式。

 

        在呈现详细规范之前，我们首先说明协议的高层抽象，以理解其基本行为。图 8.3 显示了缓存控制器发出一致性请求以将权限从 I 更改为 S、从 I 或 S 更改为 M、从 M 更改为 I 以及从 S 更改为 I 的事务。与上一章的窥探协议一样，我们使用以缓存为中心的表示法指定块的目录状态（例如，目录状态 M 表示存在一个缓存使块处于 M 状态）。请注意，缓存控制器不能静默逐出共享块，即需要显式的 PutS 请求。我们将共享块静默逐出协议的讨论以及静默与显式 PutS 请求的比较推迟到 8.7.4 节。

        大多数事务相当直接，但有两个事务需要在此进一步讨论。第一个是当缓存尝试将权限从 I 或 S 升级到 M 且目录状态为 S 时发生的事务。缓存控制器向目录发送 GetM，目录执行两个操作：首先，向请求者响应包含数据和 “AckCount” 的消息，AckCount 是块的当前共享者数量，用于通知请求者需要多少共享者确认因 GetM 而使块失效；其次，目录向所有当前共享者发送无效（Inv）消息。每个共享者收到无效消息后，向请求者发送无效确认（Inv-Ack）。一旦请求者收到目录的消息和所有 Inv-Ack 消息，事务完成。请求者收到所有 Inv-Ack 后，知道不再有块的读取者，因此可以安全地写入块而不违反一致性。

        需要进一步讨论的第二个事务是当缓存尝试逐出 M 状态的块时。在此协议中，缓存控制器发送包含数据的 PutM 消息到目录，目录响应 Put-Ack。如果 PutM 不携带数据，协议将需要第三条消息 —— 缓存控制器向目录发送包含已逐出 M 状态块的数据消息 —— 作为 PutM 事务的一部分。此目录协议中的 PutM 事务与窥探协议不同，后者的 PutM 不携带数据。

8.2.3 避免死锁

        在该协议中，接收消息可能导致一致性控制器发送另一条消息。通常，如果事件 A（如接收消息）会引发事件 B（如发送消息），且这两个事件都需要资源分配（如网络链路和缓冲区），则必须注意避免因循环资源依赖而引发的死锁。例如，GetS 请求可能导致目录控制器发出 Fwd-GetS 消息；如果这些消息使用相同资源（如网络链路和缓冲区），系统可能陷入死锁。图 8.4 展示了一种死锁场景：两个一致性控制器 C1 和 C2 在响应彼此的请求，但输入队列已被其他一致性请求填满。若队列为先进先出（FIFO），响应将无法越过请求。由于队列已满，每个控制器发送响应时会阻塞；由于 FIFO 特性，控制器无法切换处理后续请求（或处理响应），最终导致系统死锁。

 

        一致性协议中避免死锁的经典方案是为每类消息使用独立网络。网络可以是物理隔离或逻辑隔离（称为虚拟网络），核心在于避免消息类别间的依赖。图 8.5 展示了一个请求和响应消息在独立物理网络中传输的系统：由于响应不会被其他请求阻塞，最终会被目标节点接收，从而打破循环依赖。

        本节的目录协议使用三个网络避免死锁。由于请求可能引发转发请求，转发请求可能引发响应，因此三类消息需各自使用独立网络：

请求消息：GetS、GetM、PutM
转发请求消息：Fwd-GetS、Fwd-GetM、Inv（无效）、PutAck
响应消息：Data、Inv-Ack

        本章协议要求转发请求网络提供点到点排序，其他网络无排序约束，不同网络间的消息也无排序要求。关于死锁避免的深入讨论（包括虚拟网络详解和避免死锁的具体要求）将推迟到 9.3 节。

8.2.4 协议详细规范

        表 8.1 和表 8.2 给出了包含所有临时状态的协议详细规范。与 8.2.2 节的高层描述相比，最大差异在于临时状态。一致性控制器必须管理处于一致性事务中的块状态，例如缓存控制器在向目录发送请求后、接收所有必要响应（包括 Data 和可能的 Inv-Ack）前，可能收到其他控制器转发的请求。缓存控制器可通过缺失状态处理寄存器（MSHR）维护这些状态，核心用 MSHR 跟踪未完成的一致性请求。符号上，临时状态表示为 XYAD，其中上标 A 表示等待确认，D 表示等待数据（此表示法与窥探协议不同，后者上标 A 表示等待总线请求）。

 

        由于表格初看较为复杂，下一节将通过示例场景展开说明。

8.2.5 协议操作

        协议支持缓存获取 S 和 M 状态的块，并将块以这两种状态替换到目录。
I 到 S（常见情况 #1）
缓存控制器向目录发送 GetS 请求，块状态从 I 变为 ISD（临时状态，等待数据）。若目录为所有者（即当前无缓存持有 M 状态块），目录响应 Data 消息，将块状态改为 S（若尚未是 S），并将请求者添加到共享者列表。当 Data 到达请求者，缓存控制器将块状态改为 S，事务完成。
I 到 S（常见情况 #2）
缓存控制器发送 GetS 请求，块状态变为 ISD。若目录非所有者（存在缓存持有 M 状态块），目录将请求转发给所有者，块状态变为临时 SD。所有者响应 Fwd-GetS 请求，向请求者发送 Data 并将块状态改为 S；原所有者还需向目录发送 Data（因需将所有权移交目录，目录需维护块的最新副本）。当 Data 到达请求者，块状态改为 S，事务完成；当 Data 到达目录，目录将其写入内存，块状态改为 S，事务完成。
I 到 S（竞争情况）
上述两种 I 到 S 场景为单事务处理块的常见情况，协议的复杂性主要源于处理多并发事务的罕见情况。例如，缓存控制器可能在 ISD 状态下收到块的 Invalidation 消息：核心 C1 发送 GetS 进入 ISD，核心 C2 对同一块发送 GetM 且晚于 C1 的请求到达目录。目录先响应 C1 的 GetS 发送 Data，再响应 C2 的 GetM 发送 Invalidation。由于 Data 和 Invalidation 在不同网络传输，可能无序到达，导致 C1 在收到 Data 前先收到 Invalidation。
I 或 S 到 M
缓存控制器向目录发送 GetM 请求，块状态从 I 变为 IMAD（等待数据和确认）。Data 消息包含 AckCount（需等待的确认数，可能为 0）。图 8.3 展示了目录响应 GetM 的三种常见场景：

若目录处于 I 状态，直接发送 AckCount=0 的 Data 并转为 M 状态；
若处于 M 状态，目录将请求转发给所有者并更新所有者，原所有者响应 Fwd-GetM，发送 AckCount=0 的 Data；
若处于 S 状态，目录响应 Data（AckCount = 共享者数量），并向所有共享者发送 Invalidation。收到 Invalidation 的缓存控制器使共享副本失效，向请求者发送 Inv-Ack。请求者收到最后一个 Inv-Ack 后转为 M 状态（表 8.1 中的 Last-Inv-Ack 事件简化了协议描述）。

        并发场景示例：核心 C1 的块处于 IMA 状态（等待确认），收到 C2 的 Fwd-GetS 请求。此时目录已向 C1 发送 Data、向共享者发送 Invalidation 并转为 M 状态。C2 的 GetS 到达目录后被转发给所有者 C1，该 Fwd-GetS 可能在 C1 收到所有 Inv-Ack 前到达，此时协议会阻塞，缓存控制器等待 Inv-Ack（因 Inv-Ack 在独立网络传输，不会被未处理的 Fwd-GetS 阻塞）。
M 到 I
逐出 M 状态块时，缓存控制器发送包含数据的 PutM 请求，块状态变为 MIA（等待确认）。目录接收 PutM 后更新 LLC / 内存，响应 Put-Ack 并转为 I 状态。请求者收到 Put-Ack 前，块状态仍为 M，需响应针对该块的转发请求。若在发送 PutM 到接收 Put-Ack 期间收到转发请求（Fwd-GetS 或 Fwd-GetM），缓存控制器响应请求并将块状态分别转为 SIA 或 IIA（临时状态，实际等效于 S 和 I，但需等待 Put-Ack 完成向 I 的转换）。
S 到 I
与前章窥探协议不同，目录协议不静默逐出 S 状态块。替换 S 状态块时，缓存控制器发送 PutS 请求，块状态变为 SIA（等待确认）。目录接收 PutS 后响应 Put-Ack。请求者收到 Put-Ack 前，块状态仍为 S。若在发送 PutS 到接收 Put-Ack 期间收到 Invalidation 请求，块状态转为 IIA（等效于 I，需等待 Put-Ack 完成 S 到 I 的转换）。

8.2.6 协议简化设计

        该协议以牺牲部分性能为代价实现简洁性，主要简化包括：

        状态阻塞机制：除仅含三种稳定状态外，协议在特定场景下会阻塞（如临时状态下收到转发请求时）。8.7.2 节将讨论高性能方案（处理消息并增加临时状态）。
        数据传输优化缺失：目录响应 S 到 M 的状态转换时发送 Data 和 AckCount，但缓存已持有有效数据，实际只需发送无数据的 AckCount。该优化将在 8.4 节介绍 MOSI 协议时引入。

8.3 添加独占状态

        如前所述，在窥探协议中添加独占（E）状态是重要优化，它允许核心通过单次一致性事务完成对块的先读再写，而非 MSI 协议所需的两次事务。从高层来看，该优化与缓存一致性采用窥探还是目录机制无关：若核心发出 GetS 请求且块当前未被其他核心共享，请求者可获取 E 状态的块，随后无需额外一致性请求即可静默将状态从 E 升级为 M。

        本节将 E 状态添加到基线 MSI 目录协议中。与前章 MESI 窥探协议类似，协议的操作取决于 E 状态是否被视为所有权状态。核心差异在于：当目录将 E 状态块分配给缓存后，需确定由哪个一致性控制器响应针对该块的请求 —— 因为自目录分配 E 状态块后，该块可能已被静默升级为 M 状态。

        在 E 状态块属于所有权状态的协议中，解决方案简单：持有 E（或 M）状态块的缓存为所有者，必须响应请求。发送至目录的一致性请求将转发至持有 E 状态块的缓存。由于 E 是所有权状态，E 块的逐出不能静默进行，缓存必须向目录发送 PutE 请求 —— 若无显式 PutE，目录无法知晓自身已成为所有者并响应后续请求。本节的 MESI 协议即采用这一简单方案（假设 E 块为所有权状态）。

        在 E 状态块非所有权状态的协议中，E 块可静默逐出，但协议复杂度增加。例如，核心 C1 获取 E 状态块后，目录收到核心 C2 的 GetS 或 GetM 请求。此时目录需判断 C1 状态：①仍为 E；②已通过静默升级为 M（若 C1 执行存储操作）；③已通过静默 PutE 转为 I。若 C1 为 M，目录需将请求转发给 C1 以获取最新数据；若为 E，C1 或目录均可响应（因数据相同）；若为 I，目录必须响应。一种解决方案是让 C1 和目录共同响应（如 8.8.1 节 SGI Origin 案例所述），另一种是目录将请求转发给 C1—— 若 C1 为 I，则通知目录响应 C2；否则 C1 响应 C2 并通知目录无需介入。

8.3.1 协议高层规范

        图 8.6 展示了协议事务的高层视图，与 MSI 协议的差异如下：

新增 I 到 E 的转换：当目录收到 I 状态块的 GetS 请求时可能触发；
新增 PutE 事务：用于逐出 E 状态块。由于 E 是所有权状态，E 块不能静默逐出。与 M 状态块不同，E 块为干净状态，PutE 无需携带数据（目录已持有最新副本）。

8.3.2 协议详细规范

        表 8.3 和表 8.4 给出了 MESI 协议的详细规范（含临时状态），与 MSI 协议的差异以粗体标注。协议新增稳定 E 状态及处理初始 E 状态块事务的临时状态，复杂度主要体现在目录控制器 —— 除更多状态外，目录需区分更多事件（如收到 PutS 时，需判断是否为 “最后” 一个 PutS：若当前唯一共享者发送 PutS，则目录状态转为 I）。

8.4 添加拥有状态

        与第 7 章在基线 MSI 窥探协议中添加拥有（O）状态的动机相同，架构师可能希望在 8.2 节的基线 MSI 目录协议中引入 O 状态。回顾第 2 章：若缓存持有 O 状态块，则该块有效、只读、脏（需最终更新内存）且为所有权状态（缓存必须响应针对该块的一致性请求）。相比 MSI，添加 O 状态从三方面改变协议：

持有 M 状态块的缓存收到 Fwd-GetS 时转为 O 状态，无需立即将数据写回 LLC / 内存；
更多一致性请求由 O 状态缓存响应（而非 LLC / 内存）；
新增更多三跳事务（MSI 协议中此类事务由 LLC / 内存响应）。

8.4.1 协议高层规范

        图 8.7 展示了协议事务的高层视图，关键差异在于：当请求者对 I 或 S 状态块发送 GetM，且所有者缓存中块为 O 状态、其他缓存中块为 S 状态时，目录将 GetM 转发给所有者并附加 AckCount，同时向所有共享者发送 Invalidation。所有者响应请求者时发送 Data 和 AckCount，请求者据此判断是否收到最后一个 Inv-Ack。若 GetM 请求者本身为 O 状态所有者，目录直接向其发送 AckCount（无需转发）。

 

协议新增 PutO 事务，与 PutM 几乎相同 —— 因 M 和 O 均为脏状态，故需携带数据。

8.4.2 协议详细规范

        表 8.5 和表 8.6 给出了 MOSI 协议的详细规范（含临时状态），与 MSI 协议的差异以粗体标注。协议新增稳定 O 状态及临时状态 OMAC、OMA、OIA，用于处理初始 O 状态块的事务。OMAC 表示缓存等待来自其他缓存的 Inv-Ack（A）和目录的 AckCount（C），但无需数据（因 O 状态块已含有效数据）。

        典型场景：核心 C1 的缓存块处于 OMAC 或 SMAD 状态时，收到核心 C2 的 Fwd-GetM 或 Invalidation。此时 C2 的 GetM 在目录处的排序先于 C1 的 GetM，故目录状态已转为 M（由 C2 所有）。C1 收到 C2 的转发请求后，需将状态从 OMAC 或 SMAD 转为 IMAD——C2 的请求使 C1 的块失效，C1 需重新等待 Data 和 Inv-Ack。

8.5 目录状态表示

        前节假设目录为完整目录：为每个块维护完整状态，包括所有可能持有共享副本的缓存列表。但这与目录协议的核心目标（可扩展性）矛盾：在缓存数量庞大的系统中，即使采用紧凑位向量表示，维护每个块的完整共享者列表仍需大量存储。对于缓存数量适中的系统，完整列表可能可行；但大规模系统的架构师需要更具可扩展性的目录状态维护方案。

减少目录状态存储的方法包括：

粗粒度目录；
有限指针目录。
两者可独立或结合使用，以下对比基线设计（图 8.8 顶部）展开说明。

8.5.1 粗粒度目录

        完整共享者列表允许目录精确向 S 状态块的持有者发送 Invalidation。粗粒度目录通过维护超集列表（实际共享者的父集）减少状态存储：每个共享者列表项对应 K 个缓存（图 8.8 中部）。若该组中至少一个缓存持有 S 状态块，则列表位设为 1。当 GetM 请求到达时，目录向该组所有 K 个缓存发送 Invalidation。这种方案以额外网络带宽（发送不必要的 Invalidation）和缓存控制器处理开销为代价，减少目录状态存储。

 

 

8.5.2 有限指针目录

        在含 C 个缓存的芯片中，完整共享者列表需 C 位（每位对应一个缓存）。但研究表明，多数块的共享者数为 0 或 1。有限指针目录利用这一特性：使用 i（i<C）个指针项，每项需 log₂C 位，总计 i×log₂C 位（图 8.8 底部）。当系统尝试添加第 i+1 个共享者时，需额外机制处理，常见方案包括：

广播（DiriB）：若已有 i 个共享者且新 GetS 到达，目录将块状态设为 “过多共享者”，后续 GetM 需向所有缓存广播 Invalidation。缺点是即使实际共享者数 K（i<K<C），仍需广播至所有 C 个缓存，导致 C-K 次无效操作。极端情况 Dir0B（无指针）要求所有一致性操作广播，如 AMD 的 Coherent HyperTransport 实现无目录状态的 Dir0B，放弃优化但省去存储开销，所有请求广播至全缓存。

        非广播（DiriNB）：若已有 i 个共享者且新 GetS 到达，目录要求当前某一共享者失效，为新请求者腾出空间。该方案对广泛共享的块（共享者数 > i）可能导致显著性能损耗，尤其对含一致性指令缓存的系统（代码常被广泛共享）。
软件处理（DiriSW）：若已有 i 个共享者且新 GetS 到达，系统陷入软件处理程序，可在软件管理的数据结构中维护完整列表。但陷入软件的性能开销和实现复杂度导致该方案商业应用有限。

8.6 目录组织方式

        从逻辑上讲，目录为内存中的每个块都包含一个条目。在许多传统的基于目录的系统中，目录控制器与内存控制器集成，通过扩展内存来存储目录，直接实现了这种逻辑抽象。例如，SGI Origin 通过添加额外的 DRAM 芯片，为每个内存块存储完整的目录状态 [10]。

        然而，在当今的多核处理器和大型 LLC（最后一级缓存）中，传统的目录设计意义不大。首先，架构师不希望目录访问带来的延迟和功耗开销影响片外内存，尤其是对于片上缓存的数据。其次，系统设计人员对大型片外目录状态持保留态度，因为几乎所有内存块在任何给定时间都不会被缓存。这些缺点促使架构师通过仅在片上缓存一部分目录条目来优化常见情况。在本节的其余部分，我们将讨论目录缓存设计，其中一些之前由 Marty 和 Hill 分类 [13]。

        与传统的指令和数据缓存类似，目录缓存 [7] 提供对完整目录状态子集的更快访问。由于目录总结了一致性缓存的状态，它们表现出与指令和数据访问类似的局部性，但只需存储每个块的一致性状态，而不是其数据。因此，相对较小的目录缓存可以实现高命中率。目录缓存对一致性协议的功能没有影响，它只是减少了平均目录访问延迟。在多核处理器时代，目录缓存变得更加重要。在较旧的系统中，核心位于单独的芯片和 / 或板上，消息延迟足够长，往往可以分摊目录访问延迟。在多核处理器中，消息可以在几个周期内从一个核心传输到另一个核心，而片外目录访问的延迟往往使通信延迟相形见绌，并成为瓶颈。因此，对于多核处理器，强烈需要实现片上目录缓存，以避免昂贵的片外访问。

        片上目录缓存包含完整目录条目的子集。因此，关键的设计问题是处理目录缓存未命中，即当一致性请求到达时，所请求块的目录条目不在目录缓存中。

        我们在表 8.7 中总结了设计选项，并在下面进行描述。

8.6.1 由 DRAM 支持的目录缓存

        最直接的设计是像传统的多芯片多处理器一样，将完整的目录保存在 DRAM 中，并使用单独的目录缓存结构来减少平均访问延迟。在这种目录缓存中未命中的一致性请求会导致对该 DRAM 目录的访问。这种设计虽然简单，但存在几个重要缺点。首先，它需要大量的 DRAM 来存储目录，包括当前不在片上缓存的绝大多数块的状态。其次，由于目录缓存与 LLC 分离，可能会出现 LLC 命中但目录缓存未命中的情况，因此即使数据在本地可用，也会导致 DRAM 访问。最后，目录缓存替换必须将目录条目写回 DRAM，导致高延迟和功耗开销。

8.6.2 包含性目录缓存

        我们可以通过利用以下观察来设计更具成本效益的目录缓存：我们只需要缓存片上正在缓存的块的目录状态。如果目录缓存包含片上缓存的所有块的超集的目录条目，我们将其称为包含性目录缓存。包含性目录缓存作为 “完美” 的目录缓存，对于片上缓存的块的访问永远不会未命中。不需要在 DRAM 中存储完整的目录。包含性目录缓存中的未命中表示该块处于 I 状态；未命中不是访问某个后备目录存储的前兆。

        我们现在讨论两种包含性目录缓存设计，以及适用于这两种设计的优化。

嵌入在包含性 LLC 中的包含性目录缓存

        最简单的目录缓存设计依赖于与上层缓存保持包含性的 LLC。缓存包含性意味着如果一个块在上层缓存中，那么它也必须存在于下层缓存中。对于图 8.1 的系统模型，LLC 包含性意味着如果一个块在核心的 L1 缓存中，那么它也必须在 LLC 中。

        LLC 包含性的一个结果是，如果一个块不在 LLC 中，它也不在 L1 缓存中，因此对于片上的所有缓存，它必须处于 I 状态。包含性目录缓存利用这一特性，将每个块的一致性状态嵌入到 LLC 中。如果一致性请求被发送到 LLC / 目录控制器，并且请求的地址不在 LLC 中，那么目录控制器知道请求的块不在片上缓存中，因此在所有 L1 中都处于 I 状态。

        由于目录反映了 LLC 的内容，整个目录缓存可以简单地通过向 LLC 中的每个块添加额外的位来嵌入到 LLC 中。这些添加的位可能会导致不小的开销，具体取决于核心数量和目录状态的表示格式。我们在图 8.9 中说明了将此目录状态添加到 LLC 缓存块的情况，并将其与没有 LLC 嵌入目录缓存的系统中的 LLC 块进行了比较。

        不幸的是，LLC 包含性有几个重要缺点。首先，虽然 LLC 包含性可以为私有缓存层次结构自动维护（如果下层缓存具有足够的关联性 [4]），但对于我们系统模型中的共享缓存，通常需要在替换 LLC 中的块时发送特殊的 “Recall” 请求，以使 L1 缓存中的块失效（本节后面讨论）。更重要的是，LLC 包含性需要维护上层缓存中缓存块的冗余副本。在多核处理器中，上层缓存的总容量可能占 LLC 容量的很大一部分（有时甚至比 LLC 容量还大）。

独立的包含性目录缓存
        我们现在介绍一种不依赖于 LLC 包含性的包含性目录缓存设计。在这种设计中，目录缓存是一个独立的结构，在逻辑上与目录控制器相关联，而不是嵌入在 LLC 本身中。为了使目录缓存具有包含性，它必须包含所有 L1 缓存中块的并集的目录条目，因为 LLC 中但不在任何 L1 缓存中的块必须处于 I 状态。因此，在这种设计中，目录缓存由所有 L1 缓存中的标签的副本组成。与之前的设计相比，这种设计更加灵活，因为它不需要 LLC 包含性，但它有额外的标签存储成本。

        这种包含性目录缓存有一些显著的实现成本。最值得注意的是，它需要高度关联的目录缓存。（如果我们将目录缓存嵌入到包含性 LLC 中，那么 LLC 也必须是高度关联的。）考虑一个具有 C 个核心的芯片，每个核心都有一个 K 路组关联的 L1 缓存。目录缓存必须是 C*K 路关联的，以容纳所有 L1 缓存标签，不幸的是，关联性随着核心数量的增加而线性增长。我们在图 8.10 中为 K=2 的情况说明了这个问题。

        包含性目录缓存设计还引入了一些复杂性，以保持目录缓存的最新状态。当一个块从 L1 缓存中逐出时，缓存控制器必须通过发出显式的 PutS 请求来通知目录缓存哪个块被替换了（例如，我们不能使用具有静默逐出的协议，如 8.7.4 节所讨论的）。一个常见的优化是将显式的 PutS 附加到 GetS 或 GetX 请求上。由于索引位必须相同，PutS 可以通过指定替换的方式来编码。这有时被称为 “替换提示”，尽管一般来说这是必需的（而不是真正的 “提示”）。
限制包含性目录缓存的关联性

        为了克服之前实现中高关联性目录缓存的成本，我们提出了一种限制其关联性的技术。与其为最坏情况（CK 关联性）设计目录缓存，不如通过不允许最坏情况发生来限制关联性。也就是说，我们将目录缓存设计为 A 路组关联，其中 A<CK，并且不允许映射到给定目录缓存组的有效条目超过 A 个在片上缓存。当缓存控制器发出一致性请求以将块添加到其缓存时，并且目录缓存中的相应组已经充满了有效条目，那么目录控制器首先从所有缓存中逐出该组中的一个块。目录控制器通过向所有持有该块有效状态的缓存发出 “Recall” 请求来执行此逐出，缓存会以确认响应。一旦目录缓存中的一个条目通过此 Recall 被释放，目录控制器就可以处理触发 Recall 的原始一致性请求。

        Recall 的使用克服了目录缓存中高关联性的需求，但如果设计不当，可能会导致性能不佳。如果目录缓存太小，Recall 会很频繁，性能会受到影响。Conway 等人 [6] 提出了一个经验法则，目录缓存应该至少覆盖它所包含的聚合缓存的大小，但也可以更大以减少 Recall 的频率。此外，为了避免不必要的 Recall，该方案在 S 状态块的非静默逐出时效果最佳。使用静默逐出时，不必要的 Recall 会被发送到不再持有被召回块的缓存。

8.6.3 空目录缓存（无后备存储）

        成本最低的目录缓存是根本没有目录缓存。回想一下，目录状态有助于修剪需要转发一致性请求的一致性控制器集合。但与粗粒度目录（8.5.1 节）一样，如果这种修剪不完全，协议仍然可以正确工作，但会发送不必要的消息，协议的效率会低于预期。极端情况下，Dir0B 协议（8.5.2 节）根本不进行修剪，在这种情况下，它实际上不需要任何目录（或目录缓存）。每当一致性请求到达目录控制器时，目录控制器只需将其转发给所有缓存（即广播转发的请求）。这种目录缓存设计，我们称为空目录缓存，可能看起来过于简单，但它在中小型系统中很受欢迎，因为它不会产生存储成本。

        如果没有目录状态，人们可能会质疑目录控制器的目的，但它扮演着两个重要角色。首先，与本章中的所有其他系统一样，目录控制器负责 LLC；更准确地说，它是一个 LLC / 目录控制器。其次，目录控制器在协议中充当排序点；如果多个核心同时请求同一块，请求在目录控制器处排序。目录控制器解决哪个请求先发生。

8.7 性能与可扩展性优化

        本节讨论提升目录协议性能与可扩展性的若干优化技术。

8.7.1 分布式目录

        此前假设目录与单一整体式 LLC 相连，这种设计易在共享的中央资源处形成性能瓶颈。解决集中式瓶颈的通用方案是分布式设计：特定块的目录位置固定，但不同块的目录可位于不同位置。

        在早期多芯片多处理器（含 N 个节点，每个节点包含处理器核心和内存芯片）中，每个节点通常管理 1/N 的内存及对应 1/N 的目录状态。图 8.11 展示了此类系统模型：内存地址通常静态分配给节点，可通过简单运算（如块 B 的目录位置为 B mod N）确定。每个块有唯一 “归属目录”，负责管理其内存和目录状态。多目录设计使一致性事务带宽提升，避免所有流量集中于单一资源。重要的是，分布式目录不影响一致性协议逻辑。

        在现代多核处理器（含大型 LLC 和目录缓存）中，分布式目录设计逻辑与传统多芯片系统一致：可将 LLC 和目录缓存分片（bank），每个块对应 LLC 的一个分片及其关联的目录缓存分片。

 

8.7.2 非阻塞目录协议

        现有协议的性能限制之一是一致性控制器在某些场景下会阻塞。例如，缓存控制器在临时状态（如 IMA）下收到转发请求时会暂停处理。表 8.8 和表 8.9 展示了基线 MSI 协议的非阻塞变体：

        当缓存控制器处于 IMA 状态并收到 Fwd-GetS 时，它处理请求并将状态转换为 IMAS。该状态表示：待 GetM 事务完成（收到最后一个 Inv-Ack）后，缓存控制器将块状态转为 S，并向 GetS 请求者和目录（现为所有者）发送数据。通过不阻塞 Fwd-GetS，缓存控制器可继续处理队列中的后续请求，提升性能。

        非阻塞协议的复杂性在于：处于 IMAS 状态时可能收到 Fwd-GetM，此时缓存控制器处理请求并将状态转为 IMASI（从 I 到 M，等待 Inv-Ack，再到 S，最终到 I）。类似的临时状态也会出现在 SMA 状态块中。总体而言，消除阻塞会增加临时状态数量，因为控制器需跟踪更多处理中的消息。

 

        目录控制器的阻塞未被消除 —— 若要避免所有场景下的阻塞，需添加大量临时状态，不具现实可行性。

8.7.3 无需点到点有序的互连网络

        在 8.2 节讨论基线 MSI 协议时，假设转发请求网络提供点到点有序性（消息按发送顺序到达），该假设简化了协议设计，避免了潜在竞争条件。

若无点到点有序性，可能出现以下竞争：

有序网络（图 8.12）：核心 C1 持有 M 状态块，C2 发送 GetS，C3 发送 GetM。目录先转发 GetS 至 C1，C1 响应 Data 并将状态转为 O；随后目录转发 GetM，C1 响应 Data 并将状态转为 I，符合预期。
无序网络（图 8.13）：C3 的 Fwd-GetM 可能先到达 C1，C1 响应 Data 并将状态转为 I。随后 C2 的 Fwd-GetS 到达，但 C1 已转为 I 状态，无法响应，导致 C2 的请求永久挂起，系统死锁。

        现有目录协议依赖转发请求网络的点到点有序性。若网络不提供该特性，需修改协议以处理竞争（如添加额外握手消息）。例如，目录可在转发下一请求前，等待缓存确认收到上一转发请求。

        点到点有序性虽降低协议复杂度，但限制了互连网络的优化（如自适应路由）。自适应路由允许消息动态选择路径以避开拥塞，但可能导致消息乱序到达（如图 8.14：交换机 A 发送的消息 M1 和 M2 可能因路径不同，导致后发送的 M2 先到达）。

8.7.4 S 状态块的静默与非静默逐出

        基线协议要求缓存逐出 S 状态块时必须显式发送 PutS 通知目录，并等待 Put-Ack。另一种方案是允许静默逐出（尤其当 E 状态不被视为所有权状态时，E 块也可静默逐出）。

        显式 PutS 的开销：即使最终无用，PutS 和 Put-Ack 仍会消耗网络带宽。例如，C1 发送 PutS 后立即请求同一数据，需重新发送 GetS，此前的 PutS 事务仅浪费带宽。

显式 PutS 的优势：

        精确共享者列表：目录可及时从共享者列表中移除不再持有块的缓存，带来三方面收益：
后续 GetM 无需向已逐出块的缓存发送 Invalidation，加速事务；
        在 MESI 协议中，目录可通过精确计数识别 “最后共享者”，从而在响应 GetS 时提供 Exclusive 状态；
支持 Recall 机制的目录缓存（8.6.2 节）可利用 PutS 避免不必要的 Recall 请求。
简化协议：避免潜在竞争。例如，若允许静默逐出，缓存可能在重新获取 S 状态块时，先收到目录的 Invalidation（无法确定该 Invalidation 针对的是前一次还是当前的 S 状态）。最简单的解决方案是保守处理（假设 Invalidation 针对当前状态），但更高效的方案会增加协议复杂度。

8.8 案例研究

        本节讨论几种商用目录一致性协议：首先介绍传统多芯片系统 SGI Origin 2000，然后讨论较新的设计（如 AMD 的 Coherent HyperTransport 及其升级版 HyperTransport Assist），最后介绍 Intel 的 QuickPath Interconnect（QPI）。

8.8.1 SGI Origin 2000

        SGI Origin 2000 [10] 是 20 世纪 90 年代中期设计的商用多芯片多处理器，支持扩展至 1024 个核心。对可扩展性的强调催生了首个商用目录协议之一，其设计源自斯坦福 DASH 多处理器 [11]（两者架构团队重叠）。

        如图 8.15 所示，Origin 系统最多包含 512 个节点，每个节点由两个 MIPS R10000 处理器通过总线连接至专用 ASIC（Hub）构成。与类似设计不同，Origin 的处理器总线不依赖窥探机制，仅用于连接处理器与 Hub。Hub 负责管理缓存一致性协议，并将节点接入互连网络，同时连接分布式内存和目录的本地部分。网络不保证任何有序性（包括点到点有序），因此处理器间消息可能乱序到达。

Origin 目录协议的特点：

动态目录表示：为保证可扩展性，每个目录条目使用动态选择的表示方式（粗粒度位向量或有限指针，见 8.5 节），而非存储完整共享者列表。
无序网络处理：由于网络不保证有序性，协议需处理多种竞争条件（如 8.7.3 节所述），确保一致性。
非所有权 E 状态：E 状态非所有权状态，缓存可静默逐出 E（或 S）状态块。
Upgrade 请求：提供特殊的 Upgrade 请求（从 S 升级到 M 时无需请求数据），但引入新竞争窗口：若另一处理器的 GetM/Upgrade 请求先于 Upgrade 到达目录，则发送者需重新发送 GetM。
E 状态响应机制：当处理器处于 E 状态时，目录响应 GetS 请求的方式：目录向请求者返回数据，并转发请求至 E 状态持有者。持有者根据自身状态（M 或 E）决定发送新数据或确认消息，请求者需等待两者以确定使用哪份数据。
双网络设计：仅使用请求和响应两个网络（而非避免死锁所需的三个）。协议检测潜在死锁时，通过响应网络发送 “回退” 消息，指示请求者在请求网络上重新发送请求。

8.8.2 Coherent HyperTransport

        目录协议最初为大规模系统设计（如 SGI Origin），但近年因其支持点对点互连网络，也被用于中小型系统。AMD 的 Coherent HyperTransport（HT）[5] 便是典型案例，它通过无桥接方式连接 AMD 处理器，构建小规模多处理器系统。尽管 Coherent HT 使用广播机制，但仍归类为目录协议，因其核心优势在于支持点对点链路，而非可扩展性。

        AMD 发现，通过每芯片 3 条点对点链路（最大链路距离为 3），可构建最多 8 芯片（共 48 核）的系统。为简化协议，Coherent HT 采用 Dir0B 目录协议变体（见 8.5.2 节）：不存储稳定目录状态，所有一致性请求均广播至所有缓存控制器。这种设计因广播开销无法扩展至大规模系统，但满足了小规模系统的需求。

        在 Coherent HT 系统中，每个处理器芯片包含多个核心、集成内存控制器、HyperTransport 控制器及 1-3 条连接其他芯片的链路。“节点” 由处理器芯片及其本地内存组成。协议支持多种网络拓扑（如图 8.16 的四节点系统），且不要求一致性请求的全局有序，提升了网络灵活性。

一致性事务流程：

核心向归属节点的目录控制器单播一致性请求；
目录因无状态，将请求广播至所有核心（含请求者）；
各核心处理请求并向请求者返回响应（数据或确认）；
请求者收集所有响应后，向归属节点发送完成消息。

优缺点：

优点：支持点对点链路，无目录状态复杂性，适用于≤8 处理器的系统。
缺点：继承目录协议的长延迟（三跳或四跳），且广播流量比窥探协议更高（因每个广播请求都触发响应）。这些缺点促使 AMD 开发了升级版 HyperTransport Assist。

8.8.3 HyperTransport Assist

        针对代号 Magny Cours 的 12 核 AMD Opteron 处理器系统，AMD 开发了 HyperTransport Assist [6]。该技术通过消除 Coherent HT 的广播机制，提升性能。与 Coherent HT 的 Dir0B 协议不同，HT Assist 采用类似 8.6.2 节的目录缓存设计：每个多核芯片包含一个包含性目录缓存，存储（a）归属本节点且（b）在系统中被缓存的所有块的目录条目。无 DRAM 目录，保留了 Coherent HT 的轻量级特性。目录缓存通过 Recall 请求处理满状态时的条目替换。

关键特性：

简化的目录状态：目录条目仅存储足够信息，区分请求需广播至所有核心、单播至特定核心还是由本地内存响应。不维护精确共享者数量，仅用两种状态区分 “一个共享者” 和 “多个共享者”，降低存储开销。
避免频繁 Recall：遵循 “目录条目数至少为缓存块数两倍” 的经验法则，并通过实验证明，显式 PutS 请求的带宽开销与减少 Recall 的收益不匹配，因此取消该机制。
与 LLC 共享存储：目录缓存与 LLC 静态分区（默认 1MB 用于目录缓存，5MB 用于 LLC）。每个分配给目录缓存的 64 字节 LLC 块被解释为 16 个 4 字节目录条目，组织为 4 个 4 路组关联集。

8.8.4 Intel QPI

        Intel 为 2008 年推出的 Core 微架构开发了 QuickPath Interconnect（QPI）[9, 12]，首次应用于 Core i7-9xx 处理器。此前，Intel 使用共享总线（Front-Side Bus，FSB）连接处理器，但受限于电气信号限制。QPI 采用点对点链路，定义了从物理层到协议层的多层网络栈，本节聚焦其协议层特性。

        QPI 支持五种稳定一致性状态：MESI 状态 + F（Forward）状态。F 状态为干净只读状态，与 S 状态的区别在于：持有 F 状态块的缓存可响应数据请求。同一时刻仅一个缓存可持有 F 状态块。F 状态与 O 状态类似，但 F 块非脏，可静默逐出；而 O 块必须写回内存才能逐出。F 状态的优势在于允许从缓存而非内存提供只读数据，通常具有更低延迟。

两种协议模式：

Home Snoop 模式：本质是可扩展目录协议（名称中的 “Snoop” 易引起误解）。核心 C1 向归属节点 C2 的目录发送请求，目录仅将请求转发至相关节点（如持有 M 状态块的 C3）。C3 向 C1 返回数据并通知 C2，C2 再向 C1 发送 “完成” 消息，此时 C1 方可使用数据。目录作为协议中的序列化点，解决消息竞争。

Source Snoop 模式：为低延迟场景设计，但扩展性较差。核心 C1 向所有节点（含归属节点）广播请求，各核心向归属节点返回 “窥探响应”（指示块状态）。若块为 M 状态，核心还需直接向请求者发送数据。归属节点收集所有响应后，向请求者发送数据或非数据消息，完成事务。

Source Snoop 的竞争处理：
        与传统目录协议不同，Source Snoop 的广播请求不依赖全局有序网络，因此需特殊机制解决竞争。例如，当 C1 和 C2 同时广播 GetM 请求时，归属节点根据 “窥探响应” 的到达顺序决定请求顺序：假设 C2 的响应先到达，归属节点将 C1 的请求排序为第一，向 C1 提供数据并通知存在竞争。C1 确认后，归属节点指示 C1 将数据转发给 C2。这种竞争处理比传统目录协议更复杂。

与 Coherent HT 的对比：
        两者均使用广播，但 Coherent HT 由归属节点广播请求，而 Source Snoop 由请求者直接广播，导致竞争解决更复杂（因无单一排序点）。Source Snoop 的带宽开销高于 Home Snoop，但常见场景（无竞争）的延迟更低。

8.9 讨论与目录协议的未来

        目录协议已占据市场主导地位，即使在小规模系统中也比窥探协议更常见，主要因其支持点对点互连网络。此外，目录协议是实现可扩展缓存一致性的唯一选择 —— 尽管窥探协议可通过优化缓解瓶颈，但无法根本消除。对于需扩展至数百甚至数千节点的系统，目录协议是唯一可行方案。鉴于其可扩展性，预计目录协议在可预见的未来将继续保持主导地位。

        未来的高扩展性系统可能不完全支持一致性，或仅在子系统内保持一致性，而子系统间不保证一致性。另一种可能是借鉴 Cray 超级计算机的设计，要么不提供一致性 [14]，要么限制可缓存的数据范围 [1]。