玻尔百科对更强计算能力的追求引领我们进入了多处理器系统时代，即多个处理核心在单个芯片上并行工作。尽管将工作分配给多个执行者的想法预示着巨大的速度提升，但它也引入了一个根本性的挑战：协调。简单地增加更多核心并不能保证更快的结果；它们必须高效且正确地通信和同步，避免冲突并确保数据视图的一致性。本文旨在解决并行计算中的这一核心问题。首先，文章将探讨构成多处理器设计基础的核心“原理与机制”，从由缓存一致性协议维持的单一内存幻象，到同步的艺术和内存排序的微妙规则。随后，“应用与跨学科联系”一章将展示操作系统和软件如何协调这些原理，以实现真实世界的性能、管理能源并解决复杂问题，揭示了驱动现代计算的硬件与软件之间错综复杂的舞蹈。
多处理器系统背后的理念看似简单却极具吸引力。如果厨房里的一位厨师能在一小时内准备好一顿饭，那么两位厨师肯定能在半小时内完成。这种简单的直觉——即更多的工作者带来更快的结果——正是并行计算的前景。通过将多个处理单元（即核心）放置在单个芯片上，我们希望能解决日益庞大的问题，从模拟气候到训练人工智能。
但正如任何与伴侣一起做过饭的人所知，简单地增加人手并不能保证任务成功。厨师们必须相互协调。他们需要无冲突地共享餐具，就食谱达成一致，并确保在下一步开始前，一位厨师完成的步骤已为另一位所知。这种协调正是多处理器设计的核心问题。解决这一问题的优雅且往往微妙的方案构成了一幅美丽的计算机科学画卷，揭示了硬件与软件之间深刻的相互作用。
在最高层次上，我们可以想象不同的厨房布局。我们可以让厨师们在各自独立的私人厨房工作，通过一个窗口传递完成的菜肴——这是一种分布式内存模型。或者，我们也可以让他们都在一个大型共享厨房里工作，使用相同的储藏室和工作台——这是一种共享内存模型。我们此处的旅程将聚焦于共享内存模型，这也是我们日常使用的计算机内部的主流设计。
即便是在一个共享厨房内，也有许多可能的安排。我们是为每位厨师配备一套相同的标准工具（对称多处理，或SMP），还是创造出专家（非对称多处理，或AMP）？例如，想象一个需要处理大量食材的任务。一种方法是让一位通用厨師从附近库存充足的架子上（一个缓存）逐一拿取食材。对于小规模、重复性的任务来说，这很快。另一种方法可能是让一位专家厨师，“大核心”，派遣一名助手带着一辆大手推车（一个直接内存访问或DMA引擎），从主储藏室（主内存）取回整个食材清单，并将其运送到一个特殊的准备站（一个暂存内存）。正如一个引人入issheng的设计练习所示，没有一种方法是普遍更优的。基于缓存的方法几乎没有启动成本，但受限于其逐项获取的速率；而DMA方法有显著的初始延迟，但能以快得多的速度批量移动数据。最佳选择取决于任务的规模；对于小任务，缓存更快，但对于大负载，DMA卓越的带宽最终会胜出。这种延迟与带宽之间的权衡是计算机体系结构中一个反复出现的主题，是追求性能过程中不断的平衡之举。
多处理器系统提供的最强大的幻象之一是，所有核心都在与一个单一、统一的内存块交互。实际上，为了弥合CPU与主内存之间巨大的速度鸿沟，每个核心都有自己的私有高速记事本——它的缓存。缓存对性能极佳，但它们也带来一个根本问题：如果一个核心将新值写入其私有缓存，其他可能持有该数据旧的、过时副本的核心如何得知？这就是缓存一致性问题。
想象每位厨师都有一份食谱的个人副本。如果一位厨师决定将盐的用量从一茶匙改为两茶匙，并且只在自己的副本上潦草记下，那么最终的菜肴注定会失败。系统必须确保一个核心所做的更改最终能被所有其他核心看到，并且对于任何单个内存位置的写入顺序有明确的共识。
对于拥有少数核心的系统，最常见的解决方案是监听协议。在我们的厨房比喻中，这就像所有厨师工作得足够近，可以互相听到对方的话。每当一个核心想要访问内存时，它会在共享总线上广播其意图。所有其他核心都会“监听”这条总线。如果它们拥有被请求数据的副本，它们可以相应地做出反应。为了管理这一点，缓存中的每一行都标有一个状态。最常见的协议是MESI，它代表修改（Modified）、独占（Exclusive）、共享（Shared）和无效（Invalid）。
这些状态构成了一场精密的电子舞蹈。对一个Shared行的写入会迫使一个核心广播一个无效化消息，通知所有其他核心将它们的副本标记为Invalid。写入者的行则变为Modified。当另一个核心读取那个Modified行时，其请求将被所有者拦截，由所有者提供最新的数据。
对这场舞蹈的巧妙改进带来了显著的性能提升。考虑MOESI协议，它增加了一个Owned (O)状态。假设一个核心持有一个Modified行，而第二个核心希望读取它。在一个简单的MESI协议中，第一个核心必须将其数据一直写回主内存（一个缓慢的过程），然后第二个核心才能读取它。Owned状态提供了一个绝佳的优化：所有者可以直接通过快速的缓存到缓存传输将数据提供给请求者，同时它自己的行状态转变为Owned。Owned状态就像Modified状态，因为数据是脏的，但又像Shared状态，因为其他核心现在也持有一份副本。这个简单的补充通过避免不必要的慢速主内存访问，显著减少了内存访问所浪费的时间。
然而，监听协议无法扩展。在一个有数百名厨师的宴会厅里，大声喊出你的意图不再现实——总线会变得饱和。对于这些更大型的系统，会使用基于目录的协议。在这里，系统维护一个中央目录，就像一个总账本，记录着哪些核心拥有哪个内存块的副本。核心不再向所有人广播，而是将其请求发送到管理该内存块目录的“宿主节点”。宿主节点随后只向相关核心发送 targeted messages。这种方式的可扩展性要好得多。但即便如此，也仍有优化空间。如果许多核心都在读取相同的共享数据，宿主节点可能会因为为每个请求从主内存获取数据而陷入困境。一个聪明的解决方案是在宿主节点本身增加一个特殊缓存，专门用于存放这些流行的、只读共享的块。这个“共享读取缓存”可以服务许多请求而无需打扰主内存，从而进一步减少大型系统中的流量和延迟。
维持内存的一致性视图只是战斗的一半。核心还必须协调它们的行动，尤其是在修改共享数据时。这就是同步的挑战。这个问题的最简单形式是临界区：一段为了正确性而必须在任意时刻只由一个核心执行的代码。可以把它想象成一个共享的盐瓶——一次只能有一个厨师使用。
我们如何强制实现这种排他性？在只有一个核心的老式单处理器系统上，一个简单而有效的技巧是禁用中断。由于上下文切换是由定时器中断触发的，禁用它们实际上给了当前线程对CPU的独占使用权。这就像厨师锁上厨房门独自工作一样。
但在多处理器系统中，这个技巧完全失效。在一个核心上禁用中断，并不能阻止另一个核心并行执行。锁上你自己的厨房门，并不能阻止隔壁厨房的厨師从他们的门进来。这个根本性的差异——从交错并发到真正并行的转变——意味着我们需要一个更强大的机制。在多处理器信号量上尝试使用禁用中断可能导致一种毁灭性的竞争条件，称为丢失的唤醒，即一个核心决定进入睡眠状态，而恰在此时另一个核心试图唤醒它，导致第一个核心永远沉睡[@problem-id:3681473]。
解决方案必须来自硬件本身，以原子指令的形式出现。这些是硬件保证作为单个、不可分割步骤执行的特殊指令。像Test-and-Set或更强大的Compare-and-Swap (CAS)这样的指令是几乎所有多处理器同步的基础构建块。它们就像一个一次只能由一个人打开和关闭的魔法锁盒。
即使有了这些强大的工具，我们如何使用它们也对性能产生深远影响。实现锁的一种常见方式是自旋锁，即等待的核心在一个紧凑的循环中反复尝试获取锁。一个简单的自旋锁可能在每次迭代中都使用Test-and-Set。从缓存一致性的角度看，这是一场灾难。每次Test-and-Set都是一次写操作，需要获得包含锁的缓存行的独占所有权。如果有十个核心在自旋，它们将为所有权展开一场激烈的争夺，用无效化请求淹没共享总线，即使锁的状态并未改变。这就像十个厨师不停地试图从对方手中抢夺盐瓶。
一个优雅得多的解决方案是测试-测试并设置锁。在这里，等待的核心首先通过只读取锁的值来进行自旋。由于锁是共享的，所有核心都可以在其缓存中以Shared状态持有副本，这些读取不会产生总线流量。只有当一个核心读到锁是空闲时，它才会尝试执行昂贵的原子Compare-and-Swap操作来获取它。这就像厨师们耐心地看着盐瓶，只有看到它被放下时才伸手去拿。软件算法中的这个简单改变极大地减少了硬件一致性流量，是软件必须结合对底层硬件的认知来编写以获得良好性能的完美示例。这场舞蹈是如此精妙，以至于其他性能问题也可能出现，比如伪共享，即两个核心修改逻辑上分离但恰好位于同一缓存行中的变量，导致该行在它们之间被浪费地来回穿梭。
我们现在来到了多处理器系统中最微妙却也最深刻的原理：内存一致性模型。我们已经看到，缓存一致性保证了所有核心对单一内存位置的写入序列达成一致。但它对不同位置访问的表观顺序不做任何承诺。
现代处理器是急躁的典范。为了最大化性能，它们会积极地重排序指令，以不同于程序员编写的顺序执行它们，只要在那个单一核心上的结果看起来是正确的。一个常见的优化是存储缓冲区，这是一个核心放置其待写出内容的小队列。这使得核心可以继续执行后续指令，而无需等待缓慢的写操作完成。对不同地址的加载操作可以绕过存储缓冲区并提前执行。
这种重排序在单个核心上是不可见且无害的，但在多处理器系统中，它可能导致令人费解的结果。思考这个著名的思想实验：两个共享变量和初始化为。两个核心并发执行：
可能的结果是什么？直观上看， 似乎是不可能的。要让 为 ，核心0对 的读取必须在核心1对 的写入可见之前发生。要让 为 ，核心1对 的读取必须在核心0对 的写入可见之前发生。这构成了一个逻辑循环。然而，在大多数现代处理器上， 这个结果是完全可能的！
原因如下：核心0执行 ，但这个写入进入了它的存储缓冲区。然后它立即执行对 的读取，由于核心1的写入尚不可见，它读到了值 。对称地，核心1将其对 的写入缓冲起来，并立即读取 ，得到 。每个核心都重排序了自己的存储和加载操作。缓存一致性没有被违反，因为对于 或 的最终值没有分歧。问题在于跨不同变量的操作顺序。这就是内存一致性模型所定义的。程序员直观期望的严格的顺序一致性 (SC)模型禁止这种结果。大多数硬件实现的是弱序或松散内存模型，为了性能而允许这种情况发生。
为了恢复秩序，程序员必须使用内存栅栏（或屏障）。栅栏是一条指令，它告诉处理器强制执行一个排序约束。在我们的例子中，在每个核心的写入和读取之间放置一个栅栏，将迫使每个核心在继续其读取操作之前，等待其写入操作变得全局可见，从而使 的结果变得不可能。
虽然通用栅栏有效，但现代编程使用一种更精炼、更具沟通性的方法，称为释放-获取语义。这非常适合常见的模式，比如一个“生产者”核心准备数据，然后一个“消费者”核心处理它。想象一个生产者更新一个数据结构，然后设置一个标志来表示它已准备好。如果没有排序保证，消费者可能会在数据实际准备好之前就看到标志被设置，从而导致混乱。
这对操作构成了一个同步契约，在生产者的工作和消费者的读取之间建立了一个“happens-before”（先于发生）关系。这是以最小和最高效的方式，在恰好需要的地方强制执行顺序，而无需使用重量级的完整栅栏。
这些原理——一致性、同步和内存一致性模型——不仅仅是抽象的学术概念。它们是构建操作系统和高性能软件的工程师们的日常现实。一个典型的例子是TLB 击落（TLB Shootdown）。转译后备缓冲器（TLB）是用于虚拟地址到物理地址转换的每核心缓存。当操作系统更改共享页表中的一个映射时，它必须通知所有其他核心，使其TLB中任何过时的条目无效。
这个过程是多处理器挑战的一个缩影。首先，它是一个性能瓶颈。向所有其他核心发送处理器间中断（IPI）并等待确认是一个同步过程，其延迟可能随核心数量的增加而扩展。但更重要的是，它是一个关键的正确性问题，构成了我们所讲原理的一曲完整交響乐。
任何一步的失败——忘记一个栅栏，过早确认——都可能允许一个程序使用过时的地址访问内存，导致系统崩溃。TLB击落协议是由操作系统精心编排的一支美丽而复杂的舞蹈，它依赖于一致性、原子操作和内存排序等基本硬件原语，以维持所有现代软件所依赖的稳定、简单的虚拟内存抽象。它证明了一个事实：在多处理器系统中，一切都是相互关联的，让更多的厨师协同工作不仅需要一个更大的厨房，更需要对沟通规则的深刻理解。
在深入机舱，理解了多处理器系统的原理与机制之后，我们现在踏上征程，去看看这个引擎是如何运作的。一个多处理器系统很像一个由才华横溢但又极其独立的专家组成的团队。真正的魔力不在于他们个人的才华，而在于让他们和谐共奏的艺术。如果说上一章是关于乐器本身——小提琴、大提琴、铜管乐器——那么这一章就是关于它们创造的音乐。
我们将看到同步、调度和一致性这些抽象概念如何为我们日常使用的设备注入生命，使它们同时做到快速、响应灵敏和高效。这次探索是一次穿越计算机科学宏伟谜题的旅行，工程师和科学家们如同大师级指挥家，必须平衡相互竞争的需求，以实现一个优美而功能完整的整体。我们将发现，协调这些核心的挑战将我们与概率论、热力学和图论等不同领域联系起来，揭示了计算原理中深刻而令人满意的统一性。
拥有多个处理器的最显而易见的原因是对速度的 intoxicating promise。如果一个工人一小时能挖一个洞，那么六十个工人肯定一分钟就能挖好！但正如任何管理过团队的人所知，事情从没那么简单。工人们需要协调，他们可能会相互妨碍，而且工作的某些部分根本无法并行完成。
这就是著名的阿姆达尔定律的精髓——一条关于并行计算的基本且时而令人 sobering 的“收益递减定律”。它提醒我们，每个程序都有一个固有的串行部分，一个无论多少并行处理都无法加速的瓶颈。因此，性能工程的真正艺术不仅在于并行化可并行的部分，更在于最小化串行部分。
考虑计算机接收数据的普通任务。系统可以使用微小的缓冲区，每当一小片数据到达时就中断处理器。这会产生大量的串行开销，因为操作系统需要不断介入。一个看似聪明的解决方案是使用一个非常大的缓冲区，在收集一大块数据后才触发一个频率较低的单一中断。这减少了中断开销。然而，这引入了一种新的串行开销：等待大缓冲区填满的延迟。存在一个“甜蜜点”，一个最优的缓冲区大小，它通过平衡这两种相互竞争的成本来最小化总串行部分。找到这个最优值是系统调优中的一个经典难题，工程师们利用数学模型来驾驭权衡，从硬件中榨取每一滴性能。这表明，让事情变快是一场巧妙妥协的游戏，而不仅仅是靠蛮力。
如果说处理器是管弦乐队，那么操作系统（OS）就是指挥家。它手持指挥棒，引导工作流，确保没有人闲置太久，并防止整个演出陷入混乱。操作系统调度器每毫秒都要面对一系列令人眼花缭乱的选择，而它的决定正是让系统感觉流畅和响应迅速的原因。
想象一个线程需要一个资源——一段内存，一个文件——而这个资源当前正被另一个线程使用。它应该做什么？一个天真的策略是简单地排队等待。一个更激进的策略是“忙等待”，即线程疯狂地反复检查：“它空闲了吗？它空闲了吗？”这被称为自旋锁。
在多处理器系统上，自旋锁可能是一个非常好的主意。这就像赛车手在起跑线上保持引擎高速运转。一旦资源被释放，等待的线程可以零延迟地抓住它。但在只有一个处理器核心的系统上，同样的策略却是彻头彻尾的疯狂。如果持有锁的线程被调度器抢占，那么自旋的线程将获得运行机会。然后它会用掉它的整个时间片进行无用的自旋，等待一个不可能被释放的锁，因为持有该锁的线程没有在运行！这相当于在房间里只有你一个人的情况下，屏住呼吸直到有人来帮你。这种鲜明的对比揭示了一个深刻的真理：软件算法的有效性可能完全取决于它运行的底层硬件架构。
指挥家的噩梦是小提琴部分在疯狂演奏，而木管乐器却静坐一旁。同样，操作系统的噩夢是一個不平衡的系統，其中一個核心被工作淹沒，而其他核心卻處於閒置狀態。调度器的工作是成为一名杂耍大师，不断地重新分配任务以保持所有核心的高效运作。这就是所谓的负载均衡。
这应该如何完成？一种策略是拉取迁移：一个空閒或負載不足的核心可以从一个超载的核心“拉取”一个任务。这看起来很合理，但考慮這樣一种場景：一组任务突然涌入单个核心，而其他核心正忙于处理不同的、优先级较低的工作负载。由于没有其他核心真正“空闲”，它们都不会想到去拉取任务。高优先级的工作仍然在一个核心上成为瓶颈，系统无法达到其性能目标。
这就是推送迁移发挥作用的地方。一个超载的核心可以主动地将任务推给其他核心，即使它们已经很忙。这种主动的、抢占式的重新平衡对于需要强制执行公平性和资源配额的现代系统至关重要，例如在云计算环境中，不同的客户被保证获得一定比例的CPU。面对突发的工作负载爆发，推送工作的能力是将一个响应迅速的系统与一个迟缓的系统区分开来的关键。
一种更优雅、去中心化的方法是工作窃取。在这里，任何耗尽工作的核心都会成为一个“小偷”，并尝试从一个随机的“受害者”核心那里“窃取”一个任务。一个来自概率论的、奇妙而微妙的洞见，被称为“二次选择的力量”，极大地改进了这个过程。小偷不是随机挑选一个受害者，而是挑选两个并探测它们。通过简单地选择从两者中负载更重的那个窃取，小偷找到工作的几率会大大增加。这个简单的局部规则导致了一个全局高效的负载均衡系统，开销极小，它构成了许多现代并行编程语言和运行时的支柱。
调度器的智慧不止于此。它还必须是“缓存感知的”。将任务从一个核心移动到另一个核心不是没有代价的；任务会丢失它在本地缓存中预热的所有数据，并且必须在新核心上缓慢地重建它。因此，一个聪明的调度器会表现出处理器亲和性。它试图将任务保持在同一个核心上，以保护缓存局部性。只有当移动到一个不那么拥挤的核心所带来的好处超过移动所带来的惩罚时，它才会迁移任务。操作系统就像一个精明的经济学家，不断地权衡成本和收益以优化性能[@problemid:3672782]。
让我们再 peeling back 一层，看看硬件架构以深刻、有时甚至是令人惊讶的方式迫使软件如何行为。我们在编程中学到的清晰抽象，其背后往往有着混乱的现实。
计算中最优美的思想之一，即存储程序概念，是说指令就是数据。程序是内存中的一个字节序列，与图像或文本文件无异。CPU获取这些字节，将它们解释为命令，并执行它们。然而，现代处理器使这幅优雅的图景变得复杂。为了性能，它们有独立的、专门的缓存：用于读写数据的數據緩存（D-cache），以及用于获取可执行指令的指令緩存（I-cache）。
现在，想象一个在即时（JIT）编译器中常见的情景，Java和JavaScript等语言都使用这种编译器。一个核心，“编译器”，动态生成新的、高度优化的机器码——它向内存中写入数据。然后它通知另一个核心，“执行者”，去运行这段新代码。但执行者的I-cache可能包含来自同一内存地址的旧的、过时的指令。硬件没有提供自动保证，即对D-cache的写入会使I-cache中相应的行无效。
为确保正确性，软件必须执行一套复杂而仪式化的舞蹈。编译器核心必须首先写入代码，然后明确地刷新其D-cache，将新代码推送到主内存。然后它必须建立一个*内存屏障，以确保此刷新在继续之前对所有人都可见。最后，它通知执行者。执行者在收到信号后，必须明确地使其自己的I-cache无效*，然后使用一个指令屏障来清除其流水线中任何过时的、预取된的指令。只有这样，它才能安全地跳转到新代码。这个复杂的序列是一个惊人的例子，说明软件必须如何迎合最深层的架构细节，以维持“代码即数据”这个简单的幻象。
另一个挑战是如何在不拖慢强大处理器核心的情况下，将数据传入和传出机器。如果CPU必须管理来自高速网卡的每一个字节，它将没有时间进行实际计算。解决方案是直接内存访问（DMA），这是一种允许像网卡这样的设备直接将数据写入内存，完全绕过CPU的机制。
这为一种称为零拷贝网络的卓越优化打开了大门。传统上，当一个网络数据包到达时，操作系统会将其接收到一个内核缓冲区，然后执行一次内存拷贝，将其移动到目标应用程序的内存中。这次拷贝是纯粹的开销。通过零拷贝，操作系统可以转而通过将其重新映射到应用程序的地址空间，从而直接“给”应用程序包含该数据包的物理内存页。
但这个聪明的技巧充满了危险。首先，操作系统必须告诉网卡永远不要再触碰那个内存页。其次，更微妙的是，它必须通知系统中的所有其他CPU核心，这个页面不再属于内核。它们转译后备缓冲器（TLB）中关于该页面的任何缓存的虚拟到物理转换现在都已过时，必须被无效化。这是通过“TLB击落”完成的，这是一个涉及处理器间中断的昂贵过程。仔细的成本效益分析显示，由于TLB击落的高昂固定成本，零拷贝仅对于非常大的数据传输才比简单的内存拷贝更快。对于小数据包，老式的方法更好。这是一个系统工程的完美缩影：一个美丽的想法必须经过对其真实世界成本的严格定量分析来加以 tempering。
随着我们的多处理器系统变得越来越强大，我们的雄心已经超越了单纯的速度。另外两个关注点变得至关重要：能源效率和可证明的正确性。
我们再也不能通过简单地提高时钟频率来让处理器变得更快；它们会消耗巨大的电力并产生足以熔化的热量。前沿已经转向了性能每瓦特。这是动态电压与频率调整（DVFS）的领域，这是一种允许操作系统动态调整核心频率（及相关电压）的技术。
在这里我们发现了另一个优美而反直觉的结果。假设你有一定量的工作要做。是让一个核心全速运行而其他核心休息更节能，还是将工作分散到多个以较慢速度运行的核心上更节能？晶体管的物理学给了我们一个明确的答案。核心的动态功率随频率超线性增长，大约为 ，其中 通常大于2。由于这种凸函数关系，使用多个低频核心执行任务总是比使用一个高频核心更节能。这个原理，用一点微积分就可以推导出来，是你的智能手机能够执行复杂任务而电池不在几分钟内耗尽的原因。它是从移动设备到大型数据中心所有节能调度的基石。
也许并发世界中最令人恐惧的野兽是死锁。这是一种无进展的终极状态，其中一组线程全部卡住，每个线程都在等待集合中另一个线程持有的资源。一个经典的例子是两个线程 和 ，以及两个锁 和 。如果 持有 并等待 ，而 持有 并等待 ，它们将永远等待下去。
我们可以使用资源分配图来正式地推理这个问题，我们在图中画出从请求资源的线程到资源的箭头，以及从资源到持有它的线程的箭头。死锁表现为该图中的一个环路。这个形式化模型的美妙之处在于，它指向一个同样优雅且可证明正确的解决方案：锁顺序。如果系统强制执行一个规则，即所有线程必须按预定义的全局顺序（例如，按数字顺序）获取锁，那么死锁环路就变得不可能。一个持有锁 的线程只能请求锁 ，其中 。沿着图中的请求箭头，锁的编号必须总是增加，这使得永远不可能循环回到一个编号更小的锁来形成一个环路。这个简单而强大的协议将一个潜在混乱、不可预测的系统转变为一个可证明无死锁的系统。
我们为什么要费这么大的劲？为什么要构建这些由核心组成的复杂交响乐，以及它们复杂的调度器、缓存一致性协议和电源管理方案？我们这样做是为了能够解决那些否则不可能完成的大规模或耗时的问题。但要駕馭這種力量，需要的不仅仅是聰明的操作系統和硬件設計；它需要我們從根本上重新思考我们用来解决问题的算法。
你通常不能拿一个为单处理器设计的算法，就期望它能在上千个处理器上运行得很好。其逻辑本身必须被并行化。考虑寻找一个巨大图（如一个拥有数十亿用户的社交网络）的连通分量的问题。一个并行算法可能是这样工作的：最初，每个人（顶点）都在自己的分量中。然后，在一系列同步的回合中，每个人都查看他们的直接朋友（邻居），并采用他们在其中看到的最小的分量ID。这个信息像谣言一样在网络中传播。几轮之后，一个连通的朋友集群中的每个人都会同意同一个最小的ID作为他们分量的代表。这与顺序解决问题的方式完全不同，正是这种“并行思维”解锁了我们多处理器硬件的真正潜力。
从分析社交网络和模拟星系，到设计新药和破解密码，现代科学与工程的宏大挑战都需要这种并行方法。多处理器系统的复杂舞蹈使这一切成为可能。