optimization - Fibonacci numbers with OpenMP tasks

Question

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

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

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).

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
", dtime, result);

    dtime = omp_get_wtime();
    result = fib_recursive(n);
    dtime = omp_get_wtime() - dtime;
    printf("recursive time %f, results %lu
", dtime, result);

    dtime = omp_get_wtime();
    result = fib_recursive_omp(n);
    dtime = omp_get_wtime() - dtime;
    printf("recursive omp time %f, results %lu
", 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
", 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
", dtime, result);

}

Answer 1

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.