mold 项目内嵌 TBB blocked_nd_rangeN 维递归可切分区间的完整指南【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold导读本文以 oneAPI Threading Building BlocksoneTBB规范文档中的blocked_nd_range类模板为骨架结合本仓库mold 链接器项目所捆绑的 oneTBB 源码 blocked_nd_range.h、一致性测试 conformance_blocked_nd_range.cpp 与官方示例 blocked_nd_range_example.cpp系统讲解这一 N 维递归可切分区间的设计、构造、切分语义与推导指引。读完本文你将掌握blocked_nd_range的完整 API、它与blocked_range2d/3d的区别、底层切分策略的源码实现以及如何将其接入parallel_for等并行算法处理高维网格问题。blocked_nd_range是一个表示可递归切分的 N 维半开区间的类模板它是blocked_range的 N 维推广可以理解为 N 个blocked_range的笛卡尔积并满足 oneTBB 的 Range 命名需求。1. 为什么需要 blocked_nd_range与 2d/3d 变体的定位差异规范文档明确指出与blocked_range2d和blocked_range3d不同blocked_nd_range的所有维度必须使用相同的Value类型。三类类的构造函数签名也各不相同——命名模式的差异正是设计意图的体现。blocked_range2dRow, Col两维可以使用不同的值类型例如行用int、列用size_t。blocked_range3dPage, Row, Col三维各自独立指定类型。blocked_nd_rangeValue, N仅有一个值类型Value与一个编译期维度数N因此blocked_nd_rangeint, 2与blocked_range2dint, int是类似但不完全相同的类型。这一差异使blocked_nd_range适合同构的 N 维网格例如矩阵、体素、特征图feature map等高维均匀数据结构而 2d/3d 变体更适用于各维度类型异构的场景。2. 类模板声明与核心类型规范给出的公开接口如下定义于oneapi/tbb/blocked_nd_range.hnamespace oneapi { namespace tbb { templatetypename Value, unsigned int N class blocked_nd_range { public: // Types using value_type Value; using dim_range_type blocked_rangevalue_type; using size_type typename dim_range_type::size_type; // Constructors blocked_nd_range(const dim_range_type dim0 /*, ... - exactly N parameters of the same type*/); blocked_nd_range(const value_type (dim_size)[N], size_type grainsize 1); blocked_nd_range(blocked_nd_range r, split); blocked_nd_range(blocked_nd_range r, proportional_split proportion); // Capacity static constexpr unsigned int dim_count(); bool empty() const; // Access bool is_divisible() const; const dim_range_type dim(unsigned int dimension) const; }; // class blocked_nd_range } // namespace tbb } // namespace oneapi成员类型说明类型定义语义value_typeValue区间值的类型dim_range_typeblocked_rangevalue_type表示 N 个维度中某一维的类型size_typetypename dim_range_type::size_type用于度量维度大小的类型即size_t从源码看真实实现并非直接编写上述类而是通过一个巧妙的技法达成的blocked_nd_range.h 中先声明blocked_nd_range_implValue, N, make_index_sequenceN再用index_sequenceIs...展开出恰好 N 个dim_range_type参数的构造函数随后blocked_nd_range是blocked_nd_range_impl的精确模板别名式的派生类class blocked_nd_range : public blocked_nd_range_implValue, N。源码注释特别强调blocked_nd_range必须恰好是 impl 的模板别名而非例如派生类否则就要自行声明构造函数从而重蹈花括号初始化列表无法推导参数类型的覆辙。这解释了文档中此构造函数不能用变参模板替代的深层原因。硬性需求N必须大于 0源码中以static_assert(N ! 0, zero dimensional blocked_nd_range cant be constructed)强制保证见 blocked_nd_range.h。Value必须满足 BlockedRangeValue 需求可拷贝构造/赋值、可析构提供operator前驱判定、operator-返回[i,j)的元素个数结果可转换为size_t、operator返回第 k 个后继值。int、指针、STL 随机访问迭代器等均为天然满足的类型。3. 构造函数三种构建 N 维空间的方式3.1 由 N 个 dim_range_type 构造blocked_nd_range( const dim_range_type dim0 /*, ... - exactly N parameters of the same type*/ );效果构造一个表示 N 维取值空间的blocked_nd_range该空间是各一维区间dim0 x ...的半开笛卡尔积。构造函数必须恰好接收 N 个参数且类型匹配const dim_range_type。示例对blocked_nd_rangeint,4等价于blocked_nd_range( const blocked_rangeint, const blocked_rangeint, const blocked_rangeint, const blocked_rangeint );重要提示规范原文强调此构造函数不能用变参模板template typename... Dims blocked_nd_range( const Dims... dims )替代——即使后者用Dims包的大小与类型约束了参数。原因是花括号初始化列表braced-init-list中的类型无法被自动推导因此blocked_nd_rangeint,4{{0,1},{0,2},{0,3},{0,4}}这种写法将无法编译。实现中正是利用make_index_sequenceN展开出精确 N 个固定类型参数const indexed_tdim_range_type, Is... args见 blocked_nd_range.h从而允许每个维度用花括号初始化列表直接书写。3.2 由维度大小数组构造blocked_nd_range( const value_type (dim_size)[N], size_type grainsize 1 );效果构造一个表示 N 维取值空间的blocked_nd_range空间为[0, dim_size[0]) x [0, dim_size[1]) x ...的半开笛卡尔积每一维使用相同的 grain size。示例blocked_nd_rangeint,4 r( {5,6,7,8}, 4 );构造一个四维空间包含所有元组(i, j, k, l)其中i从 0含到 5不含、grain size 为 4j从 0 到 6、grain size 为 4其余维度依此类推。源码中的对应实现为my_dims { dim_range_type(0, size[Is], grainsize)... }blocked_nd_range.h即对每个维度下标Is构造blocked_range(0, size[Is], grainsize)。需要注意的是grain size 必须为正数blocked_range的调试版本会对此断言。3.3 切分构造函数供并行框架内部使用blocked_nd_range( blocked_nd_range range, split ); blocked_nd_range( blocked_nd_range range, proportional_split proportion );这两个构造函数供 oneTBB 并行算法的调度器调用用于把区间递归切分为更小的子区间一般不建议用户直接调用。其语义在切分语义与实现原理一节详细展开。4. 容量与访问成员函数函数返回/效果static constexpr unsigned int dim_count()返回由模板参数N设定的维度数bool empty() const若任一维度的empty()为真返回 true否则 falsebool is_divisible() const若任一维度的is_divisible()为真返回 true否则 falseconst dim_range_type dim(unsigned int dimension) const返回指定维度要求0 dimension N对应的blocked_range源码实现印证了任一维度这一语义empty()与is_divisible()均用std::any_of遍历内部std::arraydim_range_type, N my_dimsblocked_nd_range.hdim()带__TBB_ASSERT(dimension N, out of bound)越界检查blocked_nd_range.h。5. 切分语义与实现原理5.1 基本切分splitblocked_nd_range( blocked_nd_range range, split );的前提是is_divisible()为真。效果是新构造的blocked_nd_range约等于原range的一半range更新为剩余部分。切分只发生在一个维度上其余维度以及各子区间的 grain size 与原区间保持一致。规范给出的选维建议优先在尺寸与 grain size 之比最大的维度上切分。这样反复切分后在各维 grain size 相同的前提下子区间会趋近于正方形/立方体/超立方体形状——这对缓存局部性与负载均衡最有利。5.2 比例切分proportional_splitblocked_nd_range( blocked_nd_range range, proportional_split proportion );与基本切分类似区别仅在于对所选维度按照proportion指定的比例进行切分比例语义与 blocked_range 相同其余维度与 grain size 保持不变。5.3 源码级实现真实切分逻辑集中在私有成员do_splitblocked_nd_range.hauto my_it std::max_element(my_dims.begin(), my_dims.end(), [](const dim_range_type first, const dim_range_type second) { return (first.size() * double(second.grainsize()) second.size() * double(first.grainsize())); });该比较器以size / grainsize为键选取比值最大的维度为避免整除误差使用交叉相乘的浮点形式完全对应规范优先切分 size-to-grainsize 比值最大的维度的建议。随后在该维度上调用dim_range_type::do_split(*r_it, proportion)完成实际切分并用断言校验切分后两个子区间首尾相接半开区间语义成立。此外do_split内还有static_assert保证 split 类型只能是split或proportional_split。一致性测试 conformance_blocked_nd_range.cpp 专门验证比例切分对{{0,100},{0,100}}的 2D 区间以proportional_split(3,1)切分后检查被切分维度的边界是否符合left * size / (left right)的期望值由于两个维度都满足切分条件测试同时兼容按行切与按列切两种结果。6. 推导指引Deduction Guides让类型推导替你数维度规范定义了三组显式推导指引源码实现位于 blocked_nd_range.h需 C17受__TBB_CPP17_DEDUCTION_GUIDES_PRESENT宏保护。指引 1由一组 blocked_range 推导template typename Value, typename... Values blocked_nd_range(blocked_rangeValue, blocked_rangeValues...) - blocked_nd_rangeValue, 1 sizeof...(Values);效果传入一组blocked_range对象时推导出 N 维区间。约束仅当Values中所有类型都与Value相同才参与重载解析。源码实现为enable_if_t(... std::is_same_vValue, Values)blocked_nd_range.h。指引 2由 C 数组推导template typename Value, unsigned int N blocked_nd_range(const Value ()[N], typename blocked_nd_rangeValue, N::size_type 1) - blocked_nd_rangeValue, N;效果由单个 C 数组对象表示一组维度大小推导维度数。指引 3由花括号初始化列表推导template typename Value, /*a template parameter pack*/... Xs blocked_nd_range(/*a type deducible from a braced initialization list of Value objects*/... args) - blocked_nd_rangeValue, sizeof...(args);效果将一组花括号初始化列表推导为对应维度的blocked_range集。规范给出示例blocked_nd_range range({0, 10}, {0, 10, 5})应推导为blocked_nd_rangeint, 2。关键注意点如果只提供单个花括号初始化列表它会被解释为维度大小的 C 数组而不是blocked_range——即blocked_nd_range range({100, 200})得到的是 2 维从 0 到 100、从 0 到 200的区间而不是区间 [100, 200)。该指引规范允许两种等价实现之一方案 Ainitializer_list 版本template typename Value, typename... Values blocked_nd_range(std::initializer_listValue, std::initializer_listValues...) - blocked_nd_rangeValue, 1 sizeof...(Values);约束sizeof...(Values) 0且Values中所有类型与Value相同。方案 BC 数组引用版本仓库实际采用template typename Value, unsigned int... Ns blocked_nd_range(const Value (... dim)[Ns]) - blocked_nd_rangeValue, sizeof...(Ns);约束sizeof...(Ns) 1且每个N即每个维度列表的元素个数必须为 2 或 3。仓库实现正是此方案并附注释说明原因单个花括号列表或单个 C 数组参数会被多维区间构造优先匹配且dim_range_type只能由 2 或 3 个实参构造begin, end或begin, end, grainsize。此外实现还必须为拷贝/移动构造以及接收split、proportional_split的构造函数提供隐式或显式推导指引以便blocked_nd_range range(source_range, split{})这类写法也能正确推导。一致性测试 conformance_blocked_nd_range.cpp 用static_assert覆盖了从 1 到 4 维、含/不含 grain size、C 数组与花括号列表混用、split/proportional_split/拷贝/移动等二十余种推导场景是验证推导语义的权威参考。7. 实战将 blocked_nd_range 用于 3D 卷积并行化官方用户指南示例 blocked_nd_range_example.cpp 展示了最典型的应用——3D 卷积计算templatetypename Features, typename Output void convolution3d(const Features feature_maps, Output out, int out_length, int out_width, int out_heigth, int kernel_length, int kernel_width, int kernel_height) { using range_t oneapi::tbb::blocked_nd_rangeint, 3; oneapi::tbb::parallel_for( range_t({0, out_length}, {0, out_width}, {0, out_heigth}), { auto out_x out_range.dim(0); auto out_y out_range.dim(1); auto out_z out_range.dim(2); for (int i out_x.begin(); i out_x.end(); i) for (int j out_y.begin(); j out_y.end(); j) for (int k out_z.begin(); k out_z.end(); k) out[i][j][k] kernel3d(feature_maps, i, j, k, kernel_length, kernel_width, kernel_height); } ); }这段代码的三个关键点构造即推导range_t({0, out_length}, {0, out_width}, {0, out_heigth})利用第 3 组推导指引三个两元素花括号列表直接构造出 3 维区间各维 grain size 取默认值 1。切分由框架接管parallel_for内部会反复调用 split 构造函数把区间切到 grain size 粒度再分发给各线程——用户无需也不应手动切分。dim() 取维lambda 中通过out_range.dim(0/1/2)取出各维的blocked_rangeint用begin()/end()驱动嵌套循环遍历子立方体。一个完整的可运行骨架结合规范与测试用例下面给出可直接编译运行的演示含头文件oneapi/tbb/blocked_nd_range.h、oneapi/tbb/parallel_for.h#include oneapi/tbb/blocked_nd_range.h #include oneapi/tbb/parallel_for.h #include cstdio int main() { using range_t oneapi::tbb::blocked_nd_rangeint, 3; // 方式一由花括号初始化列表构造每个列表为 begin,end 或 begin,end,grainsize range_t r1({0, 100}, {0, 100}, {0, 100}); // 方式二由维度大小数组构造所有维共用 grain size int sizes[3] {100, 200, 50}; range_t r2(sizes, 8); // 方式三由 blocked_range 对象构造各维可带不同 grain size using dim_t oneapi::tbb::blocked_rangeint; range_t r3(dim_t(0, 100, 4), dim_t(0, 200, 8), dim_t(0, 50, 2)); // C17 自动推导维度数 oneapi::tbb::blocked_nd_range auto_nd({0, 100}, {0, 100, 5}, {0, 100}); static_assert(std::is_same_vdecltype(auto_nd), oneapi::tbb::blocked_nd_rangeint, 3); // 并行遍历 r1 oneapi::tbb::parallel_for(r1, [](const range_t sub) { for (int i sub.dim(0).begin(); i sub.dim(0).end(); i) for (int j sub.dim(1).begin(); j sub.dim(1).end(); j) for (int k sub.dim(2).begin(); k sub.dim(2).end(); k) printf((%d,%d,%d)\n, i, j, k); }); return 0; }8. 注意事项与易错点N 必须为正0 维区间在编译期即被static_assert拒绝。grain size 必须为正违反时调试版库会触发断言此约束继承自blocked_range构造函数。所有维度同类型若各维需要不同类型如行/列异构应改用blocked_range2d/blocked_range3d。单个花括号列表的歧义blocked_nd_range range({100, 200})被解释为维度大小数组2 维每维从 0 开始而非单维区间[100, 200)显式指定维度数与类型可规避歧义。切分只动一维split与proportional_split都只切分 size-to-grainsize 比值最大的维度其余维度原样保留这是设计保证的子区间形状渐近接近超立方体的关键。推导指引需要 C17旧标准下无法使用第 6 节的自动推导语法需显式写出blocked_nd_rangeint, N。9. 延伸阅读blocked_nd_range的一维基础blocked_range异构类型变体blocked_range2d、blocked_range3d值类型约束BlockedRangeValue 需求头文件实现include/oneapi/tbb/blocked_nd_range.h一致性测试test/conformance/conformance_blocked_nd_range.cpp使用示例doc/main/tbb_userguide/examples/blocked_nd_range_example.cpp【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考