oneTBB 二维并行迭代区间 blocked_range2d 详解:从 API 用法到切分源码原理

原创2026-10-08 19:04:041,913 阅读
文章标签:并发编程高性能计算

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(可复制、可赋值、支持 <、-、+ 偏移),因此既可以是整数,也可以是指针或随机访问迭代器,无需是算术类型。
登录后查看全文
oneTBB