BWoS：基于块的工作窃取¶

标题：BWoS: Formally Verified Block-based Work Stealing for Parallel Processing

日期：2023/07/10

作者：Jiawei Wang, Huawei Dresden Research Center, Huawei Central Software Institute, Technische Universität Dresden; Bohdan Trach, Ming Fu, Diogo Behrens, Jonathan Schwender, Yutao Liu, and Jitang Lei, Huawei Dresden Research Center, Huawei Central Software Institute; Viktor Vafeiadis, MPI-SWS; Hermann Härtig, Technische Universität Dresden; Haibo Chen, Huawei Central Software Institute, Shanghai Jiao Tong University

链接：https://www.usenix.org/conference/osdi23/presentation/wang-jiawei

注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。

备注：英伟达采用的实现，分区和随机化都是经典设计，但是这里会更加细化。

摘要¶

工作窃取是一种广泛用于多核并行处理的调度技术。每个核心拥有一个任务队列，并通过从其他队列窃取任务来避免空闲。先前的工作主要关注于在核心之间平衡工作负载，而忽略了窃取行为是否可能对所有者的性能产生负面影响或阻碍同步优化。现实世界中用于并行处理的工业级运行时在很大程度上依赖于工作窃取队列来实现可扩展性，而这类队列可能成为其性能瓶颈。

我们提出了基于块的工作窃取（BWoS），这是一种新颖且实用的设计，它将每个核心的队列分割成多个块。窃取者（thieves）和所有者（owners）很少在同一个块上操作，从而极大地消除了干扰，并使得所有者与窃取者之间的同步可以进行激进的优化。此外，BWoS启用了一种新颖的概率性窃取策略，保证窃取者以更高的概率从更长的队列中窃取任务。在我们的评估中，当应用于Java G1GC时，使用BWoS在Renaissance宏基准测试中性能提升高达1.25倍；当应用于Go运行时，在JSON处理方面平均提速1.26倍；当应用于Rust Tokio运行时，Hyper HTTP服务器的最大吞吐量提高了1.12倍。在微基准测试中，它比现有SOTA（state-of-the-art）设计的性能高出8-11倍。我们已经使用一个基于模型检查的框架，在弱内存模型上对BWoS进行了形式化验证和优化。

1 引言¶

许多语言运行时和类似系统（例如，JVM、Go、Rust的Tokio）将其工作划分为称为任务的更小单元，这些任务在多个核心上异步执行，并且其执行可以产生更多的任务。为了实现高性能，任务调度器必须确保良好的工作负载分布（防止在有待处理任务时核心空闲）并保持较低的调度开销。

然而，实现这些目标并非易事。将任务存储在所有核心共享的单个队列中可以实现最优的工作负载分布，但会因竞争而产生巨大开销。使用每核心的任务队列可以最小化每次操作的开销，但很容易导致工作负载分布不均，一些核心保持空闲，而其他核心则有排队的任务。

工作窃取是这两种极端情况之间的一种权衡：每个核心拥有一个队列（所有者），并同时作为其自身队列的生产者和消费者来放置和获取任务。当一个核心完成了它的任务并且队列为空时，它会从另一个处理核心的队列中窃取另一个任务以避免空闲（窃取者）。已经提出了多种窃取策略来选择合适的队列（受害者）进行窃取，这可以根据使用场景带来显著的速度提升。由于这些特性，工作窃取被广泛应用于并行计算、并行垃圾回收、GPU环境、编程语言运行时、网络和实时系统。

然而，随着并行处理被应用于更多的工作负载，当前的工作窃取实现成为了一个瓶颈，特别是对于小任务。例如，Web框架运行在轻量级线程抽象之上，如Rust的Tokio和Go的协程，通常包含许多非常小的任务，导致Tokio运行时的作者观察到“在队列上的竞争开销变得显著”，甚至影响了端到端的性能。类似地，高性能的垃圾回收器，如Java G1GC，依赖于工作窃取来并行化大量的标记/清除操作，这些操作仅包含少量指令。工作窃取的开销成为了GC的性能瓶颈。

作为第三个例子，在图1中，我们分析了GoJson对象解码基准测试的性能，该测试使用协程进行GC工作和解析复杂对象。所有CPU周期中只有51%构成了有效的工作负载（JSON解码）。其余的周期花费在运行时代码上，包括7%用于轻量级线程调度，20%用于GC，5%用于内核代码使CPU空闲等。由于调度器和GC代码都依赖于工作窃取，提高其性能可以带来巨大的效率提升。此外，这种好处不仅限于上述场景，还扩展到所有细粒度任务的并行处理场景。因此，我们提出以下问题：我们如何能为细粒度任务提高工作窃取队列的性能，从而使大量常见应用受益？

现有的工作窃取队列存在四个主要的低效来源：

P1：同步开销。 由于存在窃取的可能性，本地队列必须使用比纯粹顺序队列更强的原子原语（例如，原子比较并交换和内存屏障）。采用FIFO策略的队列通常实现为单生产者多消费者（SPMC）队列，从而将窃取与获取操作类似地处理，并将窃取成本平均分配给所有者和窃取者。这也适用于现有的基于块的队列，这些队列缺乏针对工作窃取用例的任何特定优化以在有窃取者存在时实现高性能（§6.2, §7）。采用LIFO策略的队列，例如广为人知且广泛使用的ABP队列，会遭受内存屏障开销的影响，以避免所有者和窃取者之间的冲突，即使它们在操作不同的任务时也是如此。

P2：窃取者引起的缓存未命中。 由于窃取操作会更新所有者和窃取者之间共享的元数据，它们会导致其所有者后续访问队列时出现缓存未命中。这个问题在具有高窃取率的不平衡工作负载中尤为明显——例如，在JVM Renaissance基准测试中，平均有10%的项被窃取。尽管批处理等策略（例如，窃取一半）可以减少窃取的频率，但它们通常会导致过度窃取，从而引入额外的开销（§2.1.3）。

P3：受害者选择。 为了改善工作负载分布，选择窃取受害者队列的高级策略需要扫描多个队列的元数据，例如，找到最长的队列。然而，这样做会对其所有者造成竞争，并严重限制了高级受害者选择策略带来的改进（§2.1.3）。

P4：在弱内存模型（WMMs）下的正确性。 在弱内存架构上正确实现并发工作窃取队列，例如用于数据中心的Arm服务器，是非常具有挑战性的，因为它需要额外的内存屏障来防止不希望的重排序。使用冗余的屏障会极大地降低工作窃取的性能，而不包含足够的屏障则可能导致错误，例如在C11 版本的流行的无界Chase-Lev双端队列中，该版本是从经过形式化验证的ARMv7汇编翻译过来的。即使是流行的Rust Tokio运行时也需要对其工作窃取实现进行修复。

