第一章：A Primer on Memory Consistency and Cache Coherence - 2nd Edition

引言：

        许多现代计算机系统，包括同构和异构架构的系统，都在硬件层面支持共享内存。在共享内存系统中，每个处理器核心都可以对单一的共享地址空间进行读写操作。对于共享内存计算机而言，内存一致性模型定义了其内存系统在架构层面可见的行为表现。一致性定义给出了有关加载和存储操作（或者说内存读取和写入操作）的规则，以及这些操作如何作用于内存。作为支持内存一致性模型的一部分，许多计算机还提供了缓存一致性协议，以确保数据的多个缓存副本始终保持最新状态。

        本入门读物的目的是让读者对一致性和缓存一致性有一个基本的了解。这种理解既涵盖了必须解决的问题，也包括各种各样的解决方案。我们既会介绍高层次的概念，也会给出真实系统中的具体实例。

        这一版是第二版，反映了自第一版发行以来十年间的技术进步。除了其他一些较小的改动之外，还新增了两章内容：一章是关于非 CPU 加速器（主要聚焦于图形处理器）的一致性和缓存一致性，另一章则介绍了有关一致性和缓存一致性的形式化研究工作和工具。

第二版前言：

        这本入门读物的第二版与近十年前（2011 年）出版的第一版有所不同，主要是新增了两章内容，并且做了一些小的改动。新增的第 10 章讨论了非 CPU 加速器方面的前沿研究成果，主要是通用图形处理器（GPU），这类加速器通常将一致性和缓存一致性结合起来实现。新增的第 11 章介绍了自这本入门读物第一版发行以来在一致性和缓存一致性方面取得重大进展的形式化研究工作和工具。其他改动相对较小，包括以下内容：第 2 章扩展了缓存一致性的定义，纳入了与第 10 章中类似 GPU 的解决方案；第 3 章和第 4 章分别讨论了在顺序一致性（SC）和总存储顺序（TSO）的实施方面的最新进展；第 5 章增加了一个 RISC-V 的案例研究。

        这本读物的第一版部分得到了美国国家科学基金会（资助项目编号：CNS-0551401、CNS0720565、CCF-0916725、CCF-0444516 和 CCF-0811290）、桑迪亚国家实验室 / 美国能源部（项目编号：#MSN123960/DOE890426）、半导体研究协会（合同编号：2009-HJ-1881）以及威斯康星大学（授予希尔的凯利特奖）的支持。本文所表达的观点不一定代表美国国家科学基金会、桑迪亚国家实验室、美国能源部或半导体研究协会的观点。第二版得到了英国工程与自然科学研究委员会（EPSRC）授予爱丁堡大学的 EP/M027317/1 号资助项目、美国国家科学基金会（资助项目编号：CNS-1815656、CCF-1617824、CCF-1734706）以及授予希尔的约翰・P・莫格里奇讲席教授职位的支持。本文所表达的观点仅代表作者本人。

        作者们感谢瓦西列奥斯・加夫里拉托斯、奥利维耶・吉鲁、丹尼尔・卢斯蒂格、凯利・肖、马修・辛克莱，以及 2019 年春季由希尔教授讲授的威斯康星大学麦迪逊分校研究生并行计算机架构课程（CS/ECE 757）的学生们，感谢他们富有见地且详细的评论，这些评论完善了这一第二版，尽管最终内容的责任仍由作者承担。

        作者们还感谢玛格丽特・马托诺西、娜塔莉・恩赖特・杰格、迈克尔・摩根以及他们的编辑团队，感谢他们促成了这一版入门读物的出版。

        维杰感谢尼维、萨特瓦、斯瓦拉、他的父母以及岳父母给予的爱。维杰还感谢印度理工学院马德拉斯分校对他休假的支持，大部分新章节都是在他休假期间撰写的。特别地，他深情地回忆起在金奈 “冬季” 最寒冷的时候，在印度理工学院 Chemplast 操场的板球练习场度过的时光。

        丹感谢黛博拉、杰森和朱莉给予的爱，感谢他们容忍他花时间来撰写这本入门读物的新一版。

        马克感谢苏、妮可和格雷戈里给予的爱和支持。

        大卫感谢他的合著者们容忍他在截止日期方面颇具挑战的工作风格，感谢他的父母罗杰和安・伍德激励他成为一名第二代计算机科学教授，也感谢简、亚历克斯和扎克让他铭记生活的真谛。

