oneTBB 动态任务依赖扩展:task_group 的 task_completion_handle 与 set_task_order 完整语义指南

原创2026-10-09 13:58:582,332 阅读
文章标签:并发编程高性能计算

oneTBB 动态任务依赖扩展:task_group 的 task_completion_handle 与 set_task_order 完整语义指南

本文是 oneTBB 任务组动态依赖特性(Task Group Dynamic Dependencies)的核心技术指南,基于仓库中 extended_semantics.md 子 RFC 展开,并与 总览 RFC 及 实现细节子 RFC 相互印证。读完本文,你将掌握:任务生命周期四状态模型(created/submitted/executing/completed)、新增的 task_completion_handle 类完整 API 语义、task_group::set_task_order 与 transfer_this_task_completion_to 的精确行为约定,以及它们在斐波那契、N 体问题、Wavefront、文件解析器等递归任务图场景中的实战写法,并了解底层 task_dynamic_state 的实现原理。

背景:为什么 task_group 需要动态依赖

2021 年 oneTBB 发布后,oneTBB 不再把底层任务调度接口作为面向用户的特性推广,而是鼓励用户通过 task_group 或 flow graph API 表达并行模式(见 总览 RFC)。但有一类场景用现有 API 难以表达:非树状的动态任务图——任务创建、依赖指定、提交调度与执行可能并发发生且顺序不定。

oneTBB 现有 task_group 的核心能力是 defer 返回的 task_handle,它允许"先创建、后提交":

tbb::task_group tg;

auto split_task = [&tg] -> tbb::task_handle {
    auto first_task_handle = tg.defer([] { /* ... */ });
    auto second_task_handle = tg.defer([] { /* ... */ });

    tg.run(std::move(second_task_handle));
    return std::move(first_task_handle); // 预览扩展:返回下一个应执行任务的提示
};

tg.run_and_wait(split_task);

但现有 API 有两个局限:task_handle 只能表示 created 状态的任务,提交后即失效;task_group 只能在整体层面等待任务组,无法在两个任务之间直接建立"先完成 A 再执行 B"的顺序关系。本 RFC 正是为填补这两个空白而设计的三项扩展:

  1. 扩展 task_handle 的语义与有效生命周期,使其可表示已提交、执行中、已完成的任务;
  2. 新增设置任务间依赖关系的函数;
  3. 新增把当前执行任务的后继(successors)转移给新任务的函数,以支持递归生成的任务图。

任务生命周期四状态模型

为讨论方便,RFC 为任务定义了四个生命周期状态:

  • Created:任务已分配并注册到 task_group,但调度算法尚不知晓它,因此不会开始执行。任务在调用 task_group::defer 后、任何提交方法(如 task_group::run)调用前处于该状态。
  • Submitted:任务已提交给调度算法,其所有依赖解析完成后即可被调度执行。
  • Executing:所有依赖已完成,某个线程开始执行其函数体。
  • Completed:线程执行完任务函数体,任务转为完成状态。

任务的完整状态转换路径为:created →(提交)→ submitted →(依赖全部满足)→ executing →(函数体结束)→ completed。

核心设计决策:引入 task_completion_handle 而非改造 task_handle

父提案原本考虑直接扩展 task_handle 使其能表示任意状态的任务,但这需要同时修改所有提交方法(task_group::run、task_group::run_and_wait、task_arena::enqueue、this_task_arena::enqueue)的语义。本子 RFC 采取了更保守的方案:

  • task_handle 保持不变:它仍是"唯一所有权"句柄,要么拥有一个 created 状态的任务,要么为空。
  • 新增 task_completion_handle:用于表示任意状态的任务,并据此建立依赖。

task_completion_handle 可以由拥有 created 任务的 task_handle 构造,反向转换不被允许:

tbb::task_group tg;

tbb::task_handle handle = tg.defer([] {/*...*/});        // 任务处于 created 状态,handle 拥有该任务
tbb::task_completion_handle completion_handle = handle;  // 为 handle 拥有的任务创建 completion_handle

tg.run(std::move(handle)); // 任务进入 submitted 状态,handle 被置空

// completion_handle 仍非空,可用于设置依赖

这一设计的好处是:提交方法的语义完全不需要改变,因为 task_handle 的语义保持不变。

设置任务间依赖:set_task_order

基本语义

考虑在 predecessor 与 successor 两个任务之间建立前驱-后继依赖:task_group::set_task_order(predecessor, successor)。

父 RFC 规定:前驱可以是任意状态,但后继必须处于 created 状态(一旦任务开始执行或完成,再添加前驱就太晚了)。这一限制通过强制后继参数为 task_handle 来执行。

针对前驱任务的不同状态,行为如下:

前驱状态 行为
created / submitted / executing 把后继注册到前驱的后继列表,并在后继侧递增对应引用计数,确保后继不会在前驱完成前执行;后继的引用计数归零后才能开始执行
completed(未发生转移) API 无实际效果:不引入额外依赖,后继在其他依赖满足后即可执行
completed(发生了转移) 原任务在任务图中已被另一任务替换,API 会把新后继重定向到此前接收了原后继列表的任务;对接收方应用同样的基于状态逻辑

若前驱状态在注册过程中发生变化,API 必须保证:不为已完成的任务添加依赖、不递增引用计数。

底层实现:后继列表与顶点(vertex)

从实现角度看,该 API 要求每个前驱任务维护一个后继列表。列表中存放指向 vertex 实例 的指针,每个 vertex 表示一个后继任务,包含该后继任务的引用计数及其指针。vertex 在第一个前驱注册时创建,并被后续前驱复用。当某前驱任务完成时,它遍历自己的后继 vertex 列表并逐个递减引用计数;当某后继的引用计数归零时,该任务即可被调度执行。为避免不必要的调度开销,若某个后继的引用计数归零且用户提供的任务函数体中尚未绕过(bypass)其他任务,前驱任务可以绕过该后继任务。该实现思路如图:

