oneTBB 二维并行迭代区间 blocked_range2d 详解:从 API 用法到切分源码原理
oneTBB 二维并行迭代区间 blocked_range2d 详解:从 API 用法到切分源码原理
blocked_range2d 是 oneAPI Threading Building Blocks(oneTBB)提供的二维可递归切分区间模板类,用于把 [row_begin, row_end) × [col_begin, col_end) 这样的二维半开值空间切分成适合并行执行的子块,是 parallel_for、parallel_reduce、parallel_scan 等并行算法处理二维数据(矩阵、图像、网格)时的标准 Range 参数。阅读本文后,你将掌握 blocked_range2d 的完整构造函数语义、行列各自独立粒度(grainsize)的配置方法、两种切分(split 与 proportional_split)的行为差异,以及其底层“按纵横比选轴切分”的实现原理。
blocked_range2d 是什么
blocked_range2d 表示一个可递归切分的二维半开区间 [i0,j0)×[i1,j1),其中 i 方向通常称为“行”(rows),j 方向称为“列”(cols)。与一维的 blocked_range 不同,blocked_range2d 的两个轴各自拥有独立的切分阈值(grain size);只要任意一个轴可切分,整个二维区间就是可切分的(divisible)。
它是 Range 概念(见 Range 需求文档)的一个实现:支持复制构造、empty()、is_divisible()、基本切分构造和可选的比例切分构造。该类的官方参考文档位于 blocked_range2d 类参考,实际声明位于头文件 include/oneapi/tbb/blocked_range2d.h(同时也在旧命名空间头文件 include/tbb/blocked_range2d.h 中可用)。
类模板签名
// Defined in header <oneapi/tbb/blocked_range2d.h>
namespace oneapi {
namespace tbb {
template<typename RowValue, typename ColValue=RowValue>
class blocked_range2d {
public:
// Types
using row_range_type = blocked_range<RowValue>;
using col_range_type = blocked_range<ColValue>;
// Constructors
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);
blocked_range2d( RowValue row_begin, RowValue row_end,
ColValue col_begin, ColValue col_end );
// Splitting constructors
blocked_range2d( blocked_range2d& r, split );
blocked_range2d( blocked_range2d& r, proportional_split proportion );
// Capacity
bool empty() const;
// Access
bool is_divisible() const;
const row_range_type& rows() const;
const col_range_type& cols() const;
};
} // namespace tbb
} // namespace oneapi
RowValue 和 ColValue 分别代表行、列维度上的值类型,ColValue 默认为 RowValue,因此二维同类型区间可以直接写 blocked_range2d<int>。两个模板参数都必须满足 BlockedRangeValue 需求:可复制、可赋值、支持 operator<、支持差值 operator-(结果可转换为 size_t)、支持 Value + 整数偏移。典型的合法类型包括整型、指针以及差值可隐式转换为 size_t 的 STL 随机访问迭代器。
成员类型:rows 与 cols 各是什么
using row_range_type = blocked_range<RowValue>;
using col_range_type = blocked_range<ColValue>;
blocked_range2d 内部并不重新造轮子,而是复合了两个一维 blocked_range:row_range_type 是行方向的一维区间类型,col_range_type 是列方向的一维区间类型。从源码 include/oneapi/tbb/blocked_range2d.h 可以看到,类内部只保存两个成员:
private:
row_range_type my_rows;
col_range_type my_cols;
因此,rows() 返回的是一维行区间(含行向 begin/end/grain size),cols() 返回的是一维列区间;遍历二维空间时,标准的双层循环就是分别对 rows() 和 cols() 做一维迭代。一维 blocked_range 的完整语义见 blocked_range 类参考。
构造函数:完整参数与默认粒度
六参数版本(指定行列各自粒度)
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);
效果:构造一个表示二维值空间的 blocked_range2d,该空间是半开笛卡尔积 [row_begin, row_end) x [col_begin, col_end),并分别给定行、列的粒度。官方文档给出的示例:
blocked_range2d<char,int> r('a', 'z'+1, 3, 0, 10, 2 );
该语句构造了一个包含所有形如 (i, j) 值对的二维空间:i 从 'a' 到 'z'(共 26 个值)、行粒度 3;j 从 0 到 9、列粒度 2。注意半开区间意味着 'z'+1 作为上界,实际取值到 'z' 为止,10 作为上界,实际取值到 9 为止。
四参数版本(默认粒度 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 的构造默认参数正是 grainsize_=1(见 include/oneapi/tbb/blocked_range.h)。
粒度注意事项:一维 blocked_range 在 debug 版本中会对 grainsize>0 做断言校验(__TBB_ASSERT( my_grainsize>0, "grainsize must be positive" )),因此传给 blocked_range2d 的粒度也必须为正。粒度表示“视为不可再切分的最大区间大小”,即只有当某一轴的长度大于其粒度时,该轴才被认为可切分(is_divisible() == (size() > grainsize()))。
切分构造函数:split 与 proportional_split
基本切分构造(split)
blocked_range2d(blocked_range2d& range, split);
前置条件:is_divisible() 为 true。
效果:把 range 切分成两个子区间。新构造出的 blocked_range2d 近似为原 range 的后半部分,而 range 被更新为剩余的前半部分;两个子区间保持与原区间相同的粒度。切分要么按行、要么按列进行。
关键在于选轴策略:切分轴的选择旨在经过反复切分后,让子区间的纵横比趋向于行列粒度的比例。从 include/oneapi/tbb/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 的大小:当行区间相对列区间“过长”(换算到粒度单位后行更大)时切分行,否则切分列。这样反复切分后,子块的行列长度之比会趋近于 row_grainsize : col_grainsize 的纵横比,从而避免出现“细长条”子块导致负载不均。
一维层面的基本切分取中点:do_split 计算 middle = r.my_begin + (r.my_end - r.my_begin) / 2,把旧区间的 my_end 更新为 middle,新区间从 middle 开始(见 include/oneapi/tbb/blocked_range.h)。
比例切分构造(proportional_split)
blocked_range2d(blocked_range2d& range, proportional_split proportion);
前置条件:is_divisible() 为 true。
效果:把 range 按给定 proportion 沿某一轴切分成两个子区间。选轴方式与基本切分构造完全一致;选好轴后,再对该轴执行比例切分。另一轴以及两个子区间的粒度保持与原区间相同。
proportional_split 通过左右两个 size_t 系数描述比例,构造形如 proportional_split(left, right),并提供 left()、right() 访问器,以及到 split 的显式转换(便于与不支持比例切分的 Range 类型互操作),详见 proportional_split 类参考。一维 blocked_range 的比例切分按 right / (left + right) 计算右侧部分长度并四舍五入:
size_type right_part = size_type(float(r.size()) * float(proportion.right())
/ float(proportion.left() + proportion.right()) + 0.5f);
return r.my_end = Value(r.my_end - right_part);
(见 include/oneapi/tbb/blocked_range.h)。比例切分常用于工作负载不均衡的场景,例如 parallel_reduce 需要按已知的不均衡比例划分区间。
测试验证切分行为
仓库的 conformance_blocked_range2d.cpp 提供了比例切分的验证用例:对 blocked_range2d<int> original(0, 100, 0, 100) 用 proportional_split ps(3, 1) 切分后,检查切分发生在行轴还是列轴(比较 first.rows().size() 与 second.rows().size() 是否相等),再通过 utils::check_range_bounds_after_splitting 校验被切分轴的新旧边界是否符合 left : right = 3 : 1 的比例。
容量与访问接口
bool empty() const
效果:判断区间是否为空。
返回值:rows().empty() || cols().empty(),即只要行或列任一方向为空,整个二维区间即为空。源码实现与此完全一致(include/oneapi/tbb/blocked_range2d.h)。
bool is_divisible() const
效果:判断区间能否被切分成子区间。
返回值:rows().is_divisible() || cols().is_divisible(),即只要任一轴的长度超过其粒度,二维区间就可切分。一维语义为 size() > grainsize()(include/oneapi/tbb/blocked_range.h)。
const row_range_type& rows() const / const col_range_type& cols() const
分别返回值空间中“行”和“列”所对应的一维 blocked_range。它们是只读访问器(返回 const 引用),配合一维的 begin()/end()/grainsize() 使用。
在 parallel_for 中实际使用 blocked_range2d
blocked_range2d 最常见的用法是直接作为 parallel_for 的 Range 参数。参考 conformance_blocked_range2d.cpp 中 Striker 的写法,函数对象通过 r.rows() 和 r.cols() 两层循环遍历子块:
const int N = 1<<10;
unsigned char Array[N][N];
struct Striker {
void operator()( const oneapi::tbb::blocked_range2d<int>& r ) const {
for( oneapi::tbb::blocked_range<int>::const_iterator i=r.rows().begin(); i!=r.rows().end(); ++i )
for( oneapi::tbb::blocked_range<int>::const_iterator j=r.cols().begin(); j!=r.cols().end(); ++j )
++Array[i][j];
}
};
// 行粒度 7、列粒度 5
const oneapi::tbb::blocked_range2d<int> r( 0, i, 7, 0, j, 5 );
oneapi::tbb::parallel_for( r, Striker() );
该测试在 global_control::max_allowed_parallelism 限定的并发级别下运行,并在结束后逐一校验 Array 中每个格子是否恰好被访问一次(Array[k][l] != (k<i && l<j)),从而证明无论 blocked_range2d 如何被递归切分,子块的并集恰好覆盖整个二维空间且不重不漏——这正是 Range 语义的核心保证。
典型的二维图像/矩阵并行处理代码如下:
#include <oneapi/tbb/blocked_range2d.h>
#include <oneapi/tbb/parallel_for.h>
void process_matrix(float* data, int rows, int cols) {
oneapi::tbb::parallel_for(
oneapi::tbb::blocked_range2d<int>(0, rows, 16, 0, cols, 32),
& {
for (int i = r.rows().begin(); i != r.rows().end(); ++i)
for (int j = r.cols().begin(); j != r.cols().end(); ++j)
data[i * cols + j] = compute(i, j);
});
}
这里行粒度 16、列粒度 32 表示每个子块大约覆盖 16×32 个元素,粒度按行、列分别调优,可以让子块形状贴合缓存行与负载特性。
与 blocked_range3d、blocked_nd_range 的关系
blocked_range2d 是 blocked_range3d(三维扩展,增加 pages() 维度与 page_grainsize)的直接基础;更高维的 blocked_nd_range 也是同一系列。三者都遵守同样的 Range 需求,并把“切分轴选择”推广到多轴:反复切分后子块各维度长度之比趋向于各轴粒度之比。选择 blocked_range2d 而非嵌套两个一维 blocked_range 的收益在于,二维类统一管理纵横比切分策略,并且只需一次函数对象调用即可拿到完整子块,减少了调度开销。
源码级要点小结
- 复合而非继承:
blocked_range2d内部持有两个一维blocked_range成员(my_rows、my_cols),并通过友元关系访问一维类的私有切分辅助函数do_split(见 include/oneapi/tbb/blocked_range.h)。 - 切分轴选择:比较
rows.size()×cols.grainsize与cols.size()×rows.grainsize,等价于比较rows.size()/rows.grainsize与cols.size()/cols.grainsize(可切分“份数”),始终切分份数更大的轴,从而维持子块纵横比与粒度比例一致。 - 切分不改变粒度:无论基本切分还是比例切分,两个子区间都保留原区间的行列粒度;
my_grainsize在切分构造中从r直接继承。 - 可切分条件:
is_divisible()是行列可切分性的“或”,只要任一轴size() > grainsize()即为真;empty()是行列空性的“或”。 - 类型要求:
RowValue/ColValue只需满足 BlockedRangeValue(可复制、可赋值、支持<、-、+偏移),因此既可以是整数,也可以是指针或随机访问迭代器,无需是算术类型。