使用现代 C++ 进行动态任务图编程¶

标题：Programming Dynamic Task Graph using Modern C++

日期：2026/06/28

作者：Tsung-Wei Huang

链接：https://www.youtube.com/watch?v=zAeGOJYZdHY

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

感谢您的介绍。大家早上好。我叫 Tsung-Wei Huang，大多数人直接叫我 TW，这样好记得多。今天我要讲的主题是：如何使用现代C++对动态任务图（Dynamic Task Graph）进行编程。这是一个旨在帮助您克服在编写动态并行工作负载时遇到的一些关键挑战的项目。

演讲核心要点¶

这是今天演讲的核心要点。我们首先将了解带有依赖关系的异步任务处理的重要性，并审视现有异步任务模型的局限性。接着，我将介绍一种名为 AsyncTask 的新型动态任务图编程模型（包含在我们的系统中），并向您展示我们如何克服一些关键的调度挑战来支持该模型。最后，我将演示我们模型的效率，并对本次演讲进行总结。

并行计算与硬件发展趋势¶

我相信在座的大多数人都已经知道，并行计算或并行编程已经将许多应用程序的性能提升到了一个非常有希望的水平，或者说是以前遥不可及的水平。例如，如果你想使用拥有 40 核的众核 CPU 来训练一个机器学习模型，你可能会获得 10 倍的加速。但如果再加一块 GPU，你还可以带来另外 10 倍的加速。这就是并行处理的威力。

更重要的是，现代硬件的设计本身就是为了并行运行事物，当然，这是为了性能。例如，在这张幻灯片中，我向大家展示的是 Intel 众核 Haswell 微架构，该架构发布于 2013 年初。这种架构通常配备 4 到 8 个核心，并板载一个集成 GPU。它基于超标量（superscalar）架构，这基本上意味着它可以在每个周期发出并完成多个独立的指令。它还可以支持超线程技术，允许一个物理 CPU 核心在操作系统看来像两个逻辑处理器。这里的核心信息是：既然芯片设计公司和制造商设计的硬件已经具备了这样的能力，如果你不进行并行编程，你就没有在高效地利用你的硬件。

不规则并行计算问题与任务图¶

但是，基础的计算问题并不容易。事实上，它们非常复杂且不规则。在这张幻灯片中，我展示了一个 GPU 加速的表面模拟（surface simulation）工作负载的计算任务图。如果你看看这个任务图，它将 GPU 操作建模为一个异步任务，并将两个 GPU 操作之间的依赖关系（如数据移动、内核同步等等）建模为一条边。这整个计算任务图实际上可以非常非常大。在这个例子中，我们正在模拟一个 NVIDIA 深度学习加速器设计，它拥有超过 5 亿个逻辑门。生成的图可能包含超过 1000 个异步内核任务和依赖关系。即使有 GPU，它仍然需要几个小时才能完成。

这是另一个不规则并行计算问题的例子：在这个例子中，我们使用众核 CPU 对超大规模集成电路（VLSI）的电路时序分析问题进行了并行化。给定电路模型，分析算法将给定的电路建模为一个任务图，并将时序值从电路的输入端一直传播到电路的输出端。对于具有数百万个门和网络的超大型设计，生成的任务图可以轻松包含超过 1 亿个异步任务和 1.5 亿个任务依赖关系。

事实证明，如果你想并行化这种非常不规则的工作负载，这并非易事。因为你总是需要处理大量的技术细节，不仅仅是来自你应用领域的知识，还包括来自并行计算领域的专业知识，例如抽象（无论是软件还是硬件的并行抽象）、并发控制、调度效率、负载均衡、运行时等等。而且，在你想要的东西和你想要的东西的成本之间总是存在权衡。例如，每个人都希望有简单、可维护、可扩展和可移植的实现，对吧？但是这些意图中的每一个都可能以牺牲性能为代价。因此，我们总是希望有一个处于上层的解决方案能够尽可能地帮助我们管理这些技术细节，因为从程序员的角度来看，他们真正关心的是他们能多快地完成工作。我所说的“快”，既指性能，也指生产力。

任务并行编程（TPP）的优势¶

在各种编程解决方案中，**任务并行编程（Task Parallel Programming, TPP）**已被证明是一种非常有效的解决方案，特别适用于不规则的工作负载。这是因为它允许开发者捕捉他们的意图，将算法自上而下分解为一个任务图，其中每个任务可以代表一个独立或单独的计算单元，而每条边可以代表两个独立计算之间的函数依赖关系。

但在同时，一旦你将应用程序算法传递到一个任务图中，你就可以将任务图所有困难的调度细节（如负载均衡、并发控制）委托给优化的运行时。因此，你不必担心任务将如何分配、工作负载将如何在众核 CPU 和 GPU 等之间进行平衡的复杂细节。这正是为什么在过去几年中，如果你观察并行编程社区，我们会看到越来越多的并行编程库。它们都在向越来越多的任务并行化方向发展，例如 OpenMP 的任务依赖子句、C++20 的 execution 库、TBB 的流图（flow graph）等等。

现有的异步任务模型及其局限性¶

