OpenMP 总结

技术总结 评论

本文档尝试快速介绍 OpenMP（如版本 4.5），这是一个简单的 C/C++/Fortran 编译器扩展 C++，它允许在现有源代码中添加并行性，而无需重写它。

引言 多线程的重要性

随着 CPU 速度不再像以前那样显著提高，多核系统正变得越来越流行。要利用这种功能，程序员在并行编程中知识化变得非常重要。本文档试图快速介绍 OpenMP，这是一个简单的 C/C++/Fortran 编译器扩展，允许将并行性添加到现有源代码中，而无需完全重写它。

多个编译器支持

  • GCC (GNU Compiler Collection)
  • Clang++
  • Solaris Studio
  • ICC (Intel C Compiler)
  • Microsoft Visual C++

C++中的OpenMP介绍

OpenMP 由一组编译器#pragmas控制程序工作原理的编译器。pragmas的设计使即使编译器不支持它们，程序仍将产生正确的行为，但没有任何并行性。
下面是演示 OpenMP 的两个简单的示例程序。你可以像这样编译它们：

1
g++ tmp.cpp -fopenmp

Example: Initializing a table in parallel (multiple threads)
此代码将表初始化划分为多个线程，这些线程同时运行。每个线程初始化表的一部分

1
2
3
4
5
6
7
8
9
10
11
12
#include <cmath>
int main()
{
  const int size = 256;
  double sinTable[size];

  #pragma omp parallel for
  for(int n=0; n<size; ++n)
    sinTable[n] = std::sin(2 * M_PI * n / size);

  // the table is now initialized
}

