mold 项目内嵌 oneTBB 的 blocked_range2d 详解:二维可递归划分区间的原理、分裂算法与并行实践
mold 项目内嵌 oneTBB 的 blocked_range2d 详解:二维可递归划分区间的原理、分裂算法与并行实践
blocked_range2d 是 oneAPI Threading Building Blocks(oneTBB)中表示二维半开区间的类模板,它将两个一维 blocked_range 组合成一个可递归划分的矩形值空间,常作为 parallel_for、parallel_reduce 等并行算法的迭代范围参数。在 mold 项目所内嵌的 oneTBB 源码树 中,该组件位于 include/oneapi/tbb/blocked_range2d.h。读完本文,你将掌握 blocked_range2d 的构造方式、划分判定、分裂构造函数的行为差异,以及其底层分裂轴选择策略在源码中的具体实现。
blocked_range2d 是什么:可递归划分的二维半开区间
blocked_range2d 表示一个二维半开区间 [i0,j0)×[i1,j1),即两个维度各自取半开区间的笛卡尔积。它由行区间与列区间两个一维 blocked_range 组成,两个维度各自拥有独立的切分阈值(grain size,即粒度)。只要其中任一维度可继续划分,整个二维区间就是可划分(divisible)的。
该类型满足 oneTBB 的 Range 需求,因此可以直接作为并行算法的 range 参数使用。官方规范文档 blocked_range2d_cls.rst 对其接口给出了完整定义。
头文件与命名空间
blocked_range2d 定义于头文件 <oneapi/tbb/blocked_range2d.h>,位于命名空间 oneapi::tbb(在 blocked_range2d.h 中实际位于 tbb::detail::d1,并通过 inline namespace v1 暴露为 tbb::blocked_range2d)。由于 mold 使用了较新版本的 oneTBB 头文件布局,源码中的命名空间为 tbb,而规范文档以 oneapi::tbb 描述同一类型。
模板参数与成员类型
blocked_range2d 的模板签名为:
template<typename RowValue, typename ColValue = RowValue>
class blocked_range2d {
using row_range_type = blocked_range<RowValue>;
using col_range_type = blocked_range<ColValue>;
// ...
};
其中 RowValue 与 ColValue 分别描述行、列两个维度上值的类型,ColValue 默认与 RowValue 相同。两个维度值的类型可以不同——例如规范文档中的示例 blocked_range2d<char,int> 就同时使用了 char 和 int 两种值类型。成员类型 row_range_type 与 col_range_type 分别指向对应维度的一维 blocked_range 实例。
模板参数需要满足 BlockedRangeValue 需求:可拷贝构造、可赋值、支持 operator<、operator-(返回可转换为 size_t 的差值)以及 operator+(值加偏移)。整数类型、指针以及差值可隐式转换为 size_t 的 STL 随机访问迭代器都是合格的候选类型。在 C++20 环境下,detail/_range_common.h 中的 blocked_range_value concept 也以 std::copyable 与上述运算要求的形式约束了这一需求。
构造函数:从显式粒度到两种分裂语义
六参数构造:为两个维度分别指定粒度
blocked_range2d(
RowValue row_begin, RowValue row_end,
typename row_range_type::size_type row_grainsize,
ColValue col_begin, ColValue col_end,
typename col_range_type::size_type col_grainsize);
该构造函数创建表示值空间 [row_begin, row_end) × [col_begin, col_end) 的二维区间,并为行、列分别指定粒度。规范文档给出了一个直观示例:
blocked_range2d<char,int> r('a', 'z'+1, 3, 0, 10, 2);
上述语句构造了一个包含所有形如 (i, j) 值对的二维空间:i 从 'a' 到 'z'(粒度 3),j 从 0 到 9(粒度 2)。注意粒度的单位是"迭代次数"而非字节或索引:例如行方向 'z' + 1 - 'a' = 26 个字符,以粒度 3 划分时,只有当行跨度大于 3 时该维才可再切分。
四参数构造:粒度默认为 1
blocked_range2d(RowValue row_begin, RowValue row_end,
ColValue col_begin, ColValue col_end);
该构造等价于 blocked_range2d(row_begin, row_end, 1, col_begin, col_end, 1),即两个维度的粒度均为 1。从源码看,它委托给两个一维构造:my_rows(row_begin,row_end) 与 my_cols(col_begin,col_end),而 blocked_range.h 中的默认参数正是 grainsize_ = 1,并带有一条 __TBB_ASSERT(my_grainsize>0, ...) 断言——粒度必须为正数,调试版本中传入非正粒度会触发断言失败。
split 基本分裂构造函数
blocked_range2d(blocked_range2d& range, split);
基本分裂构造函数将原区间一分为二:新构造的 blocked_range2d 约为原区间的"后半部分",原 range 被更新为"前半部分",两个子区间保留与原区间相同的粒度。前提条件是 is_divisible() 必须为 true。
分裂时只会选择行或列中的一个轴进行切分。规范文档指出,轴的选择策略旨在经过反复分裂后,使子区间的纵横比趋近于行、列粒度的比例。分裂语义与 Range 需求中的约定一致:新对象承载第二部分、原对象保留第一部分,这使得 parallel_for 等算法在串行退化时能以递增顺序遍历区间,行为与普通顺序循环一致。
proportional_split 比例分裂构造函数
blocked_range2d(blocked_range2d& range, proportional_split proportion);
比例分裂构造函数按 proportion 给定的比例(left() : right())在选定的轴上切分区间,切分轴的选择方式与基本分裂构造函数相同,随后对选中轴执行比例切分;另一个轴以及两个子区间的粒度保持不变。前提条件同样是 is_divisible() 为 true。split 与 proportional_split 的定义位于 detail/_range_common.h,proportional_split 的默认比例为 1:1,当某个 range 类型不支持比例分裂时,会通过显式转换运算符退化为普通 split。
成员函数:empty、is_divisible、rows 与 cols
| 成员函数 | 返回值语义 |
|---|---|
bool empty() const |
区间是否为空,返回 `rows().empty() |
bool is_divisible() const |
区间是否可继续分裂,返回 `rows().is_divisible() |
const row_range_type& rows() const |
值空间的行区间 |
const col_range_type& cols() const |
值空间的列区间 |
从源码 blocked_range2d.h 可以确认:empty() 与 is_divisible() 都只做"或"逻辑组合,没有额外的二维维度耦合判断。而一维层面的判定由 blocked_range 决定——blocked_range.h 中 is_divisible() 的实现是 my_grainsize < size(),即只有当区间跨度严格大于粒度时才可划分。
在实际遍历中,rows() 与 cols() 是访问子区间边界的主要入口:rows().begin()、rows().end()、cols().begin()、cols().end() 分别给出两个维度的下界与上界。
分裂算法源码剖析:轴选择与切分点计算
blocked_range2d 的核心逻辑集中在私有成员 do_split 中(blocked_range2d.h):
template <typename Split>
void do_split(blocked_range2d& r, Split& split_obj) {
if (my_rows.size()*double(my_cols.grainsize()) < my_cols.size()*double(my_rows.grainsize())) {
my_cols.my_begin = col_range_type::do_split(r.my_cols, split_obj);
} else {
my_rows.my_begin = row_range_type::do_split(r.my_rows, split_obj);
}
}
这段代码揭示了轴选择的精确判据:比较 rows.size() × cols.grainsize() 与 cols.size() × rows.grainsize(),若前者更小则切分列,否则切分行。等价地看,它比较的是"行跨度相对行粒度"与"列跨度相对列粒度"的比值,目的是让子区间在反复切分后,纵横比逐步趋近于"行粒度比列粒度"。这正是规范文档中"subranges to approach the aspect ratio of the respective row and column grain sizes"一句的源码实现。
切分点本身由一维 blocked_range::do_split 计算:
- 基本分裂(blocked_range.h):取中点
middle = my_begin + (my_end - my_begin) / 2u,将[begin, end)切成[begin, middle)与[middle, end)两个近似等长的子区间; - 比例分裂(blocked_range.h):以浮点运算计算右半部分大小
right_part = size_type(float(r.size()) * float(proportion.right()) / float(proportion.left() + proportion.right()) + 0.5f),再据此确定切分点。源码注释说明,对超过 2^24 次迭代的区间使用 32 位浮点会产生可忽略的均匀性误差(约 0.000001%),追求精确切分的场景可参考test_partitioner_whitebox中的实现思路。
此外,blocked_range 的成员声明顺序有讲究:my_end 必须先于 my_begin 声明,否则分裂构造函数会破坏区间不变量(blocked_range.h 中有专门注释说明),并配套了 __TBB_ASSERT 断言校验分裂结果的边界正确性。
与并行算法结合:真实示例与一致性测试
规范测试:接口一致性验证
oneTBB 的一致性测试 conformance_blocked_range2d.cpp 针对 [algorithms.blocked_range2d] 规范逐项验证:
- SerialTest 穷举了行、列起点、终点与粒度的大量组合,断言
empty()等于(row_x==row_y || col_x==col_y),is_divisible()等于(row_y-row_x>row_grain || col_y-col_x>col_grain),并验证分裂后子区间的边界关系(新对象为后半、原对象为前半)。 - ParallelTest 将
blocked_range2d<int>(0, i, 7, 0, j, 5)直接交给parallel_for,逐像素校验Array中每个格子恰好被访问一次,同时通过global_control::max_allowed_parallelism在不同并发度下重复验证。 - 比例分裂测试 使用
proportional_split(3, 1)切分blocked_range2d<int>(0, 100, 0, 100),根据分裂后两个子区间的行大小是否相等来判断切分发生在行轴还是列轴,再校验边界是否与left()/(left()+right())比例吻合。 - Deduction guides 测试(C++17 起)验证了 CTAD 推导:
blocked_range2d r1(v.begin(), v.end(), 2, v2.begin(), v2.end(), 2)可推导为blocked_range2d<迭代器类型1, 迭代器类型2>——这也是ColValue允许与RowValue不同的直接佐证。
真实示例:分形渲染与自组织映射
mold 内嵌的 oneTBB 示例树展示了 blocked_range2d 的典型使用场景:
- fractal.cpp:分形渲染示例将整个画布建模为
blocked_range2d<int>(0, size_y, grain_size, 0, size_x, grain_size),在operator()中通过r.cols().begin()、r.rows().begin()等边界调用render_rect渲染矩形子区域,并分别演示了auto_partitioner与simple_partitioner两种分区器下的用法。 - trace.tbb.cpp:光线追踪示例按屏幕矩形子区域并行,同样以
blocked_range2d<int>作为parallel_for的 range。 - som.hpp:自组织映射示例将二维网格定义为
typedef oneapi::tbb::blocked_range2d<int> subsquare_type;,直接用别名表达"子方块"这一概念。
这些示例的共同模式是:先用 blocked_range2d 把二维迭代空间表达出来,交给 parallel_for 自动切分;在循环体内通过 rows()/cols() 获取子矩形的边界,对局部数据块进行操作。相比手工编写二维分块循环,这种方式把"何时切分、切哪个轴"完全委托给 oneTBB 的并行框架处理,天然适配负载均衡。
与其他 Range 类型的关联
blocked_range2d 是 oneTBB Range 家族的一员,同族类型包括一维 blocked_range、三维 blocked_range3d 以及任意维度的 blocked_rangeNd,后两者在同目录的规范文档 blocked_ranges 中定义。blocked_range2d 内部正是由两个一维 blocked_range 组合而成(成员 my_rows 与 my_cols),维度扩展采用的是"包含一维 range"的递归组合方式,而非平铺索引计算,这保证了任意维度上的粒度控制与分裂语义的一致性。
在实际项目中,选择哪个维度的 range 取决于迭代空间的形状:图像处理、矩阵分块、光线追踪的屏幕分块等天然适合 blocked_range2d;体素或三维网格场景则应考虑 blocked_range3d;而只有单一循环维度的任务使用一维 blocked_range 即可,粒度概念与分裂规则完全一致。
小结
blocked_range2d 用"两个一维 blocked_range + 一个轴选择策略"实现了对二维迭代空间的高效递归切分:empty() 与 is_divisible() 以"或"逻辑组合两个维度;基本分裂与比例分裂分别支持等分与按比例切分;轴选择依据 rows.size()×cols.grainsize() 与 cols.size()×rows.grainsize() 的大小比较,使子区间纵横比逐步逼近行列粒度之比。配合 parallel_for 等算法使用,它是 oneTBB 中处理二维数据并行的基础构件,其规范文档与一致性测试分别位于 blocked_range2d_cls.rst 与 conformance_blocked_range2d.cpp。