第一章   一致性与缓存一致性简介

        许多现代计算机系统以及大多数多核芯片（芯片级多处理器）都在硬件层面支持共享内存。在共享内存系统中，每个处理器核心都可以对单一的共享地址空间进行读写操作。这些设计追求多种优良特性，比如高性能、低功耗和低成本。当然，如果不能首先确保正确性，提供这些优良特性也就没有价值了。从表面上看，正确的共享内存似乎是直观易懂的，但正如本次讲座将展示的那样，即便只是定义一个共享内存系统的正确性意味着什么，其中也存在一些微妙的问题，而且在设计一个正确的共享内存实现时，还会有许多容易被忽视的特殊情况。此外，在硬件实现中，这些微妙之处必须被掌握，因为在硬件中修复错误的成本很高。即使是研究人员也应该掌握这些微妙之处，这样才能使他们提出的设计更有可能行得通。

        设计和评估一个正确的共享内存系统，要求架构师理解内存一致性和缓存一致性，这也是本入门读物的两个主题。内存一致性（一致性、内存一致性模型或内存模型）是对共享内存正确性的一种精确的、在架构层面可见的定义。一致性定义给出了有关加载和存储操作（或内存读写操作）的规则，以及这些操作如何作用于内存。理想情况下，一致性定义应该简单易懂。然而，定义共享内存的正确行为所涉及的微妙之处，比定义例如单线程处理器核心的正确行为要多得多。单处理器核心的正确性标准将行为分为一种正确结果和许多错误结果。这是因为处理器的架构规定，即使是在一个乱序执行的核心上，线程的执行也会将给定的输入状态转换为一个明确的输出状态。然而，共享内存一致性模型关注的是多个线程的加载和存储操作，通常允许多种正确的执行情况，同时禁止许多（更多）错误的执行情况。之所以会出现多种正确的执行情况，是因为指令集架构（ISA）允许多个线程并发执行，而且不同线程的指令通常有许多可能的合法交错方式。多种正确的执行情况使得原本简单的判断一次执行是否正确的问题变得复杂起来。尽管如此，为了实现共享内存，并且在某些情况下编写使用共享内存的正确程序，一致性是必须要掌握的。

        微架构（即处理器核心和共享内存系统的硬件设计）必须实现所期望的一致性模型。作为对一致性模型支持的一部分，硬件提供了缓存一致性（或一致性）。在带有缓存的共享内存系统中，当其中一个处理器更新其缓存值时，缓存中的值可能会过时（或不一致）。缓存一致性旨在使共享内存系统的缓存像单核系统中的缓存一样，在功能上对用户不可见；它通过将一个处理器的写入操作传播到其他处理器的缓存中来实现这一点。值得强调的是，与一致性不同，一致性是定义共享内存正确性的架构规范，而缓存一致性是支持一致性模型的一种手段。

        尽管内存一致性是本入门读物的第一个主要主题，但我们在第 2 章先简要介绍缓存一致性，因为缓存一致性协议在提供一致性方面起着重要作用。第 2 章的目标是对缓存一致性进行足够的解释，以便读者理解一致性模型如何与一致性缓存相互作用，但不会深入探讨具体的缓存一致性协议或实现方式，我们将这些内容留到本入门读物的第二部分，即第 6 章至第 9 章。