oneTBB 前驱-后继依赖的底层实现:每个前驱维护一个后继顶点链表,顶点指向后继任务并携带引用计数

源码层面,该特性在 _task_handle.h 中以 task_dynamic_state 类承载:其成员 m_successor_list_head(原子后继链表头)、m_num_dependencies(依赖计数)、m_new_completion_point(转移指向)共同实现了上述逻辑;task_group.h 中的 set_task_order 两个重载分别从 task_handle 或 task_completion_handle 取出前驱的动态状态,再调用 add_successor(succ)。

转移完成:transfer_this_task_completion_to

基本语义

考虑把任务 current 的完成转移到任务 target(由 target_handler 拥有)的使用场景:应在 current 的函数体内部调用 tbb::task_group::transfer_this_task_completion_to(target_handler)。该函数把先前添加到当前执行任务的后继全部转移给 target。

按父 RFC 约定,在同一个 task_group 之外的任务中调用转移将导致未定义行为。当前提案把 API 限制为从执行中任务转移到 created 状态任务;转移到 submitted/executing/completed 状态的任务留待未来支持。调用该函数会把 current 与 target 的后继列表合并,并将合并结果赋给 target;同时要求:转移期间向 current 并发添加新后继(通过 set_task_order)必须是线程安全的。

将当前执行任务的后继(successors)转移到目标任务的基本示意

两种跟踪方案与竞态分析

转移之后如何管理 current 的后继列表,存在两种方案:

方案一:分开跟踪(separate tracking)。转移后 current 的后继列表为空,target 持有合并列表,两者各自独立跟踪;之后向任一方添加新后继只影响该方的列表。但该方案存在确定性缺陷:当新后继添加与转移并发发生时(例如线程 A 向任务 A 添加后继,同时任务 A 正在向 B 转移后继),存在逻辑竞态——新后继可能在转移前加入(随转移进入 B 的列表),也可能在转移后加入(留在 A 上),导致无法保证确定性的前驱-后继关系。

方案二:合并跟踪(merged tracking)。转移后 current 与 target 联合跟踪。这要求引入 task_completion_handle 的特殊状态——proxy 状态:若执行中的任务在函数体内调用 transfer_this_task_completion_to,则所有为该任务创建的完成句柄都转入 proxy 状态。此时 current 与 target 共享同一个合并后的后继列表,无论线性化顺序如何,任何新添加的后继都会同时出现在两者的列表中。

正如后文 Wavefront 组合递归示例 所示,现实中存在必须采用合并跟踪的场景:一个线程用 task_completion_handle 向 executing 状态的任务添加后继,同时另一个线程用 transfer_this_task_completion_to 用子树替换图中该任务。因此本文档最终采用合并后继跟踪方案。

备选方案与已剔除功能

备选方案一:task_handle 作为唯一所有者

保留 task_handle 作为各种状态任务的唯一所有者,并允许非空句柄用于设置或转移依赖。由于当前 API 只允许以右值方式提交 task_handle,提交后(例如 task_group::run(std::move(task_handle)))再使用该对象容易造成误导。为此需要为所有接受 task_handle 的函数增加接受非 const 左值引用的重载,并给出保证:

  • 接受右值引用的重载要求非空句柄,执行后置空(保持现状);
  • 接受左值引用的新重载也要求非空句柄,但提交后不置空,因此句柄可继续表示 submitted/executing/completed 状态的任务并设置依赖;在此类提交函数中复用句柄属于未定义行为。

所有提交函数(task_group::run、task_group::run_and_wait、task_arena::enqueue、this_task_arena::enqueue)都需扩展。当预览扩展启用时,从任务函数体返回指向非 created 状态任务的非空 task_handle 属未定义行为。

备选方案二:task_handle 作为共享所有者

让 task_handle 成为共享所有者,允许多个实例共同拥有同一任务。但由于任务只能被提交一次,在提交函数中使用 task_handle 会使所有副本失效,或将其置为只能用于设置任务间依赖的 "weak" 状态。

已剔除:向当前执行任务添加后继

早期提案允许 task_group::current_task::add_successor(task_handle&),用法如下:

tbb::task_group tg;

tg.run_and_wait([&tg] {
    tbb::task_handle succ1 = tg.defer(...);
    tbb::task_handle succ2 = tg.defer(...);

    tbb::task_group::current_task::add_successor(succ1);
    tbb::task_group::current_task::add_successor(succ2);

    tg.run(std::move(succ1));
    tg.run(std::move(succ2));

    // Run current task's computations
    run_computations();
});

该功能被剔除,因为其行为可通过调整操作顺序复现——在当前任务计算之后运行后继,或绕过其中一个:

tbb::task_group tg;

tg.run_and_wait([&tg] -> tbb::task_handle {
    tbb::task_handle succ1 = tg.defer(...);
    tbb::task_handle succ2 = tg.defer(...);

    // Run current task's computations
    run_computations();

    tg.run(std::move(succ1)); // run
    return std::move(succ2);  // bypass
});

已剔除:任务进度跟踪函数

早期版本包含 task_completion_handle::was_submitted() 与 is_completed() 成员函数。它们被排除的原因有二:缺乏令人信服的使用案例(现有示例无需这些函数即可实现);当任务执行 transfer_this_task_completion_to 时语义不清晰——例如任务 A 把完成转移给 B 后退出函数体,一方面 A 已提交并完成(两函数应返回 true),另一方面 A 在任务图中用 B 替换了自己,可能期望完成句柄现在指向 B 的完成(类似 set_task_order 中转移后新后继被重定向到 B 的行为)。

API 提案全览