贡献。 作为回应，我们引入了BWoS，一个基于块的工作窃取（BWoS）有界队列设计，它为这些问题提供了一个实用的解决方案，极大地减少了工作窃取的调度开销。我们的解决方案基于以下见解。

首先，我们将每个核心的队列分割成多个具有独立元数据的块，并安排所有者和窃取者在块级别进行同步。因此，在操作保持在块内的常见情况下，我们可以省略同步操作，实现近乎单线程的性能（§3.2）。同样，由于队列所有者和窃取者只共享块级局部元数据，它们在操作不同块时不会相互干扰（§2.1）。我们可以通过允许从队列中间窃取任务来安排这种情况频繁发生。

其次，我们通过一种概率性策略改进了受害者选择，该策略近似于选择最长的队列（§3.4），同时避免了先前SOTA技术中典型的严重干扰（§2.1），我们还可以在其中集成NUMA感知和批处理。

最后，我们通过使用GenMC模型检查器验证BWoS并在VSync工具链的帮助下优化其屏障选择，来确保在WMMs下的正确性（§5）。

因此，BWoS在SOTA技术上提供了巨大的性能改进（§6）。在微基准测试中，BWoS的吞吐量比其他算法高出8-11倍。在代表性的真实世界宏基准测试中，当应用于Java G1GC时，BWoS将Java工业应用的性能提高了高达25%；当应用于Tokio运行时，Rust Hyper HTTP服务器的吞吐量增加了12.3%，延迟降低了6.74%，CPU利用率降低了60.9%；当应用于Go运行时，它在9个不同库上的JSON处理速度平均提高了25.8%。

回到我们的激励性例子（图1），将BWoS应用于Go运行时，减少了29%的调度时间、55%的GC时间和40%的CPU空闲时间，同时将用于有效工作的CPU时间比率从51%增加到71%。

[图1：go-json复杂对象解码（~1µs/op）基准测试的性能分析结果，分别使用原始工作窃取队列（上）和BWoS（下）。（图片已忽略）]

2 背景¶

任务处理。 不同基准测试中的任务差异很大。它们的处理时间范围从几纳秒（例如，Java G1GC），到几微秒（例如，RPC），甚至到几秒（例如，HPC任务）。在本文中，我们主要关注纳秒和微秒级别的任务。忽略窃取操作，任务可以按以下方式处理：

FIFO（先进先出）顺序，当最小化处理延迟很重要时（例如，网络连接）。
LIFO（后进先出）顺序，当只关心整体执行时间时，这在多线程的分叉-连接程序中很常见。我们使用术语队列来指代工作窃取数据结构的实例，而不暗示特定的任务排序。

受害者选择。 有多种策略用于选择要窃取的受害者队列。随机策略从剩余队列中均匀随机地选择一个：它的复杂性最低，但负载均衡效果较差。基于大小的策略（例如，二选一最优和多选一最优）通过扫描队列的大小来从一个大队列中窃取，以改善负载均衡。NUMA感知策略 被提出来优化远程通信成本，它倾向于从本地缓存域中的队列窃取。基于批处理的策略（例如，窃取一半，在Go和Rust的Tokio运行时中使用）允许窃取者一次窃取多个任务，以减少他们对所有者的干扰。在本节的后面部分（§2.1.3），我们将量化这些开销来源，以指导我们的队列设计。

2.1 性能开销分解¶

接下来，我们分析了SOTA的工作窃取算法，以剖析其性能问题，并为BWoS的设计决策提供动机。图2包含了我们在x86服务器上的实验结果。

[图2：激励性基准测试：（a）SOTA工作窃取算法的顺序性能。（b,c）ABP队列所有者性能，取决于（b）窃取和（c）getsize操作的频率。（d）Hyper HTTP服务器在使用原始Tokio工作窃取队列时，不同窃取批次大小的性能：S是受害者队列大小，S/2是指默认的窃取一半策略。（e,f）在两种缓存行集大小下，两个线程之间的干扰。（图片已忽略）]

2.1.1 同步操作的成本¶

由于窃取可能在任何时候发生，本地队列操作引入了强原子原语。为了量化其成本，我们首先在一个顺序设置中测量了SOTA工作窃取算法的吞吐量，其中一个所有者从其本地队列中放入和获取数据，而没有任何任务被窃取（§6.2）。我们将结果与理论性能上限进行比较：一个不支持窃取的单线程FIFO（FIFO_seq）或LIFO（LIFO_seq）队列实现。尽管没有所有者-窃取者干扰，这些同步操作也带来了巨大的开销（图2a）：这些工作窃取算法的吞愈量，与上限相比，基于FIFO的不到0.25倍（基于LIFO的为0.19倍）。

[表1：通过NUMA感知策略降低窃取开销。（表格已忽略，但其数据显示NUMA感知策略可以将窃取开销从跨节点通信的141ns降低到同节点通信的15ns，但受害者干扰开销仍然存在，分别为278ns和170ns。理想情况下，干扰应为零，开销降低可达90%，而当前只能达到56%）]

2.1.2 与窃取者的干扰成本¶

为了估算窃取者如何影响所有者的吞吐量，我们考虑一个ABP队列基准测试，其中有一个所有者和一个以不同频率从队列中窃取任务的窃取者（总共一个队列和两个线程）。作为“理想”基线，我们采用ABP队列的单线程性能（即没有窃取）。为了考虑任何NUMA效应，我们使用了两种配置，让窃取者在相同或不同的NUMA节点上运行。如图2b所示，窃取者显著降低了所有者的吞吐量：例如，仅窃取1%的任务，当窃取者在同一NUMA节点时，所有者的吞吐量下降了17.8%，而在不同NUMA节点时下降了25.2%。这种性能下降是由于所有者和窃取者在共享元数据上的缓存干扰造成的。我们将在§2.2中进一步解释这一点。

2.1.3 受害者选择带来的开销¶

窃取开销主要有两个来源：首先，次优的受害者选择可能导致工作负载不平衡，从而引发更多窃取；其次是窃取操作本身的成本。

**基于大小的策略。**像二选一最优或多选一最优这样的策略会读取多个队列的全局元数据（它们的长度）来确定受害者。有点令人惊讶的是，如图2c所示，这些读取操作给所有者带来了显著的开销，尤其是在跨NUMA场景中：即使getsize频率仅为1%，所有者的吞吐量也会下降34.4%。由于getsize对于单次窃取会被多次调用，这种情况会进一步加剧。因此，对于基于大小的策略，尽管读取更多队列的大小（例如，多选一最优）可以实现更好的负载均衡，但这不可避免地会给这些队列的所有者带来更大的减速（§6）。

