c - openmp递归任务示例比顺序慢

Question

我刚刚开始研究 OpenMP 并一直在阅读任务。看来 Sun 这里的例子实际上比顺序版本慢。我相信这与任务创建和管理的开销有关。它是否正确？如果是这样，有没有一种方法可以在不更改算法的情况下使用任务使代码更快？

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

Answer 1

唯一明智的方法是将并行度降低到一定水平，低于该水平就没有意义，因为开销变得大于正在完成的工作。最好的方法是有两个独立的 fib实现 - 一个连续的，比方说 fib_ser ，和平行的，fib - 并在给定阈值下在它们之间切换。

int fib_ser(int n)
{
  if (n < 2)
    return n;
  else
    return fib_ser(n-1) + fib_ser(n-2);
}

int fib(int n)
{
  int i, j;

  if (n <= 20)
    return fib_ser(n);
  else
  {
    #pragma omp task shared(i)
    i = fib(n-1);
    #pragma omp task shared(j)
    j = fib(n-2);
    #pragma omp taskwait
    return i+j;
  }
}

这里的阈值是n == 20 .它是任意选择的，其最佳值在不同的机器和不同的 OpenMP 运行时会有所不同。

另一种选择是使用 if 动态控制任务分配子句:

int fib(int n)
{
  int i, j;
  if (n<2)
    return n;
  else
  {
    #pragma omp task shared(i) if(n > 20)
    i=fib(n-1);

    #pragma omp task shared(j) if(n > 20)
    j=fib(n-2);

    #pragma omp taskwait
    return i+j;
  }
}

如果 n <= 20，这将关闭两个显式任务，并且代码将串行执行，但 OpenMP 代码转换仍然会产生一些开销，因此它的运行速度会比使用单独的串行实现的先前版本慢。