c++ - 在同一线程上运行的所有 OpenMP 任务

Question

我使用 OpenMP 中的任务编写了一个递归并行函数。虽然它给了我正确的答案并且运行良好，但我认为并行性存在问题。与串行解决方案相比，运行时无法扩展我在没有任务的情况下解决的其他并行问题。当为任务打印每个线程时，它们都在线程 0 上运行。我正在 Visual Studio Express 2013 上编译和运行。

int parallelOMP(int n)
{

    int a, b, sum = 0;
    int alpha = 0, beta = 0;

    for (int k = 1; k < n; k++)
    {

        a = n - (k*(3 * k - 1) / 2);
        b = n - (k*(3 * k + 1) / 2);


        if (a < 0 && b < 0)
            break;


        if (a < 0)
            alpha = 0;

        else if (p[a] != -1)
            alpha = p[a];

        if (b < 0)
            beta = 0;

        else if (p[b] != -1)
            beta = p[b];


        if (a > 0 && b > 0 && p[a] == -1 && p[b] == -1)
        {
            #pragma omp parallel
            {
                #pragma omp single
                {
                    #pragma omp task shared(p), untied
                    {
                        cout << omp_get_thread_num();
                        p[a] = parallelOMP(a);
                    }
                    #pragma omp task shared(p), untied
                    {
                        cout << omp_get_thread_num();
                        p[b] = parallelOMP(b);
                    }
                    #pragma omp taskwait
                }
            }

            alpha = p[a];
            beta = p[b];
        }

        else if (a > 0 && p[a] == -1)
        {
            #pragma omp parallel
            {
                #pragma omp single
                {
                    #pragma omp task shared(p), untied
                    {
                        cout << omp_get_thread_num();
                        p[a] = parallelOMP(a);
                    }

                    #pragma omp taskwait
                }
            }

            alpha = p[a];
        }

        else if (b > 0 && p[b] == -1)
        {
            #pragma omp parallel
            {
                #pragma omp single
                {
                    #pragma omp task shared(p), untied
                    {
                        cout << omp_get_thread_num();
                        p[b] = parallelOMP(b);
                    }

                    #pragma omp taskwait
                }
            }

            beta = p[b];
        }


        if (k % 2 == 0)
            sum += -1 * (alpha + beta);
        else
            sum += alpha + beta;


    }

    if (sum > 0)
        return sum%m;
    else
        return (m + (sum % m)) % m;
}

Answer 1

有时我希望对 SO 的评论可以像答案一样格式丰富，但事实并非如此。因此，这里出现了一条伪装成答案的长评论。

似乎在编写递归 OpenMP 代码时一个非常常见的错误是不了解并行区域的工作原理。考虑以下代码(使用显式任务，因此需要支持 OpenMP 3.0 或更新版本):

void par_rec_func (int arg)
{
   if (arg <= 0) return;

   #pragma omp parallel num_threads(2)
   {
      #pragma omp task
      par_rec_func(arg-1);

      #pragma omp task
      par_rec_func(arg-1);
   }
}

// somewhere in the main function
par_rec_func(10);

这段代码有问题。问题在于，除了 par_rec_func() 的顶级调用外，在所有其他调用中，并行区域将在封闭的外部并行区域的上下文中创建。这称为嵌套并行性，默认情况下是禁用，这意味着顶级区域下面的所有并行区域都将处于非事件状态，即它们将串行执行。由于任务绑定(bind)到最里面的并行区域，因此它们也会串行执行。这段代码会发生什么，它将在 par_rec_func() 的顶层调用处产生一个额外的线程(总共两个)，然后每个线程将执行递归的整个分支树(即整棵树的一半)。如果在具有 64 个内核的机器上运行该代码，则其中 62 个将空闲。为了启用嵌套并行性，必须将环境变量 OMP_NESTED 设置为 true 或调用 omp_set_nested() 并将其传递一个真正的标志:

omp_set_nested(1);

启用嵌套并行性后，就会面临一个新问题。每次遇到嵌套的并行区域时，遇到的线程都会产生一个额外的线程(因为 num_threads(2))或从运行时的线程池中获取一个空闲线程。在每一个更深的递归层次上，这个程序将需要两倍于前一层的线程。尽管可以通过 OMP_THREAD_LIMIT(另一个 OpenMP 3.0 功能)设置线程总数的上限，并且不考虑开销，但这并不是在这种情况下真正想要的。

在这种情况下，正确的解决方案是在单个并行区域的动态范围内使用孤立任务:

void par_rec_func (int arg)
{
   if (arg <= 0) return;

   #pragma omp task
   par_rec_func(arg-1);

   #pragma omp task
   par_rec_func(arg-1);

   // Wait for the child tasks to complete if necessary
   #pragma omp taskwait
}

// somewhere in the main function
#pragma omp parallel
{
   #pragma omp single
   par_rec_func(10);
}

这种方法的优点很多。首先，只创建一个具有指定数量线程的并行区域(例如，通过设置 OMP_NUM_THREADS 或通过任何其他方式)。当子任务递归调用 par_rec_func() 时，这只是将新任务添加到并行区域而不会产生新线程。这在递归树不平衡的情况下非常有帮助，因为许多高质量的 OpenMP 运行时实现任务窃取，例如线程 i 可以执行在线程 j 中执行的任务的子任务，其中 i != j。

对于像 VC++ 这样的 OpenMP 2.0 编译器，除了通过使用嵌套并行并在特定级别显式禁用它来近似上述想法之外，我们无能为力:

void par_rec_func (int arg)
{
   if (arg <= 0) return;

   int level = omp_get_level();

   #pragma omp parallel sections num_threads(2) if(level < 4)
   {
      #pragma omp section
      par_rec_func(arg-1);

      #pragma omp section
      par_rec_func(arg-1);
   }
}

// somewhere in the main function
int saved_nested = omp_get_nested();
omp_set_nested(1);

par_rec_func(10);

omp_set_nested(saved_nested);

omp_get_level() 用于确定嵌套级别，if 子句用于选择性地停用第四级或更深嵌套级别的并行区域。当递归树不平衡时，这个解决方案是愚蠢的并且不会很好地工作。