NUMA感知策略。 NUMA感知策略试图通过优先从同一NUMA节点中的队列窃取来减少每次窃取的开销。我们观察到，尽管这类NUMA感知策略可以在我们的ABP队列基准测试中将窃取开销降低56%，但它们未能发挥其全部潜力。在表1中，我们将ABP队列中的窃取开销分解为两个主要部分：窃取者的通信成本和所有者的干扰惩罚。前者在窃取者和所有者运行在不同NUMA节点时为141ns（由Intel MCA测量），当它们在同一NUMA节点时减少到15ns（与L3缓存访问延迟一致）。受害者的干扰惩罚在窃取者和受害者运行在相同(Is)和不同(Id)NUMA域时分别为170ns和278ns。现有队列的NUMA感知策略通常可以消除第一个通信开销，但第二个干扰开销没有得到充分优化。如果队列足够长，窃取理想上可以发生在队列的不同部分，不会对受害者造成干扰。这将使Is和Id减少到零，从而因NUMA感知带来90%的改进（而不是56%）。

基于批处理的策略。 基于批处理的策略一次窃取更多任务，旨在减少窃取的频率。确实，在Hyper HTTP服务器基准测试中（见图2d），选择更大的批处理大小可以减少窃取操作的数量。然而，这些更大的窃取操作使得工作负载更加不平衡（即被盗任务的百分比增加），这导致了额外的开销（例如，任务乒乓），抵消了因窃取次数减少而带来的开销降低：端到端的吞吐量大致保持不变。

2.2 回顾以引出BWoS¶

总之，所有者的性能受到同步成本和与窃取者干扰（由于受害者选择和任务窃取）的双重影响。这种干扰的发生是由于队列元数据上的缓存竞争：与窃取操作的写-写干扰，以及与基于大小的窃取策略中getsize操作的读-写干扰。

为了更好地理解这些类型的缓存竞争的影响，我们进行了一个简单的微基准测试，有两个线程：线程t₀连续写入一个缓存行，而线程t₁以指定的频率读取或写入一个缓存行（图2e和2f）。t₀和t₁的缓存行在每次迭代中从大小为1或64的缓存行集合中独立随机选择。

在这两种情况下，单个缓存行上的缓存竞争显著损害了t₀的吞吐量，无论NUMA域的邻近性如何。引入多个缓存行（本例中为64个）可以减少竞争并显著提高吞吐量。因此，在BWoS的设计中，我们分离了元数据。

3 设计¶

BWoS基于一个概念上简单的思想：队列的存储被分割成多个块，而窃取者和所有者之间共享的全局可变元数据被替换为每个块的实例。

BWoS队列的结构有助于将操作抽象为跨块工作的块推进（block advancement），以及在块推进选择的块内部操作的快速路径（fast path）（§3.1）。将大部分同步从快速路径移到块推进，使得BWoS能够充分利用我们之前观察（§2.1.1）所显示的性能优势，从而接近理论上限。get和steal总是在不同的块上发生。我们精心构造了算法，使得窃取者不会阻碍get的进度，而get可以安全地接管窃取者正在操作的块而无需等待。考虑到复杂性，我们不禁止put和steal在同一个块中¹，因为它们可以通过弱屏障进行同步而不会损失性能（§6.2）。

由于元数据也按块分割，窃取者和所有者很可能在不同的块上操作，从而更新不同的元数据。如§2.2所解释，这减少了窃取者和所有者之间的干扰。对于基于FIFO的BWoS，块级局部元数据允许从队列中间窃取，而无需强制执行SPMC队列总是窃取最旧任务的限制，这在工作负载中并非必需。

BWoS比其他队列更能从NUMA感知策略中受益，因为对受害者干扰的减少使得跨NUMA域窃取开销的两个组成部分都变得可以忽略不计（表1）。此外，与基于批处理的策略不同，与BWoS集成的窃取策略可以专注于平衡工作负载本身，而无需担心频繁调用steal所带来的干扰。

¹ 尽管如此，在LIFO BWoS中这是自动保证的。

[图3：put、get和steal操作的伪代码。（图片已忽略）]

3.1 队列的鸟瞰图¶

为了更好地理解基于块的方法，让我们考虑BWoS队列的put、get和steal操作（图3）。对于这些操作中的每一个，第一步是选择一个要操作的块（第3、14和27行）。对于LIFO BWoS，所有者使用顶部块进行put和get；对于FIFO BWoS，所有者从前部块获取，并放入后部块。在这种情况下，顶部、后部和前部块指针是所有者专属的元数据，对窃取者不可用。对于steal，块的选择更为复杂，我们将在后面的章节中解释（§3.4）。

选择块后，操作执行快速路径（第4、15和28行），这可能返回三种结果之一：（1）快速路径成功，对于get和steal返回数值。（2）快速路径失败，因为没有数据可供消费（第18和31行），或者因为窃取者检测到与其他窃取者或由于接管而与所有者的冲突（第33行）。在冲突的情况下，快速路径会重试（第34行），否则返回null值。（3）当前块的边界（开始或结束）已达到（第7、20和35行）。在这种情况下，操作尝试通过执行块推进移动到下一个块，如果成功则重试，否则返回空或满的队列状态。

将全局元数据分割成块级实例，使得操作可以分为快速路径和块推进，通过保持快速路径极其轻量级来提高性能。然而，缺乏所有者和窃取者之间共享的全局可变元数据带来了额外的挑战，这些挑战主要委托给块推进——它现在负责维护复杂的块级不变量。我们引入以下不变量：（1）put永远不会覆盖未消费的数据；（2）steal和get永远不会读取相同的数据；（3）steal和get永远不会读取已经被读取过的数据；（4）进行中的steal不能阻止get从窃取者的块中读取。在解释快速路径和块推进实现之前，我们引入两个我们依赖的关键概念来确保上述不变量的成立：块级同步（§3.2）和轮次控制（§3.3）。

[图4：BWoS中的块级同步。(a) LIFO BWoS (b) FIFO BWoS。（图片已忽略）]

[图5：每个块中轮次号的更新。（图片已忽略）]

3.2 块级同步¶

块级同步是块推进的关键职责，并确保窃取者永远不会从get操作当前使用的块中窃取。每个块要么由所有者拥有，要么由窃取者们拥有。例如，在图4中，颜色较浅和较深的块分别属于所有者和窃取者。所有者通过块推进将一个块授予窃取者，或从他们那里收回一个块。更具体地说，对于LIFO BWoS，get推进到前一个块（3到2）并从窃取者手中接管它；put授予当前块并推进到下一个块（3到4）。对于FIFO BWoS，get（相应地put）推进并接管（相应地授予）下一个块。