现在我将谈谈一些已被现有应用程序广泛使用的流行异步任务模型，更重要的是，我们将深入探讨它们的局限性。

我们知道在 C++ 中，你可以使用 std::async 创建一个异步任务，这是一个用于异步启动任务的高级标准库设施。为了让大家更好地理解 std::async 是如何工作的，这里我有一个 compute 函数。它什么都不做，只是简单地返回其输入参数的值。我们可以使用 std::async 启动一个异步任务，在一个新线程上运行这个 compute 函数。而 std::async 将为应用程序返回一个 future 对象，供我们等待这个异步任务完成，然后我们就可以访问它的结果。在这个例子中，结果将是 42。非常简单。

这是一个关于如何实现这个设施的示例实现。我们可以有两个模板，一个是函数类型的，另一个是参数类型的。首先，我们获取函数的返回类型，然后使用它来创建一个 future 对象——一个用于线程间同步的 future 和 promise 对。基本上你可以把这想作：我向你承诺（promise），我会在将来的某个时候运行你的函数，然后你可以从由承诺对象的共享状态管理的未来（future）对象中获取结果。接下来，我们可以从一个捕获了该函数及其参数的 lambda 函数对象创建一个线程，然后在 lambda 函数对象的主体中调用该函数。最后，我们可以分离（detach）该线程来模仿 std::async 的“触发即遗忘”（fire and forget）行为。最后，我们可以将 future 对象返回给调用者。

借助 std::async 和 std::future，我们可以构建一个动态任务组来处理具有依赖关系的异步任务。这是因为 std::future 允许我们执行特定于任务的同步。一旦你从 promise 获得了一个 future，你就可以在该 future 上等待，以执行特定任务的同步。例如，假设我的应用程序有一个包含四个任务（A、B、C、D）和四个依赖关系的任务图。在这个例子中，函数 A（任务 A）在 B 和 C 之前运行，并且任务 D 必须在 B 和 C 之后运行。为了确保正确执行，显然，我们需要等待 A 完成后再异步启动 B 和 C。类似地，在异步启动任务 D 之前，我们需要等待 B 和 C 完成。结果就是，通过使用 future.wait 正确地同步任务，我们可以动态地创建一个任务图。

让我们来看看使用 C++26 Sender/Receiver 模型 实现的同一个任务组，这是一个用于组合任务和依赖关系的标准化抽象。这里，我们定义了一个静态线程池，以在一个工作线程池上调度任务。然后我们为 A 创建一个发送器（sender）任务，并在异步启动这里的两个并行发送器任务 B 和 C 之前同步其执行。然后我们可以使用原语 when_all 等待 B 和 C 都完成它们的执行，然后我们才能创建最终的发送器任务 D。最后，我们再同步一次以完成任务组 A、B、C、D 的执行。

这张幻灯片展示了同样的图，但是使用 TBB（Threading Building Blocks）库 的 task_group 实现的，这是一个用于创建同步任务组的类。这是一个创建异步任务并等待它们完成的类。在这个例子中，我们首先创建一个任务组 tg，然后使用 run 方法创建四个异步任务 A、B、C 和 D。类似地，我们需要在运行 B 和 C 之前等待 A，并在启动任务 D 之前等待 B 和 C。非常简单。

同样，这张幻灯片实现了同一个任务组，但使用的是 OpenMP 的任务依赖子句。如果您不知道的话，OpenMP 是一个非常流行的并行编程库。它利用编译器指令（directive）让你在编程时定义任务和依赖关系。一旦定义了该指令，你就不必担心将如何生成并行代码。它会自动被编译器处理。所以你只需专注于定义那些并行指令，以提示编译器生成并行代码。所以在这个例子中，在 OpenMP 秉性区域（parallel region）内，我们定义了四个整数的依赖句柄：AB、AC、BD 和 CD。它们分别代表从 A 到 B、A 到 C、B 到 D 和 C 到 D 的任务依赖关系。然后我们在创建 OpenMP 任务时，使用 in 和 out 关键字子句指定任务依赖关系。例如，这里的 OpenMP 任务 A 在 B 和 C 上有两个外出的依赖关系。而这里的任务 D 有来自 B 和 C 的两个传入依赖关系。有了这些 OpenMP 指令，支持 OpenMP 语言扩展的编译器将插入并行代码来启动由这些指令定义的异步任务，并强制执行它们的依赖约束，这些约束将由运行时调度器正确满足。

最后，这张幻灯片展示了使用 OpenCilk（注：原转录为 OpenSilk）的实现，这是另一个用于并行计算的流行编程库。在这种情况下，它专门针对依赖于特定库的编译器和语言扩展（即 cilk_spawn 和 cilk_sync）的 fork-join 编程模型。在这里，运行任务 A 之后，我们可以使用语言扩展 cilk_spawn 在任务 B 上生成一个子线程。然后主线程将继续处理任务 C（运行函数 C），然后在此处使用 cilk_sync 同步 B 和 C，然后它才能继续运行任务 D。这与 OpenMP 非常相似。在这种情况下，你需要一个支持 OpenCilk 语法语义的编译器来运行 OpenCilk 应用程序。

