「并行学习」 OpenMP_openmp collapse

OpenMP

What’s OpenMP

OpenMP == Open specification for Multi-Processing
An API : multi-threaded, shared memory parallelism

Portable: the API is specified for C/C++ and Fortran

Fork-Join model: the master thread forks a specified number of slave threads and divides task among them

Compiler Directive(指示) Based: Compiler takes care of generating code that forks/joins threads and divide tasks to threads

#include <omp.h>
// Serial code
int A[10], B[10], C[10];
// Beginning of parallel section. Fork a team of threads. 

#pragma omp parallel for num_threads(10)
{
  for (int i=0; i<10; i++)
  A[i] = B[i] + C[i];
} /* All threads join master thread and terminate */
1
2
3
4
5
6
7
8
9
10

OpenMP Directives(C/C++ Format):

每一个directive后面只能接一个succeeding statement，必须是被structured block的。

Parallel Region Constructs

Parallel Directive

并行区域是一块通过多线程（multiple threads）执行的代码。

1. 当使parallel构建时，实际上产生了一系列的线程（threads）。

2. parallel region中的代码实际上会被多个线程执行，每个线程执行的是相同的代码。

3. 在并行的结束部分将会有一个barrier，使线程之间同步。

4. 当一个线程终止时，所有的线程都会终止。

限制

1. 不能在parallel region中调用其他文件的function。
2. 不能使用goto或者jump语句，因为这样可能跳转到非parallel区域。但可以调用其他的function call（虽然不建议）。

多少个Threads

1. 首先看IF子句：如果是FALSE，那么并行部分将会被序列执行
   例如：#pragma omp parallel IF(para == true)
2. 然后看num_threads()子句：
   例如：#pragma omp parallel num_threads(10)
3. 然后看是否使用了omp_set_num_threads()库函数：需要在执行parallel region之前执行。
4. 查看OMP_NUM_THREADS环境变量：需要在执行parallel region之前设置。
5. 默认：使用一个node上CPU的个数

嵌套调用Parallel Region

// A total of 6 “hello world!” is printed
#pragma omp parallel num_threads(2)
{
	{
    #pragma omp parallel num_threads(3)
  	printf("hello world!");
  }
}
1
2
3
4
5
6
7
8

1. 有时候，有些库可能不支持这样的嵌套操作，这个时候就可以使用omp_get_nested()函数，来检查是否可以嵌套。

2. 使用omp_set_nested(bool)来enable/disable parallel region；或通过设置OMP_NESTED环境变量。

3. 如果嵌套是disable的状态，或者是不support的，那么在嵌套parallel region中只会创建一个线程。

Work-Sharing Construct

定义：

1. work-sharing construct将code region中的任务分开，让不同的线程执行不同的任务。
2. work-sharing construct不会创建新的threads，创建threads的工作是parallel做的。
3. 同 Parallel Construct一样，虽然在进入程序时没有barrier，但是在程序执行的最终阶段会有一个barrier（但是可以用clause来override这个设定）。

DO/for Directive

是数据的并行。只要数据和数据之间没有dependency，就可以使用DO/for来让每一个线程出来一部分的数据。

DO/for Directive Specific Clauses：

1. nowait：最后没有了barrier，不进行同步。
2. schedule：描述iterations是怎么在threads之间分配的。
3. ordered：不同的线程并发执行，直到遇到该ordered区域为止，然后按与在串行循环中执行顺序相同的顺序依次执行该区域。这仍然允许一定程度的并发性，尤其是在该区域之外的代码段ordered具有大量运行时间的情况下。
4. collapse：使用在嵌套循环中。实际上是将多层的嵌套转换为一个一层的特别长的嵌套。

Schedule Clause

1. STATIC：
   schedule(static, chunk-size)循环结构的子句指定for循环具有静态调度类型。OpenMP将迭代划分为多个大小块，chunk-size并将其按循环顺序分配给线程。
   如果未chunk-size指定 ，则OpenMP将迭代划分为大小近似相等的块，并且最多将一个块分配给每个线程。

2. DYNAMIC：

   当一个线程完成了一个chunk（ default size:1 ）后，就会动态的分配给它其他的任务。先做完的便可以做更多的iteration，保证了每个thread做的任务的平均。

3. GUIDED：

   与DYNAMIC类似。由于任务随着执行越来越少，因此做到后面就不需要很大的chunk -size了，这就是GUIDEDd的做法，随着任务的执行，任务总量的减少，逐步减小chunk-size。

4. RUNTIME：

   运行时（runtime）根据系统变量OMP_SCHEDULE来决定使用哪种scheduling方法。

5. AUTO：

   完全由编译器决定scheduling方法（不推荐使用 不够智能嗷）。

Scheduling Examples

​ A for loop with 100 iterations and 4 threads:

schedule(static, 10)
Thread0: Iter0-10, Iter40-50, Iter80-90
Thread0: Iter10-20, Iter50-60, Iter90-100
Thread0: Iter20-30, Iter60-70
Thread0: Iter30-40, Iter70-80

schedule(dynamic, 10) 由于一些threads做的比较快，所以这些threads做的较多，而另一些做的比较少。
Thread0: Iter0-10, Iter70-80, Iter80-90, Iter90-100
Thread0: Iter10-20, Iter50-60
Thread0: Iter20-30, Iter60-70
Thread0: Iter30-40, Iter40-50

schedule(guided, 10)
Thread0: Iter0-10, Iter40-50, Iter80-85
Thread0: Iter10-20, Iter50-60, Iter85-90
Thread0: Iter20-30, Iter60-70, Iter90-95
Thread0: Iter30-40, Iter70-80, Iter95-100

Do/for Directive Examples

一个典型程序

#define CHUNKSIZE 100 
#define N 1000
int main () {
	int a[N], b[N], c[N];
	/* Some initializations */
	for (int i=0; i < N; i++) 
		a[i] = b[i] = i; 
	int chunk = CHUNKSIZE;
	int thread = NUM_THREAD;
	#pragma omp parallel num_thread(thread) shared(a,b,c) private(i)
	{
		#pragma omp for schedule(dynamic,chunk) nowait 
		for (int i=0; i < N; i++) 
			c[i] = a[i] + b[i];
	} /* end of parallel section */ 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

order的使用

#pragma omp parallel for 
for (int i = 0; i < 10; i++)
	printf("i=%d, thread = %d\n",i, omp_get_thread_num());
1
2
3

执行结果：

#pragma omp parallel for order 
for (int i = 0; i < 3; i++)
	printf("i=%d, thread = %d\n",i, omp_get_thread_num());
1
2
3

执行结果：

两者的区别在于使用order后，执行到order的代码区会按照循环的方式串行化（但是前面执行的过程仍然是并行的）。可以看下这个网页。

collapse的使用：

#pragma omp parallel num_thread(6) 
#pragma omp for schedule(dynamic) 
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			printf("i=%d, j=%d, thread = %d\n",i, j, omp_get_thread_num());
1
2
3
4
5

#pragma omp parallel num_thread(6) 
#pragma omp for schedule(dynamic) collapse(2)
for (int i = 0; i < 3; i++) 
  for (int j = 0; j < 3; j++)
		printf("i=%d, j=%d, thread = %d\n", i, j, omp_get_thread_num());
1
2
3
4
5

使用collapse()来进行嵌套循环，在含有collapse()的 statement和循环之间不能再加其他的循环。collapse()的参数是collapse在一起的循环的层级数。如果不是用collapse()，即第一个例子中，编译器只会识别到第一层循环，也就是说，只有第一次循环会被分配到不同的线程中，第二层循环不会被分配到不同线程中，而是一次性丢给第一次循环对应的线程。相对应的，第二个例子使用了collapse()，两个循环对应9个任务，将会被独立的分配给不同的线程。

对于不同的循环，要对应的选择是否使用collapse()。比如，如果第二个循环的执行顺序将影响执行结果，那么显然就不应该使用collapse()了。

SECTIONS

是function call这个等级上的并行。也就是说，一个section，也就是一个function call，就需要一个线程来执行。同时，每一个section中执行的function call是不同的，需要单独写出。每个section是不会重复做的！！

1. 是一种非循环迭代式的work-sharing的construct。

2. 每一个section of code都将被分配到不同的threads中执行。

3. 每一个独立的section都在sections指令中嵌套定义。

4. 每一个section都被一个thread执行仅一次。

# pragma omp sections[clause......]
{
	#pragma omp section
		/*structured_block*/
	#pragma omp section
		/*structured_block*/
}
1
2
3
4
5
6
7

int N = 1000
int a[N], b[N], c[N], d[N];
#pragma omp parallel num_thread(2) shared(a,b,c,d) private(i)
{
	#pragma omp sections /* specify sections*/
	{
		#pragma omp section /* 1st section*/
		{
      for (int i=0; i < N; i++) c[i] = a[i] + b[i];
		}
		#pragma omp section /* 2nd section*/
		{
      for (int i=0; i < N; i++) d[i] = a[i] + b[i];
		}
	} /* end of section */
}/* end of parallel section */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

SINGLE

是SECTIONS的特例。

1. 执行时，其中一个thread将会串行执行这一个single，而其他的thread视作没有看到它。

2. 对于其他不执行single的thread，除非有nowait子句，否则他们等待single的这段代码执行完。

int input;
#pragma omp parallel num_thread(10) shared(input)
{
	// computing code that can be prcessed in parallel
	#pragma omp single /* specify section */
	{
		scanf("%d", &input);
	} /* end of seralized I/O call */
	printf(“input is %d”, input);
} /* end of parallel section */
1
2
3
4
5
6
7
8
9
10

Synchronization Construct