授予和接管过程基于窃取者索引（thief index）——块元数据中的一个条目，指示块内的窃取位置。接管通过原子交换将此索引设置为块边界，并使用旧值作为该块中所有者和正在进行的窃取者之间的阈值。这确保了所有者在接管块时不会被窃取者阻塞。此外，并发的所有者和窃取者永远不会读取相同的数据，因为它们之间的阈值是原子设置的。类似地，授予过程通过向窃取者索引写入阈值来将块转移给窃取者。我们将在§4.2.1中介绍细节。

3.3 轮次控制¶

每个块还记录了最后一次数据访问的轮次号。当推进块时，当前块的轮次号被复制到下一个块；除非是在环绕（wrap-around）的情况下，块号会增加1（图5）。

实际上，每个块中都有生产者、消费者和窃取者的轮次号。当生产者尝试将轮次r’的数据写入一个块时，消费者和窃取者必须已经完成了从该块读取所有轮次r-1的数据；这样生产者就永远不会覆盖任何未读的数据。类似地，当消费者或窃取者尝试从一个块读取轮次r的数据时，该块的生产者轮次必须已经是r；这可以防止任何数据被读取两次，或者读取从未被写入的数据。细节可以在§4.2.2中找到。

3.4 概率性窃取¶

如§2.1.3中所讨论的，基于大小的策略可以实现更好的负载均衡，但代价是降低每个队列所有者的性能。在我们的设置中计算大小更加困难，因为相应的元数据分布在所有块中。然而，BWoS带来了一个机会，可以采用一种新的基于大小的概率性窃取策略，它可以在不负面影响所有者性能的情况下提供强大的负载均衡。

我们通过使选择一个队列作为受害者的概率与其大小成正比来确保强大的负载均衡。我们用一个两阶段算法实现这个方法：Pselect阶段首先随机选择一个潜在的受害者，然后Paccept阶段以概率S/C决定是否从它那里窃取，其中S是所选队列的大小，C是其容量；否则（以概率1 – S/C）它返回到Pselect进行新一轮迭代。因此，给定一个包含N个容量相同队列的池，并且Pselect中的选择器以等概率选择每个队列，Paccept可以保证窃取者从一个队列窃取的概率与其大小成正比。

为了最小化对所有者性能的影响，我们不测量S，而是通过采样直接估计S/C。窃取者从队列的所有块中随机选择一个块，并检查其中是否有可供窃取的数据，返回true的概率接近S/C。由于窃取者只读取一个块的元数据，它对所有者的干扰是最小的（参见§2.2）。

对于FIFO BWoS，上述方法可以实现零开销的窃取：在估计返回true后，我们可以直接从用于估计的块中窃取，因为块级局部元数据使窃取者能够从任何已授予窃取者的块中窃取。我们将这种将我们的概率性窃取策略应用于FIFO BWoS的实例称为随机化窃取过程。

对于LIFO BWoS，窃取仍然从底部块发生（图4）。窃取者在完成当前块后会推进到下一个块。对于FIFO BWoS，当随机化窃取启用时，窃取者不推进块，而是回退到窃取策略以选择新的队列和块（§3.4）。在这种情况下，在窃取时推进到下一个块的操作（图3第36行）变成了一个空操作。

[图6：块内部的put、get和steal操作。（图片已忽略）]

此外，我们可以进一步将概率性窃取策略与Pselect阶段的各种选择器（例如，来自NUMA感知策略）相结合，以从更好的工作负载均衡和降低的窃取成本中双重受益。结果表明，混合的概率性NUMA感知策略为BWoS带来了最佳性能（§6）。

4 实现¶

4.1 单块操作（快速路径）¶

让我们考虑块内部的put、get和steal操作是如何实现的（图3中的第4、15和28行）。因为get和steal总是在不同的块上发生，我们只需要考虑一个块中多种操作的两种情况：生产者-消费者和生产者-窃取者（图6）。

为了支持这些情况，每个块有4个元数据变量：块中准备好供消费者使用的条目位于前部位置（f_pos）和后部位置（b_pos）之间，而窃取者使用窃取位置（s_pos）和块中已完成窃取的计数器（s_cnt）来在它们之间以及与生产者之间进行协调。

要生产一个值，put首先检查是否达到了块边界NE（条目数），如果没有，就将数据写入生产者位置（b_pos），并让它指向下一个条目。

要消费一个值，有两个get操作，getf和getb，分别对应FIFO和LIFO BWoS。get检查是否已达到块边界，或者块是否已用尽数据（f_pos已达到b_pos），如果没有，它就读取数据并更新块元数据中的消费者位置变量。get的两个变体在它们使用的位置变量和边界上有所不同。getf使用f_pos作为消费者位置变量，NE作为块边界，b_pos作为有效数据的边界。getb出于相同目的分别使用b_pos、块的零位置和f_pos。

窃取者遵循类似的模式：steal首先检查是否已达到块边界，或者块是否已用尽数据（s_pos已达到b_pos）。然后，它使用原子比较并交换（CAS）更新s_pos以指向下一个条目，读取数据，最后通过原子增量更新s_cnt。如果CAS失败，steal返回冲突。（使用CAS是因为多个窃取者可以在同一个块中操作。）

所有这些操作在达到块边界时返回block_done。否则，如果块用尽数据，get和steal返回empty。

[图7：块推进中的接管和授予过程。（图片已忽略）]

4.2 块推进¶

当达到块边界时，put、get和steal移动到下一个块：它们首先检查是否允许通过轮次控制进行推进，如果允许，它们调用接管（由get）或授予（由put）过程，并重置块级元数据。

4.2.1 接管和授予过程¶

我们使用一个有4个条目块的队列作为例子来解释接管和授予过程（图7）。

LIFO。假设6个元素（a-f）被放入队列。因此，所有者在块b₁中；b₀和b₁中的b_pos分别变为4和2，而f_pos和s_pos保持在初始值（0）（状态①）。然后，两个动作并发发生：两个窃取者尝试窃取条目，将b₀中的s_pos更新为2，并开始复制数据（图7中的steal），而所有者获取3个值，消费f, e（状态②），并推进到b₀，从而开始接管。为了执行接管，所有者原子地将s_pos与块边界（4）交换，然后将f_pos设置为先前的s_pos值（2）（状态③）。接管后，所有者获取d并放入g。同时，一个正在进行的窃取完成（图7中的steal’），使s_cnt增加1（状态④）。这两个哪个先完成无关紧要。当所有者放入新项h和i时，它将b₀授予窃取者并推进到b₁。为了执行授予，它将s_pos设置为f_pos的值（2），向窃取者表明该块可用（状态⑤）。在窃取者窃取了b₀中的所有条目后，s_cnt达到了块边界（状态⑥）。因此，b₀可以在下一轮中被重用。

