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 Do iterative and recursive versions of an algorithm have the same time 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);
    
    }

score 3 · Accepted Answer · answered Jun 09 '13 at 08:01

3

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.

answered Jun 09 '13 at 08:01

Massimiliano

7,842
2
47
62

1

Thank you, that answers my question. It's time I read the OpenMP standard. It still seems a bit silly to use an example which gives worse performance with OpenMP. I mean the recursive algorithm, even if it's slower than the iterative one, is even slower with OpenMP. – Jun 09 '13 at 09:41
Well, I think it's silly only if you use it to show how OpenMP can improve performance by parallelism (like it seems they do in the OpenMP forum, unfortunately). If you use it to show the logic of the program I think it's completely fine (like when one explains the `reduction` clause by adding `1` to the same scalar in a loop) – Massimiliano Jun 09 '13 at 09:55
Thanks, this confirms what I thought - that the forum is wrong. I even tried the guys suggestion in the forum and only used OpenMP for n>20 (see my code if you're interested). That's much faster for n>20 but still worse than without OpenMP at all. – Jun 09 '13 at 09:58

Fibonacci numbers with OpenMP tasks

1 Answers1

Linked