openmp 递归任务示例比顺序慢 [英] openmp recursive tasks example slower than sequential

问题描述

我刚刚开始研究 OpenMP 并且一直在阅读任务.看起来 Sun 在这里的例子实际上比顺序版本慢.我相信这与任务创建和管理的开销有关.这样对吗?如果是这样，有没有办法在不改变算法的情况下使用任务使代码更快?

I've just started looking into OpenMP and have been reading up on tasks. It seems that Sun's example here is actually slower than the sequential version. I believe this has to do with the overhead of task creation and management. Is this correct? If so, is there a way to make the code faster using tasks without changing the algorithm?

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

推荐答案

唯一明智的方法是将并行度降低到某个级别，低于该级别则没有意义，因为开销变得大于正在完成的工作.最好的方法是有两个单独的 fib 实现 - 一个串行的，比如 fib_ser，一个并行的，fib -并在给定的阈值下在它们之间切换.

The only sensible way is to cut the parallelism at a certain level, below which it makes no sense as the overhead becomes larger than the work being done. The best way to do it is to have two separate fib implementations - a serial one, let's say fib_ser, and a parallel one, fib - and to switch between them under a given threshold.

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 运行时会有所不同.

Here the threshold is n == 20. It was chosen arbitrarily and its optimal value would be different on different machines and different OpenMP runtimes.

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

Another option would be to dynamically control the tasking with the if clause:

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 代码转换仍然会有一些开销，因此它会运行比使用单独串行实现的先前版本慢.

This would switch off the two explicit tasks if n <= 20, and the code would execute in serial, but there would still be some overhead from the OpenMP code transformation, so it would run slower than the previous version with the separate serial implementation.

这篇关于openmp 递归任务示例比顺序慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！