1.1 一致性（又称内存一致性、内存一致性模型或内存模型）

        一致性模型根据加载和存储操作（内存读写操作）来定义正确的共享内存行为，而不涉及缓存或缓存一致性。为了获得一些关于为什么我们需要一致性模型的现实直观理解，考虑一所大学在网上公布其课程表的情况。假设计算机体系结构课程最初安排在 152 教室。在课程开始的前一天，大学注册员决定将课程移到 252 教室。注册员发送了一封电子邮件，要求网站管理员更新在线课程表，几分钟后，注册员又给所有已注册的学生发送了一条短信，让他们查看新更新的课程表。不难想象这样一种情况：比如说，如果网站管理员太忙而没有立即发布更新，那么一个勤奋的学生收到短信后，立即查看在线课程表，可能仍然会看到（旧的）课程地点 152 教室。即使在线课程表最终更新为 252 教室，并且注册员按照正确的顺序执行了 “写入” 操作，但这个勤奋的学生却以不同的顺序看到了这些操作，因此去错了教室。一致性模型定义了这种行为是正确的（在这种情况下，用户是否必须采取其他行动来达到预期结果）还是错误的（在这种情况下，系统必须避免这些重新排序的情况）。

       虽然这个人为编造的例子使用了多种媒介，但类似的行为也可能发生在具有乱序处理器核心、写缓冲区、预取功能和多个缓存体的共享内存硬件中。因此，我们需要定义共享内存的正确性，也就是哪些共享内存行为是被允许的，这样程序员就知道可以期待什么，而实现者也知道他们所能提供的功能的限制。

       共享内存的正确性是由内存一致性模型，或者更简单地说，由内存模型来规定的。内存模型规定了使用共享内存执行的多线程程序的允许行为。对于使用特定输入数据执行的多线程程序，内存模型规定了动态加载操作可能返回的值，并且在某些情况下，还规定了内存可能的最终状态。与单线程执行不同，多线程执行通常允许多种正确的行为，这使得理解内存一致性模型变得有些微妙。

       第 3 章介绍了内存一致性模型的概念，并介绍了顺序一致性（SC），这是最强且最直观的一致性模型。本章首先阐述了规定共享内存行为的必要性，并精确地定义了内存一致性模型是什么。接下来深入探讨了直观的顺序一致性模型，该模型指出，多线程执行应该看起来像是每个组成线程的顺序执行的交错，就好像这些线程在单核处理器上进行时间复用一样。除了这种直观的理解，本章还对顺序一致性进行了形式化定义，并探讨了以简单和激进的方式通过缓存一致性来实现顺序一致性，最后以 MIPS R10000 的案例研究作为总结。

       在第 4 章中，我们超越了顺序一致性，重点关注由 x86 和早期 SPARC 系统实现的内存一致性模型。这个一致性模型被称为总存储顺序（TSO），其产生的原因是希望使用先进先出的写缓冲区在将已提交的存储操作结果写入缓存之前暂存这些结果。这种优化违反了顺序一致性，但它带来了足够的性能提升，促使架构师定义了总存储顺序模型，该模型允许这种优化。在本章中，我们展示了如何在顺序一致性的形式化定义基础上对总存储顺序进行形式化定义，总存储顺序如何影响实现，以及顺序一致性和总存储顺序之间的比较。

       最后，第 5 章介绍了 “宽松” 或 “弱” 内存一致性模型。通过展示强一致性模型中的大多数内存排序其实是不必要的，来阐述这些模型存在的意义。如果一个线程更新了十个数据项，然后更新了一个同步标志，程序员通常并不关心这些数据项之间是否按顺序更新，而只关心在标志更新之前所有数据项都已更新。宽松模型试图利用这种更大的排序灵活性来获得更高的性能或更简单的实现。在阐述了这一动机之后，本章开发了一个名为 XC 的宽松一致性模型示例，在这个模型中，程序员只有在使用 FENCE 指令（例如，在最后一次数据更新之后但在标志写入之前使用 FENCE 指令）请求排序时才能获得顺序保证。然后，本章扩展了前两章的形式化方法来处理 XC 模型，并讨论了如何实现 XC 模型（在核心之间以及缓存一致性协议中存在大量的重新排序情况）。接着，本章讨论了一种许多程序员可以避免直接考虑宽松模型的方法：如果他们添加足够的 FENCE 指令以确保他们的程序没有数据竞争（DRF），那么大多数宽松模型将表现得像顺序一致性模型一样。通过 “无数据竞争时的顺序一致性（SC for DRF）”，程序员既可以获得顺序一致性模型相对简单的正确性保证，又可以获得 XC 模型相对较高的性能。对于那些想要更深入思考的人，本章最后区分了获取操作和释放操作，讨论了写入原子性和因果关系，给出了商业示例（包括一个 IBM Power 的案例研究），并简要提及了高级语言模型（Java 和 CCC）。

       回到课程表这个现实中的一致性例子，我们可以看到，电子邮件系统、人工网站管理员和短信系统的组合代表了一种极其弱的一致性模型。为了避免勤奋的学生去错教室的问题，大学注册员在发送电子邮件之后需要执行一个 FENCE 操作，以确保在发送短信之前在线课程表已经更新。