FIFO。首先，生产者将7个元素（a-g）放入队列。生产者和消费者分别在b₁和b₀中，窃取者可以从b₁窃取（状态①）。然后，消费者获取b₀中的所有元素，并推进到b₁（状态②）。这需要从窃取者手中接管b₁：为此，它以与LIFO BWoS相同的方式更新s_pos和f_pos，但同时将新的f_pos（2）与块边界（即块的长度）之间的差值加到s_cnt上（状态③）。这样，当所有窃取者完成在b₁中的操作时，其s_cnt将等于块边界。之后，生产者放入一个新项h，并推进到b₂，将其授予窃取者（状态④）。

最后，窃取者和消费者都已读取了b₁中的所有条目，其f_pos和s_cnt等于块边界（状态⑤）。生产者使用这个条件来检查该块是否可以被重用以生产新值。

4.2.2 轮次控制和重置过程¶

为了实现轮次控制（§3.3），块元数据中的位置变量（f_pos, b_pos, s_pos, s_cnt）既包含§4.2.1中描述的索引或计数器（idx字段），也包含轮次号（rnd字段）。我们将这两个组件装入一个可以原子更新的64位变量中。

[图8：FIFO BWoS中的轮次控制。（图片已忽略）]

以FIFO BWoS的put操作为例（图8）。在put中，当生产者的idx达到块blk的块边界NE时（步骤①），下一个块nblk的新轮次x按§3.3所述计算（步骤②）。当以生产者轮次x推进到块nblk时，生产者通过检查消费者和窃取者的idx字段是否等于NE且其rnd字段为x-1，来确认它们已经完成了从nblk中前一轮次数据的读取（步骤③）。当检查成功时，带有索引0和轮次x的新值将被写入生产者位置变量（步骤④），从而为下一轮生产重置该块。否则，报告“队列满”条件。

FIFO BWoS的get操作类似。为了决定get是否可以使用下一个块，它检查该块的下一个消费者轮次是否等于生产者轮次（步骤③），如果检查成功，则重置轮次和索引字段。

每个操作只重置位置变量（b_pos, f_pos, s_pos, s_cnt）的一个子集。我们仔细选择每个操作重置哪些变量，以便所有者的接管和授予过程与窃取者完成的重置没有写冲突。

5 验证和优化¶

BWoS算法的复杂性使得必须使用形式化验证技术来确保没有潜在的设计或实现错误，并优化其在WMMs上的使用。人们可以轻易想象出块推进中的一些棘手情况。例如，对于LIFO BWoS，当所有者调用put和get并推进到下一个块时，它很容易在轮次控制和接管过程中触发ABA 错误。

与像ABP这样更简单的算法不同，通过审查来证明最佳内存屏障放置的正确性几乎是不可能的。幸运的是，模型检查工具被广泛用于检查并发算法的正确性并自动优化WMMs下的内存屏障，从而提高了性能和开发者信心。例如，Tokio库使用了模型检查器Loom，它帮助他们找到了超过10个错误。

5.1 验证客户端¶

模型检查器以一个小的验证客户端程序作为输入，该程序调用队列操作。它验证输入程序的所有可能执行是否满足一些通用的正确性属性，如内存安全和终止性，以及任何作为断言包含在验证客户端中的算法特定属性。每当验证失败时，模型检查器会返回一个具体的错误执行作为反例。

为了能够将验证结果泛化到所验证的特定客户端程序之外，客户端程序必须触发所有可能的竞争场景并覆盖所有期望的属性。由于BWoS的对称性（每个所有者操作自己的队列并从其他队列窃取），验证一个由一个线程拥有并由几个窃取者线程竞争的队列的使用就足够了。

已验证的属性。 我们使用GenMC模型检查器验证了以下属性：

内存安全：程序不访问未初始化、未分配或已释放的内存。
无数据竞争：在标记为非原子的变量上没有数据竞争。
一致性：由生产者写入的每个元素仅由消费者或窃取者读取一次。没有数据损坏或丢失发生。
循环终止：程序中的每个无界自旋循环和有界失败-重试循环最终都会终止，即使在弱内存模型下也是如此。

[图9：验证和优化客户端代码。（图片已忽略）]

[表2：验证和优化的统计数据。（表格已忽略，但其数据显示了LIFO BWoS、FIFO BWoS和ABP在验证/优化时间、内存屏障数量和探索的执行次数方面的统计。例如，LIFO BWoS用时62分钟，有0个SEQ、2个ACQ、2个REL、14个RLX屏障，探索了1.39M次执行。）]

所有可能的执行，包括那些由于在IMM和RC11内存模型下弱内存重排序而发生的执行，都已被探索，并且上述属性对它们中的每一个都成立。使用GenMC，我们能够验证安全属性和循环的终止性，但不能验证单个操作的属性。

竞争场景。 与任何模型检查验证一样，我们的模型在有限的大小内保持上述属性。用于验证和优化BWoS的put、get、steal操作的客户端代码如图9所示。我们将队列配置为有两个块，每个块的容量为两个条目（第23行）。因此，放入5个条目足以触发队列环绕。然后我们启动3个并行运行的线程：所有者线程T0有3轮put和get（第24-26行），每次的条目数不同，试图在每轮中为生产者和消费者触发块推进。窃取者线程T1和T2分别窃取一个和两个条目，因此与T0一起，它们触发了队列空条件、接管、授予和重置过程，以及窃取者之间的冲突。

断言和属性。 在线程T0-T2退出后，线程T3获取所有剩余的条-目，并断言放入元素的总和等于通过get和steal读取的元素的总和（第30-31行）。请注意，元素是作为2的幂生成的（第6行），因此这个断言确保了由生产者写入的每个元素只被读取一次。

5.2 结果¶

我们使用VSync框架和GenMC模型优化并验证了LIFO和FIFO BWoS的C代码。我们还使用我们的验证客户端作为基线验证了ABP队列。统计数据显示在表2中，按内存屏障类型细分：顺序一致（SEQ）、获取（ACQ）、释放（REL）和松散（RLX，即普通内存访问）。

对于BWoS，屏障优化和验证在大约一小时内在一个6核工作站上完成，探索了超过100万次执行。对于ABP，检查在16分钟内完成。为ABP探索了更多的执行，因为窃取者和所有者为每个操作进行同步，这带来了更多的交错情况。

验证信心。 通过增加一个线程并发现不需要进一步的屏障，我们得出结论，进一步增加线程数不太可能发现一些缺失的屏障。因此，我们可以避免随着线程数增加而发生的状态空间爆炸。另一方面，发现现有屏障需要更强，将迫使我们重新审视整个算法。