现有模型的四大局限性¶

到目前为止，我们已经看到了许多不同的异步任务模型来创建一个动态任务图，或者动态地创建一个任务图。虽然这些模型中的每一个在特定的应用领域都有其自身的优势，但我们发现它们经常伴随着以下局限性，使得我们无法充分利用动态任务图的潜力。

首先，如果你注意到我们刚才讨论的这些模型，任务及其依赖关系在任务图构建期间通常是相互解耦的。如果依赖关系没有与任务创建逻辑一起表达，那么推断任务图的结构就会变得非常困难。更重要的是，对于运行时而言，如果没有清晰的依赖结构，在构建异步任务图时，运行时优化任务放置、负载均衡等方面的机会就不多。
第二个局限性在于，同步调用（wait 调用）的正确放置几乎完全留给了程序员。你必须在一个非常细粒度的层面上决定正确的同步顺序。在最坏的情况下，根据任务图的复杂性，同步调用的数量等于你图中的依赖关系数量。不幸的是，在实践中，许多应用程序只关心整个任务图的完成，而不是中间任务。因此，这种细粒度的同步常常变得非常不必要、昂贵且极易出错。
第三个局限性是它们对构建高度动态任务图的支持不是很强。我所说的“高度动态任务图”，是指工作负载的结构、依赖关系、任务主体内容高度依赖于运行时变量或动态控制流结果的应用。例如，我们知道 OpenMP 要求你在编程时插入指令，以便编译器可以获取这些静态指令来生成你的并行代码。仅仅因为这些指令非常静态，你实际上没有太多机会在运行时构建图，尤其是当图的结构依赖于运行时变量、控制流结果等等时。
最后，某些模型可能需要非标准的 C++ 编译器来生成并行代码，例如我们刚才讨论的 OpenMP 和 OpenCilk。在这种情况下，你可能会在不同平台上遇到可移植性问题。

问答环节一：关于协程与任务并行¶

在我们进入下一个话题之前，我想看看观众到目前为止是否有任何问题。

观众： 是的，我只是想确认一下。我知道这里讨论的是异步（async），但协程（coroutines）实际上也会影响现在的某些代码吗？尽管这未必，我的意思是，从我的角度来看，它似乎在很多 C++ 标准中并没有被完全涵盖。

TW： 是的，但我会说协程，肯定是我们未来考虑整合到这个库中的东西。但目前，我们不处理协程，因为协程与我们在此系统中目标的模型根本不同。我们更专注于任务并行，这意味着您可以拥有跨不同线程运行的许多任务。但是协程更像是多任务处理（multitasking），对吧？你可以有一个线程同时处理函数主体的多个部分。你可以上下文切换到协程的不同部分。这是一个从根本上完全不同的执行模型，与我们系统目标函数模型不同。但可以肯定的是，将协程集成到我们的系统中，我猜这需要对调度器进行一些重大更改，这也是我即将要谈论的内容。

如果没有更多问题，那我们就继续。好的。

AsyncTask：一种新的动态任务图编程模型¶

所以现在我将介绍一种名为 AsyncTask 的新动态任务图（Task Graph）编程模型，并向您展示我们如何解决刚才提到的关于现有编程系统的部分局限性。

在我讨论动态任务图编程之前，让我们首先了解在我们的语境下，静态和动态任务图编程（TGP）之间的区别。

我们到目前为止讨论的所有例子都是动态任务图编程（DTGP）。在**静态任务图编程（STGP）**中，执行遵循“构建并运行”（construct and run）模型。你基本上是先构建一个任务图，然后运行它。你将构建好的任务图提交给一个运行时，运行时将为你调度并运行任务图。另一方面，在 DTGP 中，异步任务可以在其依赖项得到满足时立即开始，这意味着任务的构建和任务图的执行可以相互重叠。对于非常大的任务图，这种重叠有时可以提供优于 STGP 的非常好的性能优势。

为了更好地理解这种区别，让我们来看看 Taskflow 中的静态任务图编程，Taskflow 是一个用于任务并行编程的 C++ 库。假设你有一个任务图，使用我们刚才讨论的同一个例子，包含四个任务 A、B、C 和 D。A 在 B 和 C 之前运行，D 在 B 和 C 之后运行。在 STGP 中，你必须在一个名为 Taskflow 的图对象中定义这个任务图。然后你使用 C++ Lambda 函数对象定义四个任务 A、B、C、D。接着，你使用 precede 和 succeed 方法建立 A、B、C 和 D 之间的依赖关系。构建好任务图后，你将其提交给执行器（executor）执行。正如你所见，任务图的执行和构建是相互分离的。这就是我们语境下关于静态任务图编程的定义。

基于 Taskflow 的动态任务图构建¶

我们没有从头开始，而是建立在 Taskflow 之上构建了我们的动态任务图编程模型 AsyncTask。这样我们可以重用它的许多设施。使用同一个图作为例子，我们可以使用方法 silent_dependent_async 或 dependent_async 从 C++ Lambda 函数对象创建一个任务。如果您想获取一个额外的 future 对象，让您执行特定任务的或细粒度的同步，就可以使用后者。

