oneTBB 动态任务依赖扩展:task_group 的 task_completion_handle 与 set_task_order 完整语义指南
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 正是为填补这两个空白而设计的三项扩展:
- 扩展
task_handle的语义与有效生命周期,使其可表示已提交、执行中、已完成的任务; - 新增设置任务间依赖关系的函数;
- 新增把当前执行任务的后继(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)其他任务,前驱任务可以绕过该后继任务。该实现思路如图:
源码层面,该特性在 _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)必须是线程安全的。
两种跟踪方案与竞态分析
转移之后如何管理 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)(若存在)。因此网格中同一反对角线上的元素无相互依赖,可并行计算:
非递归方法
最简单的方式是执行前先创建所有单元格计算任务并建立依赖:
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 特性。



