oneTBB parallel_scan 函数式接口实战：ParallelScanFunc 命名需求解析（基于 mold 内置 TBB 源码）

oneTBB parallel_scan 函数式接口实战ParallelScanFunc 命名需求解析基于 mold 内置 TBB 源码【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文围绕 mold 仓库内置的 oneTBB 规格文档 par_scan_func.rst 展开深度解析parallel_scan算法函数式形式所要求的ParallelScanFunc概念其伪签名、语义约束、与pre_scan_tag/final_scan_tag两趟扫描机制的关系以及它在真实源码中的落地实现。读完本文你将能够依据该命名需求正确编写自己的Scan函数对象并通过命令式Body与函数式lambda两种形式实现可并行化的前缀扫描prefix scan。一、ParallelScanFuncparallel_scan 函数式形式的核心概念在 oneTBBoneAPI Threading Building Blocks中parallel_scan是一个计算并行前缀parallel prefix的算法模板即对序列z₀, z₁, ..., zₙ₋₁计算yᵢ id× × z₀ × ... × zᵢ其中×是满足结合律的运算id×是其左单位元。当×为加法时前缀扫描退化为累加和running sum。ParallelScanFunc是parallel_scan函数式形式functional form对用户提供的扫描函数对象Scan提出的命名需求named requirement在规格文档中被标记为[req.parallel_scan_func]完整定义位于 par_scan_func.rst。它描述的是一个可同时承担汇总summary计算与最终扫描结果计算两种职责的单参数化调用运算符。1.1 需求伪签名与语义ParallelScanFunc要求类型Scan必须提供如下形式的调用运算符Value Scan::operator()(const Range r, const Value sum, bool is_final) const其语义可拆解为三点以sum为起点对区间r内的元素从给定的sum开始做归约reduction得到一个摘要值summary。当is_final true时除计算摘要外还必须同时把**扫描结果scan result**写回r对应的输出位置。返回值计算得到的摘要summary。该返回值会沿扫描树向上传播用于拼接相邻子区间的摘要。此外Value类型必须与parallel_scan算法中对应的模板参数完全一致参见 parallel_scan_func.rst 的 Requirements 一节。1.2 与命令式形式的核心区别一次调用两种职责理解ParallelScanFunc的关键在于认识到parallel_scan采用两趟two-pass扫描策略第一趟pre-scan / prescan只做look-ahead部分归约以生成前瞻摘要第二趟final scan才真正写出扫描结果。函数式形式巧妙地把这两趟的区分收敛为一个布尔参数is_final使同一个Scan函数对象可以在两趟中被复用从而隐藏了命令式形式中pre_scan_tag/final_scan_tag两个标签类型的复杂性It uses the samescanfunctor in both passes, differentiating them via a boolean parameter, combines summaries withcombinefunctor, and returns the summary computed over the wholerange.来源parallel_scan_func.rst这正是ParallelScanFunc伪签名中第三个参数bool is_final的存在意义false代表 prescan 趟true代表 final scan 趟。二、函数式形式的完整调用形态parallel_scan的函数式形式有四种重载默认分区器与显式分区器各两种原型定义于 parallel_scan_func.rst// Defined in header oneapi/tbb/parallel_scan.h templatetypename Range, typename Value, typename Scan, typename Combine Value parallel_scan( const Range range, const Value identity, const Scan scan, const Combine combine ); templatetypename Range, typename Value, typename Scan, typename Combine Value parallel_scan( const Range range, const Value identity, const Scan scan, const Combine combine, /* partitioner */ );range满足 Range 需求 的区间类型最常用的是blocked_range。identityScan::operator()的左单位元即伪签名中的sum初值。scan满足ParallelScanFunc需求的函数对象Scan。combine满足ParallelScanCombine需求的函数对象Combine负责把左右子区间的两个摘要拼接成一个摘要其签名见 par_scan_combine.rstValue Combine::operator()(const Value left, const Value right) constpartitioner可选取const auto_partitioner或const simple_partitioner。若使用simple_partitioner必须在构造blocked_range时显式提供粒度grain size。函数返回值是整个range上的总摘要summary。2.1 各模板参数的类型约束规格文档对上述模板参数给出明确的约束详见 parallel_scan_func.rst参数必须满足的需求备注RangeRange 需求可递归二分、可判空、可判断是否可再分ValueISO C 标准的CopyConstructible与CopyAssignable摘要值会频繁拷贝与赋值ScanParallelScanFunc本文主题C17 起可为成员函数指针见下文CombineParallelScanCombineC17 起可为成员函数指针特别地自 C17 起Scan还可以是指向Range中一个const成员函数的指针该成员函数接受const Value与bool两个参数并返回ValueCombine同理可以是指向Value中接受const Value并返回Value的const成员函数指针。2.2 源码中的 C20 概念约束在 mold 内置 TBB 源码 oneapi/tbb/parallel_scan.h 中当编译环境支持 C20 概念时上述需求会被直接翻译为概念concept并用于约束模板。其中与本文主题直接对应的parallel_scan_function概念定义于该文件第 66–71 行template typename Function, typename Range, typename Value concept parallel_scan_function std::invocableconst std::remove_reference_tFunction, const Range, const Value, bool std::convertible_tostd::invoke_result_tconst std::remove_reference_tFunction, const Range, const Value, bool, Value;它精确复刻了ParallelScanFunc伪签名Scan必须以(const Range, const Value, bool)为参数被调用且返回值可转换为Value。这就是命名需求在代码层面的可验证形式__TBB_CPP20_CONCEPTS_PRESENT控制开关见同文件第 53 行。三、函数式形式如何落地lambda_scan_body 剖析函数式形式之所以隐藏复杂性是因为库内部用了一个适配器lambda_scan_body把ScanCombine包装成命令式形式要求的Body。该适配器定义于 oneapi/tbb/parallel_scan.h 第 500–538 行其关键成员与行为如下templatetypename Range, typename Value, typename Scan, typename ReverseJoin class lambda_scan_body { Value m_sum_slot; // 摘要槽初始化为 identity const Value identity_element; // 左单位元 const Scan m_scan; // 用户 Scan 函数对象 const ReverseJoin m_reverse_join; // 用户 Combine 函数对象 public: // 分裂构造函数新 body 的摘要槽重新初始化为 identity lambda_scan_body( lambda_scan_body b, split ) : m_sum_slot(b.identity_element), identity_element(b.identity_element), m_scan(b.m_scan), m_reverse_join(b.m_reverse_join) {} templatetypename Tag void operator()( const Range r, Tag tag ) { m_sum_slot tbb::detail::invoke(m_scan, r, m_sum_slot, tag); // bool 参数 ←—— Tag 隐式转换而来 } void reverse_join( lambda_scan_body a ) { m_sum_slot tbb::detail::invoke(m_reverse_join, a.m_sum_slot, m_sum_slot); } void assign( lambda_scan_body b ) { m_sum_slot b.m_sum_slot; } Value result() const { return m_sum_slot; } };几个值得注意的实现细节operator()(const Range, Tag tag)把命令式形式的两趟标签pre_scan_tag/final_scan_tag隐式转换为bool后传给用户的Scan。这个隐式转换能力正是 pre_scan_tag_and_final_scan_tag_clses.rst 中operator bool()成员函数的作用true表示final_scan_tagfalse表示pre_scan_tag。对应源码见 oneapi/tbb/parallel_scan.h 第 36–48 行struct pre_scan_tag { static bool is_final_scan() {return false;} operator bool() {return is_final_scan();} }; struct final_scan_tag { static bool is_final_scan() {return true;} operator bool() {return is_final_scan();} };分裂split语义并行分裂出的每个子 body 都以identity_element重新初始化摘要槽保证各子任务从单位元开始独立做局部归约这正是 Splittable 需求 所描述的 Forking a body into two bodies that can run concurrently。reverse_join的方向性a是更早由this分裂出去的左半部分因此拼接顺序是a.m_sum_slot左在前、this-m_sum_slot右在后——这与parallel_reduce的join方向相反故而得名 reverse。最终result()返回的m_sum_slot即整个 range 上的总摘要由 oneapi/tbb/parallel_scan.h 第 586–617 行的函数式重载对外返回Value parallel_scan( const Range range, const Value identity, const Scan scan, const ReverseJoin reverse_join ) { lambda_scan_bodyRange, Value, Scan, ReverseJoin body(identity, scan, reverse_join); parallel_scan(range, body, __TBB_DEFAULT_PARTITIONER()); return body.result(); }可以看出函数式形式的所有复杂度都被封装在lambda_scan_body中用户只需提供满足ParallelScanFunc的Scan与满足ParallelScanCombine的Combine其余两趟调度、摘要传播、结果回收全部由库完成。四、完整可运行示例命令式与函数式双实现为直观印证ParallelScanFunc的语义这里给出规格文档 parallel_scan_func.rst 中的两个经典示例。二者均计算数组z的前缀累加和并写入y串行等价形式为T temp id; for( int i1; in; i ) { temp temp z[i]; y[i] temp; }4.1 命令式形式Body命令式形式要求Body满足 ParallelScanBody 需求提供operator()(Range, pre_scan_tag)、operator()(Range, final_scan_tag)、分裂构造函数、reverse_join与assign。一个同时覆盖两趟的典型实现class Body { T sum; T* const y; const T* const z; public: Body( T y_[], const T z_[] ) : sum(id), z(z_), y(y_) {} T get_sum() const { return sum; } templatetypename Tag void operator()( const oneapi::tbb::blocked_rangeint r, Tag ) { T temp sum; for( int ir.begin(); ir.end(); i ) { temp temp z[i]; if( Tag::is_final_scan() ) // 仅 final 趟写回扫描结果 y[i] temp; } sum temp; } Body( Body b, oneapi::tbb::split ) : z(b.z), y(b.y), sum(id) {} void reverse_join( Body a ) { sum a.sum sum; } // this 是右操作数 void assign( Body b ) { sum b.sum; } }; T DoParallelScan( T y[], const T z[], int n ) { Body body(y,z); oneapi::tbb::parallel_scan( oneapi::tbb::blocked_rangeint(0,n), body ); return body.get_sum(); }该实现体现了parallel_scan的两个典型模式文档原文要点单个模板函数同时覆盖两趟Tag可为pre_scan_tag或final_scan_tag通过静态方法is_final_scan()区分。pre-scan 变体只计算归约不更新y用于生成前瞻部分归约final scan 变体既计算归约又更新y。reverse_join参数反转this是×的右操作数与parallel_reduce的join相反。4.2 函数式形式lambda ParallelScanFunc函数式形式把上述繁琐的 Body 接口压缩为两个 lambda其中第一个 lambda 即为满足ParallelScanFunc的Scan——这正是本文核心概念的实战形态T DoParallelScan( T y[], const T z[], int n ) { return oneapi::tbb::parallel_scan( oneapi::tbb::blocked_rangeint(0,n), id, // identity左单位元 [](const oneapi::tbb::blocked_rangeint r, T sum, bool is_final_scan)-T { T temp sum; for( int ir.begin(); ir.end(); i ) { temp temp z[i]; if( is_final_scan ) // 仅 final 趟写回 y[i] temp; } return temp; // 返回摘要 }, // ← 这就是 ScanParallelScanFunc []( T left, T right ) { return left right; // Combine拼接左右摘要 } ); }对照ParallelScanFunc伪签名Value Scan::operator()(const Range r, const Value sum, bool is_final) const可逐一对应r←blocked_rangeintsum← 前驱摘要is_final← 是否 final 趟返回值 ← 本子区间摘要。4.3 指定分区器与粒度若改用simple_partitioner必须显式给出粒度例如粒度 1000文档原例parallel_scan( blocked_rangeint(0,n,1000), total, simple_partitioner() );五、使用约束与注意事项基于规格与源码结合律是正确性的前提。parallel_scan会自行决定何时、如何切分并行任务因此Scan与Combine所表达的运算×必须严格满足结合律否则结果不确定。规格文档特别提示浮点加法只是近似结合somewhat associative不同结合方式会产生不同的舍入结果且同一台机器上不同次运行的重关联也可能不同来源parallel_scan_func.rst。不过当串行执行时parallel_scan与文首的串行前缀形式结合方式完全一致。parallel_scan会尽力避免 prescan串行执行时它从左到右只做 final scan每个子区间的 final scan 必须同时产出摘要以备无其他线程 prescan 该区间时继续传播文档原述。这也解释了为什么ParallelScanFunc要求两趟都必须返回摘要——摘要可能被下游区间依赖。额外工作量并行前缀可能把×的调用次数提高到串行算法的两倍。文档明确说明尽管做了更多计算只要粒度合适并行版本仍可通过把工作分发到多硬件线程上胜过串行版本。Value的一致性Scan、Combine与parallel_scan模板参数三处的Value必须一致且需满足CopyConstructibleCopyAssignable摘要值在lambda_scan_body的分裂、reverse_join、assign中会被反复拷贝赋值见源码第 500–538 行。旧头文件兼容除 oneAPI 风格头文件 oneapi/tbb/parallel_scan.h 外仓库还提供兼容头文件 tbb/parallel_scan.h二者实现同一套parallel_scan接口族。六、进一步阅读本文围绕的规格文档还引用了以下直接相关的命名需求与算法文档均在 mold 仓库内可查阅ParallelScanBody 需求命令式形式对Body的完整要求operator()两趟重载、分裂构造、reverse_join、assign。ParallelScanCombine 需求函数式形式对Combine的要求。Range 需求所有并行算法共用的一维区间需求含分裂构造函数与is_divisible()语义。Splittable 需求Range与Body可分裂的理论基础。pre_scan_tag 与 final_scan_tag两趟扫描的标签类型及其is_final_scan()/operator bool()成员。parallel_scan 算法总览两趟机制、数学定义与全部示例。核心实现源码oneapi/tbb/parallel_scan.hlambda_scan_body、pre_scan_tag/final_scan_tag、parallel_scan全部重载。一句话总结ParallelScanFunc用一参两用的设计让一个普通的(Range, Value, bool) - Value函数对象同时承担 prescan 与 final scan 两趟职责是 oneTBBparallel_scan函数式接口简洁性与表达力的根基。理解它的伪签名与语义是正确编写并行前缀扫描代码的第一步。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考