当您创建一个具有依赖关系的异步任务时，您可以使用 C++ 可变参数模板（variadic parameter pack）指定任意依赖项。例如，在这里，当我创建任务 B 时，我将 B 和 C 作为最后两个参数传入（注：结合语义，此处指将前置依赖项作为参数传入，这表明任务 B 直到其依赖项完成才能开始）。更重要的是，当您创建一个带有依赖关系的异步任务时，只要其依赖项得到满足，运行时就可以立即开始该异步任务的执行。因此，现在任务图的构建可以与任务图的执行重叠。

如果你不需要像前面的例子那样进行细粒度同步（在前面的例子中，你可以在从最终任务 B 返回的 future 对象上同步这个任务图），你实际上可以直接调用执行器（executor）的 wait_for_all，执行器是管理调度任务图所有调度细节的运行时对象。在这种情况下，刚刚提交给执行器的所有内容都将运行到完成。

你可能已经可以想象出 DTGP 模型的局限性。DTGP 需要一个正确的拓扑排序（topological order）才能动态指定依赖关系。这是因为当您在动态任务上定义依赖关系时，该依赖关系的父任务必须已经以正确的拓扑排序存在。否则，您无法指定该依赖关系。在我们的例子中，这基本意味着你要么以 A、B、C、D 的顺序编写动态任务图，要么以另一个拓扑顺序 A、C、B、D 编写，因为这两种都是正确的拓扑顺序。正如我所说，如果在您的应用程序中，没有简单的方法来挖掘出任务创建的拓扑顺序，那么这将阻止您表达一个正确的动态任务图。在这种情况下，动态任务图可能不是您应用程序的正确选择。例如，如果您想以 A、D、B、C 的顺序创建此任务图，这是不可能的，因为您无法在任务 D 上指定依赖关系。由于任务 D 在 B 和 C 之前被指定，而当时 B 和 C 还不存在，因此您无法正确指定从 BC 到任务 D 的依赖关系。所以你需要一个正确的拓扑顺序。

动态控制流与数据抽象的设计选择¶

silent_dependent_async 和 dependent_async 这两种方法都可以接受一个可变范围（variable range）的带依赖异步任务。这当然非常有用，尤其是当任务依赖项是在运行时确定时（例如，图的结构是从文件加载的，或者是从函数返回的）。例如，你可以创建一个带依赖异步任务的 vector，并在创建另一个任务时使用它来指定依赖项。虽然你可能觉得这个功能微不足道，但我可以告诉你的是，如果你想在一个动态任务图中创建任务时指定一个可变范围或可变数量的依赖项，我发现这是相当困难和具有挑战性的。如果你想使用例如 OpenMP 或 C++ Sender/Receiver 模型，这个看似微不足道的功能实际上是那些现有系统很难实现的，因为它们不允许你同时描述任务和依赖项。任务创建和依赖项创建彼此是解耦的。

动态任务图编程的一个主要优势是运行时驱动执行的灵活性。这意味着您可以在运行时灵活且非常通用地组装不同的任务图结构，或者由运行时结果和动态控制流变量来驱动。例如，看看这里的代码片段，根据变量 A 和 B 的值，我可以创建一个不同的任务图。如果 A 为真，我将构建 G1。如果 B 为真且 A 为真，那么我将创建一个任务图 G2，并让 G1 在 G2 之前运行。否则，我将创建一个完全不同的任务图 G3，并要求 G3 在 G1 之后运行。或者动态依赖于任务图 G1 的结构：如果任务图 G1 有 100 个任务，我将要求 G1 在 G2 之前运行；否则，我将通过创建一个新的任务图 G3 来构建一个完全不同的任务图结构，并要求 G1 在 G2 和 G3 之前运行，等等。如果你使用静态任务图编程，这种类型的动态任务图是很难实现的，因为你不能预先决定任务图的结构。

如您所见，这可能也回答了讲座早期观众提出的问题：我们的库不涉及数据抽象（data abstraction）。这是我们在 AsyncTask 早期设计阶段做出的一个非常重要的决定。这里的核心要点是，我们希望专注于粗粒度级别的任务并行算法，而不是细粒度的数据并行算法。首要目标是让应用程序开发人员使用干净、富有表现力的接口来描述任务及其依赖关系。借助此接口，用户可以将函数定义为 lambda，并自行捕获任何他们想要的数据。这基本上就是 std::async 实现的方式。

当然，做出这个决定的优势有两点：

第一，您保留了对数据布局和所有权的完全控制。基本上，这允许您为特定的应用领域优化任何数据结构和内存布局。
第二，让用户管理自己的数据和依赖项，使我们的系统保持非常轻量级和非侵入性。由于您只是想利用我们的框架，真的没有必要去修改您现有的数据结构或内存布局。试想一下，这种模型与现有的具有数据抽象的系统（例如 FastFlow、TBB 的 pipeline 编程模型）非常不同，那些系统通常需要您修改代码，重构您的数据布局，以适应其库特定的数据抽象，从而获得并行性。

