玻尔百科在追求计算速度的道路上，并行处理——将一个问题分配给多个处理器——是一项基本策略。然而，其效率常常被一个持续存在的挑战所削弱：负载不均。当任务分配不均时，一些处理器会提前完成任务并处于空闲状态，而其他处理器仍在超负荷工作，这使得整个计算的速度取决于最慢的那个工作者。这种被浪费的潜力是高性能计算中一个显著的性能障碍。
本文探讨了针对此问题的一个强大而优雅的解决方案：工作窃取。与僵化、预先分配的劳动分工不同，工作窃取引入了一个动态、去中心化的系统，空闲的处理器会主动去寻找更多的工作。这是一个极其有效的方法，其规模可从小型多核芯片扩展到大型超级计算机。
我们将分两个主要部分深入探讨该技术的核心概念。首先，在原理与机制部分，我们将剖析工作窃取如何运作，探索双端队列的巧妙运用、缓存局部性与工作粒度之间的权衡，以及为适应现代计算机架构所需的调整。之后，在应用与跨学科联系部分，我们将见证这一思想的深远影响，了解工作窃取如何驾驭计算机图形学、科学模拟和复杂优化等领域中那些不可预测的工作负载。
想象一个工坊，里面有一组工匠，每人都被分配了一个大项目。然而，这些项目并非生而平等。一个工匠的任务很简单，而另一个工匠的任务则是一件复杂精细、需要两倍精力的作品。如果每个工匠被告知只能做自己的项目，一种奇怪的低效率就会出现。第一个工匠早早完工，然后坐着喝茶闲着，而他的同事仍然被埋在堆积如山的工作中。整个工坊只有在最后一个、负担最重的工匠最终完成工作时，才能宣布“完工”。
这个简单的故事揭示了并行计算的根本挑战：负载不均。当我们将一个大型计算问题分配给多个处理器时，这些部分很少能完美均等。例如，在科学模拟中，一位物理学家可能正在模拟一个星系。空间的某些区域是空的，而其他区域则充满了恒星形成或黑洞等复杂的相互作用。如果我们简单地将星系切成网格，并将每个网格片分配给一个处理器，那么处理“繁忙”区域的处理器将有更多的工作要做。
许多并行程序在一种称为块同步并行（BSP）的模型下运行。在这种模型中，处理器们先在各自的本地数据上进行计算，然后它们全部停下来，在一个“屏障”处等待，以交换信息，然后开始下一阶段。在我们工坊的类比中，这就像每个人都必须等待最后一个工匠完工，然后才能一起开始第二天的工作。每一步的总时间不是由平均水平的工作者决定的，而是由最慢的那个决定的。这种等待，这种强制的空闲，是性能的敌人。如果一个处理器花费 秒，而其他三个处理器花费 秒，那么整个步骤就需要 秒，这意味着我们近一半的潜在计算能力都浪费在了等待上。
解决方案似乎显而易见：空闲的工匠应该帮助忙碌的工匠！这个简单直观的想法正是动态负载均衡的基础。
一个空闲的处理器应该如何获得更多工作？主要有两种哲学，两种可以采取的架构“道路”。
第一种，也许是最显而易见的，是创建一个集中式任务队列。想象一下我们工坊中央的一个大箱子。任何创造了新子任务的工匠都把它放进箱子里。任何没有工作的工匠都去箱子里拿一个新任务。这看起来井然有序且公平。但随着我们增加越来越多的工匠，问题就出现了。每个人都不断地涌向同一个箱子，争抢位置。箱子本身成了一个瓶颈。
在计算中，这是一个经典的竞争问题。单个队列成为一个串行点，一个一次只能让一个处理器通过的窄门。在硬件层面，这具有非常物理的现实意义。为了安全地添加或移除任务而不引起混乱，队列由一个“锁”来保护。处理器必须获取这个锁才能修改队列。在现代芯片上，获取一个锁涉及到获得对特定内存——一个缓存行——的独占所有权。这个所有权必须从上一个持有它的处理器那里物理迁移过来，这个过程可能需要数百纳秒，在处理器时间里堪称永恒。因此，当你增加更多的处理器时，它们并不能完成更多的工作；它们只是排成一个越来越长的队伍，等待轮到自己与队列对话。系统的总吞吐量受限于这一个单一队列的服务速率。此外，这种设计还有一个明显的弱点：它是单点故障。如果托管中央队列的计算机崩溃，整个系统就会瘫痪。
这就把我们带到了第二条道路，一种看起来更微妙、更混乱——但实际上效率高得多的方法：工作窃取。
在这种模型中，没有中央箱子。每个工匠，或者说处理器，都有其自己的私有任务队列。它们大部分时间都愉快地处理自己的任务，这完全是本地的、快速的事情。只有当一个处理器的队列变空时，它才会采取行动。它变成一个“窃取者”。它随机选择另一个处理器——一个“受害者”——并试图从其队列中“窃取”一项工作。
这种方法的美妙之处在于其去中心化的特性。没有单一的瓶颈。负载均衡的行为分布在所有处理器之间。竞争很少发生，因为两个窃取者不太可能同时选择同一个受害者。当恒定比例的处理器处于繁忙状态时，一个空闲的处理器平均只需常数次尝试就能找到工作，无论系统有多大。这种方法具有极佳的可扩展性，并且天然具有容错性。一个处理器的故障不会拖垮整个系统；其他处理器只会注意到它的缺席，并停止尝试从它那里窃取。
然而，工作窃取的真正天才之处不仅在于“做什么”，更在于“如何做”。这些私有任务列表不是简单的队列；它们是特殊的双端队列，或称deques。而它们的使用规则就像一种能解锁惊人性能的秘密握手。
规则是这样的：“所有者”从队列的一端（我们称之为顶部）添加和移除任务。而“窃取者”总是从相反的一端（底部）窃取。
为什么是这种特定的、不对称的安排？这是一种巧妙的优化，它平衡了两个相互竞争的力量：缓存局部性和工作粒度。
我们先来看所有者这边。所有者将新任务推送到顶部，当它需要新任务时，也从顶部弹出。这是一种后进先出（LIFO）策略。可以把它想象成在迷宫中总是选择最近的岔路口来探索。在计算上，这对应于对问题任务图的深度优先遍历。这样做带来的巨大好处是时间局部性和空间局部性。一个刚由所有者创建的任务很可能需要与创建它的任务相同的数据，或位于内存中附近位置的数据。通过始终处理“最新”的事物，所有者使其所需的数据在其高速的本地CPU缓存中保持“热”状态。这是一个巨大的胜利，因为访问缓存比访问主内存快几个数量级。由于只有所有者会接触到双端队列的顶部，这些最频繁的操作可以在没有任何昂贵的同步锁的情况下完成。
现在，考虑窃取者这边。窃取者从双端队列的底部窃取，拿走最旧的任务。这是一种先进先出（FIFO）策略。在许多分治算法中，最早创建的任务是原始问题中最大、最实质性的部分。通过窃取最旧的任务，窃取者得到了一大块工作。这非常高效。一次成功的窃取可以让窃取者长时间保持忙碌，从而最大限度地减少了它执行昂贵的窃取行为的次数。这也最大限度地减少了干扰：窃取者正在处理问题数据的“冷”部分，远离所有者正在积极使用的“热”数据，从而减少了对内存和缓存资源的竞争。
这种关注点的分离——所有者在顶部，窃取者在底部——是该机制的核心。它使得最常见的情况（本地工作）快如闪电且几乎无竞争，同时使不那么常见的情况（窃取）尽可能有效且不具干扰性。
工作窃取尽管优雅，却并非魔杖。其有效性是一种微妙的权衡平衡，一场“恰到好处”的游戏。
首先，窃取行为本身有成本。管理任务及其依赖关系的运行时系统会引入少量计算开销。这意味着当启用工作窃取时，CPU执行的总指令数实际上会增加。然而，为了大幅减少*停顿时间*——即处理器空闲等待工作的时间——这通常是值得付出的小代价。通过将浪费的空闲周期转化为少量有用的开销指令，总执行时间可以被显著缩短。并行效率，定义为每个处理器所实现的加速比，最终受限于这种开销与有用工作之比。
其次，任务的粒度——它们的大小——至关重要。为了实现动态均衡，我们经常采用过度分解，将问题分解成比处理器数量多得多的任务。但这些任务的合适大小是多少呢？
存在一个“恰到好处”的任务大小，一个最佳点。这个最佳大小，我们称之为 ，完美地体现了其中的权衡。它平衡了将工作组合在一起的好处（这能提高缓存复用）与工作集对于缓存来说太大所带来的惩罚，以及调度每个任务的固定开销 。我们甚至可以为其推导出一个公式，该公式表明最佳大小取决于硬件参数（如内存带宽 ）和描述数据复用的算法参数之间的微妙相互作用。一个这样的模型给出了 ，其中 和 分别捕捉了数据复用和缓存容量惩罚的影响。这告诉我们，一个程序的最佳并行化方式与其运行的机器并非无关。
最后一层复杂性来自于直面现代大型计算机的现实。在一台拥有多个处理器插槽的服务器上，并非所有内存都是平等的。一个处理器在其自己的插槽上有一个“本地”内存库，访问它速度很快。访问位于不同插槽上的内存则是一种“远程”访问，速度明显更慢。这种架构被称为非统一内存访问（NUMA）。
如果位于插槽0上的一个窃取者天真地窃取了一个其数据位于插槽1内存中的任务，会发生什么？这种“帮助”行为可能变得有害。每次被窃取的任务试图访问其数据时，都会产生高延迟的远程访问惩罚。性能实际上可能变得比窃取者简单地保持空闲更差。
这迫使现代的工作窃取运行时系统必须具备局部性感知能力。它们必须明智地窃取。一个好的调度器会使用一种启发式方法来权衡一次潜在窃取的利弊。它可能会定义一个“窃取局部性度量” ，该度量估算了复用窃取者缓存中已有数据所带来的收益（），并减去一个基于远程数据比例（）以及远程与本地内存延迟差距（）的惩罚。只有当预期收益超过 NUMA 惩罚时，窃取才会被发起。
这导致了分层窃取策略：首先，尝试从同一芯片上的兄弟核心窃取。如果失败，尝试同一插槽上的另一个核心。只有作为最后手段，处理器才应尝试从远程插槽窃取这种昂贵的操作。
因此，工作窃取是一个从简单、优雅的想法演变成一门复杂艺术的原则。它是所有者有序、缓存友好的工作与窃取者有针对性、注入混乱的抓取之间的一支舞蹈。它的力量来自于对算法（揭示任务结构）、计算机架构（决定通信和内存访问的成本）以及运行时系统（实时智能地驾驭这些权衡）的统一理解。
现在我们已经探索了工作窃取优雅的机制——窃取者与受害者凭借双端队列进行的简单舞蹈——我们可以开始一段更激动人心的旅程。我们将走出算法的抽象领域，看看这个强大的思想在现实世界中留下了怎样的足迹。你将会为其触及的广度感到惊讶。工作窃取不仅仅是计算机科学家的一个聪明技巧；它是管理不规则、不可预测工作的一项基本原则，因此，它出现在最意想不到的地方，从寻找难解谜题的答案到模拟宇宙本身。
想象一下，一个巨大厨房里有一群才华横溢但杂乱无章的厨师。每人都拿到一份要准备的食谱清单。有些食谱很简单，比如切蔬菜，而另一些则是复杂的多步骤准备工作。如果每位厨师都严格遵守自己的清单，很快一些人会忙得不可开交，而另一些人则站着无所事事，因为他们简单的任务已经完成了。厨房的产出陷入停滞。显而易见的解决方案，当然是让一位空闲的厨师走到最忙碌的那位面前，从他的清单上拿走一份食谱。这便是最纯粹形式的工作窃取。它是对不均衡问题的一种自然的、去中心化的解决方案，其在计算领域的应用既深刻又多样。
计算机科学和数学中许多最困难的问题都涉及到在巨大的草堆中寻找一根针。这种搜索通常可以被形象化为探索一棵巨大的、分叉的可能性之树。其工作负载是不可预测性的完美风暴：树的某些分支可能是很快被放弃的死胡同，而其他分支可能导致深入而复杂的子问题。
考虑解决一个复杂逻辑谜题的经典挑战，即布尔可满足性问题（SAT）。在一个并行 SAT 求解器中，我们可以将搜索树的不同部分分配给不同的处理器。工作窃取是实现这一点的完美机制，因为完成了其逻辑谜题分支探索的线程可以从其他更繁忙的线程那里窃取未探索的分支。这是一个*任务并行的例子。但在这里我们遇到了一个微妙而美妙的权衡。人们可能倾向于在搜索树的单个节点内部也使用并行，例如，为了加速评估逻辑子句的过程——这是一种数据并行*的形式。然而，这可能是一个陷阱！工作窃取的威力在于它能让所有处理器都忙于处理大型、独立的任务（整个搜索分支）。将处理器专门用于稍微加快一个微小节点上的工作，可能会使系统缺乏能带来最大性能增益的任务级并行性。这是资源分配中一个深刻的教训：工作窃取在有任务森林可供选择时才能蓬勃发展，为了微小的收益而缩小这片森林可能得不偿失。
同样的原则也适用于一大类使用一种称为*分支定界法*的技术解决的优化问题 [@problem-id:3155760]。想象一下，试图为一位需要访问几十个城市的销售员找到最短的路线。该算法探索一个由部分路线组成的树，不断“修剪”那些已经比目前找到的最佳路线更长的分支。有用工作的形态是完全不可预测的，并且取决于数据。静态的劳动分工注定要失败。然而，工作窃取将这种混乱转化为易于处理、均衡的计算，允许处理器动态地分担探索最有希望的路线的负担。这种组合是如此强大，以至于我们可以为这类系统的性能建立非常精确的预测模型，考虑到从一个分支被修剪的概率到窃取操作本身的开销等所有因素。
让我们从抽象的树转向更具视觉效果的东西：一束光。在科学和娱乐领域，许多计算问题从根本上说都是关于追踪光线穿过介质的路径。
在现代计算机图形学中，通过模拟数百万条光线在场景中反弹的路径来生成逼真的图像——这种技术称为光线追踪。单条光线的计算成本变化极大。一条立即击中简单、黑暗表面的光线计算成本很低。而一条在多个镜子之间反弹、穿过玻璃折射并投下复杂阴影的光线则有一段漫长而昂贵的旅程。在一块大规模并行的图形处理单元（GPU）上，你如何平衡这种工作负载？答案仍然是工作窃取。我们可以将GPU上众多处理核心中的每一个的工作负载想象成一个光线队列。借鉴物理学的概念，我们可以将工作窃取建模为一个扩散过程。工作，就像一种流体，自然地从高浓度区域（长队列）“扩散”到低浓度区域（短队列或空队列），从而确保所有核心都保持高效。
同样的问题，以不同的面貌，出现在科学的前沿。一位研究恒星形成的天体物理学家可能会模拟辐射穿过一片巨大、湍动的气体和尘埃云的过程。就像在计算机图形学中一样，他们追踪光线，但“工作量”取决于气体的物理特性——它的不透明度。一条穿过密集、不透明团块的光线需要许多细小、谨慎的步骤来计算其路径，而一条穿过空洞的光线则毫不费力地行进。由此产生的负载不均，源于被模拟对象的物理结构，再次被工作窃取巧妙地处理。这同样适用于宇宙学的*N体模拟*，这些模拟追踪数百万颗恒星和星系的引力之舞。在这些代码的现代自适应版本中，任何给定时间可能只有一部分粒子是“活跃的”，从而产生了一个动态且不规则的工作负载，这非常适合工作窃取调度器。
一个真正基础性思想的力量，往往不仅体现在它在哪里起作用，还体现在它与其他原则之间微妙的相互作用中。工作窃取也不例外。它优美的简洁性有时会导致令人惊讶和反直觉的后果。
也许这方面最引人注目的例子在于排序这项平凡的任务。并行归并排序是一种标准的分治算法。我们可以使用工作窃取来管理递归的子问题。但一个看似无害的选择——排序是否需要“稳定”——可能对并行性造成灾难性后果。稳定排序保证了键值相等的元素保持其原始的相对顺序。为了在并行归并中实现这一点，算法必须小心地划分工作。在最坏情况的输入下，例如一个所有键都相同的数组，一种流行的稳定归并策略会完全退化。递归变得不平衡，形成一个单一、长链的依赖操作——一条几乎完全串行的关键路径。在这种情况下，我们所期望的丰富并行性消失了，工作窃取也无能为力。根本没有工作可以窃取！这是一个绝佳的例证，说明了并行调度器的优劣取决于底层算法所暴露的并行性。
此外，我们必须记住，窃取不是免费的。它涉及通信和同步，这些构成了开销。这就引出了一个关键的工程问题：我们的任务应该多大？。如果我们将工作切分得过于细粒度，那么出队、窃取和管理它们的开销可能会超过实际的有用计算。如果我们的任务过于粗粒度，我们可能没有足够的任务来有效地平衡负载，从而导致处理器空闲。应用工作窃取的艺术通常在于找到这个“最佳点”，即一种任务粒度，它既能平衡众多小任务所带来的并行性好处，又能兼顾少数大任务的效率。
在高性能计算的世界里，我们很少只有一层并行性。一台现代超级计算机是一个由相互作用的部件组成的复杂交响乐团：它是一个由许多计算机（节点）组成的分布式系统，每个节点本身又是一个拥有许多处理器核心的共享内存系统。要在这样的机器上指挥一场大规模模拟，我们需要多个层面的协调。
想象一下，在一个使用消息传递接口（MPI）划分到数千个计算机节点上的网格上解决一个复杂的物理问题，比如流体流动。在每个节点内部，我们使用线程和工作窃取来计算该节点部分的网格。但这里存在一个依赖关系：分区边缘的单元（“光环”区域）需要来自邻近节点的数据，这些数据必须通过网络到达。这种通信是异步的。如果一个线程想要计算的边界任务正在等待来自邻居的数据，它应该做什么？它应该窃取一个没有这种依赖关系的内部任务！。工作窃取是实现这种至关重要的*通信与计算重叠*的引擎。最复杂的系统更进一步，使用一种细粒度的数据流模型，其中任务只有在它们所需的特定数据到达时才变得“有资格”被窃取。
最后，我们必须考虑到并非所有工作都是平等的。在许多系统中，任务有优先级——有些任务比其他任务更紧急。一个天真的、只关心负载的工作窃取调度器可能会无意中导致*优先级反转*：一个低优先级任务在一个核心上运行，而一个高优先级任务却空闲地困在一个工作线程的队列中，该线程未被操作系统调度运行。解决方案是让系统更智能，例如，允许一个工作线程暂时“继承”它所拥有的任务的高优先级。这确保了操作系统调度器的选择与应用程序的目标保持一致。这是最后一个关键的教训：工作窃取是实现高性能的极其强大的工具，但要构建真正健壮和正确的系统，必须将其智能地编织到包括正确性、同步和公平性在内的更大关注范围中。
从一个简单的想法——一个空闲的工人从一个忙碌的工人那里拿走工作——我们看到了一个具有深远统一力量的原则的展开。它驯服了递归算法的混乱，平衡了模拟光和引力的工作负载，并在世界上最快的机器中指挥着计算与通信的复杂舞蹈。工作窃取是面对巨大复杂性时，简单、可扩展思想之美与效用的证明。