带有OpenMP任务的斐波那契数

本文介绍了带有OpenMP任务的斐波那契数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

使用OpenMP并行化斐波那契数计算是否有任何好处?

Is there any benefit by using OpenMP to parallelize the Fibonacci number calculations?

在线上有一些示例，这些示例使用OpenMP中的 task指令来计算斐波那契数.例如在 docs.oracle /cd/E19205-01/820-7883/girtd/index.html 和此处 openmp/forum/viewtopic.php?f=3&t=1231

There are several examples online which calculate Fibonacci numbers using the task directive in OpenMP. For example at docs.oracle/cd/E19205-01/820-7883/girtd/index.html and here openmp/forum/viewtopic.php?f=3&t=1231

其中一些示例声称OpenMP的性能更好.我不理解这是因为按照我的理解，计算斐波那契数列基本上是非并行的(忽略基于封闭式解决方案的方法，例如，根据Binet的公式).

Some of these examples claim the performance is better with OpenMP. I don't understand this as calculating the Fibonacci series is, to my understanding, fundamentally non parallel (ignoring methods based on closed form solutions, e.g. from Binet's formula).

此外，OpenMP示例所基于的递归与迭代计算数字相比，其性能要差很多(差几个数量级)(这众所周知迭代和递归版本是否具有相同的复杂性?).但是，当我使用OpenMP时，速度甚至会更慢！使用示例来演示如何使用性能较差的OpenMP功能似乎很愚蠢. 所以我试图理解为什么这些代码示例存在?

Additionally, recursion, which the OpenMP examples are based on, has much worse performance (several orders of magnitude worse) than calculating the numbers iteratively (this is well known Iterative and recursive version has same complexity?). But when I use OpenMP it's even slower! It seems silly to use an example to demonstrate how to use a feature of OpenMP which gives worse performance. So I'm trying to understand why these code examples exist?

这是我用来测试功能的代码.

Here is the code I used to test the functions.

#include <stdio.h> #include <stdint.h> #include <omp.h> inline uint64_t fib_iterative(const size_t n) { uint64_t fn0 = 0; uint64_t fn1 = 1; uint64_t fn2 = 0; if(n==0) return fn0; if(n==1) return fn1; for(int i=2; i<(n+1); i++) { fn2 = fn0 + fn1; fn0 = fn1; fn1 = fn2; } return fn2; } inline uint64_t fib_recursive(uint64_t n) { if ( n == 0 || n == 1 ) return(n); return(fib_recursive(n-1) + fib_recursive(n-2)); } int fib_recursive_omp(int n) { int i, j; if (n<2) return n; else { #pragma omp task shared(i) firstprivate(n) i=fib_recursive_omp(n-1); #pragma omp task shared(j) firstprivate(n) j=fib_recursive_omp(n-2); #pragma omp taskwait return i+j; } } int fib_recursive_omp_fix(int n) { int i, j; if (n<2) return n; else { if ( n < 20 ) { return(fib_recursive_omp_fix(n-1)+fib_recursive_omp_fix(n-2)); } else { #pragma omp task shared(i) firstprivate(n) i=fib_recursive_omp_fix(n-1); #pragma omp task shared(j) firstprivate(n) j=fib_recursive_omp_fix(n-2); #pragma omp taskwait return i+j; } } } int main() { const size_t n = 40; uint64_t result; double dtime; dtime = omp_get_wtime(); result = fib_iterative(n); dtime = omp_get_wtime() - dtime; printf("iterative time %f, results %lu\n", dtime, result); dtime = omp_get_wtime(); result = fib_recursive(n); dtime = omp_get_wtime() - dtime; printf("recursive time %f, results %lu\n", dtime, result); dtime = omp_get_wtime(); result = fib_recursive_omp(n); dtime = omp_get_wtime() - dtime; printf("recursive omp time %f, results %lu\n", dtime, result); omp_set_num_threads(1); dtime = omp_get_wtime(); result = fib_recursive_omp_fix(n); dtime = omp_get_wtime() - dtime; printf("recursive omp fix 1 thread time %f, results %lu\n", dtime, result); omp_set_num_threads(2); dtime = omp_get_wtime(); result = fib_recursive_omp_fix(n); dtime = omp_get_wtime() - dtime; printf("recursive omp fix 2 thread, time %f, results %lu\n", dtime, result); }

推荐答案

链接几乎等于OpenMP 3.1标准中的示例A.15.4c :

The code in the link you posted is almost equal to Example A.15.4c in the OpenMP 3.1 standard:

int fib(int n) { int i, j; if (n<2) return 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; } }

在该示例下，您可以找到以下内容:

Under the example you can find the following:

注意:有更多更有效的算法可以计算斐波纳契数 数字.这种经典的递归算法仅用于说明 目的.

Note: There are more efficient algorithms for computing Fibonacci numbers. This classic recursion algorithm is for illustrative purposes.

所以我认为这只是一个用于教学目的的小例子.

So I assume this is just to have a small example for didactic purposes.