namespace oneapi {
namespace tbb {

// Existing API
class task_handle;

// New APIs
class task_completion_handle {
public:
    task_completion_handle();

    task_completion_handle(const task_completion_handle& other);
    task_completion_handle(task_completion_handle&& other);

    task_completion_handle(const task_handle& handle);

    ~task_completion_handle();

    task_completion_handle& operator=(const task_completion_handle& other);
    task_completion_handle& operator=(task_completion_handle&& other);

    task_completion_handle& operator=(const task_handle& handle);

    explicit operator bool() const noexcept;
}; // class task_completion_handle

bool operator==(const task_completion_handle& t, std::nullptr_t) noexcept;
bool operator==(std::nullptr_t, const task_completion_handle& t) noexcept;

bool operator!=(const task_completion_handle& t, std::nullptr_t) noexcept;
bool operator!=(std::nullptr_t, const task_completion_handle& t) noexcept;

bool operator==(const task_completion_handle& t, const task_completion_handle& rhs) noexcept;
bool operator!=(const task_completion_handle& t, const task_completion_handle& rhs) noexcept;

class task_group {
    static void set_task_order(task_handle& pred, task_handle& succ);
    static void set_task_order(task_completion_handle& pred, task_handle& succ);

    static void transfer_this_task_completion_to(task_handle& h);
}; // class task_group

} // namespace tbb
} // namespace oneapi

task_handle 规范变更

~task_handle():销毁 task_handle 对象及其关联任务(若存在)。若关联任务是一个前驱或后继,则行为未定义。

task_completion_handle 类详解

构造、析构与赋值

  • task_completion_handle():构造一个不引用任何任务的空句柄。
  • task_completion_handle(const task_completion_handle& other):拷贝 other 到 *this;之后两者引用同一任务。
  • task_completion_handle(task_completion_handle&& other):移动 other 到 *this;之后 *this 引用 other 原先引用的任务,other 被置空。
  • task_completion_handle(const task_handle& handle):构造引用 handle 所拥有任务的完成句柄;若 handle 为空,行为未定义。
  • ~task_completion_handle():销毁该完成句柄。
  • operator=(const task_completion_handle& other):拷贝赋值,之后两者引用同一任务,返回 *this。
  • operator=(task_completion_handle&& other):移动赋值,之后 *this 引用 other 原先引用的任务,other 被置空,返回 *this。
  • operator=(const task_handle& handle):用 handle 拥有的任务替换 *this 引用的任务;若 handle 为空,行为未定义,返回 *this。

观察器

explicit operator bool() const noexcept:若 *this 引用任何任务返回 true,否则返回 false。

比较运算符

  • operator==(t, nullptr):t 为空返回 true,否则 false。
  • operator==(nullptr, t):等价于 t == nullptr。
  • operator!=(t, nullptr) 与 operator!=(nullptr, t):等价于 !(t == nullptr)。
  • operator==(lhs, rhs):lhs 与 rhs 引用同一任务返回 true,否则 false。
  • operator!=(lhs, rhs):等价于 !(lhs == rhs)。

这些运算符在 _task_handle.h 中有完整实现;其行为与 test_task_group.cpp 中 test task_completion_handle 测试用例一一对应(含空句柄的默认构造、拷贝/移动、nullptr 比较、多副本指向同一任务、经 task_arena::enqueue 提交后句柄依然非空等断言)。

task_group 成员函数详解

static void task_group::set_task_order(task_handle& pred, task_handle& succ)

把 pred 拥有的任务注册为前驱,它必须完成后 succ 拥有的任务才能开始执行。以下操作是线程安全的:并发向同一后继添加多个前驱;为多个后继注册同一前驱;向正在转移后继的任务和接收后继的任务并发添加后继。以下情况行为未定义:pred 或 succ 为空;pred 与 succ 的任务属于不同 task_group。

static void task_group::set_task_order(task_completion_handle& pred, task_handle& succ)

把 pred 所处理完成的任务注册为前驱。线程安全约定同上。行为未定义的情形:pred 或 succ 为空;两者任务属于不同 task_group;pred 引用的任务在未提交执行的情况下被销毁。

static void transfer_this_task_completion_to(task_handle& h)

把当前执行任务的完成转移给 h 拥有的任务。转移后,当前任务的后继将在 h 拥有的任务完成后执行。在 transfer_this_task_completion_to 执行后添加到当前执行任务的后继,同样会成为 h 的后继。线程安全约定:可在向 h 添加后继、或其他线程向当前执行任务添加后继的同时并发转移。行为未定义的情形:

  • h 是空 task_handle;
  • 在 task_group 任务函数体之外调用;
  • 对已完成转移的任务再次调用;
  • 当前执行任务与 h 的任务属于不同 task_group。

源码中该函数通过 d1::current_task_ptr() 获取当前执行任务指针,随后调用 transfer_completion_to(new_task)(见 task_group.h);提交函数(如 task_group::run)在预览扩展下会检查 task_ptr->has_dependencies() && !task_ptr->release_dependency(),有未决依赖的任务不会被立即 spawn(task_group.h、task_arena.h)。

潜在增强方向

RFC 还记录了若干暂未纳入提案的增强方向:

部分任务树销毁语义

task_group API 允许销毁收到的 task_handle 而不运行任务。销毁未提交的 task_handle 会释放其在 tg 的 wait_context 中预留的引用:

tbb::task_group tg;
{
    // 为 t 在 tg 的 wait_context 中预留了一个引用
    tbb::task_handle t = tg.defer(task_body);

    // 作用域结束时 t 被销毁,引用被释放
}
tg.wait(); // 立即返回,因为没有注册任何任务

