简明 OpenMP: C/C++ 并行计算

目录

本文使用的 OpenMP 版本为 \(4.5\), 机器的处理器个数为 \(16\).

1. 简介

1.1. 执行方式

OpenMP 采用 fork-join 的方式进行并行运算: 

             __    __
            / _ 并 _ \
           / /      \ \
------> FORK -- 行 -- JOIN -->
主线程     \ \_    _/ /
            \__ 域 __/

在这个模型中, 一开始只有一个主线程, 然后主线程遇到相关的命令就会创建多个线程.

OpenMP 就是关于

  • 如何控制并行域
  • 并行域中的任务该如何分配
  • 设置集合点控制各个线程
  • 线程之间如何 访问​/​修改 数据

的一种机制.

1.2. 语句的书写

OpenMP 通过 pragma 语句的书写来指导程序进行并行计算, 格式如下: 

#pragma omp DIRECTIVE [CLAUSE [[, ] CLAUSE] ...]

指令 (directive) 可以单独出现, 子句 (clause) 必须出现在指令之后.

每条 pragma 仅指导下一句代码的执行方式.

1.3. 并行域

#pragma omp parallel
cout << 1 << 2;

以上在并行域中调用 std::cout.operator<<, 默认有处理器数量个线程执行了这句代码.

2. 设置线程数量

2.1. 在 pragma 中设定线程数量

#pragma omp parallel num_threads(3)
cout << 1 << 2;

2.2. 运行时 API 调整线程数量

omp_set_num_threads(5);
#pragma omp parallel
cout << 1 << 2;

2.3. 环境变量控制线程数量

#pragma omp parallel
    cout << 1 << 2;

(save-excursion
  (org-previous-block 1)
  (with-environment-variables (("OMP_NUM_THREADS" "3"))
    (org-babel-execute-src-block)))

2.4. TODO Priority of Various Methods for Setting Thread Count1

同时使用 环境变量 和 运行时 API 时, 后者将获得更高的优先权 (吗).

3. 查询线程信息

3.1. 获取线程数量

const int n = 100, dest = rand() % n;
#pragma omp parallel for
for (int i = 0; i < n; ++i)
    if (i == dest)
        cout << omp_get_num_threads();

3.2. 获取线程编号

#pragma omp parallel num_threads(5)
    cout << omp_get_thread_num();

34021

从结果看出, 它是从 0 编号的.

4. 分配 for-loop

4.1. 并行域中的 for-loop

4.1.1. 在并行域中包含 for-loop 和其它代码

我们先来看下并非是单独为 for-loop 创建的并行域, 以和后文作对比. 

#pragma omp parallel
{
    cout << '.';
    #pragma omp for
    for (int i = 0; i < 10; ++i)  // 标准写法, 不建议写成其它形式.
        cout << i;
}

上述并行域中, 众线程首先打印了各自的 '.'. 之后, (从结果可以看出) 都停下来等待, 直到所有线程准备就绪, 才开始执行下一句由 

#pragma omp for

制导的 for-loop. 这个 for-loop 根据默认的策略, 被分配给了若干线程, i.e., 所有 iteration 都被 不重复 不遗漏 地执行了.

4.1.2. 为 for-loop 单独创建并行域

#pragma omp parallel for
for (int i = 0; i < 10; ++i)
    cout << omp_get_thread_num();

这种写法更加方便, 但是在并行域中创建的线程会在离开 for-loop 后被立刻销毁. 这对性能有影响.

4.2. for-loop 的分配策略

我们可以使用 schedule(TYPE, CHUNK_SIZE) 子句设置 OpenMP 分配 for-loop 时使用的策略.

4.2.1. static for-loop schedule

constexpr int number_of_threads = 3;
array<vector<int>, number_of_threads> their_vectors;
#pragma omp parallel for schedule(static), num_threads(number_of_threads)
for (int i = 0; i < 20; ++i)
    their_vectors[omp_get_thread_num()].push_back(i);
for (const auto& its_vec : their_vectors) {
    for (const int i : its_vec)
        cout << i << ' ';
    cout << endl;
 }

