C++ OpenMP 斐波那契 : 1 thread performs much faster than 4 threads

Question

我试图理解为什么以下代码在 OpenMP 上在 1 个线程上比在 4 个线程上运行得快得多。下面的代码实际上是基于一个类似的问题:OpenMP recursive tasks但是当尝试实现建议的答案之一时，我没有得到预期的加速，这表明我做错了什么(并且不确定它是什么)。人们在 4 个线程上运行以下程序时比在 1 个线程上运行时速度更快吗？在 4 核上运行时我的速度下降了 10 倍(我应该得到适度的加速而不是显着的减速)。

int fib(int n)
  {
    if(n == 0 || n == 1)
        return n;
    if (n < 20) //EDITED CODE TO INCLUDE CUTOFF
        return fib(n-1)+fib(n-2); 
    int res, a, b;
    #pragma omp task shared(a)
    a = fib(n-1);
    #pragma omp task shared(b)
    b = fib(n-2);
    #pragma omp taskwait
    res = a+b;
    return res;
  }

int main(){
  omp_set_nested(1);
  omp_set_num_threads(4);
  double start_time = omp_get_wtime();
  #pragma omp parallel
  {
    #pragma omp single
    {
      cout << fib(25) << endl;
    }
  }
  double time = omp_get_wtime() - start_time;
  std::cout << "Time(ms): " << time*1000 << std::endl;
  return 0;
}

Answer 1

你用大数字试过吗？

在多线程中，CPU 内核的初始化工作需要一些时间。对于在单核上完成速度非常快的小型作业，线程会因此减慢作业速度。

如果作业通常花费的时间长于秒而不是毫秒，则多线程显示速度增加。

线程还有一个瓶颈。如果您的代码尝试创建过多的线程(主要是通过递归方法)，这可能会导致所有正在运行的线程延迟，从而造成巨大的挫折。

在此OpenMP/Tasks维基页面，它被提及并建议手动切断。该函数需要有 2 个版本，当线程太深时，它会继续使用单线程递归。

编辑:在进入 OMP 区域之前需要增加截止变量。

---

以下代码是为了测试目的，供OP测试

#define CUTOFF 5
int fib_s(int n)
{
    if (n == 0 || n == 1)
        return n;
    int res, a, b;
    a = fib_s(n - 1);
    b = fib_s(n - 2);
    res = a + b;
    return res;
}
int fib_m(int n,int co)
{
    if (co >= CUTOFF) return fib_s(n);
    if (n == 0 || n == 1)
        return n;
    int res, a, b;
    co++;
#pragma omp task shared(a)
    a = fib_m(n - 1,co);
#pragma omp task shared(b)
    b = fib_m(n - 2,co);
#pragma omp taskwait
    res = a + b;
    return res;
}

int main()
{
    omp_set_nested(1);
    omp_set_num_threads(4);
    double start_time = omp_get_wtime();
#pragma omp parallel
    {
#pragma omp single
        {
            cout << fib_m(25,1) << endl;
        }
    }
    double time = omp_get_wtime() - start_time;
    std::cout << "Time(ms): " << time * 1000 << std::endl;
    return 0;
}

---

结果:当 CUTOFF 值设置为 10 时，计算第 45 项不到 8 秒。

co=1   14.5s
co=2    9.5s
co=3    6.4s
co=10   7.5s
co=15   7.0s 
co=20   8.5s
co=21 >18.0s
co=22 >40.0s