问题在于:若某个前驱或后继被销毁且未提交,相关任务应如何表现。对于两个任务 p 与 s(s 是 p 的后继)且 p 未提交即被销毁,s 有两种可选行为:直接执行(前驱已消失,适合依赖仅约束共享资源访问的场景);无限等待(s 可能严格依赖 p 的结果)。对于三个相连任务 L1、L2、L3 且 L2 被销毁,则需回答 L1 的完成是否应保证先于 L3 执行。由于尚无具体的部分任务树销毁用例且所需行为未知,当前提案将其视为未定义行为,进入 supported 前需要定义该语义。

提交竞技场(arena)的保留

引入动态依赖会推迟任务的实际执行。当前设计中,一旦最后一个依赖被释放,任务会在完成最后一个前驱的线程所在 arena 中被 spawn——不一定是任务最初提交的 arena:

tbb::task_arena arena1;
tbb::task_arena arena2;
tbb::task_group tg;

tbb::task_handle pred = tg.defer(...);
tbb::task_handle succ1 = tg.defer(...);
tbb::task_handle succ2 = tg.defer(...);

tbb::task_group::set_task_order(pred, succ1);
tbb::task_group::set_task_order(pred, succ2);

arena1.execute([&] {
    tg.run(std::move(succ1));
    tg.run(std::move(succ2));
});

arena2.execute([&] {
    tg.run_and_wait(std::move(pred));
});

pred 被 arena2 中的线程完成后,succ1、succ2 变为可执行;其中一个被绕过、另一个被 spawn,导致二者实际在 arena2 执行——尽管它们是从 arena1 提交的。这在启用 arena 约束时可能引发性能问题。即使后继通过 task_arena::enqueue 提交也存在此问题。保留提交方法(run 还是 enqueue)对维持期望的调度语义(如 enqueue 的强制并发保证)可能很重要。从实现角度看,需要扩展 task_dynamic_state,增加指向任务提交处隐式或显式 arena 的指针及提交方法标志。

empty_task API

由于后继只能转移给单个任务,某些用例(如 N 体问题)需要创建仅用于同步的空任务,把子图中的多个末端任务汇聚起来再转移后继:

// N-body rectangle split
tbb::task_handle left_lower_rectangle_task = tg.defer(...);
tbb::task_handle right_upper_rectangle_task = tg.defer(...);
tbb::task_handle left_upper_rectangle_task = tg.defer(...);
tbb::task_handle right_lower_rectangle_task = tg.defer(...);

tbb::task_handle empty_sync_task = tg.defer([] {});

tbb::task_group::set_task_order(left_lower_rectangle_task, left_upper_rectangle_task);
tbb::task_group::set_task_order(left_lower_rectangle_task, right_lower_rectangle_task);
tbb::task_group::set_task_order(right_upper_rectangle_task, left_upper_rectangle_task);
tbb::task_group::set_task_order(right_upper_rectangle_task, right_lower_rectangle_task);

tbb::task_group::set_task_order(left_upper_rectangle_task, empty_sync_task);
tbb::task_group::set_task_order(right_lower_rectangle_task, empty_sync_task);

tbb::task_group::transfer_this_task_completion_to(empty_sync_task);

当前 TBB 实现中 empty_sync_task 仍会被 spawn 或绕过并执行,可能引入不必要的调度开销。可能的扩展是为 task_group 增加 get_empty_task() API——一种永不调度、依赖解析后即被跳过的任务类型;或者让 transfer_this_task_completion_to 接受多个任务参数,内部仍可创建同一个空同步任务。

向任意状态任务转移后继

当前提案用只接受 task_handle 参数来限制转移目标必须处于 created 状态。若未来需要,可为 transfer_this_task_completion_to 增加接受 task_completion_handle 的重载。实现层面这要求合并后继跟踪支持的不只是两个任务(发送方与接收方),而是整个任务集合——因为一个任务可能把完成转移给另一个同样在执行 transfer_this_task_completion_to 的任务,以此类推。

用 task_completion_handle 作为后继

当前提案通过只允许 task_handle 作为 set_task_order 第二参数来限制后继必须处于 created 状态。可考虑两项增强:允许引用 created 状态任务的 task_completion_handle 作为后继;允许引用 submitted 状态任务 T 的 task_completion_handle 作为后继,前提是 T 的其他尚未提交或仍在执行的前驱阻止了 T 被调度。相应需要增加 set_task_order(task_handle&, task_completion_handle&) 与 set_task_order(task_completion_handle&, task_completion_handle&) 重载;若第二参数引用 executing 或 completed 状态的任务,行为未定义。备选方案是提供把 task_completion_handle 转换为有效 task_handle 的函数(任务尚未开始时),返回的 task_handle 可用于添加新前驱,且需要重新提交执行。

从提交函数返回 task_completion_handle

也许有用的是不仅允许给 task_handle 表示的任务添加后继,也允许给通过接受函数对象的提交函数创建的任务添加后继:

tbb::task_group tg;
tbb::task_completion_handle ch = tg.run([] { /*task body*/ });
// ...

tbb::task_handle successor = tg.defer([] { /*successor body*/ });
tbb::task_group::set_task_order(ch, successor);

由于把 task_group::run 的返回类型改为 task_completion_handle 会给不需要返回值的场景带来额外开销,可通过新增提交函数或为 task_group::run 增加额外参数实现:

namespace oneapi {
namespace tbb {
class task_group {
    // Option 1 - introduce a new submission function
    template <typename Body>
    tbb::task_completion_handle run_and_get_completion_handle(const Body& body);

    // Option 2 - add overload with an extra argument
    template <typename Body>
    tbb::task_completion_handle run(const Body& body, additional-flag-argument);
};
} // namespace tbb
} // namespace oneapi

命名考量