问答环节二：任务定义与库对比¶

在我们继续讨论如何克服调度挑战以支持我们的编程模型之前，我想再次停顿一下，看看观众是否有问题。还是那句话，如果您有问题，直接发言即可。

George： 喂，TW，能听到我说话吗？

TW： 是的，我能听到，是 George，对吧？

George： 是的，我想澄清一下我的理解，关于您在这个编程模型中提到的任务，例如在 Sender/Receiver 模型中，他们如何将任务称为协程。在这里，当您提到任务时，它指的是类似于图（graph）里的节点，对吗？

TW： 是的。任务基本上是一个函数。一个可以在单个线程上运行的东西。非常类似于 std::async。

George： 好的，所以 Sender/Receiver 模型中的任务和任务图中的任务之间确实有一些相似之处。

TW： 是的。但是 std::async 不允许你指定依赖项。这完全取决于您自己来实现您自己的依赖项跟踪机制来调度您的任务图。

George： 好的。所以，结合您一直在讲的内容，在某些情况下，您也可以在 Sender/Receiver 模型中实现这种方式？

TW： 我认为答案是肯定的。你可以，比方说，在我们的系统之上构建 Sender/Receiver 模型，或者你可以使用 Sender/Receiver 模型来构建我们的系统。

George： 好的。非常感谢您的澄清。谢谢你，TW。

TW： 没问题。非常感谢您的提问。通过与观众互动，我学到了很多。还有其他问题吗？

观众： 是的。我只是很好奇。那么，现在是否有任何针对 AsyncTask 的标准库功能？或者这就像是您必须从头开始做所有事情一样？

TW： 在 C++ 标准方面，没有。而这正是我们这个库的目的和动机。我们希望完全使用标准的 C++ 特性（线程、异步、依赖、数据结构）来构建我们的库。但回答你的问题，没有标准 C++ 库可以支持像 AsyncTask 这样的功能。这是该项目背后的动机之一，因为当我们试图使用 std::async 编写任务图时，我们意识到实际上没有办法跟踪依赖关系。如果一个任务库不允许进行依赖跟踪，那么它的实际应用将非常有限。因为如果应用程序没有任何依赖关系，那么它就变成了易并行（embarrassingly parallel）任务。

观众： 好的，好的。

观众补充： 那么，这可能是我试图理解的一点。但这有点类似于 C++23 的 Generator 吗？尽管它使用了协程，而且看起来不完全一样。但如果是要像 AsyncTask 中的任务那样，你会有一个在底层设置样板代码来配置函数的任务。然后你就可以编写自己的函数，假设你定义了输入参数，然后基本上就是返回你的输出参数。你可以像这样定义你的依赖关系。您是这个意思吗？

TW： 嗯，我会说有几分相似，但谈到协程，正如我刚刚提到的，与 AsyncTask 或任务并行编程库相比，它是一个根本不同的执行模型。协程更多的是多任务处理（multitasking）。您刚才提到的关于协程的所有现有基础设施，尽管它生成了某种在非常繁琐的协程显式编程之上的高级抽象，但它们仍然不允许你指定依赖关系。这是因为，我猜其中一个原因是，协程的依赖关系实际上更线性。它是多任务的。在没有完成位于函数开头的第一个协程之前，你不能跳到函数体的任意部分。因此，它是一个根本不同的执行模型。协程或多任务处理的依赖关系相对来说是线性的。而且所有现有的协程库，比如 Generator 或者你刚才提到的任何库，它们通常不允许你指定依赖关系。这说得通吗？

观众： 我想是的。我想我只需要去玩一玩它。它看起来有点令人困惑，因为协程是多任务的，你可以让函数的多个部分通过切换来运行，但在大多数情况下，它仍然由一个线程运行。

TW： 好的。再次感谢您。如果协程是有栈的（stackful），那么跨不同线程调度协程是非常困难的。

主持人（代转 Discord 提问）： Discord 上有一个问题。原谅我的无知，但 AsyncTask 使用操作系统（OS）线程来处理任务，还是更像一种用户空间的绿色线程（green thread）模型？

TW： 我们使用 std::thread。

主持人续问： DAG 中的每个节点都会生成一个新的 OS 线程吗？

TW： 有一个线程池管理着在开始时生成的一组工作线程，因此我们可以重用池中的这些线程。所以它不像每当有任务时我们总是创建一个新线程。希望这能回答这个问题。

主持人： 如果我可以插一句话，还有一个问题。有人想知道，在处理异步任务和动态任务图时，您会在 Taskflow 和 Cilk 之间如何选择？

TW： 嗯，这取决于您的用例。我的意思是，Taskflow 和 OpenCilk 之间最大的区别之一是，Taskflow 完全建立在标准 C++ 之上。你不需要安装另一个支持 OpenCilk 特定语言扩展的编译器。此外，OpenCilk 也没有让您显式指定依赖项的工具。您仍然需要使用 cilk_sync 来显式捕捉您的任务图依赖关系。

主持人： 谢谢。

TW： 好的。那我想我们可以继续了。

调度挑战及解决方案¶

