1

使用 OpenMP 并行化斐波那契数计算有什么好处吗？

网上有几个示例使用 taskOpenMP 中的指令计算斐波那契数。例如在http://docs.oracle.com/cd/E19205-01/820-7883/girtd/index.html和这里http://openmp.org/forum/viewtopic.php?f=3&t=1231

其中一些示例声称 OpenMP 的性能更好。我不明白这一点，因为据我了解，计算斐波那契数列基本上是非并行的（忽略基于封闭形式解决方案的方法，例如来自比内特的公式）。

此外，OpenMP 示例所基于的递归比迭代计算数字的性能差得多（差几个数量级）（这是众所周知的迭代和递归版本具有相同的复杂性？）。但是当我使用 OpenMP 时，它甚至更慢！用一个例子来演示如何使用 OpenMP 的一个性能更差的特性似乎很愚蠢。所以我试图理解为什么这些代码示例存在？

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

#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);

}
4

1 回答 1

3

您发布的链接中的代码几乎等于OpenMP 3.1 标准中的示例 A.15.4c ：

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

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

注意：有更有效的算法来计算斐波那契数。这个经典的递归算法用于说明目的。

所以我认为这只是为了教学目的而举一个小例子。

于 2013-06-09T08:01:17.583 回答