本提案最初的 API 命名包括:task_tracker 类(表示任意状态的任务)、tbb::task_group::make_edge 函数(建立前驱-后继关系)、tbb::task_group::current_task::transfer_successors_to 函数(从当前执行任务移动后继)。最终命名决策如下:

  • task_tracker → task_completion_handle:task_tracker 的缺陷在于该类并不实际跟踪任务进度,仅表示任务以便添加后继;task_completion_handle 更能体现它与 set_task_order、transfer_this_task_completion_to 的相关性——二者都依赖任务完成。
  • make_edge → set_task_order:为强调与 flow graph 的 flow::make_edge(在图节点间建立永久边)的语义差异,改用 set_task_order。
  • transfer_successors_to → transfer_this_task_completion_to:原名称未能清晰描述转移的扩展效果;新名称强调当前任务的后继只有在 t 完成后才会继续执行。transfer_this_task_completion_to 与 task_completion_handle 的组合表明:转移后添加的后继会关联到接收完成的任务,完成句柄跟随任务的转移完成。

实现细节:task_dynamic_state 与源码印证

完整的实现细节见 implementation_details.md,此处概述关键点。

task_dynamic_state 类

新 API 的核心组件是 task_dynamic_state 类,它管理任务状态(进行中/完成/已转移)、维护后继列表、处理转移时与新任务的链接。任务组中每个有前驱或后继的任务都关联一个 task_dynamic_state 实例。其布局如下:

class task_dynamic_state {
private:
    task_handle_task*                  m_task;
    std::atomic<successor_list_node*>  m_successor_list_head;
    std::atomic<task_dynamic_state*>   m_new_dynamic_state;
    std::atomic<std::size_t>           m_num_dependencies;
    std::atomic<std::size_t>           m_num_references;
    small_object_allocator             m_allocator;
};
  • m_task:指向该动态状态关联的任务;
  • m_successor_list_head:后继链表头,同时充当任务完成或转移的标记;
  • m_new_dynamic_state:指向另一动态状态,任务在执行中调用 transfer_this_task_completion_to(new_task) 后指向 new_task 的动态状态;
  • m_num_dependencies:跟踪 m_task 被调度前必须完成的依赖数;
  • m_num_references 与 m_allocator:管理动态状态的生命周期(引用计数与分配释放)。

由于 set_task_order 允许已完成任务作为前驱,动态状态的生命周期必须延伸到任务完成之后——直到最后一个引用该任务的 task_completion_handle 被销毁。task_completion_handle 在实现上类似指向 task_dynamic_state 的共享指针:每次拷贝递增引用计数。它没有直接包装 std::shared_ptr<task_dynamic_state>,因为 task_handle_task 与 task_dynamic_state 含有指向 task_dynamic_state 的原子指针,而 std::atomic<std::shared_ptr> 是 C++20 扩展。

为减少不使用该特性的应用的额外开销,task_handle_task 中新增的原子指针字段初始为 nullptr,get_dynamic_state() 在首次调用时惰性创建动态状态(构造/赋值 task_completion_handle、调用 set_task_order、调用 transfer_this_task_completion_to 时)。多线程并发首次初始化同一任务时,各线程分配动态状态后用原子 CAS 竞争写入指针,失败的分配即被销毁。

后继列表的三态

task_dynamic_state 的后继链表头可以是三种状态:

  • alive(头指针为普通值,nullptr 也视为 alive):任务未完成且完成未被转移,可继续添加后继;
  • completed(头指针为 ~std::uintptr_t(0)):任务已完成,添加新后继不再引入真实依赖,后继在其他依赖满足后即可执行;
  • transferred(头指针为 ~std::uintptr_t(0) - 1):任务的完成已转移给另一任务,新后继应重定向到接收任务对应的动态状态(m_new_dynamic_state 指向该状态)。

提交与调度

接受 task_handle 的提交函数(task_group::run、task_group::run_and_wait、task_arena::enqueue、this_task_arena::enqueue)已更新以支持带依赖的任务:提交时检查任务是否还有依赖(m_num_dependencies 非零),若有则递减计数并暂不 spawn;计数归零后才被 spawn,或由最后一个释放后继列表的前驱绕过。

转移实现与生命周期问题

transfer_this_task_completion_to 通过设置当前执行任务动态状态中的 m_new_dynamic_state 指向 new_task 的动态状态来实现。为获取当前执行任务的指针,需新增库入口 tbb::detail::rN::d1::task* current_task_ptr():调度器从任何来源取出任务执行时,先把任务指针存入对应 task_dispatcher 对象,再调用 task::execute 或 task::cancel;任务体内发生阻塞式 TBB 调用而取出其他任务时,指针被临时替换、阻塞调用结束后恢复。

实现中还发现并解决了一个生命周期问题:任务 A 把完成转移给 B,B 执行完毕后其动态状态 B_state 被销毁;若此后通过 A 的完成句柄添加新后继,请求会被重定向到已销毁的 B_state,导致 use-after-free。解决方案是:A_state 存续期间为其指向的 B_state 递增引用计数(对每个把完成转移给 B 的任务动态状态同样处理),待 A_state 销毁时递减。

退出标准与待决问题

特性要推进到 supported 需要解决:

  • 定义本特性的性能目标;
  • 当前 API 名称是否清晰反映各自方法的目的;
  • 定义任务树部分销毁的语义(见上文);
  • 考虑依赖存在时提交函数与 arena 的保留(见上文);
  • 是否定义 task_completion_handle 与 task_handle 之间的比较函数;
  • 是否允许引用 created/submitted 状态任务的 task_completion_handle 作为 set_task_order 中的后继;
  • 是否提供 empty_task 辅助 API 优化空同步任务的创建与 spawn;
  • 是否引入返回 task_completion_handle 的提交函数。

高级实战示例