经验。 模型检查在BWoS的开发过程中证明了其宝贵价值。例如，LIFO BWoS的早期版本有一个错误，即窃取者在推进到其下一个块（blk）时会重置s_pos变量。在所有者推进到其前一个块（也恰好是blk）的情况下，它会在接管过程中更新s_pos，这与窃取者的重置过程冲突，导致数据丢失。这个数据丢失被GenMC通过验证客户端断言（第30-31行）检测到。我们通过将窃取者的s_pos重置过程委托给所有者来修复它，从而消除了这个冲突。

优化。 对于BWoS，大多数并发访问都被转换为松散屏障，少数剩余的情况是释放或获取屏障。对于决定性能的所有者快速路径，我们在FIFO BWoS中只有一个释放屏障。相比之下，高度优化的ABP 包含许多屏障。特别是，所有者操作包含2个顺序一致、1个获取和1个释放屏障，这显著降低了其性能。

我们注意到这些优化结果是最优的：放宽任何这些屏障都会产生一个反例。为了进一步增加我们对验证结果的信心，我们增加了另一个窃取一个条目的窃取者线程，并用GenMC检查了优化的BWoS。BWoS在3天内通过了检查，探索了大约2亿次执行。

屏障分析。 LIFO BWoS在快速路径中不包含任何屏障，因为所有者和窃取者不在同一个块内同步。一个获取-释放对与所有者慢速路径和窃取者快速路径中的s_pos相关，确保了接管过程的正确性。另一个获取-释放对与s_cnt相关，确保所有者在追上窃取者块（环绕情况）时不会覆盖正在进行的读取。对于FIFO BWoS，除了上述屏障外，由于生产者和窃取者需要在块内同步，它们的快速路径中需要一个额外的获取-释放对。

6 评估¶

实验设置。 我们在两台通过10Gbps以太网连接的x86机器上进行所有实验，每台机器有88个超线程（x86），以及一台有96个核心的Arm机器（arm）。操作系统是Ubuntu 20.04.4 LTS，Linux内核版本为5.7.0。

6.1 块大小和内存开销¶

与其他队列相比，BWoS有额外的参数需要用户在初始化数据结构时选择，即块大小和块的数量。在我们的微基准和宏基准测试经验中，只要块大小或块数量高于某个最小值，系统的吞吐量基本上保持不变：队列中8个或更多块，块中64个或更多元素，这在我们的x86和arm机器上都适用。

这种对块大小变化不敏感的原因有两方面：首先，由于单个线程负责推进其自己队列的块，块大小不会引入任何与竞争相关的开销。较大的块大小导致队列所有者推进块的频率降低，但在某个块大小之后，推进块的开销变得可以忽略不计。其次，由于BWoS禁止所有者和窃取者在同一个块中使用块级同步来消费项，它们在队列上的竞争在很大程度上与块的数量无关。这些见解指导了我们基准测试的块大小选择：我们将块的数量设置为8，并根据队列容量计算块大小。

因此，选择一个合适的块大小是直接的。对这些参数的进一步微调可能对内存大小受限或过大块大小对窃取有害的极端情况有益（§8）。

BWoS为每个队列包含三个指针，为每个块包含四个原子变量、两个指针和一个布尔变量作为其元数据。实际内存使用还包括为防止伪共享而添加的缓存填充。这种元数据带来的内存开销是静态的，因此在大多数用例中可以忽略不计。

6.2 微基准测试¶

为了验证我们的主张，我们设计了一个支持LIFO和FIFO工作窃取的微基准测试，并将BWoS与SOTA算法进行了比较：一个来自Taskflow v3.4.0 的现成ABP 实现，带有屏障优化 (abp)，基于块的有界队列 (bbq)，来自Tokio v1.17.0 的工作窃取队列 (tokioq)，Go的运行时 v1.18 (goroutineq)，Kotlin协程 v1.6.4 (coroutineq)，和Eigen v3.3 (eigenq)。每个队列容量为8k个条目，数据项为8字节；BWoS配置为有8个块。我们进行以下三个实验：

无窃取的单个队列（§6.2.1）：所有者线程在一个循环中执行工作负载：它首先放入直到队列满，然后获取直到队列空。
有窃取的单个队列（§6.2.2）：一个额外的窃取者线程在一个循环中调用steal操作。我们调整put/get的比率，以及每次steal之间的空闲时间，以在不同的窃取百分比下进行实验²。
由8个队列组成的池（§6.2.3）：8个线程在一个循环中执行以下操作：向其队列放入项直到满，然后获取直到空，然后尝试从池中窃取k * C个项，其中k是平衡因子（百分比），C是队列容量。线程均匀分布在两个NUMA域之间，并在每个NUMA域内分布在两个L3缓存组之间。在每个实验中，我们测量总吞吐量：put、get和steal操作吞吐量的总和（ops/sec）。

²窃取者线程位于与所有者相同的L3缓存组中；将窃取者线程放在别处的结果类似。

6.2.1 无窃取的队列¶

总体性能。 图10和11中窃取百分比为0的情况显示了无窃取时队列的性能。BWoS明显优于其他算法。例如，LIFO BWoS (bwos_opt) 在x86上的吞吐量比ABP (abp_opt) 高4.55倍，而用C/C++、Rust、Go和Kotlin编写的FIFO BWoS分别比C中的bbq、C++中的eigenq、Rust中的tokioq、Go中的goroutineq、Kotlin中的coroutineq高出8.9x, 10.15x, 3.55x, 1.61x和1.82x。

内存屏障优化的影响。 abp和LIFO BWoS在x86上分别获得了1.65x和5.39x的速度提升，在arm上分别获得了2.03x和3.38x的速度提升，这都归功于内存屏障优化。我们对FIFO工作窃取算法也观察到了类似的结果³。BWoS相比ABP有更大的速度提升，这在很大程度上是由于快速路径和块推进的分离，使得快速路径中的大多数屏障都变得松散。

块级同步的有效性。 结果显示，在x86上，LIFO和FIFO BWoS分别只比理想情况慢10.7%和5.4%。在arm上的结果类似。因此，块级同步允许BWoS通过从快速路径中移除消费者-窃取者同步来接近理论上限。

³ 注意这里bwos_go没有屏障优化，因为Go不暴露松散原子操作的接口。然而，对于宏基准测试，我们通过使用Go内部原子库应用了屏障优化。

[图10：LIFO BWoS和ABP在有(opt)或无(sc)内存屏障优化的情况下，在x86和arm上运行，不同窃取百分比下的吞吐量。（图片已忽略）]

[图11：FIFO BWoS与其他SOTA的FIFO工作窃取算法的吞吐量对比。（图片已忽略）]

