是否有可能比我发现的像 openMP 这样的并行化更好地改善处理时间？

问题描述 投票：0回答：3

我想用 openMP 优化递归。所以，我从这个问题开始： 使用 openmp 并行化此递归的最佳方法

在寻找优化递归函数时，我首先对 openMP 感兴趣。从我在那里找到的下面的代码开始（https://en.cppreference.com/w/cpp/chrono）：

#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

然后我使用 openMP 类似于上面的答案......但我不得不停止这个过程，因为它花费了非常非常长的时间。我对 openMP 递归并行性了解不多，因为我只是用它来优化我代码中的循环......另外，我在 gcc 文档中找到了一些东西：

__attributes__((const))

然后我将它添加到我的 openMP“优化”版本，但我得到的只是一个核心转储！！！

所以我删除了我的 omp pragmas 以检查核心转储是由于我的代码还是其他原因......

然后代码变成了：

#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

现在执行 42:

的斐波那契计算所需的时间少了很多 
f(42) = 267914296
elapsed time: 0.00106504s

省电模式 在性能模式下它给

f(42) = 267914296
elapsed time: 0.000187806s

这是我电脑的 lscpu（如果有人想比较结果）：

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 需要多少时间，因为我无法获得令人满意的结果......我希望有人能找到一种方法将 omp pragmas 添加到这种递归案例中。

根据需要，这里是这个案例的omp版本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";
}

让我陷入“傻代码”的版本：

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

这些 omp 版本的构建命令是：

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

他们两个似乎都“永远”循环（幸运的是 Ctrl-C 工作正常）。 但是，在写这个问题的结尾时，第二个带有“for”的版本，处理成功：

f(42) = 267914296
elapsed time: 480.953s

明确地说，我不是在寻找“最佳性能”，我的目标是尝试获得一个在合理时间内处理的 omp 版本，目的是找到在递归代码上使用 openMP 的方法。老实说，我期待比 480s 更好的执行时间！我也很惊讶它在“糟糕的调试”版本中花费的时间少于 0.001s 来处理......

现在我想知道如果我将这个模型应用于“havier”任务或者我做错了什么，我使用 openMP 的方式是否可以接受。

c++ recursion g++ openmp fibonacci
3个回答
1
投票

如果你想快速计算斐波那契数列，你通常希望从使用迭代而不是递归开始。

unsigned long long fib(unsigned input) {
    unsigned long long old1 = 0;
    unsigned long long old2 = 1;

    for (int i = 1; i < input; i++) {
        unsigned long long sum = old1 + old2;
        old1 = old2;
        old2 = sum;
    }
    return old2;
}

请注意，我对此做了一些更改，始终使用 64 位 unsigned long long，因此我们可以使用更大的数字进行测试。 64 位数字足以计算 F(93)。

做一些测试，

high_resolution_clock
（至少在我的系统上）可以测量的最短时间间隔约为 427 纳秒。如果我在关闭优化的情况下编译它，并计算 F(93)，它通常说它在 427ns 内运行，但有时在 855ns 内运行。如果我打开优化，那么时间意味着什么，它通常说 0ns，但偶尔会说 427ns。

做一些计算，我猜它真的更像是 30-35ns（每次迭代大约 1 个时钟，93 次迭代/2.8 GHz）。在你的 CPU 上可能接近 20-25ns。

OpenMP/线程

我发现使用线程处理这个任务有两个问题。

首先，当你拥有彼此独立的事物时（例如，一个循环，其中循环的每次迭代都执行相同的操作，但它们中的每一个都在不同的数据上），线程工作得最好。斐波那契数与此相反——每次计算都取决于前一次计算的结果，因此很难并行进行。

其次，使用线程会增加一些开销来创建线程、向它们传递数据、从它们收集数据等等。要使线程正常工作，您需要完成足够的工作，使每个线程完成的工作比让它完成该工作的开销要多得多。同样，这几乎与本例相反。在一个典型的系统上，创建一个线程所花费的时间比上面的代码计算 F(93) 所花费的时间要长得多。

尝试将线程用于这项工作就像尝试在一张纸上写一个字，由几个人各自写一封信的一部分，然后将纸传给下一个人。一个人可以用更少的时间写下整个单词，而不是传递一张纸。

0
投票

你的实现很愚蠢。

电话

    return fibonacci(n-1) + fibonacci(n-2);

应该是对（未）有序集合的查找。

0
投票

因此，在考虑了所有评论和答案之后，这个新代码似乎是在递归代码上应用 openMP 编译指示的更好方法：

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

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

    if (n < 2) return n;
    #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();
    long res;
    #pragma omp parallel
    {
        #pragma omp single
        res = fibonacci(42);
    }
    std::cout << "f(42) = " << res << '\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.cpp -o omp_fibonacci -Wall -fopenmp

输出：

f(42) = 267914296
elapsed time: 255.225s

@DanielLangr 评论特别有用。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.