用 oneTBB Wavefront 模式并行化 DAG 依赖计算从 LCS 内核到 mold 链接器的工程实践【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldWavefront波前是 oneTBB 官方设计模式文档本仓库 third-party/tbb/doc/main/tbb_userguide/design_patterns/Wavefront.rst收录的经典并行模式当一组计算之间存在有向无环图DAG形式的依赖关系时用原子计数器做并行拓扑排序再借助oneapi::tbb::parallel_for_each的feeder馈送器动态派发就绪任务。读完本文你将掌握该模式的问题建模、计数器初始化、未知前驱数的兜底技巧、分块粒度优化以及它在 mold 链接器垃圾回收-gc-sections与并行读入输入文件中的真实落地方式。问题Problem与适用场景ContextWavefront 模式要解决的问题非常朴素对一个数据集中的若干项执行计算而其中某一项的计算结果要依赖其若干前驱项的计算结果。原文给出的适用约束如下依赖图为无环图acyclic graph这是模式成立的前提一旦存在环波前就无法收敛计数永远无法归零。每个项的直接前驱数量可以预先知道要么一开始就知道要么能在最后一个前驱完成之前的某个时刻确定下来。满足这两个条件的典型场景包括动态规划填表如最长公共子序列、图像处理中的像素扫描线算法、编译/链接阶段的依赖传播、电路仿真等。凡是可以画出谁先算、谁依赖谁的 DAG 的工作负载都可以尝试套用该模式。原文同时强调了一个必要修正如果某个项的前驱数量无法提前确定就把知道前驱个数这件事本身当作一个额外的概念上的前驱。当前驱数量最终变得可知时再把这个概念前驱视为已完成。这样计数逻辑在结构上保持统一不依赖具体业务时序。解Solution原子计数器 parallel_for_each feeder 的并行拓扑排序该模式的解决方案本质上是一个并行的拓扑排序原文给出的算法骨架如下为每个待计算项关联一个原子计数器atomic counter初值设为该项的前驱数量调用oneapi::tbb::parallel_for_each处理那些没有前驱计数为零的项每当一项处理完毕递减其后继的计数器若某个后继的计数器递减到零说明它的所有依赖均已就绪立即通过feeder把它喂给正在运行的parallel_for_each。feeder 的底层机制源码佐证本仓库 bundled 的 oneTBB 头文件 third-party/tbb/include/oneapi/tbb/parallel_for_each.h 完整实现了这一机制class feederItem第 57–71 行暴露两个add重载拷贝版与移动版其注释直截了当Add a work item to a running parallel_for_each即向正在运行中的并行循环动态追加工作项实际执行类是feeder_implBody, Item第 172 行起internal_add_move通过small_object_allocator分配一个feeder_item_task第 117–167 行再spawn到执行上下文从而把新项转成一条可被其他线程窃取的 task头部feeder_holder特化第 458–475 行展示了编译器检测技巧只有函数体签名接受第二个 feeder 参数时feeder_is_required通过std::invoke探测feeder 对象才会被真正构造出来两参数形式的体才会被调度parallel_for_each_operator_selector第 79–114 行。也就是说feeder 并不是一个最终会统一合并的队列而是每add一次就立刻产生一个新任务参与调度——这正是波前传播能保持高并发度的关键。一个通用模板把原文算法转写为可直接套用的伪代码骨架// Count[item] 已初始化为 item 的前驱数量 oneapi::tbb::parallel_for_each(roots.begin(), roots.end(), { compute(item); // 1. 计算当前项 for (Item succ : successors(item)) // 2. 递减后继计数 if (--Count[succ] 0) // 3. 就绪即派发 feeder.add(succ); });依赖图的 DAG 化只保留必要的依赖边原文在示例中特别强调参与计数的每条依赖都会产生一次原子操作开销因此应当尽量剔除冗余依赖边。后面 LCS 示例中的灰色对角依赖就是典型它可由相邻两条边传递闭包推出忽略它不改变正确性却能省掉一条边上的计数器递减。对大型 DAG 而言这种稀疏化带来的原子操作节省是实打实的。示例Example最长公共子序列LCS串行内核原文以最长公共子序列算法作为贯穿示例。串行内核如下参数是字符串x、y及其长度xlen、ylenint F[MAX_LEN1][MAX_LEN1]; void SerialLCS( const char* x, size_t xlen, const char* y, size_t ylen ) { for( size_t i1; ixlen; i ) for( size_t j1; jylen; j ) F[i][j] x[i-1]y[j-1] ? F[i-1][j-1]1: max(F[i][j-1],F[i-1][j]); }内核把F[i][j]设为x[0..i-1]与y[0..j-1]的最长公共子序列长度并假定第 0 行与第 0 列F[0][0..ylen]与F[0..xlen][0]已被初始化为零。外层循环逐行、内层逐列的顺序使每个格子总是先于其依赖者被填充。依赖结构与冗余边计算F[i][j]的数据依赖如上面第一张图所示它需要F[i-1][j-1]字符相等时加一、F[i-1][j]与F[i][j-1]取二者较大。而第二张图指出灰色对角依赖是另外两条依赖的传递闭包F[i-1][j-1]的值在串行语义中必须先行算出但对并行调度而言只要F[i-1][j]和F[i][j-1]都就绪F[i][j]依赖的数值事实上已经确定因此对角边可以放心丢弃。原文给出的取舍原则是It is generally good to remove redundant dependences from consideration, because the atomic counting incurs a cost for each dependence considered.每个被纳入考量的依赖都要付出一次原子计数的代价所以通常值得剔除冗余依赖。粒度grain size把元素聚合成块原文明确指出第二个关键工程决策逐元素调度F[i][j]计算开销过高应当把元素聚合为连续块块内串行处理。分块后块与块之间保持与元素相同的依赖模式只是尺度放大了每块只需一个原子计数器调度开销被均摊到块内N×N个元素的计算上。这也正是波前模式的通用建议If the overhead of counting individual items is excessive, aggregate items into blocks, and do the wavefront over the blocks.并行 LCS 完整代码以下并行版本每个块含N×N个元素Count二维数组按块组织计数器初始化完成后从原点块无任何前驱开始滚动波前const int N 64; std::atomicchar Count[MAX_LEN/N1][MAX_LEN/N1]; void ParallelLCS( const char* x, size_t xlen, const char* y, size_t ylen ) { // Initialize predecessor counts for blocks. size_t m (xlenN-1)/N; size_t n (ylenN-1)/N; for( int i0; im; i ) for( int j0; jn; j ) Count[i][j] (i0)(j0); // Roll the wavefront from the origin. typedef pairsize_t,size_t block; block origin(0,0); oneapi::tbb::parallel_for_each( origin, origin1, { // Extract bounds on block size_t bi b.first; size_t bj b.second; size_t xl N*bi1; size_t xu min(xlN,xlen1); size_t yl N*bj1; size_t yu min(ylN,ylen1); // Process the block for( size_t ixl; ixu; i ) for( size_t jyl; jyu; j ) F[i][j] x[i-1]y[j-1] ? F[i-1][j-1]1: max(F[i][j-1],F[i-1][j]); // Account for successors if( bj1n --Count[bi][bj1]0 ) feeder.add( block(bi,bj1) ); if( bi1m --Count[bi1][bj]0 ) feeder.add( block(bi1,bj) ); } ); }要点解读计数器初值Count[i][j] (i0)(j0)即上方有块 左侧有块的前驱个数恰好对应剔除对角边后的两条依赖右邻居依赖左块、下邻居依赖上块就绪判定--Count[...] 0是原子递减只有最后一个前驱完成的那次递减才会触发feeder.add保证每个后继恰好被派发一次只沿右、下两个方向传播去掉对角边后块(i,j)的后继只有(i,j1)与(i1,j)每个后继的计数至多为 2代码简洁且无重复派发边界处理xu min(xlN, xlen1)、yu min(ylN, ylen1)处理不整除的尾部块移动语义feeder.add(block(bi,bj1))走的是feeder::add(Item)的移动重载与头文件中internal_add_move的 task 化路径对应。从执行轨迹看这是一个沿对角线逐波前行的过程同一斜线上的块彼此无依赖、可充分并行斜线之间则通过计数器形成天然的栅栏这正是波前名称的由来。工程佐证mold 链接器如何用同一模式Wavefront 模式并非纸上谈兵。本仓库的核心项目 mold一个现代链接器就在多个关键路径上使用了tbb::parallel_for_each feeder的同一套机制可以作为该模式在高性能工程中的真实范例。-gc-sections的 mark 阶段图可达性波前mold 的垃圾收集器把每个输入节section当作顶点、重定位当作边从根集出发标记所有可达节。标记本身就是一个 DAG 依赖传播问题。在 src/gc-sections.cc 中第 203–206 行的mark()用tbb::parallel_for_each(rootset, ...)启动标记函数体同时接收tbb::feederInputSectionE * feeder第 130–145 行的visit_section()内marklambda 对每个新发现的节调用feeder.add(sec)动态加入工作集注释特别写道For better performance, we dont callfeeder.addtoo often——深度小于 3 时改为递归内联访问超过深度才转交给 feeder这与 Wavefront 文档用块均摊调度开销的思路异曲同工第 176–189 行对__start_name/__stop_name符号的处理更进一步一个符号可能引用海量同名节于是对整组节发起嵌套的parallel_for_each用并行扇出替代逐一feeder.add避免单个任务的 fan-out 成为瓶颈。并行读入输入文件生产者-消费者波前另一个例子在 src/main.cc 第 234–288 行的read_input_files()。链接器需要并行读取成千上万个输入文件但命令行语义--as-needed、--whole-archive等只影响其后参数要求读入结果最终按命令行顺序排列。mold 的做法是每个ReaderJob是一个工作项parallel_for_each的体带tbb::feederReaderJob feeder当某个 job 发现当前输入是归档文件FileType::AR/THIN_AR时把它的每一个成员展开成一个新的ReaderJob通过feeder.add(std::move(job2))动态注入并行读取队列第 263–279 行实现归档成员同样并行读入读完后统一parallel_sort回命令行顺序并分配优先级第 298–313 行。这里归档展开的边是运行时才知道的恰好对应文档中前驱数量无法预先确定的变体——用运行期动态feeder.add天然化解。此外 src/arch-arm32.cc、src/arch-ppc64v1.cc、src/icf.cc 等多处也以三参数形式使用parallel_for_each可见该 API 与 feeder 模式在 mold 中是贯穿始终的基础设施。实战要点与常见坑综合原文与源码落地 Wavefront 模式时有四条经验值得固化先证无环再谈并行依赖图必须是无环图有环场景下计数永远无法归零程序将死锁或漏算。剔除冗余依赖边传递闭包内的边可以安全忽略能显著减少原子操作次数原文与 LCS 示例的核心建议。用分块均摊调度开销元素粒度过细时把元素聚合成N×N的块、块内串行、块间走波前LCS 中N 64。能算前驱数就算算不出就加概念前驱前驱数量未知时把得知数量当作一个额外的、最后完成的虚拟前驱保持计数逻辑一致。小结Wavefront 模式用原子计数器 parallel_for_each的 feeder把经典的拓扑排序改造成可动态生长的并行任务流计数器决定正确性每个项恰好在其全部依赖完成后被处理feeder 决定并发度就绪项立即变成可窃取的任务。LCS 示例展示了从串行内核到分块并行内核的完整改造路径而 mold 的-gc-sections标记与输入文件并行读取则证明该模式在真实的高性能系统中既能处理边已知也能处理边动态产生的场景。本模式的原始参考文献为 Eun-Gyu Kim 与 Mark Snir 的Wavefront Pattern收录于伊利诺伊大学厄巴纳-香槟分校并行模式讲义。如需继续深入可阅读同目录下的 Design Patterns 总览、oneTBB 头文件实现 与 mold 的 gc-sections.cc、main.cc 源码。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 用 oneTBB Wavefront 模式并行化 DAG 依赖计算：从 LCS 内核到 mold 链接器的工程实践
用 oneTBB Wavefront 模式并行化 DAG 依赖计算从 LCS 内核到 mold 链接器的工程实践【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldWavefront波前是 oneTBB 官方设计模式文档本仓库 third-party/tbb/doc/main/tbb_userguide/design_patterns/Wavefront.rst收录的经典并行模式当一组计算之间存在有向无环图DAG形式的依赖关系时用原子计数器做并行拓扑排序再借助oneapi::tbb::parallel_for_each的feeder馈送器动态派发就绪任务。读完本文你将掌握该模式的问题建模、计数器初始化、未知前驱数的兜底技巧、分块粒度优化以及它在 mold 链接器垃圾回收-gc-sections与并行读入输入文件中的真实落地方式。问题Problem与适用场景ContextWavefront 模式要解决的问题非常朴素对一个数据集中的若干项执行计算而其中某一项的计算结果要依赖其若干前驱项的计算结果。原文给出的适用约束如下依赖图为无环图acyclic graph这是模式成立的前提一旦存在环波前就无法收敛计数永远无法归零。每个项的直接前驱数量可以预先知道要么一开始就知道要么能在最后一个前驱完成之前的某个时刻确定下来。满足这两个条件的典型场景包括动态规划填表如最长公共子序列、图像处理中的像素扫描线算法、编译/链接阶段的依赖传播、电路仿真等。凡是可以画出谁先算、谁依赖谁的 DAG 的工作负载都可以尝试套用该模式。原文同时强调了一个必要修正如果某个项的前驱数量无法提前确定就把知道前驱个数这件事本身当作一个额外的概念上的前驱。当前驱数量最终变得可知时再把这个概念前驱视为已完成。这样计数逻辑在结构上保持统一不依赖具体业务时序。解Solution原子计数器 parallel_for_each feeder 的并行拓扑排序该模式的解决方案本质上是一个并行的拓扑排序原文给出的算法骨架如下为每个待计算项关联一个原子计数器atomic counter初值设为该项的前驱数量调用oneapi::tbb::parallel_for_each处理那些没有前驱计数为零的项每当一项处理完毕递减其后继的计数器若某个后继的计数器递减到零说明它的所有依赖均已就绪立即通过feeder把它喂给正在运行的parallel_for_each。feeder 的底层机制源码佐证本仓库 bundled 的 oneTBB 头文件 third-party/tbb/include/oneapi/tbb/parallel_for_each.h 完整实现了这一机制class feederItem第 57–71 行暴露两个add重载拷贝版与移动版其注释直截了当Add a work item to a running parallel_for_each即向正在运行中的并行循环动态追加工作项实际执行类是feeder_implBody, Item第 172 行起internal_add_move通过small_object_allocator分配一个feeder_item_task第 117–167 行再spawn到执行上下文从而把新项转成一条可被其他线程窃取的 task头部feeder_holder特化第 458–475 行展示了编译器检测技巧只有函数体签名接受第二个 feeder 参数时feeder_is_required通过std::invoke探测feeder 对象才会被真正构造出来两参数形式的体才会被调度parallel_for_each_operator_selector第 79–114 行。也就是说feeder 并不是一个最终会统一合并的队列而是每add一次就立刻产生一个新任务参与调度——这正是波前传播能保持高并发度的关键。一个通用模板把原文算法转写为可直接套用的伪代码骨架// Count[item] 已初始化为 item 的前驱数量 oneapi::tbb::parallel_for_each(roots.begin(), roots.end(), { compute(item); // 1. 计算当前项 for (Item succ : successors(item)) // 2. 递减后继计数 if (--Count[succ] 0) // 3. 就绪即派发 feeder.add(succ); });依赖图的 DAG 化只保留必要的依赖边原文在示例中特别强调参与计数的每条依赖都会产生一次原子操作开销因此应当尽量剔除冗余依赖边。后面 LCS 示例中的灰色对角依赖就是典型它可由相邻两条边传递闭包推出忽略它不改变正确性却能省掉一条边上的计数器递减。对大型 DAG 而言这种稀疏化带来的原子操作节省是实打实的。示例Example最长公共子序列LCS串行内核原文以最长公共子序列算法作为贯穿示例。串行内核如下参数是字符串x、y及其长度xlen、ylenint F[MAX_LEN1][MAX_LEN1]; void SerialLCS( const char* x, size_t xlen, const char* y, size_t ylen ) { for( size_t i1; ixlen; i ) for( size_t j1; jylen; j ) F[i][j] x[i-1]y[j-1] ? F[i-1][j-1]1: max(F[i][j-1],F[i-1][j]); }内核把F[i][j]设为x[0..i-1]与y[0..j-1]的最长公共子序列长度并假定第 0 行与第 0 列F[0][0..ylen]与F[0..xlen][0]已被初始化为零。外层循环逐行、内层逐列的顺序使每个格子总是先于其依赖者被填充。依赖结构与冗余边计算F[i][j]的数据依赖如上面第一张图所示它需要F[i-1][j-1]字符相等时加一、F[i-1][j]与F[i][j-1]取二者较大。而第二张图指出灰色对角依赖是另外两条依赖的传递闭包F[i-1][j-1]的值在串行语义中必须先行算出但对并行调度而言只要F[i-1][j]和F[i][j-1]都就绪F[i][j]依赖的数值事实上已经确定因此对角边可以放心丢弃。原文给出的取舍原则是It is generally good to remove redundant dependences from consideration, because the atomic counting incurs a cost for each dependence considered.每个被纳入考量的依赖都要付出一次原子计数的代价所以通常值得剔除冗余依赖。粒度grain size把元素聚合成块原文明确指出第二个关键工程决策逐元素调度F[i][j]计算开销过高应当把元素聚合为连续块块内串行处理。分块后块与块之间保持与元素相同的依赖模式只是尺度放大了每块只需一个原子计数器调度开销被均摊到块内N×N个元素的计算上。这也正是波前模式的通用建议If the overhead of counting individual items is excessive, aggregate items into blocks, and do the wavefront over the blocks.并行 LCS 完整代码以下并行版本每个块含N×N个元素Count二维数组按块组织计数器初始化完成后从原点块无任何前驱开始滚动波前const int N 64; std::atomicchar Count[MAX_LEN/N1][MAX_LEN/N1]; void ParallelLCS( const char* x, size_t xlen, const char* y, size_t ylen ) { // Initialize predecessor counts for blocks. size_t m (xlenN-1)/N; size_t n (ylenN-1)/N; for( int i0; im; i ) for( int j0; jn; j ) Count[i][j] (i0)(j0); // Roll the wavefront from the origin. typedef pairsize_t,size_t block; block origin(0,0); oneapi::tbb::parallel_for_each( origin, origin1, { // Extract bounds on block size_t bi b.first; size_t bj b.second; size_t xl N*bi1; size_t xu min(xlN,xlen1); size_t yl N*bj1; size_t yu min(ylN,ylen1); // Process the block for( size_t ixl; ixu; i ) for( size_t jyl; jyu; j ) F[i][j] x[i-1]y[j-1] ? F[i-1][j-1]1: max(F[i][j-1],F[i-1][j]); // Account for successors if( bj1n --Count[bi][bj1]0 ) feeder.add( block(bi,bj1) ); if( bi1m --Count[bi1][bj]0 ) feeder.add( block(bi1,bj) ); } ); }要点解读计数器初值Count[i][j] (i0)(j0)即上方有块 左侧有块的前驱个数恰好对应剔除对角边后的两条依赖右邻居依赖左块、下邻居依赖上块就绪判定--Count[...] 0是原子递减只有最后一个前驱完成的那次递减才会触发feeder.add保证每个后继恰好被派发一次只沿右、下两个方向传播去掉对角边后块(i,j)的后继只有(i,j1)与(i1,j)每个后继的计数至多为 2代码简洁且无重复派发边界处理xu min(xlN, xlen1)、yu min(ylN, ylen1)处理不整除的尾部块移动语义feeder.add(block(bi,bj1))走的是feeder::add(Item)的移动重载与头文件中internal_add_move的 task 化路径对应。从执行轨迹看这是一个沿对角线逐波前行的过程同一斜线上的块彼此无依赖、可充分并行斜线之间则通过计数器形成天然的栅栏这正是波前名称的由来。工程佐证mold 链接器如何用同一模式Wavefront 模式并非纸上谈兵。本仓库的核心项目 mold一个现代链接器就在多个关键路径上使用了tbb::parallel_for_each feeder的同一套机制可以作为该模式在高性能工程中的真实范例。-gc-sections的 mark 阶段图可达性波前mold 的垃圾收集器把每个输入节section当作顶点、重定位当作边从根集出发标记所有可达节。标记本身就是一个 DAG 依赖传播问题。在 src/gc-sections.cc 中第 203–206 行的mark()用tbb::parallel_for_each(rootset, ...)启动标记函数体同时接收tbb::feederInputSectionE * feeder第 130–145 行的visit_section()内marklambda 对每个新发现的节调用feeder.add(sec)动态加入工作集注释特别写道For better performance, we dont callfeeder.addtoo often——深度小于 3 时改为递归内联访问超过深度才转交给 feeder这与 Wavefront 文档用块均摊调度开销的思路异曲同工第 176–189 行对__start_name/__stop_name符号的处理更进一步一个符号可能引用海量同名节于是对整组节发起嵌套的parallel_for_each用并行扇出替代逐一feeder.add避免单个任务的 fan-out 成为瓶颈。并行读入输入文件生产者-消费者波前另一个例子在 src/main.cc 第 234–288 行的read_input_files()。链接器需要并行读取成千上万个输入文件但命令行语义--as-needed、--whole-archive等只影响其后参数要求读入结果最终按命令行顺序排列。mold 的做法是每个ReaderJob是一个工作项parallel_for_each的体带tbb::feederReaderJob feeder当某个 job 发现当前输入是归档文件FileType::AR/THIN_AR时把它的每一个成员展开成一个新的ReaderJob通过feeder.add(std::move(job2))动态注入并行读取队列第 263–279 行实现归档成员同样并行读入读完后统一parallel_sort回命令行顺序并分配优先级第 298–313 行。这里归档展开的边是运行时才知道的恰好对应文档中前驱数量无法预先确定的变体——用运行期动态feeder.add天然化解。此外 src/arch-arm32.cc、src/arch-ppc64v1.cc、src/icf.cc 等多处也以三参数形式使用parallel_for_each可见该 API 与 feeder 模式在 mold 中是贯穿始终的基础设施。实战要点与常见坑综合原文与源码落地 Wavefront 模式时有四条经验值得固化先证无环再谈并行依赖图必须是无环图有环场景下计数永远无法归零程序将死锁或漏算。剔除冗余依赖边传递闭包内的边可以安全忽略能显著减少原子操作次数原文与 LCS 示例的核心建议。用分块均摊调度开销元素粒度过细时把元素聚合成N×N的块、块内串行、块间走波前LCS 中N 64。能算前驱数就算算不出就加概念前驱前驱数量未知时把得知数量当作一个额外的、最后完成的虚拟前驱保持计数逻辑一致。小结Wavefront 模式用原子计数器 parallel_for_each的 feeder把经典的拓扑排序改造成可动态生长的并行任务流计数器决定正确性每个项恰好在其全部依赖完成后被处理feeder 决定并发度就绪项立即变成可窃取的任务。LCS 示例展示了从串行内核到分块并行内核的完整改造路径而 mold 的-gc-sections标记与输入文件并行读取则证明该模式在真实的高性能系统中既能处理边已知也能处理边动态产生的场景。本模式的原始参考文献为 Eun-Gyu Kim 与 Mark Snir 的Wavefront Pattern收录于伊利诺伊大学厄巴纳-香槟分校并行模式讲义。如需继续深入可阅读同目录下的 Design Patterns 总览、oneTBB 头文件实现 与 mold 的 gc-sections.cc、main.cc 源码。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考