现在让我们谈谈我们如何在非常高的层面上克服一些调度挑战来支持我们的模型。

我们的调度器是建立在 Taskflow 的工作窃取（work-stealing）调度器之上的，它基本上有两个层级：任务层级和工作线程（worker）层级。在任务层级，其工作是决定每当某个任务的依赖关系满足时，将哪些满足依赖关系的任务纳入哪个工作线程。在工作线程层级，其工作是决定只要有任务可用（意味着其依赖约束已满足），哪个工作线程去运行哪些任务。这是一项杰作。因为时间关系，我不打算谈论所有的细节。事实上，这是我们多年来一直在开发的东西。如果您感兴趣，我鼓励您去查看我们发表在 TPDS 上的原创 Taskflow 研究论文。

相反，我将重点关注如何在宏观层面上在这个工作窃取设施之上调度动态任务图。我将谈谈我们克服的三个主要挑战。我相信这三个主要挑战是，如果你开发一个动态任务图库，几乎肯定也会遇到的：

ABA问题：这基本上意味着，每次带依赖的异步任务基于一个依赖项时，该前置任务必须正确存在。
数据竞争（Data Race）：由于在 DTGP 中任务图的构建和执行可以同时发生并相互重叠，多个工作线程可能会同时访问这个带依赖异步任务的后继节点。我们必须防止数据竞争。
同步（Synchronization）：如您所见，我们允许您进行全局同步，以使整个任务图完成；或者在本地，您可以随时使用细粒度同步来同步子图的特定点。我们要确保同步开销不会变得非常大。

让我们来看看第一个挑战，ABA。ABA 意味着每次你指定一个任务依赖（例如任务 B 不能在任务 A 完成之前启动，它必须等待任务 A 完成），这个依赖项必须正确存在。这是因为在动态任务编程中，当创建任务 A 时，运行时可能会立即开始其执行。在这种情况下，A 没有任何依赖项。很可能当你试图在这里使用任务 A 时，任务 A 已经完成了。现在，如果任务 A 完成得非常非常快，并且其资源被运行时回收（例如通过内存池优化或对象回收），那么你在这里引用的任务 A 可能已经不是原来的那个了。当您仍在使用相同的内存地址时，其他人可能创建或重用了该内存地址。这就是经典的 ABA 问题。

为了解决这个 ABA 问题，我们引入了一个名为 AsyncTask 的特殊句柄（这也是库的名字），它要求应用程序保留所需每个任务的共享所有权。这个 AsyncTask 句柄的行为就像标准的 C++ std::shared_ptr，它确保任务在被使用时保持存活。有了这种共享所有权，我们总是可以保证任何指定的任务依赖关系都将正确存在，因为当你想使用它时，你会获得一个共享所有权，并且不会出现 ABA 问题。

接下来的第二个挑战是数据竞争。这是因为多个线程可能会同时访问任务的后继节点。例如在这个例子中，你在任务 A 之后立即创建任务 B 和任务 C。它们可能都想将自己添加到 A 的后继节点中。同时，A 可能也想在它完成时移除其后继节点。

当然，一个简单的解决方案是你可以为每个依赖项或每个任务添加一个互斥锁（mutex）来确保排他性访问。但这互斥锁非常沉重，尤其是当你的任务有许多依赖项时。在这个场景中，我们取而代之使用的是带有自旋（spinning）的**比较并交换（CAS）**操作来实现排他性访问。根据我们的经验，这种自旋不会产生太多的开销，因为现实世界中的大多数任务图都非常稀疏，它们没有那么多依赖项。如果你的任务图非常密集，有大量的依赖项，那么任务并行可能并不是适合你应用程序的正确解决方案。

最后的挑战是同步。这基本意味着用户可以随时发出粗粒度和细粒度的同步。您可以使用执行器的 wait_for_all 等待整个图完成，或者使用细粒度同步等待特定的子图完成（例如通过 dependent_async 获取的 future 的 wait 调用）。

为了同步这种执行，一个简单的解决方案当然是你仍然可以使用互斥锁加上一个条件变量（condition variable），当条件满足时（例如当任务数变为零，意味着任务图已经完成），通知应用程序。然而，这种基于锁的解决方案可能非常昂贵，特别是当任务数量和线程数量变得非常大时。

为了减少这种同步开销，我们利用了 C++20 的原子变量（atomic variables） 来执行等待和通知操作，这基本上允许大量的这种同步仅在用户空间发生，而不是在内核空间中发生。正如我们稍后将展示的，通过这样做，我们能够实现 11% 的性能提升。

综合以上这些想法，我们的调度算法完全是无锁的（lock-free）。不涉及任何互斥锁。一切都只有基于 C++20 的原子操作。如前所述，这是我们多年研究出的一项杰作。由于时间关系，我无法谈及所有细节。我们已在 ICCAD 2023 上发表了该算法，我鼓励您如果有兴趣的话，去查看该论文了解更多细节。由于我们只剩下 10 分钟了，我想把提问留到最后，这样我就可以完成演示的最后部分。

系统评估与基准测试¶