以下示例完整展示新 API 在真实并行算法中的用法。全部示例均以 tbb::task_group 为骨架,模式可概括为:分解 → 建立依赖 → 转移完成 → 提交。

递归斐波那契

递归斐波那契以并行方式计算第 N 个斐波那契数:每个第 N 个数由并行计算的第 N-1 与第 N-2 个数求和得到。计算第 N 个数的任务应创建两个子任务 subtask1、subtask2 分别计算第 N-1 与 N-2 个数,以及一个 merge_sum 任务求和。由于 merge_sum 必须在两个子任务完成后执行,需在 subtask1→merge_sum 与 subtask2→merge_sum 之间建立前驱-后继依赖;为保持任务图中的前驱-后继关系,当前执行任务应把后继转移给 merge_sum,用后者在图中替换自己:

int serial_fibonacci(int n) {
    if (n == 0 || n == 1) return n;
    return serial_fibonacci(n - 1) + serial_fibonacci(n - 2);
}

constexpr int serial_fibonacci_cutoff = 25;

void recursive_fibonacci_number(tbb::task_group& tg, int n, int* result_placeholder) {
    if (n <= serial_fibonacci_cutoff) {
        *result_placeholder = serial_fibonacci(n);
    } else {
        int* subtask1_placeholder = new int(0);
        int* subtask2_placeholder = new int(0);

        tbb::task_handle subtask1 = tg.defer([&tg, n, subtask1_placeholder] {
            recursive_fibonacci_number(tg, n - 1, subtask1_placeholder);
        });

        tbb::task_handle subtask2 = tg.defer([&tg, n, subtask2_placeholder] {
            recursive_fibonacci_number(tg, n - 2, subtask2_placeholder);
        });

        tbb::task_handle merge_sum = tg.defer([=] {
            *result_placeholder = *subtask1_placeholder + *subtask2_placeholder;
            delete subtask1_placeholder;
            delete subtask2_placeholder;
        });

        tbb::task_group::set_task_order(subtask1, merge_sum);
        tbb::task_group::set_task_order(subtask2, merge_sum);

        tbb::task_group::transfer_this_task_completion_to(merge_sum);

        tg.run(std::move(subtask1));
        tg.run(std::move(subtask2));
        tg.run(std::move(merge_sum));
    }
}

int fibonacci_number(int n) {
    tbb::task_group tg;
    int result = 0;
    tg.run_and_wait([&tg, &result, n] {
        recursive_fibonacci_number(tg, n, &result);
    });
    return result;
}

其依赖图如下(每个任务把自身替换为其 merge_sum 节点,从而保持图结构):

递归斐波那契的任务依赖图:两个子任务完成后才执行求和任务

N 体问题

并行 N 体模拟建模 N 个在太空中漂移的行星体,逐时间步计算各体的连续位置。由于第 i 个物体对第 j 个物体施加的力与第 j 个对第 i 个施加的力大小相等、方向相反,问题可归结为遍历矩阵上三角并在每个点计算力。该算法在 Parallel Programming with Cilk I 论文中有描述:把三角形分成两个更小的三角形和一个矩形;非相交的 i、j 索引上的并行计算只能在两个三角形间进行,蓝色矩形必须等两个三角形都完成后才能处理。每个子三角形按同样算法继续划分;矩形也可再划分,其黑、灰子矩形可并行计算。

用新 API 实现时,每个处理三角形的任务创建两个三角形子任务与一个矩形子任务,在三角形子任务与矩形子任务之间建立前驱-后继依赖,并把自身替换为 rectangle_subtask(转移后继)。每个处理矩形的任务创建四个子任务,在对应配对间建立依赖(保证黑、灰子矩形不同时计算),并创建一个空任务作为同步点、把当前任务的后继转移给它:

class Body;
void calculate_force(double& fx, double& fy, Body& body1, Body& body2);
void add_force(Body* body, double fx, double fy);

constexpr int threshold = 16;

void serial_calculate_and_update_forces(int i0, int i1, int j0, int j1,
                                        Body* bodies)
{
    for (int i = i0; i < i1; ++i) {
        for (int j = j0; j < j1; ++j) {
            // 更新 bodies[i] 受到的由 bodies[j] 施加的力向量
            // 以及对称地 bodies[j] 受到的由 bodies[i] 施加的力向量
            if (i == j) continue;

            double fx, fy;
            calculate_force(fx, fy, bodies[i], bodies[j]);
            add_force(&bodies[i], fx, fy);
            add_force(&bodies[i], -fx, -fy);
        }
    }
}

// 遍历矩形 i0 <= i <= i1, j0 <= j <= j1
void n_body_rectangle(tbb::task_group& tg,
                      int i0, int i1, int j0, int j1,
                      Body* bodies)
{
    int di = i1 - i0;
    int dj = j1 - j0;
    if (di <= threshold || dj <= threshold) {
        serial_calculate_and_update_forces(i0, i1, j0, j1, bodies);
    } else {
        int im = i0 + di / 2;
        int jm = j0 + dj / 2;

        tbb::task_handle left_lower_subtask = tg.defer([=, &tg] {
            n_body_rectangle(tg, i0, im, j0, jm, bodies);
        });

        tbb::task_handle right_upper_subtask = tg.defer([=, &tg] {
            n_body_rectangle(tg, im, i1, jm, j1, bodies);
        });

        tbb::task_handle left_upper_subtask = tg.defer([=, &tg] {
            n_body_rectangle(tg, i0, im, jm, j1, bodies);
        });

        tbb::task_handle right_lower_subtask = tg.defer([=, &tg] {
            n_body_rectangle(tg, im, i1, j0, jm, bodies);
        });

        tbb::task_handle sync = tg.defer([] {});

        tbb::task_group::set_task_order(left_lower_subtask, left_upper_subtask);
        tbb::task_group::set_task_order(left_lower_subtask, right_lower_subtask);
        tbb::task_group::set_task_order(right_upper_subtask, left_upper_subtask);
        tbb::task_group::set_task_order(right_upper_subtask, right_lower_subtask);

        tbb::task_group::set_task_order(left_upper_subtask, sync);
        tbb::task_group::set_task_order(right_lower_subtask, sync);

        tbb::task_group::transfer_this_task_completion_to(sync);

        tg.run(std::move(left_lower_subtask));
        tg.run(std::move(right_upper_subtask));
        tg.run(std::move(left_upper_subtask));
        tg.run(std::move(right_lower_subtask));
        tg.run(std::move(sync));
    }
}

