DinS          Written on 2017/7/12

一、何谓OpenMP?

现在的计算机通常都有多个核心，这为并行编程开创了可能。
正常的程序都是串行的，执行完一句再执行下一句。并行编程是让多个核心同时执行程序，一次获得更高的效率。
一般的程序员很难直接与硬件打交道，为了简化并行编程出现了OpenMP和MPI。这些都是并行编程的API。多个核心共享内存使用OpenMP，PC机都属于这个范畴。每个计算节点贡献内存，节点之间是分布式内存，使用MPI，网络计算属于这一范畴。

本文探讨OpenMP。（注：想学多线程编程的可看这里）首先需要说一下并行计算的原理，见下图：

共享内存计算机上并行程序的基本思路就是使用多线程，从而将可并行负载分配到多个物理计算核心，从而缩短执行时间（同时提高CPU利用率）。
主线程执行算法的顺序部分，当遇到需要进行并行计算式，主线程派生出（创建或者唤醒）一些附加线程。
在并行区域内，主线程和这些派生线程协同工作，在并行代码结束时，派生的线程退出或者挂起，同时控制流回到单独的主线程中，称为汇合。

OpenMP的作用在哪里呢？就是使用一些接口告知程序该进入并行区，并分配出线程进行计算，然后合并。所有这些底层操作都不需要程序员关注。

二、初识OpenMP

使用OpenMP很简单，编译器里一般都有个开关，打开即可。以VS为例，只需要在项目属性->C/C++ ->语言里开启OpenMP即可。

之后只要按照API进行编程即可。具体而言先看如下代码：

首先需要包含头文件omp.h。

#pragma那句称为Compiler Directive，指示编译器要进入并行区，{}内就是并行区的代码。

{}里面使用了OpenMP的库函数，作用是取得执行该代码的线程编号。

Compiler Directive的基本格式是：#pragma omp directive-name [clause[ [,] clause]…]
具体有哪些内容稍后讲解，现在只关注“#pragma omp parallel”的意思，也是最基本的意思。
“#pragma omp parallel”表示其后语句将被多个线程并行执行，线程个数由系统预设。也可以显示指定线程数，比如#pragma omp parallel num_threads(4)”。

总而言之，上述这段代码的功能是让多个线程输出字符串。
运行结果是什么呢？下面是相同代码运行了4次的结果：

非常有趣，因为出乎我们的预期。观察一下会发现这么几件事：

1.一共出现了4次Hello World，也就是说在并行区的代码被执行了4次。
因此pragma omp parallel带来的并行计算是使用不同线程执行相同代码。这一点不要搞错。
2.输出的顺序是无序的。这意味着不同线程之间不存在固定的先后顺序关系，每次执行的效果都不一样。
3.即使是在同一行代码中也可能被打乱次序执行。
结果中有出现连续两个Hello World的情况，然后跟两个线程编号。

我们的预期是什么？是四句完整的Hello World，每一句由不同线程执行。
虽然我们无法锁定线程之间的执行顺序，但是我们至少要保证输出的逻辑完整性。

为此我们只需要加入一行代码即可做到这一点：

两次执行的效果：

问题来了：这句#pragma omp critical有什么作用？
其作用是定义一个临界区，保证同一时刻只有一个线程访问临界区。
这么说还是有点抽象，通俗的说就是不允许一个线程在执行一行代码期间被其他线程打断。概念上看就是输出的这一行代码是一个整体的单元，在执行过程中不能插入其他线程。当然这只是对一个线程内部而言，线程之间的先后顺序依然无法保证。
#pragma omp critical只对紧邻的下一行代码有效。

三、数据并行

通过上例我们知道了如何使用OpenMP，但是这并不是我们想要的。一般来说我们不会希望同样的代码执行n次，意义不大。我们更多的情况是希望把一个计算拆成若干块，每个线程执行一部分，然后将结果合并，这样才能体现并行编程的威力。

为了实现这种效果，需要使用#pragama omp for
顾名思义，OpenMP for指示将C++ for循环的多次迭代划分给多个线程（划分指，每个线程执行的迭代互不重复，所有线程的迭代并起来正好是C++ for循环的所有迭代）为了达到划分目的，for循环需要遵循一些限制条件：
1.在执行C++ for之前要能够确定循环次数，这意味着for中不应含有break等
2.for的各次迭代的执行顺序不影响结果正确性，这是因为线程之间的执行顺序无法保证
3.for的循环标志i必须是int型，终止条件必须是< <= > >=之一。

看一个代码示例：

功能很简单，就是给数组赋值。
使用omp for的限制条件都满足，所以可以通过编译，效果如下：

从效果图我们可以知道几条信息：
1.for循环的100次迭代确实被4个线程分别执行，因此理论上来说执行时间变成顺序执行的四分之一
2.for循环的100次迭代的划分很均匀，以25次为一组分别由4个线程执行

可以说满足了我们的需求。那么可不可以手动指定分组呢？
当然可以，使用schedule指令。

