mold 内嵌 TBB 的 parallel_reduce 归约算法全解析：函数签名、两种形式与并行求和实战

mold 内嵌 TBB 的 parallel_reduce 归约算法全解析函数签名、两种形式与并行求和实战【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold导读mold一个现代链接器在实现并行链接流水线时大量借助了内嵌在仓库third-party/tbb中的 oneAPI Threading Building BlocksTBB并行算法库。本文以 TBB 官方规范文档中parallel_reduce一节parallel_reduce_func.rst为骨架系统讲解这一对区间执行归约reduction的并行算法包括 8 种重载签名、四种 partitioner 的取舍、函数式与命令式两种形式、底层的递归分割与 join 合并语义以及完整的数组求和实战代码。读完本文你将能够在自己的并行程序或修改 mold 链接器中正确、高效地使用parallel_reduce并理解它与parallel_for、parallel_deterministic_reduce等兄弟算法的关系。一、什么是 parallel_reduceparallel_reduce是一个对区间range计算归约结果的函数模板定义于头文件oneapi/tbb/parallel_reduce.h中。所谓归约即把区间内所有元素通过一个二元运算合并为一个结果例如求和、求最大值、矩阵连乘等。TBB 将该算法设计为两种形式对应不同的使用场景函数式形式functional formparallel_reduce(range, identity, func, reduction)专为配合 lambda 表达式使用一行代码即可完成并行归约返回归约结果。命令式形式imperative formparallel_reduce(range, body)通过一个自定义body对象累积结果最小化数据复制适合对性能敏感或需要携带复杂中间状态的场景。二、函数签名与全部重载TBB 规范给出了 8 个重载按是否传入 partitioner 与task_group_context分为两组// Defined in header oneapi/tbb/parallel_reduce.h namespace oneapi { namespace tbb { // ---------- 函数式形式返回归约后的 Value ---------- templatetypename Range, typename Value, typename Func, typename Reduction Value parallel_reduce(const Range range, const Value identity, const Func func, const Reduction reduction, /* see-below */ partitioner, task_group_context context); templatetypename Range, typename Value, typename Func, typename Reduction Value parallel_reduce(const Range range, const Value identity, const Func func, const Reduction reduction, /* see-below */ partitioner); templatetypename Range, typename Value, typename Func, typename Reduction Value parallel_reduce(const Range range, const Value identity, const Func func, const Reduction reduction, task_group_context context); templatetypename Range, typename Value, typename Func, typename Reduction Value parallel_reduce(const Range range, const Value identity, const Func func, const Reduction reduction); // ---------- 命令式形式结果累积进 body ---------- templatetypename Range, typename Body void parallel_reduce(const Range range, Body body, /* see-below */ partitioner, task_group_context context); templatetypename Range, typename Body void parallel_reduce(const Range range, Body body, /* see-below */ partitioner); templatetypename Range, typename Body void parallel_reduce(const Range range, Body body, task_group_context context); templatetypename Range, typename Body void parallel_reduce(const Range range, Body body); } // namespace tbb } // namespace oneapi各参数含义参数含义range要归约的区间必须满足 Range 需求如blocked_rangefloat*见 blocked_range 类文档identityfunc的operator()的左单位元left identity element即func(r, identity) 对 r 的归约结果例如求和时为0func对每个子区间做局部归约的函数可传 lambdareduction合并两个局部结果的二元运算符可传 lambdabody命令式形式的状态对象内部持有累积结果partitioner控制区间如何切分与负载均衡的划分器详见下文context可选的任务组上下文控制任务执行的调度环境三、partitioner控制切分策略的第四种参数partitioner形参签名中标为/* see-below */允许以下四种实体之一const auto_partitionerconst simple_partitionerconst static_partitioneraffinity_partitioner四者的取舍参考 TBB 规范中的分区器章节affinity_partitioner、auto_partitioner、simple_partitioner、static_partitionerauto_partitioner默认自动感知负载与线程数动态切分并粗化coarsen子区间多数场景的推荐选择simple_partitioner持续递归切分直到每个子区间不可再分!r.is_divisible()。注意它不会自动粗化配合blocked_range使用时必须显式指定合适的 grain size——默认 grain size 为 1会让子区间过碎而严重损失效率simple_partitioner 文档对此有专门提示static_partitioner一次静态切分任务开销最小适合已知负载均衡良好的场景affinity_partitioner记录子区间与线程的亲和关系供后续并行循环复用改善缓存局部性。四、类型需求Range / Body / Func / Reduction / Valueparallel_reduce对参与类型有明确的接口约束TBB 规范将其拆分为四个命名需求文档Range必须满足 Range 需求可分割、可判断is_divisible()。Value必须满足 ISO C 标准的CopyConstructible可复制构造与CopyAssignable可复制赋值需求因为中间结果会在线程间传递与合并。Func函数式形式必须满足 ParallelReduceFunc 需求核心签名是Value Func::operator()(const Range range, Value x) const;即以初始值x起步对range内元素累积计算返回该子区间的归约值。此外自 C17 起Func也可以是Range中某个接收const Value、返回Value的 const 成员函数指针。Reduction函数式形式必须满足 ParallelReduceReduction 需求核心签名是Value Reduction::operator()(Value x, Value y) const;即合并两个局部结果x与y返回合并值。Body命令式形式必须满足 ParallelReduceBody 需求要求提供三个关键成员成员语义Body::Body(Body, split)分割构造函数splitting constructor必须能与operator()及join并发运行void Body::operator()(const Range range)对子区间累积结果void Body::join(Body rhs)把rhs的结果并入this的结果五、工作方式递归分割、body 复制与 join 合并parallel_reduce的并行机制可以概括为分而治之 树形合并递归分割区间算法把range递归切分为子区间直到每个子区间is_divisible()为 false 为止分割构造 body每次区间被切分时算法通过分割构造函数为每个线程复制出一个或多个 body 副本parallel_reduce可能在一个 body 的operator()或join正在并发执行时复制该 body因此你有责任保证这种并发的安全性——在典型用法中通常无需额外努力例如 body 只维护一个普通值成员局部累积每个 body 副本在其负责的子区间上反复调用operator()累积局部结果join 合并每完成一次 body 分割就调用对应 body 的join方法把两个副本的结果合并。join的约定是this更新为this与rhs的累积结果。归约运算只需满足结合律associative不必满足交换律commutative。对非交换运算op规范明确要求left.join(right)应将left更新为left op right的结果即保持左到右的语义顺序。例如op可以是矩阵乘法——非交换但结合完全可以用于parallel_reduce。规范还强调两点实现语义body 只有在区间被切分时才可能被切分但反之不一定body 的切分与否由算法非确定性地决定用户既不能依赖某个特定的 body 切分方案也不能假设某个 body 对象处理的子区间是连续的。串行执行时parallel_reduce与parallel_for一样从左到右顺序执行且永远不会调用分割构造函数和join方法——这保证了命令式形式在串行/并行下逻辑一致性。所有重载都可接受一个 task_group_context 对象使算法任务在该上下文中执行默认情况下算法运行在它自己绑定的上下文中。六、实战示例一命令式形式自定义 Body以下代码摘自 TBB 规范文档对数组求和是命令式形式的标准写法#include oneapi/tbb/parallel_reduce.h #include oneapi/tbb/blocked_range.h using namespace oneapi::tbb; struct Sum { float value; Sum() : value(0) {} Sum( Sum s, split ) {value 0;} // 分割构造函数副本从 0 开始 void operator()( const blocked_rangefloat* r ) { // 局部累积 float temp value; for( float* ar.begin(); a!r.end(); a ) { temp *a; } value temp; } void join( Sum rhs ) {value rhs.value;} // 合并两个副本的结果 }; float ParallelSum( float array[], size_t n ) { Sum total; parallel_reduce( blocked_rangefloat*( array, arrayn ), total ); return total.value; }观察这个例子的三个要点Sum( Sum s, split )是分割构造函数参数表中的split是 TBB 的 tag 类型编译器据此区分复制构造与分割构造。注意其函数体将value初始化为 0而非复制源对象operator()先把value读入局部变量temp再累加减少对成员变量的反复读写也避免多个调用交错时的数据竞争join合并子区间结果通过join汇入主 body。该示例可泛化为任意结合运算op只需三步把代码中的0替换为op的单位元identity element把替换为op的赋值形式或其逻辑等价写法把结构体名Sum改为与op语义相符的名字。由于归约运算可以是非交换的如矩阵乘法这种泛化在数学上依然成立。七、实战示例二函数式形式lambda 表达式同样的数组求和用 lambda 与函数式形式改写后简洁得多#include oneapi/tbb/parallel_reduce.h #include oneapi/tbb/blocked_range.h using namespace oneapi::tbb; float ParallelSum( float array[], size_t n ) { return parallel_reduce( blocked_rangefloat*( array, arrayn ), // range整个数组 0.f, // identity左单位元 [](const blocked_rangefloat* r, float init)-float { // func局部归约 for( float* ar.begin(); a!r.end(); a ) init *a; return init; }, []( float x, float y )-float { // reduction合并局部结果 return xy; } ); }函数式形式把累积状态init显式地在 lambda 之间传递返回值即最终归约结果无需自定义结构体也无需手写分割构造函数与 join。它的代价是Value此处为float在分割/合并过程中会被复制因此当Value是巨大对象时应改用命令式形式以最小化复制。八、复杂度TBB 规范给出的空间复杂度为若 range 与 body 占用 O(1) 空间且 range 被切分为近似均匀的片段则空间复杂度为 O(P×log(N))其中 N 为 range 的大小P 为线程数。每个线程同时只保留 O(log N) 层递归的中间结果这保证了即使在大数组上并行归约内存占用依然可控。九、延伸对比parallel_deterministic_reduce与parallel_reduce密切相关的是 parallel_deterministic_reduce定义于同一头文件oneapi/tbb/parallel_reduce.h。两者结构几乎相同但后者承诺确定性的 split/join 行为无论多少线程参与、任务如何映射到线程对给定参数它执行的 split 与 join 操作序列完全一致若用户函数本身也确定多次调用结果必定相同但可能与等价串行算法的结果不同为此它只接受simple_partitioner或static_partitioner因为其他分区器会响应随机的工作窃取work stealing行为使用simple_partitioner时务必指定合适的 grain size规范对此有专门警告。十、mold 中的 TBB 实践同一算法族在链接器中的落地mold 仓库内嵌了完整的 TBB 源码third-party/tbb/链接器实现大量使用该算法族。从源码看gc-sections.cc 使用tbb::concurrent_unordered_map与tbb::concurrent_vector管理 GC 根集合并用tbb::parallel_for_each并行遍历所有目标文件arch-arm32.cc第 810、827 行附近用tbb::parallel_for并行处理重定位条目第 873 行用tbb::parallel_for_each遍历对象文件arch-ppc64v1.cc第 568 行附近同样以tbb::parallel_for_each并行扫描对象文件。从源码结构看mold 目前主要直接使用parallel_for/parallel_for_each这类遍历型并行算法而parallel_reduce作为同一算法族中面向归约的成员其函数式/命令式两种形式、partitioner 选择、join语义等设计正是 mold 内嵌 TBB 并行设施中聚合类计算的通用答案——凡是需要把并行子结果合并为单一结果如统计、哈希聚合、极值扫描的场景均可按本文的模式套用。十一、使用建议与注意事项小结优先函数式形式配合 lambda 最简洁适合Value轻量标量、简单结构的场景命令式形式用于重型状态当累积状态复杂、复制代价高时用自定义 Body并正确实现分割构造函数、operator()与join牢记结合律、不要求交换律非交换运算务必让join保持left op right的顺序语义并行安全分割构造函数可能与其他成员并发运行确保 Body 状态不被裸共享partitioner 按需选择默认 auto 即可追求确定性用simple_partitioner/static_partitioner 显式 grain size不要依赖切分细节body 切分是非确定性的子区间也不保证连续代码必须对这些不变量免疫需要可复现结果时切换到parallel_deterministic_reduce并注意其结果可能异于串行算法。延伸阅读parallel_reduce 规范原文parallel_deterministic_reduce 规范ParallelReduceBody 需求、ParallelReduceFunc 需求、ParallelReduceReduction 需求Range 需求、blocked_range 类文档、Partitioners 章节mold 中的 TBB 使用实例gc-sections.cc、arch-arm32.cc、arch-ppc64v1.cc【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考