现在我将演示我们系统 AsyncTask 的效率。我们在微基准测试（microbenchmarks）和真实世界的应用程序上评估了 AsyncTask 的性能，以研究在有和没有应用任务影响的情况下的性能。

在微基准测试方面，我们测量了四种常用任务图模式的性能：线性链（Linear chain）、二叉树（Binary tree）、易并行（Embarrassing parallelism）和随机图（Random graph）。

在真实世界应用方面，我们使用 AsyncTask 在 VLSI 设计中实现了一个真实的、任务并行的静态时序分析（Static Timing Analysis, STA）应用程序，我们在其中使用 AsyncTask 并行化了时序传播算法。

这是我们与之比较的基线：OpenMP、Parsec、OpenCilk、AsyncTaskLK 和 AsyncTaskCV。

AsyncTaskLK 是一个基线，它将我们的调度器替换为 OpenMP 的任务调度器，该调度器利用基于锁的哈希表在编译时和运行时跟踪任务及其依赖关系。这种比较使我们能够测量在与最先进的任务并行编程系统 OpenMP 相比时，我们的无锁调度算法有多好。
AsyncTaskCV 用条件变量替换了我们基于原子变量的通知算法。这种比较使我们能够看到，通过利用基于 C++20 原子变量的通知算法，我们的调度算法有多优秀。

所有程序均使用启用 C++20 并开启优化级别 3 的 G++ 12 进行编译。我们测试评估的机器是一台 64 位 Linux 机器，配备 128GB 内存和 20 个 Intel i5 核心，每个核心主频为 4.8 GHz。在此报告的所有数据都是 10 次运行的平均值。

这张幻灯片展示了四个微基准测试的性能对比。总的来说，你可以看到 AsyncTask 做得非常出色，在几乎所有场景中都优于所有基线。特别是对于随机图，这正是我们目标的任务图编程模型。随着我们在坐标轴上增加任务数量，AsyncTask 的扩展性比其他基线好得多，与 OpenMP 的差距继续扩大。对于一个包含 200 万个任务的固定大图，我们测量了跨越不同线程数量的可扩展性，我们系统的运行时间随着线程数量的增加而减少，并在大约 4 个线程时饱和。当然，这种饱和取决于您任务图中可用的最大并行度。

现在我要谈谈评估中最有趣的部分——在真实世界的应用上的评估：静态时序分析（STA）。STA 在超大规模集成电路（VLSI）设计自动化中是非常非常重要的一步，因为它能验证电路的时序行为。基本上，你要确保你的电路在给定的时钟频率下能正确工作。

我们使用 AsyncTask 实现了由我们研究组开发的这种任务并行 STA 算法，其中时序传播被建模为动态任务图。我们将时序数据从电路的输入端一直传播到电路的输出端。作为一个例子，我这里有一个任务图，表示这个具有四个组合逻辑门和一个触发器的简单电路的时序传播。

我们在四个工业级的、超大规模电路图上评估了性能。从性能图表中可以看出，AsyncTask 总是优于基线。无论我们使用多少个线程来运行任务图，AsyncTask 总是能在输出上表现出非常一致的效果。这一结果凸显了我们调度算法的效率。

我们还将其与使用 Taskflow 实现的 STGP（静态任务图编程）性能进行了比较。该实验的目的是研究和强调 DTGP 的优势，特别是对于大型任务图，其中这种动态重叠的任务图构建和执行可以提供一定的性能优势。我们知道，在 STGP 中，构建任务图仅在一个线程中完成，并且不与任务图执行重叠。对于像 VGA LCD 这样具有 40 万个任务和依赖项的大型图来说，我们花在构建图上的时间变得不可忽视——它占据了大约 15% 的运行时间。这就是使用静态任务图并行化应用程序的开销，您总是需要先构建应用任务图，然后才能运行它。显然，当图规模很小时，DTGP 的调度开销可能无法为您提供相比于重叠所能带来的太多性能优势。在图很小的这种情况下（像一些非常小的电路，可能只有几百或几千个门），DTGP 的调度开销将大于重叠带来的优势。

总结¶

总结一下，在今天的演讲中，我们了解了带有依赖关系的异步任务处理的重要性。我们也探讨了现有异步任务模型的几个局限性。接着，我们介绍了一种名为 AsyncTask 的新型动态任务图编程模型，并展示了我们如何克服一些重要的调度挑战来支持我们的模型。最后，我们在微基准测试和真实世界的大规模应用上证明了该系统的效率。

今天我们讨论的关于 AsyncTask 的所有内容都已集成到 Taskflow 项目中。如果您不知道 Taskflow，它是一个仅包含头文件（header-only）的用于任务并行编程的 C++ 库。该项目实际上始于 2018 年，旨在帮助 DARPA（美国国防部）并行化无法由现有模型有效处理的重要微电子设计自动化工作负载。

使用 AsyncTask 系统非常简单。我们构建该系统时充分考虑到了应用程序体验，基于应用程序开发人员真正想要的东西来构建。您只需下载 Taskflow 项目，并在编译程序时告诉您的编译器在哪里可以找到 Taskflow 的头文件，仅此而已。没有安装带来的各种纠缠。一切都是完全标准的 C++，没有任何不符合标准的特性。