1.2 缓存一致性（又称一致性）

       除非特别注意，否则如果多个参与者（例如多个核心）可以访问一个数据的多个副本（例如在多个缓存中），并且至少有一个访问是写入操作，就可能会出现缓存一致性问题。考虑一个与内存一致性示例类似的例子。一个学生查看在线课程表，看到计算机体系结构课程在 152 教室上课（读取数据），并将此信息复制到她手机上的日历应用程序中（缓存数据）。随后，大学注册员决定将课程移到 252 教室，更新了在线课程表（写入数据），并通过短信通知了学生。此时，学生手机上的数据副本就过时了，我们就遇到了不一致的情况。如果她去 152 教室，就会找不到她的课程。在计算领域中，除了计算机体系结构之外，缓存不一致的例子还包括过时的网页缓存和程序员使用未更新的代码库。

       使用缓存一致性协议可以防止访问过时数据（不一致）的情况，缓存一致性协议是由系统内的分布式参与者实现的一组规则。缓存一致性协议有很多种变体，但都遵循一些共同的原则，这些将在第 6 章至第 9 章中展开讨论。从本质上讲，所有变体都是通过将一个处理器的写入操作传播到所有缓存，使其他处理器能够看到该写入操作，即保持日历与在线课程表同步。但是不同的协议在同步的时间和方式上有所不同。缓存一致性协议主要有两大类。第一种方法中，缓存一致性协议确保写入操作同步传播到缓存中。当在线课程表更新时，缓存一致性协议确保学生的日历也会更新。在第二种方法中，缓存一致性协议异步地将写入操作传播到缓存中，同时仍然遵循一致性模型。缓存一致性协议不能保证当在线课程表更新时，新的值也会传播到学生的日历中；但是，该协议确实确保在短信到达她的手机之前，新的值已经传播出去了。本入门读物主要关注第一类缓存一致性协议（第 6 章至第 9 章），而第 10 章将讨论新兴的第二类协议。

       第 6 章介绍了缓存一致性协议的总体情况，并为后续关于具体缓存一致性协议的章节奠定了基础。本章涵盖了大多数缓存一致性协议共有的问题，包括缓存控制器和内存控制器的分布式操作，以及常见的 MOESI 缓存一致性状态：已修改（M）、已拥有（O）、独占（E）、共享（S）和无效（I）。重要的是，本章还介绍了我们基于表格驱动的方法，用于描述具有稳定（例如 MOESI）和瞬态缓存一致性状态的协议。在实际实现中需要瞬态状态，因为现代系统很少允许从一个稳定状态原子地转换到另一个稳定状态（例如，处于无效状态的读缺失在进入共享状态之前会花费一些时间等待数据响应）。缓存一致性协议的许多实际复杂性都隐藏在瞬态状态中，这与处理器核心的许多复杂性隐藏在微架构状态中类似。

       第 7 章介绍了窥探式缓存一致性协议，该协议最初在商业市场上占据主导地位。从表面上看，窥探式协议很简单。当发生缓存缺失时，一个核心的缓存控制器会对共享总线进行仲裁，并广播其请求。共享总线确保所有控制器以相同的顺序看到所有请求，因此所有控制器可以协调它们各自的分布式操作，以确保维护全局一致的状态。然而，窥探式协议会变得复杂，因为系统可能使用多条总线，并且现代总线不会原子地处理请求。现代总线有用于仲裁的队列，并且可以发送单播、因流水线而延迟或乱序的响应。所有这些特性都会导致更多的瞬态缓存一致性状态。第 7 章以 Sun UltraEnterprise E10000 和 IBM Power5 的案例研究作为结尾。

       第 8 章深入探讨了目录式缓存一致性协议，与依赖广播的窥探式协议相比，该协议有望扩展到更多的处理器核心和其他参与者。有一个玩笑说，计算机科学中的所有问题都可以通过增加一层间接性来解决。目录式协议证实了这个玩笑：缓存缺失会向更高一级的缓存（或内存）控制器请求一个内存位置，该控制器维护一个目录，用于跟踪哪些缓存持有哪些位置。根据所请求内存位置的目录项，控制器会向请求者发送响应消息，或者将请求消息转发给当前缓存该内存位置的一个或多个参与者。每条消息通常只有一个目的地（即没有广播或多播），但是瞬态缓存一致性状态大量存在，因为从一个稳定的缓存一致性状态转换到另一个稳定状态可能会生成与系统中参与者数量成比例的大量消息。本章从一个基本的 MSI 目录式协议开始，然后对其进行改进，以处理 MOESI 状态中的独占（E）和已拥有（O）状态、分布式目录、减少请求的停顿、近似的目录项表示等。本章还探讨了目录本身的设计，包括目录缓存技术。本章以旧的 SGI Origin 2000 和较新的 AMD HyperTransport、HyperTransport Assist 以及 Intel QuickPath Interconnect（QPI）的案例研究作为结尾。

       第 9 章讨论了缓存一致性方面的一些（但不是全部）高级主题。为了便于解释，之前关于缓存一致性的章节有意将内容限制在解释基本问题所需的最简单系统模型上。第 9 章深入探讨了更复杂的系统模型和优化方法，重点关注窥探式协议和目录式协议共有的问题。初始主题包括处理指令缓存、多级缓存、直写式缓存、转换后备缓冲区（TLB）、一致性直接内存访问（DMA）、虚拟缓存和分层缓存一致性协议。最后，本章深入探讨了性能优化（例如针对迁移共享和伪共享）以及一个名为令牌一致性的新协议族，该协议族涵盖了目录式和窥探式缓存一致性。

