如何用OpenMP优化递归代码？以斐波那契函数为例的疑问

背景与初始测试 #

我尝试用OpenMP优化递归代码，从递归斐波那契函数入手。先拿基础版本测试：

#include <iostream>
#include <chrono>
 
long fibonacci(unsigned n)
{
    if (n < 2) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}
 
int main()
{
    auto start = std::chrono::steady_clock::now();
    std::cout << "f(42) = " << fibonacci(42) << '\n';
    auto end = std::chrono::steady_clock::now();
    std::chrono::duration<double> elapsed_seconds = end-start;
    std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
}

用g++无优化编译后，运行结果：

f(42) = 267914296
elapsed time: 1.88232s

添加__attribute__((const))后的优化效果 #

之后我在GCC文档里看到__attribute__((const))，先移除OpenMP指令测试这个属性的效果：

#include <iostream>
#include <chrono>

__attribute__ ((const))
long fibonacci(unsigned n)
{
   
   int long r[2];

   if (n < 2) return n;
   r[0]=fibonacci(n-1);
   r[1]=fibonacci(n-2);
   return (r[0]+r[1]);
}
 
int main()
{
    auto start = std::chrono::steady_clock::now();
    std::cout << "f(42) = " << fibonacci(42) << '\n';
    auto end = std::chrono::steady_clock::now();
    std::chrono::duration<double> elapsed_seconds = end-start;
    std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
}

用编译命令g++ fibonacci.cpp -o fibonacci -Wall -O2 -march=native编译后，耗时大幅降低：

• 节能模式：

f(42) = 267914296
elapsed time: 0.00106504s

• 性能模式：

f(42) = 267914296
elapsed time: 0.000187806s

我的设备CPU信息：

Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU(s) scaling MHz:  95%
    CPU max MHz:         4500,0000
    CPU min MHz:         800,0000
    BogoMIPS:            8403,00

OpenMP版本的问题 #

我尝试了两个OpenMP版本的代码，但效果很差：

版本1 #

#include <iostream>
#include <chrono>
#include <omp.h>

__attribute__ ((const))
long fibonacci(unsigned n)
{
   
    int long a, b;

    if (n < 2) return n;
    #pragma omp parallel
    #pragma omp single nowait
    {         
       #pragma omp task shared(a)
       a=fibonacci(n-1);
       #pragma omp task shared(b)
       b=fibonacci(n-2);
       #pragma omp taskwait
    }
    return (a+b);
}
 
int main()
{
    auto start = std::chrono::steady_clock::now();
    std::cout << "f(42) = " << fibonacci(42) << '\n';
    auto end = std::chrono::steady_clock::now();
    std::chrono::duration<double> elapsed_seconds = end-start;
    std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
}

含for循环的版本 #

#include <iostream>
#include <chrono>
#include <omp.h>

__attribute__ ((const))
long fibonacci(unsigned n)
{
   
   int long r[2];
   int i;
   if (n < 2) return n;
   #pragma omp parallel
   #pragma omp single
   for(i=0;i<2;++i) 
   {
       #pragma omp task shared(r)   
       r[i]=fibonacci(n-i-1);
   }      
    
    return (r[0]+r[1]);
}
 
int main()
{
    auto start = std::chrono::steady_clock::now();
    std::cout << "f(42) = " << fibonacci(42) << '\n';
    auto end = std::chrono::steady_clock::now();
    std::chrono::duration<double> elapsed_seconds = end-start;
    std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
}

编译命令：

g++ omp_fibonacci_for.cpp -o omp_fibonacci_for -Wall -fopenmp

版本1看起来像无限循环，只能用Ctrl-C终止；含for循环的版本最终执行完成，但耗时长达480.953s：

f(42) = 267914296
elapsed time: 480.953s

我不是要最优性能，只是想掌握递归代码用OpenMP的正确方式，对这个耗时结果很意外，也惊讶于无OpenMP的优化版本能快到0.001s以内。

现在想知道：我用OpenMP的方式是否合理？这种任务并行模式是否适用于更繁重的递归任务？

内容的提问来源于stack exchange，提问作者user10475133