个人理解
Openmp自从3.0以后全面走向任务驱动。task机制非常重要,可以显式定义任务,而其余parallel代码块中不用task定义的实际上是隐式任务。
抽象来说就是有两个池子:线程池与任务池。闲置的线程会在线程池等待任务。显式任务与隐式任务会放在任务池中等待线程取走。
task子句相当于显式定义一个任务。常用在不规则循环(不适用parallel for的循环)与递归函数中。默认任务只能由一个线程执行。当线程遇到task子句时,既可能自己立即执行,也可能将其放入任务池等待别的线程取走。
taskwait显式等待之前定义的任务执行结束。用于同步。
final:当final条件为真时,该任务与子任务不再作为任务,与if本质应该是一致的。
if:当if条件为假时,该任务将不再放入任务池中,而是由碰到它的线程立即执行。
final与if子句用来防止过于细粒度的任务放在任务池中,造成资源浪费。因为我们更希望粗粒度的任务,从而分摊线程创建,启动,同步等带来的开销。
官方示例
#include <stdio.h>
#include <omp.h>
int fib(int n)
{
int i, j;
if (n<2)
return n;
else
{
#pragma omp task shared(i) firstprivate(n)
i=fib(n-1);
#pragma omp task shared(j) firstprivate(n)
j=fib(n-2);
#pragma omp taskwait
return i+j;
}
}
int main()
{
int n = 10;
omp_set_dynamic(0);
omp_set_num_threads(4);
#pragma omp parallel shared(n)
{
#pragma omp single
printf ("fib(%d) = %d\n", n, fib(n));
}
}
用于双调归并排序
双调归并排序本质其实不难,但理解还是有一定难度,有两部分递归。
第一步将一个序列,分成两部分,第一部分是升序的,第二部分是降序的。第二部分是利用双调队列的性质,将其变为有序,CSDN与知乎均有介绍。
#include <stdio.h>
#include <algorithm>
#include <omp.h>
#include <functional>
#include <math.h>
typedef std::function<bool(int, int)> Func;
Func op[2];
void to_one_sequence(int* a, int n, int selector);
void bitonicSort(int* a, int n, int selector)
{
if (n <= 1)
return;
else
{
#pragma omp task if(n > 1024)
bitonicSort(a, n / 2, selector);
#pragma omp task if(n > 1024)
bitonicSort(a + n / 2, n / 2, selector ^ 1);
#pragma omp taskwait
to_one_sequence(a, n, selector);
}
}
void to_one_sequence(int* a, int n, int selector)
{
if (n <= 1)
return;
else
{
//#pragma omp task if(n > 1024)
{
auto judge = op[selector];
for (int i = 0; i < n / 2; i++) {
if (judge(a[i], a[i + n / 2]))
std::swap(a[i], a[i + n / 2]);
}
}
//#pragma omp taskwait
#pragma omp task if(n > 1024)
to_one_sequence(a, n / 2, selector);
#pragma omp task if(n > 1024)
to_one_sequence(a + n / 2, n / 2, selector);
#pragma omp taskwait
}
}
int main()
{
Func big = [](int a, int b)->bool {return a <= b;};
Func small = [](int a, int b)->bool {return a >= b;};
op[0] = small;
op[1] = big;
const int maxn = pow(2, 22);
int* a = new int[maxn];
#pragma omp parallel for
for (int i = 0; i < maxn; i++)
a[i] = rand() % 10000;
double begin = omp_get_wtime();
omp_set_dynamic(1);
//omp_set_num_threads(4);
#pragma omp parallel
{
#pragma omp single
{
printf("%d\n", omp_get_num_threads());
bitonicSort(a, maxn, 0);
}
}
printf("%lf\n", omp_get_wtime() - begin);
bool ok = 1;
for (int i = 0; i < maxn; i++)
{
if (i != 0)
{
if (a[i] < a[i - 1])
{
ok = 0;
break;
}
}
}
printf("%d\n", ok);
return 0;
}