OpenMP task 原理與實例

個人理解

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;
}