众线程按照次序, 每次取 CHUNK_SIZE 个 连续的 iteration. 省略 CHUNK_SIZE 则表示, 每次取尽可能多的 iteration, 且尽量平均分配.

4.2.2. dynamic for-loop schedule

先到先得的方式进行任务分配. 一次性分配 CHUNK_SIZE 个连续的 iteration, 先把任务干完的线程先取下一段任务, 而不是一开始就分配固定的任务数; CHUNK_SIZE 默认为 \(1\). 

constexpr int number_of_threads = 3;
array<vector<int>, number_of_threads> their_vectors;
#pragma omp parallel for schedule(dynamic, 4), num_threads(number_of_threads)
for (int i = 0; i < 24; ++i)
    this_thread::sleep_for(1us * rand()),
      their_vectors[omp_get_thread_num()].push_back(i);
for (const auto& its_vec : their_vectors) {
    for (const int i : its_vec)
        cout << i << ' ';
    cout << endl;
 }

在任务难度不均衡的时候适合用 dynamic; 其余情况下则不推荐, 毕竟频繁的动态的任务申请会造成较大的开销.

4.2.3. guided for-loop schedule

刚开始给每个线程分配比较多的连续的 iteration. 后来每次分配的 iteration 的数量逐渐递减至 CHUNK_SIZE, 省略该参数则降至 \(1\). 

constexpr int number_of_threads = 2;
array<vector<int>, number_of_threads> their_vectors;
#pragma omp parallel for schedule(guided), num_threads(number_of_threads)
for (int i = 0; i < 25; ++i)
    this_thread::sleep_for(1us * rand()),
      their_vectors[omp_get_thread_num()].push_back(i);
for (const auto& its_vec : their_vectors) {
    for (const int i : its_vec)
        cout << i << ' ';
    cout << endl;
 }

4.2.4. TODO runtime for-loop schedule

4.3. 串行执行 parallel for 中的某段代码

以下这段代码要求众线程串行地打印各自 iteration 中的 i: 

constexpr int num_of_threads = 4;
#pragma omp parallel for ordered, schedule(static, 1), num_threads(num_of_threads)
for (int i = 0; i < num_of_threads; ++i) {
    this_thread::sleep_for(50ms * i);
    cout << '(';
#pragma omp ordered
    {
        cout << i;
        this_thread::sleep_for(50ms * i);
        cout << i;
    }
    cout << ')';
 }

(00)(1(1)2(2)33)

可以看到, 结果是一个 S-表达式2; 删除括号之后 (00112233), 数字按​顺序​出现, 且 相同数字之间​无间隔. 这些是 串行 的特征.

而结果中的 (​/​) 并没有连续出现, 这说明 #pragma omp ordered 的前后并没有隐式同步点. 它只是保证: 在 当前 iteration 执行完 被 #pragma omp ordered 制导的代码 之前, 下一个 iteration 不会 开始执行 当前 iteration 正在 执行的 那段代码.

5. 词法地划分并行域

5.1. 并行域中任一代码仅由一个线程执行

使用 section 指令, 对 由 parallel sections 指令制导的并行域 中的代码文本进行划分, 分配给众线程, 划分的区域只会被执行一次. 

#pragma omp parallel sections num_threads(10)
{
#pragma omp section
    cout << omp_get_thread_num();
#pragma omp section
    cout << omp_get_thread_num();
#pragma omp section
    cout << omp_get_thread_num();
}

5.2. 并行域中某段代码仅由一个线程执行

5.2.1. 并行域中某段代码由任意一个线程执行

#pragma omp parallel num_threads(10)
{
#pragma omp single nowait
    for (int i = 0; i < 5; this_thread::sleep_for(4ms), ++i)
        cout << '.';
    this_thread::sleep_for(5ms);
    cout << omp_get_thread_num();
}

若不写 nowait 子句, 则其它线程会等待那个 正在执行 由 single 指令制导的语句 的线程 执行完成, 在一起执行后续的代码. (I.e., 存在一个隐式同步点.)

5.2.2. 并行域中某段代码仅由​主线程​执行