schedule(static, size)将所有迭代按每连续size个为一组，然后将这些组轮转分给各个线程。
schedule(dynamic, size)同样分组，然后依次将每组分给目前空闲的线程（故叫动态）。
schedule(guided, size) 把迭代分组，分配给目前空闲的线程，最初组大小为迭代数除以线程数，然后逐渐按指数方式（依次除以2）下降到size。
schedule(runtime)的划分方式由环境变量OMP_SCHEDULE定义。

不过一般而言用默认的设置就够了。

#pragama omp for大概是最常使用到的指令。

四、任务并行

使用#pragma omp sections可以将代码段划分为若干sections，每一个section由一个线程执行。
如下代码：

在#pragma omp sections的区域内使用了若干#pragma omp section划分子区域
这些子区域的代码将分别由不同线程执行，但是具体是哪个线程无法确定。

效果如下：

sections相当于给程序员更大的自由度，让其自主决定代码将如何被划分。

五、其他常用指令

这里涉及到许多多线程的概念，可参考《Windows多线程编程》专题。

#pragma omp single：指示代码将仅被一个线程执行，具体是哪个线程不确定
#pragma omp master：指示代码将仅被主线程执行
#pragma omp barrier：定义一个同步，所有线程都执行到该行后，所有线程才继续执行后面的代码。for/sections自带隐藏的barrier
#pragma omp atomic:保证变量被原子的更新，即同一时刻只有一个线程再更新该变量。#pragma omp critical也可以实现此功能，但是大材小用，效率不如atomic
#pragma omp ordered:确保代码将被按迭代次序执行，只能在有ordered的for中使用，这个还是很有实用价值的，看下面的代码：

DoCalc函数模拟一个计算过程，这里就是根据输入的整数生成一个字符串。

main中准备一个数据，相当于并行计算的数据。

这里使用了for ordered指令，此处仅仅是配合#pragma omp ordered使用，并不是让整个for顺序执行。for的计算部分是并行的。

后面再次出现ordered，并用{}圈出区域，该区域是顺序执行。此处模拟写数据库过程，是按顺序一条一条写的。

效果如下：

一开始出现了四个done，说明计算部分确实是由多个线程并行完成的，但是后面的输出部分却是按照for的顺序一条一条输出的。

有什么用呢？有很大作用。
在某些情况下，我们希望计算是并行的，但是给出的结果操作是按顺序进行的，比如要写数据库之前需要执行SELECT操作，筛选出一条记录，再写入。并且记录的顺序跟数据顺序一致，此时ordered的作用就体现出来了。

不过也可以不使用omp的指令使用编程技巧达到同样效果。

六、线程间变量

虽然大多数情况下我们不需要直接对线程间变量进行操作，但是OpenMP提供了一系列指令。
首先需要理解线程的变量是什么意思。在并行区内声明的变量是线程私有的，并行区外声明的变量是所有线程共享的。
看如下代码：

a在并行区之前声明，b在并行区内声明，输出a/b的地址，即查看a/b到底是不是同一个变量。

结果如下：

可见a对所有线程而言是同一个变量，但是每一个线程都有一个独立的b，这也与我们的直觉一致。

那么我们可不可以手动操作这些变量的归属问题呢？当然是可以的。
#pragma omp threadprivate(a)： 顾名思义，将变量a变为线程私有的。

仅仅增加了一句threadprivate指令，但是编译不过，报错：

看来使用omp有诸多限制，更改代码如下：

将a移到了全局变量，结果如下：

可见a在每个线程中是不一样的了。

接下来的问题是a非得是全局变量或者静态数据才能变成线程私有？
我们可以使用private达到目的，如下代码：

效果：

a在每个线程中是不一样的。

那么现在你应该有疑问：threadprivate(a)和private(a)有什么区别？
从上面的例子来看private(a)的适用范围应该更广啊？
让我们来做个试验，如下代码：

意图很明显，就是打印出a/b/c的地址和值，看看有什么不同

运行结果如下：

运行失败，原因是变量a没有初始化就使用了。
奇怪啊？A明明在并行区之前被初始化了，值是0，为什么会报错？
让我们把输出a的值的代码注释掉看看效果：

运行正常，从这里可以看出几个问题：
1.a的地址都不同，说明每个线程中的a确实不一样，private的作用是有效的
2.c的地址也都不同，说明每个线程中的c确实不一样，但是c的值却是一样的，即初始化时的值

再结合刚才运行失败的原因，我们应该就能够知道threadprivate和private的区别了：
private(a)将变量a由默认线程共享变为线程私有的，此时每个线程会调用默认构造函数生成一个变量a的副本。因为int没有默认构造函数，所以没有被初始化，就报错了。
threadprivate则是多了一步初始化动作，将线程外的值作为副本的值。

我们可以更加精确地操作private。
firstprivate(a)会用共享版本变量a来初始化
lastprivate在private基础上，将执行最后一次迭代（for）或最后一个section块（sections）的线程的私有副本拷贝到共享变量。
shared和private相对，将变量声明为共享的。也就是说一个线程修改了变量后，其他线程中的该变量的值也变了。

---

虽然介绍了这么多，但是OpenMP主要的作用是并行计算而不是多线程编程，协调线程之间的问题，比如互斥或同步不是他的强项。用得最多的是并行for计算，从高层抽象地解决并行计算问题，不需要程序员过多关注底层复杂的问题。