1

我刚刚开始研究 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;
  }
}
4

2 回答 2

6

唯一明智的方法是将并行度削减到一定水平，低于这个水平就没有意义，因为开销变得大于正在完成的工作。最好的方法是有两个单独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;
  }
}

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

于 2013-02-07T11:38:03.500 回答
3

你是对的，减速与任务创建和管理的开销有关。

添加 if(n > 20) 是修剪任务树的好方法，并且可以通过不创建第二个任务来进行更多优化。当新任务产生时，父线程什么也不做。可以通过允许父任务处理其中一个 fib 调用而不是创建更多任务来加速代码：

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

    j=fib(n-2);

    #pragma omp taskwait
    return i+j;
  }
}
于 2013-02-12T23:08:33.773 回答