mold 内嵌 oneTBB 指南精读parallel_reduce 并行归约模板详解与实现剖析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本指南基于当前仓库内嵌的 oneTBBIntel Threading Building Blocks官方用户指南文档 parallel_reduce.rst 展开系统讲解模板parallel_reduce的使用方式、Body 类的三个核心接口operator()、splitting constructor、join及其底层任务调度原理。本文面向需要在 C 项目中把求和、求极值、字符串拼接等归约型循环并行化的开发者读完即可独立编写正确的parallel_reduceBody 类并理解其分拆split与合并join的完整执行流程。上图为 oneTBB 用户指南中 parallel_reduce 的分拆-合并序列示意图原文档 fig5箭头表示时间先后顺序。一、动机从串行归约循环说起归约reduction是最常见的循环模式之一——把整个迭代空间上的计算结果汇总成一个值。用户指南给出了一个最典型的串行求和示例float SerialSumFoo( float a[], size_t n ) { float sum 0; for( size_t i0; i!n; i ) sum Foo(a[i]); return sum; }这段代码的循环体是可交换且可结合的累加操作迭代之间互不依赖。这正是 oneTBB 中parallel_reduce的用武之地它把区间切分成多个子区间让不同工作线程各自累加出子和最后再把子和合并起来。串行版本中那个唯一的sum变量在并行版本中会被复制成多个实例各自独立累加、最后归并。二、最小并行化示例ParallelSumFoo若迭代相互独立可用模板类parallel_reduce将上述循环并行化float ParallelSumFoo( const float a[], size_t n ) { SumFoo sf(a); parallel_reduce( blocked_rangesize_t(0,n), sf ); return sf.my_sum; }这里做了三件事构造 Body 对象sf持有输入数组指针与归约结果my_sum用blocked_rangesize_t(0,n)描述要迭代的半开区间[0, n)调用parallel_reduce(range, body)结束后从sf.my_sum读取归约结果。parallel_reduce的全部入口重载定义在 parallel_reduce.h其中最基本的形态就是void parallel_reduce(const Range range, Body body)默认使用__TBB_DEFAULT_PARTITIONER即auto_partitioner。由于 Body 是按引用传入的调用结束后你仍能从原对象中取回归约结果。三、Body 类 SumFoo 的完整定义归约的细节——如何累加子区间、如何合并子结果——全部由 Body 类承担。SumFoo的定义如下用户指南原文class SumFoo { float* my_a; public: float my_sum; // 对子区间 [r.begin(), r.end()) 执行累加 void operator()( const blocked_rangesize_t r ) { float *a my_a; float sum my_sum; size_t end r.end(); for( size_t ir.begin(); i!end; i ) sum Foo(a[i]); my_sum sum; } // 拆分构造函数为工作线程复制只读信息并把结果初始化为单位元(0) SumFoo( SumFoo x, split ) : my_a(x.my_a), my_sum(0) {} // 合并方法把 y 的累积结果并入 this void join( const SumFoo y ) { my_sum y.my_sum; } SumFoo( float a[] ) : my_a(a), my_sum(0) {} };与parallel_for中的ApplyFoo相比这个类有三处关键差异operator()不是const的。它必须更新SumFoo::my_sum因此不能在方法内部修改成员状态。必须提供 splitting constructor拆分构造函数签名形如SumFoo(SumFoo x, split)。必须提供join方法负责把另一个 Body 实例的累积结果合并进当前实例。split 类型的作用splitting constructor 接收两个参数对原始对象的引用x以及一个库定义的哑元类型split的临时对象。这个哑元参数的作用是把 splitting constructor 与拷贝构造函数区分开来——SumFoo(SumFoo x)是拷贝构造而SumFoo(SumFoo x, split)是拆分构造编译器可以据此进行重载决议。split类型定义在 _range_common.h注释明确写着它是用于区分拆分构造函数与拷贝构造函数的哑元类型。同文件中还有proportional_split带左右比例的拆分类型供支持按比例拆分的 Range 使用。四、分拆-合并序列parallel_reduce 的执行模型当任务调度器判定有空闲工作线程可用时parallel_reduce会调用 splitting constructor 为工作线程创建一个子任务子任务完成后再用join方法把子任务的结果累积回父任务。上文图片展示的就是这一 split-join 序列原始对象x先被拆分出y两个分支分别对各自区间做归约最后y的结果通过join合并进x。图中的箭头表示时间顺序这里蕴含一个重要的并发约束splitting constructor 可能与对象x正在执行前半段归约operator()并发运行。因此构造y时对x的一切读取操作都必须是线程安全的——如果 splitting constructor 需要递增一个与其他对象共享的引用计数必须使用原子递增操作。从源码看这一机制由 parallel_reduce.h 中的start_reduce任务与reduction_tree_node树节点实现start_reduce::execute在右侧子任务执行时会通过new( zombie_space.begin() ) Body(*my_body, split())在reduction_tree_node::zombie_space中就地构造拆分出的右 Bodyoffer_work负责派生右兄弟任务并挂到新的父节点上父节点引用计数为 2子任务完成回调fold_tree递减父节点引用计数最后一个完成的子任务在reduction_tree_node::join中执行left_body.join(*zombie_space.begin())完成合并整个归约树在finalize中展开销毁归还任务内存。这解释了左右子树各有一个 Body 实例合并动作在父节点完成的树形归约结构。没有空闲工作线程时怎么办如果调度器认为没有工作线程可用区间后半段会由处理前半段的同一个 Body 对象继续归约——也就是说第二半的归约从第一半结束的地方接着累加。此时 split 与 join 根本不会被调用。⚠️警告一由于没有工作线程时不使用 split/joinparallel_reduce并不保证一定会做递归拆分。不要编写依赖必定发生拆分的逻辑。operator() 绝不能丢弃已有累积⚠️警告二由于同一个 Body 可能被用来累积多个子区间operator()中绝不能丢弃之前已累积的结果。下面的错误写法是典型的反例class SumFoo { ... public: float my_sum; void operator()( const blocked_rangesize_t r ) { ... float sum 0; // 错误应为 sum my_sum ... for( ... ) sum Foo(a[i]); my_sum sum; } ... };把sum my_sum误写成sum 0后Body 只会返回最后一个子区间的部分和而不是parallel_reduce应用于它的所有子区间的总和——结果将严重偏小且不可复现。这一约束在源码的 Body 概念要求parallel_reduce.h中同样有明确说明operator()应用于区间r并累积结果。五、局部临时变量优化技巧用户指南特别给出了一条性能建议在operator()的定义中用局部临时变量如示例中的a、sum、end缓存循环体内访问的标量值。这可以向编译器明确传达这些值可以保存在寄存器而非内存中从而提升性能。适用条件需要谨慎判断如果值太大放不进寄存器或取地址方式让编译器无法跟踪该技巧可能无效对典型优化编译器而言只对被写的变量如示例中的sum使用局部临时通常就够了——编译器能推断出循环不会写其他位置从而把其他读取提升到循环外。六、Partitioner 与 grain size 规则parallel_reduce对 partitioner 和 grain size 的规则与parallel_for完全一致。parallel_reduce支持显式传入 partitioner 的重载simple_partitioner、auto_partitioner、static_partitioner、affinity_partitioner以及各自的带task_group_context版本全部在 parallel_reduce.h 中成对提供。oneTBB 用户指南的 Partitioner_Summary.rst 汇总了四种 partitioner 与blocked_range(i,j,g)搭配时的分块行为Partitioner说明与blocked_range(i,j,g)搭配时的分块大小simple_partitioner分块大小受 grain size 约束g/2 ≤ chunksize ≤ gauto_partitioner默认自动分块大小g/2 ≤ chunksizeaffinity_partitioner自动分块 缓存亲和 迭代均匀分布g/2 ≤ chunksizestatic_partitioner确定性分块、缓存亲和、无负载均衡的均匀分布max(g/3, problem_size/num_of_resources) ≤ chunksize不指定 partitioner 时默认使用auto_partitioner。一般情况下应优先auto_partitioner或affinity_partitioner因为它们会根据可用执行资源调整分块数量affinity_partitioner与static_partitioner还能利用 Range 的按比例拆分能力在计算资源间近似均匀分配迭代。simple_partitioner适合三类场景operator()需要与子区间大小成比例的临时数组受限于子区间大小即可用栈上自动变量而非动态内存大子区间会造成缓存低效如对同一内存反复扫描或需要对特定机器做手工调优。grain size 的语义可参考 Controlling_Chunking_os.rstblocked_rangeT(begin, end, grainsize)的第三个参数默认值为 1单位是每个分块包含的循环迭代数。在 blocked_range.h 的实现中is_divisible()返回my_grainsize size()——即区间大小超过 grain size 才允许继续切分grain size 就是并行化开启的最小阈值。设置过小的 grainsize 会让调度开销占比过高过大则会降低并行度如 grainsize 1000、循环仅 2000 次时最多只能分两块。七、泛化parallel_reduce 适用于任意结合运算parallel_reduce的本质是对任意结合associative运算的并行归约。推广到一般情况splitting constructor 只做两件事拷贝运行循环体所需的只读信息如SumFoo中的my_a指针把归约变量初始化为该运算的单位元identity element如加法中的 0。而join方法则负责对应的合并操作。由此可以推论一次归约可以同时做多种运算例如用一次parallel_reduce同时求最小值和最大值只要 Body 里保存多个归约变量split 时分别初始化为∞与-∞join 时分别取min与max归约运算可以不满足交换律non-commutative用户指南特别指出若把浮点加法替换为字符串拼接示例依旧成立。这是因为归约树中 join 的方向是确定的右子树并入左子树只要运算满足结合律即使不交换也能得到正确结果。这比要求可交换 可结合的简单并行方案适用范围更广。八、源码实现纵深Lambda 形式与确定性归约除 Body 类形式外oneTBB 还提供了直接传 lambda 的parallel_reduce重载parallel_reduce.h签名形如Value parallel_reduce( const Range range, const Value identity, const RealBody real_body, const Reduction reduction );它内部通过lambda_reduce_body适配器parallel_reduce.h把 lambda 包装成符合 Body 概念的对象operator()执行my_value invoke(my_real_body, range, move(my_value))join执行my_value invoke(my_reduction, move(my_value), move(rhs.my_value))拆分时my_value重置为 identity。仓库自带的完整示例见 rvalue_reduce.cpp展示了 C17 下用右值引用 lambda 高效合并std::set集合value.merge(std::move(sets[i]))避免元素拷贝其配套说明位于 rvalue_reduce.rst。此外同一头文件还实现了parallel_deterministic_reduce确定性归约它使用deterministic_reduction_tree_node在创建树节点时同步构造right_body{input_left_body, detail::split()}parallel_reduce.h从而保证无论线程调度如何归约树形状固定、合并顺序确定结果可复现——适合需要确定性输出的场景。九、小结编写 parallel_reduce Body 的检查清单operator()非 const且从my_sum继续累加绝不重置归约变量提供SumFoo(SumFoo x, split)只拷贝只读信息 把归约变量置为单位元提供join(const SumFoo y)把y的结果并入this若 splitting constructor 与operator()并发共享可变状态务必使用原子操作用局部临时变量缓存循环内标量帮助编译器寄存器化通过 grain size 与 partitioner 控制分块粒度参考 Partitioner_Summary.rst 选择策略。如需继续深入可进一步阅读用户指南中 parallel_reduce_toctree.rst 指向的进阶示例以及在 Parallelizing_Complex_Loops.rst 中了解更复杂的循环并行化模式。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考