// 遍历三角形 n0 <= i <= j <= n1
void n_body_triangle(tbb::task_group& tg, int n0, int n1, Body* bodies) {
    int dn = n1 - n0;
    // 若 dn == 1,单个体与自身无相互作用,什么都不做
    if (dn != 1) {
        int nm = n0 + dn / 2;
        tbb::task_handle triangle_subtask1 = tg.defer([=, &tg] {
            n_body_triangle(tg, n0, nm, bodies);
        });

        tbb::task_handle triangle_subtask2 = tg.defer([=, &tg] {
            n_body_triangle(tg, nm, n1, bodies);
        });

        tbb::task_handle rectangle_subtask = tg.defer([=, &tg] {
            n_body_rectangle(tg, n0, nm, nm, n1, bodies);
        });

        tbb::task_group::set_task_order(triangle_subtask1, rectangle_subtask);
        tbb::task_group::set_task_order(triangle_subtask2, rectangle_subtask);

        tbb::task_group::transfer_this_task_completion_to(rectangle_subtask);

        tg.run(std::move(triangle_subtask1));
        tg.run(std::move(triangle_subtask2));
        tg.run(std::move(rectangle_subtask));
    }
}

void calculate_forces(int n_bodies, Body* bodies) {
    tbb::task_group tg;
    tg.run_and_wait([&tg, n_bodies, bodies] {
        n_body_triangle(tg, 0, n_bodies, bodies);
    });
}

Wavefront

Wavefront 是一种科学编程模式:数据元素分布在多维网格上,因元素间依赖必须按特定顺序计算。考虑二维 wavefront:从网格左上角开始,每个元素 (i,j) 在其两个依赖子元素完成后才能计算——右上依赖 (i, j-1)(若存在)与左上依赖 (i-1, j)(若存在)。因此网格中同一反对角线上的元素无相互依赖,可并行计算:

二维网格 Wavefront 计算模式:同色反对角线元素可并行计算

非递归方法

最简单的方式是执行前先创建所有单元格计算任务并建立依赖:

void compute_cell(int i, int j);

void non_recursive_wavefront(int in, int jn) {
    tbb::task_group tg;

    std::vector<std::vector<tbb::task_handle>> cell_tasks;

    cell_tasks.reserve(in);

    for (int i = 0; i < in; ++i) {
        cell_tasks[i].reserve(jn);

        for (int j = 0; j < jn; ++j) {
            cell_tasks[i].emplace_back(tg.defer([=] { compute_cell(i, j); }));

            // 右上依赖
            if (j != 0) { tbb::task_group::set_task_order(cell_tasks[i][j - 1], cell_tasks[i][j]); }

            // 左上依赖
            if (i != 0) { tbb::task_group::set_task_order(cell_tasks[i - 1][j], cell_tasks[i][j]); }
        }
    }

    // 运行任务图
    for (int i = 0; i < in; ++i) {
        for (int j = 0; j < jn; ++j) {
            tg.run(std::move(cell_tasks[i][j]));
        }
    }
    tg.wait();
}

经典递归方法

另一种实现是分治策略的递归网格切分:初始任务把网格切成四个子任务,每个子任务递归切成四个,依此类推。每个任务创建 north_subtask、west_subtask、east_subtask、south_subtask 四个子任务,并建立依赖:north→west、north→east、west→south、east→south。为保持图结构,当前执行任务用 south_subtask 替换自己(转移后继):

void compute_cell(int i, int j);

void serial_wavefront(int i0, int in, int j0, int jn) {
    for (int i = i0; i < in; ++i) {
        for (int j = j0; j < jn; ++j) {
            compute_cell(i, j);
        }
    }
}

constexpr int threshold = 4;

void classic_recursive_wavefront_task(tbb::task_group& tg, int i0, int in, int j0, int jn) {
    int di = in - i0;
    int dj = jn - j0;

    if (di <= threshold || dj <= threshold) {
        serial_wavefront(i0, in, j0, jn);
    } else {
        int im = i0 + di / 2;
        int jm = j0 + dj / 2;

        tbb::task_handle north_subtask = tg.defer([=, &tg] {
            classic_recursive_wavefront_task(tg, i0, im, j0, jm);
        });

        tbb::task_handle west_subtask = tg.defer([=, &tg] {
            classic_recursive_wavefront_task(tg, i0, im, jm, jn);
        });

        tbb::task_handle east_subtask = tg.defer([=, &tg] {
            classic_recursive_wavefront_task(tg, im, in, j0, jn);
        });

        tbb::task_handle south_subtask = tg.defer([=, &tg] {
            classic_recursive_wavefront_task(tg, im, in, jm, jn);
        });

        tbb::task_group::set_task_order(north_subtask, west_subtask);
        tbb::task_group::set_task_order(north_subtask, east_subtask);
        tbb::task_group::set_task_order(west_subtask, south_subtask);
        tbb::task_group::set_task_order(east_subtask, south_subtask);

        tbb::task_group::transfer_this_task_completion_to(south_subtask);

        tg.run(std::move(north_subtask));
        tg.run(std::move(west_subtask));
        tg.run(std::move(east_subtask));
        tg.run(std::move(south_subtask));
    }
}