6.2.2 有窃取的队列¶

总体性能。 随着窃取百分比的增加，BWoS继续优于其他工作窃取算法。例如，在10%的窃取百分比下，LIFO BWoS比abp快12.59倍，而FIFO BWoS比bbq, eigenq, tokioq, goroutineq, coroutineq分别快11.2x, 30.1x, 9.41x, 2.78x, 和1.64x。

基于块方法的有效性。 与其他算法不同，BWoS随着窃取百分比的增加，性能下降很小。例如，对于20%的窃取百分比，LIFO和FIFO BWoS的吞吐量仅下降0.53%和9.35%，而abp_opt, tokioq和goroutineq则分别下降了71.9%, 80.2%和59.3%。注意，BBQ并发FIFO队列也是一种基于块的设计，但其性能无法与BWoS相媲美，这强调了我们为工作窃取工作负载所做设计决策的重要性。

6.2.3 不同窃取策略的池¶

窃取策略。 我们用6种窃取策略进行此实验，即随机选择策略(rand)，基于静态配置选择受害者的策略(seq)，选择上次选定受害者的策略(last)，二选一最优(best_of_two)，多选一最优(best_of_many)，和NUMA感知策略(numa)。对于多选一最优，我们选择一半最优（即四选一最优）。

总体性能。 在这个实验中，我们只将BWoS与先前实验中第二好的算法进行比较：分别为LIFO和FIFO工作窃取的abp和tokioq。图12显示BWoS的性能始终优于其他算法。当平衡因子为0%时，BWoS比abp和tokioq分别快4.69x和2.68x。随着平衡因子的增加，BWoS变体的吞吐量比abp高7.90倍，比tokioq高6.45倍。

NUMA感知策略的影响。 采用numa策略的LIFO和FIFO BWoS分别比采用其他策略的BWoS最多快2.21x和1.73x。对于其他工作窃取算法，二选一最优带来了最佳性能。因此，BWoS从numa策略中受益，而其他算法则不然。另一方面，在许多情况下，多选一最优带来了最差的性能，证明了与所有者的干扰可能会超过其在负载均衡方面的改进。

概率性窃取的有效性。 BWoS可以额外从概率性窃取中受益。当平衡因子为100%时，带有概率性窃取的numa策略(bwos+numa+prob)平均为LIFO和FIFO BWoS带来了1.34x和1.53x的性能提升。

[图12：在x86上，由8个队列组成的池在不同窃取策略和不同平衡因子下的吞吐量。rest指所有非numa策略，无论有无概率性窃取。（图片已忽略）]

6.3 宏基准测试¶

6.3.1 Java G1GC¶

我们将Java 19 HotSpot中的任务队列替换为LIFO BWoS，并运行Renaissance基准测试套件v0.14.0，该套件包含25个为测试和优化垃圾回收器而设计的现代、真实世界和并发的基准测试。两个数据库基准测试被省略，因为它们不支持JDK 19。JVM在运行基准测试时启用了-XX:+DisableExplicitGC和-XX:+UseG1GC标志。所有其他参数（例如，GC线程数，VM内存限制）均为默认值。我们对每个基准测试使用修改后的和原始的JVM运行10次迭代，并通过Renaissance测试框架测量端到端的程序运行时间。

[图13：在x86上，来自Renaissance基准测试套件的23个基准测试的加速比。（图片已忽略）]

图13显示了x86上所有23个基准测试的加速比。当启用BWoS时，其中17个获得了性能提升。所有基准测试的平均加速比为3.55%，最大加速比为25.3%。那些从并发GC中受益更多的应用也从BWoS中获得了更大的加速。arm上的结果类似，平均加速比为5.20%，18个基准测试得到改进，最大加速比为17.2%。

另一方面，几个Renaissance基准测试在使用BWoS时没有获得任何性能提升。我们通过使用-Xlog:gc+cpu和-Xlog:gc+heap+exit标志运行JVM来收集与GC相关的统计数据，从而调查了这个问题。这些实验表明，经常触发GC的应用从BWoS中表现出改进，而那些不触发GC或仅在极少数情况下（例如，在JVM退出时）触发GC的应用则没有看到加速。对于那些从未或很少触发GC的基准测试，性能下降很可能是由于更长的队列初始化时间所致。

6.3.2 Rust Tokio运行时¶

我们将Tokio v1.17.0中的运行队列替换为FIFO BWoS，并使用修改后的运行时运行Hyper HTTP服务器v0.14.18和Tonic gRPC服务器v0.6.2。Tokio运行时（以及Go运行时）提供了一个批处理窃取接口。基于类似图2d的基准测试观察，我们配置BWoS的窃取者一次性窃取其块中所有可用的条目。基准测试在两台x86机器上进行，一台运行服务器，另一台运行HTTP基准测试工具wrk v4.2.0或gRPC基准测试和负载测试工具ghz v0.017。Hyper和Tonic的所有参数均为默认值。每个基准测试运行100秒并有10次迭代。延迟和吞吐量由wrk或ghz测量，而服务器的CPU利用率通过Python psutil库收集。wrk和ghz分别运行echo工作负载和SayHello协议，并配置为利用其机器的所有超线程。

[图14：Hyper HTTP服务器在使用BWoS和原始算法时的吞吐量和延迟结果。（图片已忽略）]

图14显示了Hyper在不同连接数（100, 200, 500, 1k, 2k, 5k, 和 10k）下的吞吐量-延迟和吞吐量-CPU利用率结果。在系统过载之前，BWoS提供了1.14×10⁶ op/s的吞吐量，同时在相似延迟下CPU使用率下降了60.4%，而原始算法仅提供9.44×10⁵ op/s的吞吐量。在1k连接下，BWoS使吞吐量增加了12.3%，延迟降低了6.74%，CPU利用率降低了60.9%。

[图15：Tonic gRPC服务器在使用BWoS和原始算法时的吞吐量和延迟。（图片已忽略）]

图15显示了Tonic的吞吐量和延迟结果。使用BWoS使吞吐量增加了32.9%，平均延迟降低了32.8%，P95延迟降低了36.6%。

为了证明BWoS在应用于Web框架时的通用性，我们还对另外5个使用Tokio运行时的流行Rust Web框架进行了基准测试，使用了x86上的rust-web-benchmarks 工作负载（图16）。结果显示，BWoS使吞吐量增加了82.7%，同时平均延迟下降了45.1%。此外，任务窃取百分比从69.0%下降到49.2%。我们已经将我们为Tokio运行时的实现提供给了开源社区。

[图16：5个Rust Web框架在使用rust-web-benchmarks工作负载下，BWoS的请求吞吐量、平均延迟和任务窃取百分比与原始算法结果的比较（归一化）。（图片已忽略）]