Example: Initializing a table in parallel (single thread, SIMD)
此版本需要至少对 OpenMP 4.0 的编译器支持，并使用并行浮点库，如 AMD ACML 或英特尔SVML(可以在GCC中使用通过添加‑mveclibabi=svml）。

1
2
3
4
5
6
7
8
9
10
11
12
#include <cmath>
int main()
{
  const int size = 256;
  double sinTable[size];

  #pragma omp simd
  for(int n=0; n<size; ++n)
    sinTable[n] = std::sin(2 * M_PI * n / size);

  // the table is now initialized
}

Example: Initializing a table in parallel (multiple threads on another device)
OpenMP 4.0 增加了对将代码卸载到不同设备（如 GPU）的支持。因此，单个程序中可以有三层并行性：单个线程处理多个数据;多个线程同时运行;和多个设备同时运行同一程序。

1
2
3
4
5
6
7
8
9
10
11
12
#include <cmath>
int main()
{
  const int size = 256;
  double sinTable[size];

  #pragma omp target teams distribute parallel for map(from:sinTable[0:256])
  for(int n=0; n<size; ++n)
    sinTable[n] = std::sin(2 * M_PI * n / size);

  // the table is now initialized
}

综上所述，程序中很少指示它并行运行。如果删除 #pragma 行，则结果仍然是运行并执行预期操作。#pragma的有效 C++ 程序。它确实同时计算 N 个值，其中 N 是线程数。在 GCC 中，libgomp 从处理器数目确定这个N的值。
在C 和 C++ 标准中，如果编译器遇到#pragma但它不支持，它将忽略它。因此，添加 OMP 语句可以安全地完成，而不会破坏与旧编译器的兼容性。
还有一个运行时库，可以通过 omp.h 访问，但它不太经常需要。如果需要，可以在不支持 OpenMP #define _OPENMP检查条件编译的格式。

OpenMP语法解析

C 和 C++的所有 OpenMP 构造都用 #pragma，后跟参数，以新行结尾。#pragma通常仅适用于紧接着它的语句，但barrier和flush命令除外，它们没有关联的语句。

The parallel construct

parallel构造用parallel关键字启动并行块。它创建一组N个数目线程（其中 N 在运行时确定，通常来自 CPU 内核的数量，但可能受到一些因素的影响），所有这些线程都执行下一个语句（或下一个块，如果语句是 […] - 存储模块）。语句之后，线程将重新联接到一个线程中。

1
2
3
4
5
#pragma omp parallel
{
  // Code inside this region runs in parallel.
  printf("Hello!\n");
}

在内部，GCC 通过创建一个magic函数并移动关联的代码到该函数中实现此功能，使该块内声明的所有变量成为该函数的局部变量（从而成为每个线程的局部变量）。另一方面，ICC 使用类似于fork()的机制，并且不创建一个magic函数。当然，这两个实现都是有效和语义上相同的。
从上下文共享的变量以透明方式处理，有时通过传递引用，有时通过使用在并行块末尾刷新的寄存器变量（或每当执行flush时）。

Parallelism conditionality clause: if
通过在并行命令中包括 if 子句，可以使并行性成为条件，例如：

1
2
3
4
extern int parallelism_enabled;
#pragma omp parallel for if(parallelism_enabled)
for(int c=0; c<n; ++c)
  handle(c);

在这种情况下，如果parallelism_enabled值为零，则for循环中开启的线程数将始终为一个。

Loop construct: for

for关键字把for-loop拆分，因此每个线程都可以单独处理在循环里面不同的部分。

1
2
3
4
5
6
#pragma omp for
for(int n=0; n<10; ++n)
{
  printf(" %d", n);
}
printf(".\n");

此循环将输出 0…9 一次。但是，它可以按任意顺序执行。它可以输出，例如

1
0 5 6 7 1 8 2 3 4 9.

事实上，上述代码和如下代码效果等同：

1
2
3
4
5
int this_thread = omp_get_thread_num(), num_threads = omp_get_num_threads();
int my_start = (this_thread  ) * 10 / num_threads;
int my_end   = (this_thread+1) * 10 / num_threads;
for(int n=my_start; n<my_end; ++n)
  printf(" %d", n);

因此每个线程都会得到不同的部分代码，并且它们并行的执行只属于自己的部分。

也可以显示的指定线程数目，通过使用关键字num_threads。

1
2
3
4
5
6
7
8
9
#pragma omp parallel num_threads(3)
{
  // This code will be executed by three threads.

  // Chunks of this loop will be divided amongst
  // the (three) threads of the current team.
  #pragma omp for
  for(int n=0; n<10; ++n) printf(" %d", n);
}

注意OpenMP同样对C语言适用。在C里面，你需要显示的指定循环变量使用关键字private，因为C不允许在for循环体内声明变量。

1
2
3
4
int n;
#pragma omp for private(n)
for(n=0; n<10; ++n) printf(" %d", n);
printf(".\n");

parallel, for and a team概念

  • parallel for ：parallel for是两个命令的组合，parallel和for 。：parallel 创建一个新team，for为该team拆分以处理循环的不同部分。
  • for：用于在当前team的线程之间划分 for 循环的工作。它不创建线程，它只将工作划分到当前正在执行团队的线程之间。
  • team: 是当前执行所有线程的组合。在程序开始的时候，team里面只包含一个线程。parallel关键字把当前线程切分为多个线程team，直到执行完毕

调度策略

for-loop 的调度算法可以显式控制。

1
2
3
#pragma omp for schedule(static)
for(int n=0; n<10; ++n) printf(" %d", n);
printf(".\n")

共有5种调度算法：static, dynamic, guided, auto, runtime （OpenMP 4.0之后）。之外在OpenMP4.5之后，又添加了新的3种monotonic, nonmonotonic, simd。

使用如下demo验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <omp.h>
#include <iostream>

#define COUNT 48

int main()
{
#pragma omp parallel for schedule(static)
/* #pragma omp parallel for schedule(static, 2) */
    for(int i = 0;i < COUNT; i++)
    {
        printf("Thread: %d, Iteration: %d\n", omp_get_thread_num(), i);
    }

    return 0;
}

Build and Run:

1
2
$ g++ omp.cpp -fopenmp
$ ./a.out

本机配置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
(base) huang@mlp:~/taichi/omp$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              12
On-line CPU(s) list: 0-11
Thread(s) per core:  2
Core(s) per socket:  6
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               158
Model name:          Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz
Stepping:            10
CPU MHz:             3907.882
CPU max MHz:         4700.0000
CPU min MHz:         800.0000
BogoMIPS:            7399.70
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            12288K
NUMA node0 CPU(s):   0-11

static

static是默认的调度算法。在上面的所有例子中，每个线程独立的决定它们处理哪个loop片段。
schedule(static, chunk-size)子句指定 for 循环具有静态调度类型。OpenMP 将迭代划分为大小块大小的块，并将区块按循环顺序分发到线程。当chunk-size没有指定的时候OpenMP将迭代划分为大小大致相等的区块，并且最多将一个区块分发到每个线程。
下面是关于static调度的例子。

1
2
3
4
5
schedule(static):
****************
                ****************
                                ****************
                                                ****************

实际效果如下：这个分配是静态的，“静态”体现在这个分配过程跟实际的运行是无关的，可以从逻辑上推断出哪几次迭代会在哪几个线程上运行。具体而言，对于一个N次迭代，使用M个线程，那么，[0,size-1]的size次的迭代是在第一个线程上运行，[size, size + size -1]是在第二个线程上运行，依次类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
(base) huang@mlp:~/omp$ ./a.out
Thread: 11, Iteration: 44
Thread: 11, Iteration: 45
Thread: 11, Iteration: 46
Thread: 5, Iteration: 20
Thread: 5, Iteration: 21
Thread: 5, Iteration: 22
Thread: 5, Iteration: 23
Thread: 1, Iteration: 4
Thread: 1, Iteration: 5
Thread: 1, Iteration: 6
Thread: 1, Iteration: 7
Thread: 10, Iteration: 40
Thread: 10, Iteration: 41
Thread: 10, Iteration: 42
Thread: 10, Iteration: 43
Thread: 7, Iteration: 28
Thread: 7, Iteration: 29
Thread: 7, Iteration: 30
Thread: 7, Iteration: 31
Thread: 8, Iteration: 32
Thread: 8, Iteration: 33
Thread: 8, Iteration: 34
Thread: 2, Iteration: 8
Thread: 11, Iteration: 47
Thread: 6, Iteration: 24
Thread: 6, Iteration: 25
Thread: 6, Iteration: 26
Thread: 6, Iteration: 27
Thread: 4, Iteration: 16
Thread: 4, Iteration: 17
Thread: 4, Iteration: 18
Thread: 4, Iteration: 19
Thread: 2, Iteration: 9
Thread: 2, Iteration: 10
Thread: 2, Iteration: 11
Thread: 9, Iteration: 36
Thread: 9, Iteration: 37
Thread: 9, Iteration: 38
Thread: 9, Iteration: 39
Thread: 8, Iteration: 35
Thread: 0, Iteration: 0
Thread: 0, Iteration: 1
Thread: 0, Iteration: 2
Thread: 0, Iteration: 3
Thread: 3, Iteration: 12
Thread: 3, Iteration: 13
Thread: 3, Iteration: 14
Thread: 3, Iteration: 15

1
2
3
4
5
schedule(static, 4):
****            ****            ****            ****
    ****            ****            ****            ****
        ****            ****            ****            ****
            ****            ****            ****            ****
1
2
3
4
5
schedule(static, 8):
********                        ********
        ********                        ********
                ********                        ********
                        ********                        ********

让我解释一下这些例子。我们使用 64 次迭代并行化 for 循环，并且使用四个线程并行化 for 循环。示例中的每一行星数表示一个线程。每列表示迭代。当所有迭代具有相同的计算成本时，静态调度类型是适当的。

dynamic

schedule(dynamic, chunk-size)子句指定 for 循环具有动态调度类型。OpenMP 将迭代划分为大小块大小的块。每个线程执行一个迭代区块，然后请求另一个区块，直到不再有可用的区块。没有将区块以特定顺序分布到线程。每次执行 for 循环时，顺序会更改。
如果没有指定chunk-size，默认为1。下面是一些动态调度的例子。

1
2
3
4
5
schedule(dynamic):
*   ** **  * * *  *      *  *    **   *  *  * *       *  *   *
  *       *     *    * *     * *   *    *        * *   *    *
 *       *    *     * *   *   *     *  *       *  *  *  *  *   *
   *  *     *    * *    *  *    *    *    ** *  *   *     *   *

对于dynamic，没有size参数的情况下，每个线程按先执行完先分配的方式执行1次循环。实际运行情况如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
Thread: 5, Iteration: 4
Thread: 5, Iteration: 12
Thread: 5, Iteration: 13
Thread: 5, Iteration: 14
Thread: 5, Iteration: 15
Thread: 5, Iteration: 16
Thread: 5, Iteration: 17
Thread: 5, Iteration: 18
Thread: 5, Iteration: 19
Thread: 5, Iteration: 20
Thread: 5, Iteration: 21
Thread: 5, Iteration: 22
Thread: 5, Iteration: 23
Thread: 5, Iteration: 24
Thread: 5, Iteration: 25
Thread: 5, Iteration: 26
Thread: 5, Iteration: 27
Thread: 5, Iteration: 28
Thread: 5, Iteration: 29
Thread: 5, Iteration: 30
Thread: 5, Iteration: 31
Thread: 5, Iteration: 32
Thread: 5, Iteration: 33
Thread: 5, Iteration: 34
Thread: 5, Iteration: 35
Thread: 5, Iteration: 36
Thread: 5, Iteration: 37
Thread: 5, Iteration: 38
Thread: 5, Iteration: 39
Thread: 5, Iteration: 40
Thread: 5, Iteration: 41
Thread: 5, Iteration: 42
Thread: 5, Iteration: 43
Thread: 5, Iteration: 44
Thread: 5, Iteration: 45
Thread: 5, Iteration: 46
Thread: 5, Iteration: 47
Thread: 9, Iteration: 1
Thread: 0, Iteration: 6
Thread: 3, Iteration: 2
Thread: 7, Iteration: 0
Thread: 6, Iteration: 5
Thread: 8, Iteration: 3
Thread: 10, Iteration: 8
Thread: 1, Iteration: 7
Thread: 11, Iteration: 9
Thread: 4, Iteration: 10
Thread: 2, Iteration: 11

1
2
3
4
5
schedule(dynamic, 1):
    *    *     *        *   *    * *  *  *         *  * *  * *
*  *  *   * *     *  * * *    * *      *   ***  *   *         *
 *   *  *  *  *    ** *    *      *  *  * *   *  *   *   *
  *    *     *  **        *  * *    *          *  *    *  * *  *
1
2
3
4
5
schedule(dynamic, 4):
            ****                    ****                    ****
****            ****    ****            ****        ****
    ****            ****    ****            ****        ****
        ****                    ****            ****

实际运行情况如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
(base) huang@mlp:~/taichi/omp$ ./a.out
Thread: 0, Iteration: 12
Thread: 0, Iteration: 13
Thread: 0, Iteration: 14
Thread: 0, Iteration: 15
Thread: 3, Iteration: 28
Thread: 3, Iteration: 29
Thread: 3, Iteration: 30
Thread: 3, Iteration: 31
Thread: 8, Iteration: 8
Thread: 8, Iteration: 9
Thread: 8, Iteration: 10
Thread: 8, Iteration: 11
Thread: 4, Iteration: 4
Thread: 4, Iteration: 5
Thread: 4, Iteration: 6
Thread: 4, Iteration: 7
Thread: 11, Iteration: 36
Thread: 11, Iteration: 37
Thread: 11, Iteration: 38
Thread: 11, Iteration: 39
Thread: 5, Iteration: 24
Thread: 5, Iteration: 25
Thread: 7, Iteration: 32
Thread: 2, Iteration: 44
Thread: 9, Iteration: 16
Thread: 10, Iteration: 0
Thread: 10, Iteration: 1
Thread: 10, Iteration: 2
Thread: 10, Iteration: 3
Thread: 7, Iteration: 33
Thread: 7, Iteration: 34
Thread: 7, Iteration: 35
Thread: 9, Iteration: 17
Thread: 9, Iteration: 18
Thread: 9, Iteration: 19
Thread: 6, Iteration: 20
Thread: 6, Iteration: 21
Thread: 6, Iteration: 22
Thread: 6, Iteration: 23
Thread: 5, Iteration: 26
Thread: 5, Iteration: 27
Thread: 2, Iteration: 45
Thread: 2, Iteration: 46
Thread: 2, Iteration: 47
Thread: 1, Iteration: 40
Thread: 1, Iteration: 41
Thread: 1, Iteration: 42
Thread: 1, Iteration: 43
1
2
3
4
5
schedule(dynamic, 8):
                ********                                ********
                        ********        ********
********                        ********        ********
        ********

当迭代需要不同的计算成本时，动态调度类型是合适的。这意味着迭代之间的平衡很差。动态计划类型比静态计划类型具有更高的开销，因为它在运行时动态分布迭代。

Guided

Guided调度算法类似于动态计划类型。OpenMP 再次将迭代划分为块。每个线程执行一个迭代块，然后请求另一个区块，直到不再有可用的区块。与动态调度类型的区别在于chunk-size。区块的大小与未分配迭代数除以线程数成正比。因此，区块的大小减小。
区块的最小大小由chunk-size设置。我们在调度确定它：schedule(guided, chunk-size)。但是，包含上次迭代的区块的大小可能小于chunk-size。
如果我们不指定chunk-size，则默认为 1。对应示例如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
schedule(guided):
                            *********                        *
                ************                     *******  ***
                                     *******                   *
****************                            *****       **    *

schedule(guided, 2):
                ************                     ****     **
                                     *******         ***    **
                            *********
****************                            *****       **    **

schedule(guided, 4):
                                     *******
                ************                     ****    ****
                            *********
****************                            *****    ****    ***

schedule(guided, 8):
                ************                 ********        ***
****************
                                     ********
                            *********                ********

我们可以看出chunk的大小一直在递减。第一个chunk总是有16个iteration，这是因为我们有64个iteration共有4个线程去并行这个loop。
我们还可以看到，最小区块大小在计划子句中确定。唯一的例外是最后一个区块。其大小可能低于规定的最小大小。

当迭代之间不平衡时，引导调度类型是合适的。初始区块较大，因为它们减少了开销。较小的区块在计算结束时填充计划并改善负载平衡。当在计算接近尾声时发生负载平衡不佳的情况时，此调度类型尤其合适。

Auto

Auto调度算法将调度决策委托给编译器和runtime。在下面的示例中，编译器/系统确定静态调度。

1
2
3
4
5
schedule(auto):
****************
                ****************
                                ****************
                                                ****************

Runtime

Runtime调度策略将有关计划的决定推迟到运行时。本例中，我们已经描述了指定计划类型的不同方法。一个选项是环境变量OMP_SCHEDULE，另一个选项是函数omp_set_schedule。

Default

如果我们不指定任何调度策略：

1
2
3
#pragma omp parallel for
for (...)
{ ... }

OpenMP使用默认的调度策略，由内部的控制变量def-sched-var决定。在我的机器上面结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
Thread: 5, Iteration: 20
Thread: 5, Iteration: 21
Thread: 5, Iteration: 22
Thread: 5, Iteration: 23
Thread: 1, Iteration: 4
Thread: 1, Iteration: 5
Thread: 1, Iteration: 6
Thread: 1, Iteration: 7
Thread: 0, Iteration: 0
Thread: 0, Iteration: 1
Thread: 0, Iteration: 2
Thread: 0, Iteration: 3
Thread: 6, Iteration: 24
Thread: 6, Iteration: 25
Thread: 6, Iteration: 26
Thread: 6, Iteration: 27
Thread: 9, Iteration: 36
Thread: 9, Iteration: 37
Thread: 9, Iteration: 38
Thread: 9, Iteration: 39
Thread: 10, Iteration: 40
Thread: 4, Iteration: 16
Thread: 4, Iteration: 17
Thread: 4, Iteration: 18
Thread: 4, Iteration: 19
Thread: 2, Iteration: 8
Thread: 2, Iteration: 9
Thread: 2, Iteration: 10
Thread: 2, Iteration: 11
Thread: 8, Iteration: 32
Thread: 8, Iteration: 33
Thread: 8, Iteration: 34
Thread: 8, Iteration: 35
Thread: 3, Iteration: 12
Thread: 3, Iteration: 13
Thread: 3, Iteration: 14
Thread: 3, Iteration: 15
Thread: 7, Iteration: 28
Thread: 7, Iteration: 29
Thread: 7, Iteration: 30
Thread: 7, Iteration: 31
Thread: 10, Iteration: 41
Thread: 10, Iteration: 42
Thread: 10, Iteration: 43
Thread: 11, Iteration: 44
Thread: 11, Iteration: 45
Thread: 11, Iteration: 46
Thread: 11, Iteration: 47

参考：
https://bisqwit.iki.fi/story/howto/openmp/
https://www.openmp.org/wp-content/uploads/omp-hands-on-SC08.pdf
https://stackoverflow.com/questions/1448318/omp-parallel-vs-omp-parallel-for
http://jakascorner.com/blog/2016/06/omp-for-scheduling.html

黄志远研发攻城狮

靡不有初 鲜克有终