1.3 异构系统的一致性与缓存一致性

       现代计算机系统主要是异构的。如今的手机处理器不仅包含多核 CPU，还具有 GPU 和其他加速器（例如神经网络硬件）。为了追求可编程性，这样的异构系统开始支持共享内存。第 10 章讨论了此类异构处理器的一致性和缓存一致性问题。

       本章首先关注 GPU，这可以说是当今最流行的加速器。本章指出，GPU 最初选择不支持硬件缓存一致性，因为 GPU 是为非常适合并行处理的图形工作负载而设计的，这些工作负载并不需要太多的同步或数据共享。然而，当 GPU 用于具有细粒度同步和数据共享的通用工作负载时，硬件缓存一致性的缺失会带来可编程性和 / 或性能方面的挑战。本章详细讨论了一些有前景的缓存一致性替代方案，这些方案克服了这些限制，特别解释了为什么候选协议直接强制实施一致性模型，而不是以一种与一致性无关的方式实现缓存一致性。本章最后简要讨论了跨 CPU 和加速器的一致性和缓存一致性问题。

1.4 指定和验证内存一致性模型与缓存一致性

       一致性模型和缓存一致性协议既复杂又微妙。然而，必须处理好这种复杂性，以确保多核处理器是可编程的，并且其设计能够得到验证。为了实现这些目标，形式化地指定一致性模型至关重要。一个形式化的规范将使程序员能够在工具的支持下，清晰且详尽地理解内存模型允许哪些行为，不允许哪些行为。其次，精确的形式化规范对于验证实现是必不可少的。

       第 11 章首先讨论了两种指定系统的方法 —— 公理法和操作法，重点介绍这些方法如何应用于一致性模型和缓存一致性协议。然后，本章介绍了针对一致性模型和缓存一致性协议的规范，验证实现（包括处理器流水线和缓存一致性协议的实现）的技术。本章讨论了形式化方法和非形式化测试。

1.5 一致性与缓存一致性测验

       人们很容易认为自己对一致性和缓存一致性的知识已经足够，认为没有必要阅读这本入门读物。为了检验是否真的如此，我们提供了这个小测验。

1. 在一个保持顺序一致性的系统中，一个核心必须按照程序顺序发出一致性请求。对还是错？（答案在 3.8 节）
2. 内存一致性模型规定了一致性事务的合法顺序。对还是错？（3.8 节）
3. 为了执行一个原子的读 - 修改 - 写指令（例如，测试并设置），一个核心必须始终与其他核心进行通信。对还是错？（3.9 节）
4. 在一个具有多线程核心的总存储顺序（TSO）系统中，线程可以绕过写缓冲区中的值，而不管是哪个线程写入了该值。对还是错？（4.4 节）
5. 一个根据高级语言的一致性模型（例如 Java）编写了正确同步代码的程序员，不需要考虑架构的内存一致性模型。对还是错？（5.9 节）
6. 在 MSI 窥探式协议中，一个缓存块只能处于三种一致性状态之一。对还是错？（7.2 节）
7. 窥探式缓存一致性协议要求核心在总线上进行通信。对还是错？（7.6 节）
8. GPU 不支持硬件缓存一致性。因此，它们无法强制实施内存一致性模型。对还是错？（10.1 节）

       尽管答案在本入门读物的后面部分会给出，但我们鼓励读者在查看答案之前尝试回答这些问题。

1.6 本入门读物不涉及的内容

       本次讲座旨在作为关于缓存一致性和一致性的入门读物。我们预计这些内容大约可以在十节 75 分钟的研究生课程中讲授完（例如，第 2 章到第 11 章每章一讲）。

       为此，本入门读物不涉及很多内容。其中包括以下一些方面：

• 同步：缓存一致性使缓存对用户不可见。一致性可以使共享内存看起来像一个单一的内存模块。尽管如此，程序员可能仍然需要锁、屏障和其他同步技术，以使他们的程序发挥作用。读者可参考关于共享内存同步的综合讲座 [2]。