指令 master 和 single 相似, 区别在于 master 制导的代码块只能由主线程执行, 而且 master 指令在代码块结束时没有隐式同步, 不能​指定 nowait 子句. 

#pragma omp parallel
{
#pragma omp master /* nowait */
    cout << omp_get_thread_num();
    cout << '.';
}

6. 同步

6.1. 路障

当遇到 barrier 指令时, 线程必须停下来等待, 直到所有的线程都执行到了这一点, 才能继续往后执行. E.g., 

#pragma omp parallel
{
    this_thread::sleep_for(1us * rand());
    cout << 1;
#pragma omp barrier
    cout << 2;
}

6.2. 取消隐式同步

容易猜到, 在 parallel​&​for​&​sections​&​single 指令之后都有一个隐式的同步点. 我们可以添加 nowait 子句以取消这类隐式路障, e.g., 

constexpr int num_of_threads = 18;
#pragma omp parallel num_threads(num_of_threads)
{
#pragma omp for nowait
    for (int i = 0; i < num_of_threads / 2; ++i)
        cout << '^';
#pragma omp for
    for (int i = 0; i < num_of_threads / 2; ++i)
        cout << '.';
}

7. 附录

参考: https://www.openmp.org/resources/refguides/.

7.1. TODO 预编译指令

表1  directives (不完整)
parallel 制导并行域
for 用在​并行域中的 for 语句​之前, for-loop 的迭代将会被分配给若干线程去执行
parallel for parallel 和 for 的组合, 制导 for 语句
sections 作用域中, 每一个由 section 子句 制导的代码块 将会被若干线程执行
parallel sections parallel 和 sections 的组合
single 用在并行域内, 标注的代码块将只被单个线程执行
critical 互斥域
flush 保证线程内数据影响的一致性
barrier 使并行域内的线程同步
atomic 原子地执行
master 只由主线程执行
threadprivate 指定若干变量为线程专有
表2  clauses (不完整)
private 指定若干变量在各线程中都有自己的私有副本
firstprivate 同 private; 在变量进入 并行域​/​任务分担域 时, 继承主线程的同名变量作为初值
lastprivate 指定若干私有变量的值在并行处理之后复制到主线程的同名变量中, 负责拷贝的线程是 for​/​sections 任务分担中的最后一个线程
reduction 指定若干变量是私有的, 并且在并行处理完这些变量后指定要规约的操作
nowait 指出并发线程可以忽略其它制导指令暗含的路障同步
num_threads 指定并行域内的线程数目
schedule(type, chunk_size) 指定 for 任务当中任务分配调度的类型
shared 指定若干变量为线程间的共享变量
ordered 按照串行循环次序执行 for 任务分担域内指定的代码
copyprivate 配合 single 指令, 将指定线程的专有变量广播到并行域内其它线程的同名变量中
copyin 指定一个 threadprivate 类型的变量需要用主线程的同名变量进行初始化
default 并行域内变量的使用方式, 默认为 shared

7.2. TODO API 函数

表3  运行时 API (不完整)
omp_in_paralled 处于并行域?
omp_get_thread_num 线程号
omp_set_num_threads 设置后续的并行域的线程个数
omp_get_num_threads 当前并行域中的线程个数
omp_get_max_threads 并行域中可用的最大线程数目
omp_get_num_procs 处理器的个数
omp_get_dynamic 支持动态改变线程数目?
omp_set_dynamic 设置线程数目动态改变的功能
omp_get_nested 系统支持并行嵌套?
omp_set_nested 设置并行嵌套的功能
omp_init(_nest)_lock 初始化 (嵌套) 锁
omp_destroy(_nest)_lock 销毁 (嵌套) 锁
omp_set(_nest)_lock 设置 (嵌套) 锁
omp_unset(_nest)_lock (嵌套) 解锁操作
omp_test(_nest)_lock 非阻塞的 (嵌套) 加锁
omp_get_wtime 获取 wall time
omp_set_wtime 设置 wall time

脚注:

1

中文在此处不太能准确地表达.

2

I.e., 括号是匹配的.

作者: 谢骐

Created: 2023-12-17 周日 00:06

Validate