最后，我总是借此机会向所有使用 Taskflow 项目的人表示感谢。Taskflow 是开源的。它正被越来越多的来自学术界和工业界的人士使用。我们总是非常乐意合作。当然，如果没有赞助商，该项目是不会成功的。我们非常感谢这些资金支持。

到此，我将在这里结束演讲，我很乐意回答任何问题。非常感谢。

问答环节三：ABA问题、库适用性与能效设计¶

主持人： 我们从 Vishal 开始。你举手有一会儿了。如果你有问题，直接说就行。好吧，他还在调整。我又从 Discord 拿到几个问题。假设由于每个任务的无锁性质，可能会发生 ABA 问题？让我们问个澄清的问题。

TW： 是的，我认为这是我们无法控制的事情，因为如果你的应用程序本身已经存在 ABA 问题，那么我们无法处理。但我可以保证的是，库系统调度器本身或者使用 dependent_async、silent_dependent_async 的 API 接口是免受 ABA 问题困扰的。不存在 ABA 问题。因为我们总是要求你，每次你创建一个动态任务或带有依赖的异步任务时，你总是需要保留对该任务的所有权。

主持人： 接着是关于微基准测试中的 Random G。我相信这是刚才的一个回应。问题是：为什么不包括 Parsec 和 OpenCilk？

TW： 嗯，因为我们发现很难基于 Parsec 和 OpenCilk 来实现这个 Random G。因为这个 Random G 基准测试，就像我说的，图是来自一个文件的。我们没有办法静态地决定图的结构。我们发现使用 Parsec 和 Cilk 来实现这个基准测试非常具有挑战性。

主持人： 仅仅是因为它的动态特性吗？

TW： 是的。图是作为函数结果返回的。这是一个函数返回。

主持人： 然后是我自己的一个问题。你在演示开始附近的一张幻灯片上谈到了一点点关于能效（energy efficiency）的问题。我知道在现在这个时代，大家对数据中心数量的爆炸式增长以及它们为了 AI（用于特征开发、拟合等）试图获取的大量能源感到担忧。这是一个可能适合 AsyncTask 的领域吗？或者您是否有该领域的工作经验？

TW： 这是一个极好的问题。事实上，我会说这个系统最大的贡献之一是我们的调度器设计。正如我提到的，这是我们多年来一直在开发的东西。我们确实有一个非常专业的调度器，它会尝试动态平衡积极参与运行任务的活动工作线程与可用的任务并行度。显然，并行度会随时间改变。所以，当与 OpenMP 等其他库相比时，我们的系统几乎没有过度订阅（oversubscription）的问题。它非常节能。我们在这篇论文中也报告了相关的研究数据。当不需要时，我们不会过度订阅或过度使用工作线程。

这是一个非常好的问题，因为我们确实有一些用例。我们的一些用户在他们的嵌入式应用程序中使用 Taskflow。例如，我记得有一位用户在他们的无人机设备中使用 Taskflow。在他们的无人机中，他们想保证调度器不会消耗太多能量，否则电池很容易就会耗尽。然后他们选择使用我们的系统，因为我们的调度器实际上非常节能。

主持人： 太棒了。谢谢。Devon？

Devon： 抱歉，还有一个问题。对于工作窃取调度器，您说您基本上会去平衡实际的调度。所以我假设你有类似……（指出幻灯片）这里就是那个算法。您在论文中更深入地探讨了如何处理负载不平衡（load imbalance）之类的问题，对吧？

TW： 是的。宏观图景是，从系统运行时调度器的角度来看，可用的任务并行度随着时间的推移而不断变化，对吧？因为我们没有办法静态地决定：嘿，在时间 T1，你只能运行 4 个任务；在时间 T2，你只能运行 2 个任务。这完全取决于应用程序。所以可用的任务并行度是非常动态的。就像我提到的，我们确实有一个非常专门的算法。它们始终可以平衡可用的任务并行度和活动的工作线程，从而最大限度地减少工作线程的过度订阅。例如，如果您只有两个任务可以并行运行，没有理由唤醒您机器中可用的全部 16 个线程来运行这两个工作，因为您最多只能获得这么一点可用的并行度。

Devon： 那非常酷。我必须得去读读那篇论文。听起来非常有趣。谢谢。

TW： 您也可以看看项目的源代码。源代码非常完整地实现了这种动态的工作窃取模式是如何落地的。感谢您的提问。还有其他问题吗？

主持人： 好的。我想再次感谢您，感谢所有提出问题的人。也再次感谢您今天来这里发表演讲。我知道前几周对您来说有些时间变动，所以我非常感谢您展示这个。它看起来非常酷，非常有趣。而且我希望我们也能帮您把这个项目宣传出去。

TW： 我们非常珍惜这个与这么多优秀人才交流的机会。所以，我们大概会留意大家的情况，看看反响如何。我们会保持关注，并推荐在奥斯汀（Austin）或者未来的活动中进行更多展示。我们知道大家对此非常感兴趣，感谢大家的时间。