带有OpenMP任务的斐波那契数 [英] Fibonacci numbers with OpenMP tasks

问题描述

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

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

在线上有一些示例，这些示例使用OpenMP中的 task指令来计算斐波那契数.例如在 http://docs.oracle.com /cd/E19205-01/820-7883/girtd/index.html 和此处 http://openmp.org/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 http://docs.oracle.com/cd/E19205-01/820-7883/girtd/index.html and here http://openmp.org/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示例所基于的递归与迭代计算数字相比，其性能要差很多(差几个数量级)(这众所周知

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.

这篇关于带有OpenMP任务的斐波那契数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！