6.3.3 Go运行时¶

我们将Go编程语言 v1.18.0运行时中的运行队列替换为BWoS，并对9个JSON库 [1, 9-12, 15, 18, 19, 25] 进行基准测试。基准测试套件来自go-json库，并使用默认参数运行3次迭代。我们记录每个操作的延迟（例如，编码/解码小型/中型/大型JSON对象），并计算加速比。

如图17所示，当启用BWoS时，操作在x86上平均获得25.8%的性能提升。arm上产生了类似的结果，平均加速比为28.2%。总的来说，编码操作相比解码操作有更好的加速。我们观察到在编码布尔值和整数时没有改进。

[图17：在x86上使用BWoS在go-json库基准测试中的加速比。（图片已忽略）]

7 相关工作¶

基于块的队列。 Wang等人提出了一个基于块的有界队列 (BBQ)，它将缓冲区分割成多个块，从而减少了生产者-消费者的干扰。BWoS与BBQ在以下方面有所不同：（1）尽管BBQ也应用了元数据分离，但它所减少的生产者-消费者干扰对于工作窃取来说不是一个问题，因为这些总是在同一个核心上执行。通过引入块级同步、从中间窃取的特性和随机化窃取，FIFO BWoS在很大程度上优于BBQ（§6）。（2）对于BWoS中的轮次控制，一个块的新轮次仅由其相邻块的轮次决定，而不是像BBQ中的版本机制那样依赖于全局元数据。这种设计简化了轮次更新并减少了其开销。

所有者-窃取者干扰和同步成本。 Attiya等人证明了工作窃取通常需要在所有者和窃取者之间进行强同步。BWoS通过将这种同步委托给块推进，从而将其从快速路径中移除，克服了这个问题。Acar等人使用一个带有消息传递的顺序双端队列来移除所有者的屏障开销。然而，这种设计依赖于显式的所-有者-窃取者通信，因此窃取操作不能与所有者操作并行完成。Dijk等人提出了一个基于双端队列的LIFO工作窃取算法，它将双端队列分为所有者和窃取者部分，从而在它们不触及队列分割点时减少了所有者的内存栅栏。然而，窃取者读取的条目在整个双端队列被清空之前不能被重用。Horie等人提出了一个类似的想法，每个所有者有一个可从其他线程访问的公共队列和一个只能由自己访问的私有队列。然而，它需要更多的努力来处理负载均衡，例如，引入导致所有者更多缓存未命中的全局统计元数据。相比之下，BWoS使用块级同步、概率性和随机化窃取技术来减少干扰。Morrison等人引入了依赖于有界TSO微架构模型的工作窃取算法，x86和SPARC CPU被证明拥有该模型。Michael等人通过允许它们读取相同的任务来减少窃取者-所有者的同步，这需要对任务进行重新设计以使其幂等。BWoS在广泛的CPU架构上表现出正确和高效的执行，没有任何额外要求。

窃取策略。 Yang等人对通过工作窃取调度并行计算进行了综述。Kumar等人对窃取策略的变体进行了基准测试和分析。Mitzenmacher提出给窃取者两个选择来选择受害者，以获得更好的负载均衡。大多数被分析的策略都是基于大小的，因此目标与我们的概率性窃取策略相同——即更好的负载均衡。Hendler等人允许窃取者一次窃取给定队列中一半的项以减少干扰。BWoS支持批处理窃取，但可以原子窃取的最大数据量是一个块。然而，窃取策略可以被配置为窃取多个块。Kumar等人提出了一个NUMA感知的工作窃取策略。这个策略与BWoS完全正交，并且可以与其概率性窃取策略相结合。

形式化验证的工作窃取。 Lê等人手动验证并优化了Chase-Lev双端队列在WMMs上的内存屏障。与依赖于模型检查的BWoS验证不同，手动验证是一项高强度的工作。在并发队列的背景下，Meta的FollyQ是使用交互式定理证明器进行验证的。虽然这种方法在设计上提供了最高级别的信心，但它只适用于顺序一致的内存模型，并且也是一项高强度的工作。最近，GenMC的作者作为其模型检查器评估的一部分验证了ABP队列。BBQ的作者依赖VSync来同时验证和优化弱内存模型的屏障。BWoS也为此目的使用VSync，但我们不是使用许多手工制作的测试来锻炼BBQ中的个别角落案例，而是创建了一个覆盖多个角落案例及其交互的综合客户端。我们通过在验证客户端中增加一个窃取者，并用GenMC检查，进一步验证了优化结果。

8 结论¶

总结一下，我们从这项工作中探索了两个经验教训。

基于块的设计的好处是多方面的。 首先，通过用块级元数据替换全局可变元数据，可以消除在不同块上操作的所有者和窃取者之间的干扰。其次，通过块级同步确保所有者get操作对块的独占访问，可以放松操作快速路径中的大多数屏障，将其性能提高到理论上限。虽然在我们当前的算法中不是必需的，但第三个好处是基于块的设计所带来的验证模块化，例如，允许对块及其组合进行分步验证。最后，基于块的设计为数据结构使用的整体优化开辟了可能性，就像我们用概率性窃取策略所做的那样。

BWoS也可以应用于GPU和混合CPU-GPU计算，以及工作窃取常见的HPC调度器。我们计划在未来探索这个方向。更普遍地，BWoS设计可以应用于其他数据结构主要由单个线程访问，而仅在极少数情况下由多个线程访问的用例。在这种情况下，BWoS中展示的决策可以作为设计和实现的指导方针。

经过验证的软件可以比未经验证的软件更快。 软件中反映的硬件细节和调整越多，那段代码就变得越复杂和不透明。这种复杂性与并发性和弱内存一致性的相互作用是一个重大挑战。我们相信，实用的验证工具（即用于增加正确性信心的工具）是开发高效且不可避免的复杂并发软件（如BWoS）的关键推动者。

未来工作 未来工作有几个方向：我们计划将BWoS贡献给更多的开源项目，例如，openJDK 和Golang，并研究如何在HPC运行时中使用BWoS。我们还计划更好地探索BWoS的性能权衡：如果未完成的工作项数量小于块大小，BWoS可能会阻止窃取，从而限制了实现的并行性。此外，如果队列容量必须非常小（由于空间要求），可能需要减小块大小，从而导致更多导致性能下降的块推进。这些情况将从系统设计的更多探索中受益。在其他情况下，由于其实现了几种性能增强技术，BWoS预计将优于现有的SOTA工作窃取算法。

致谢¶

我们感谢我们的指导人Phillip Gibbons和匿名审稿人提出的富有洞察力的评论。