void classic_recursive_wavefront(int in, int jn) {
    tbb::task_group tg;
    tg.run_and_wait([=, &tg] {
        classic_recursive_wavefront_task(tg, 0, in, 0, jn);
    });
}

经典方法的主要缺点是引入了任务间本不存在的额外依赖。例如任务 21 逻辑上只依赖 12,却要等 14 完成才开始执行。

急切递归方法

改进方案(急切递归,eager recursion)出自 Cache-Oblivious Wavefront 论文。在该递归模型中,每个切分任务预期其依赖任务也会切分,并向它们通知所需的子任务,从而只建立真实依赖。急切版本同样创建 north/west/east/south 四个子任务并建立与经典方法相同的依赖;第一次切分无需额外动作(切分整个网格 [0,n) 的任务没有后继)。但在第二次切分时——即 north、west、east、south 子任务执行时——每个任务必须向其后继通知需要建立的依赖子任务。

后继通过以下方式被通知:为相应子任务创建 task_completion_handle 对象并存入后继可访问的共享容器。关键点是:建立这些额外依赖时,被引用的子任务可能已处于 submitted 状态,甚至可能已完成——这凸显了 set_task_order 允许任意状态任务作为前驱的重要性。急切递归持续切分直到达到期望深度,其完整实现(含 prepare_predecessors_container、publish_predecessor、find_predecessor 等辅助逻辑,及 wavefront_grainsize 粒度和按层存储前驱的 predecessors_container_type)较长,完整代码见 extended_semantics.md 的 "Eager recursive approach" 小节。

急切与经典组合递归

组合方案在前两层使用急切切分,对第二层创建的每个子任务使用经典切分。在 "Eager 2" 阶段,蓝、红子任务之间的依赖通过引用蓝色子任务的 task_completion_handle 建立;依赖建立时蓝色子任务可能已在执行。经典切分阶段,每个 "Eager 2" 子任务通过转移后继,在图中用对应的 south 子任务替换自己。由于红色子任务只能访问引用转移前蓝色子任务的 task_completion_handle,且蓝色子任务可能已把完成转移给经典子任务,因此要正确建立 "Eager 2" 层依赖,所有通过已完成转移任务的 task_completion_handle 添加的后继,都必须作用于接收了这些后继的任务——这正是前面所述"合并后继跟踪"方案必须实现的原因。

文件解析器

文件解析器示例模拟 XML 或 C++ 头文件解析器。考虑一组文件 file1...fileN,每个文件可能包含集合中一个或多个其他文件,且包含关系无环。解析从 fileN 开始。每个文件分两个阶段处理:解析(打开文件、读取内容、识别包含的文件并启动其处理)与收尾(把处理结果写入输出文件并执行收尾步骤)。

串行实现中,FileInfo 类通过 read() 填充 m_includes,write() 写输出文件,try_process() 尝试把当前 FileInfo 插入共享哈希表 fileMap:插入成功则继续处理该文件,否则说明文件已处理过、返回表中已有的 FileInfo;串行的 process() 依次执行 parse() 与 finalize()。

并行版本的关键改造(完整代码见 extended_semantics.md 的 "File Parser" 小节):

  • map_type 改为 tbb::concurrent_unordered_map<std::string, FileInfo*>,支持并行处理期间的线程安全插入与查找;
  • 每个 FileInfo 持有 task_group 引用、拥有解析任务的 task_handle(m_parse_task)以及初始指向该任务的 task_completion_handle(m_task_completion_handle);
  • process() 提交解析任务;
  • parse() 读取文件、创建收尾任务、对每个被包含文件建立"该文件解析任务的完成句柄 → 收尾任务"的依赖,随后调用 transfer_this_task_completion_to(finalize_task) 用收尾任务替换自己并提交收尾任务。

由于 try_process() 会触发解析任务的执行,依赖建立时解析任务可能处于 submitted、executing 或 completed 状态;解析任务还可能已把后继转移给收尾任务,因此 set_task_order 必须把后继添加到收尾任务上——这再次证明了合并后继跟踪的必要性(m_task_completion_handle 最初引用的是解析任务的完成)。

从 File 5 的解析过程可以观察到完整的动态图演化:处理 File 5 创建收尾任务 f5f 与两个解析任务 f4p、f3p(依赖建立时它们至少处于 submitted 状态);f3p 执行后创建 f3f 与 f2p、f1p,建立依赖后把完成转移给 f3f 并被销毁;f4p 执行时发现 File 2 的任务已在解析 File 3 时创建,而 File 3 的完成句柄虽最初指向 f3p,但 f3p 已把后继转移给 f3f,因此新依赖须经完成句柄加到 f3f 上;依此类推,f4p 把后继 f5f 转移给 f4f,f2p 创建 f2f 并连接 f1p,f1p 因无依赖直接替换为收尾任务。最终 File 1 先被收尾,随后 File 2、File 3、File 4、File 5 依次收尾。

总结

动态任务依赖扩展为 oneTBB 的 task_group 补齐了表达非树状动态任务图的能力。设计上它坚持 task_handle 的既有语义,以新增的 task_completion_handle 承担任意状态任务的表示,以 set_task_order 建立前驱-后继关系,以 transfer_this_task_completion_to 支持递归任务图的图内替换,并以"合并后继跟踪"保证并发场景下依赖关系的确定性。底层由 task_dynamic_state 以原子后继链表、依赖计数与引用计数实现,相关代码集中在 _task_handle.h、task_group.h 与 task_arena.h,测试覆盖见 test_task_group.cpp。该特性当前为 RFC 提案状态,需定义性能目标与若干语义细节后才能推进为 supported 特性。

登录后查看全文
oneTBB