Decrease execution time using openMP

I have this method which computes the Fibonacci function:

long optimized_p_fib(long n)
{
long i, j;
if(n < 2)
return n;

{
i = p_fib(n-1);
}
{
j = p_fib(n-2);
}

return (i+j);
}


The execution time of this method is 2.527737.
I want to use tasks in OpenMP so that the execution time will be smaller, below is what I did so far, but the execution time got bigger (4.039427) compared to the method above.

long optimized_p_fib(int n)
{
long i, j;
if(n < 2)
return n;

#pragma omp single nowait
{
#pragma omp task shared (i) firstprivate(n)
{
i = optimized_p_fib(n-1);
}
#pragma omp task shared (j) firstprivate(n)
{
j = optimized_p_fib(n-2);
}
}

return (i+j);
}


What could I possibly optimize my code, so that the execution time would get small ?

• What kind of $n$ (Fibonacci number) and number of threads $T$ are we talking about? (for the timings you have provided) How does the timings increase\decrease with changing $n$ and/or $T$? That might give you a hint on what exactly is going on with your code and parallelization strategy. Apr 2, 2017 at 16:24
• So I am trying it with the n=35 and threadNumber=4, so while I increase the thread number the timing increases Apr 2, 2017 at 16:27
• The recursive algorithm that you're using needlessly recomputes values of fib(k) many times for k between 1 and n. You can vastly improve the performance of this by using a different algorithm that avoids this wasted effort. Apr 2, 2017 at 16:36
• Well, I would change the algorithm but this is a task where I just have to change the openMP commands and leave the algorithm as it is. So my problem is that I don't really know what else to use in openMP so that the time will get small Apr 2, 2017 at 16:38
• It's probably the overhead from managing the tasks at small $n$—not something to do specifically with OpenMP, but multithreading in general, so there probably wouldn't be a specific OpenMP construct that fixes this. Try to avoid creating very small cheap tasks. Apr 2, 2017 at 17:45

The algorithm you are using spawns extremely cheap tasks, especially at small $n$. As you don't have a luxury of changing the algorithm, the only reasonable (relatively) way to avoid the overhead of creating cheap tasks would be to introduce another if-condition near the bottom of the recursion tree.

So, now you have a baseline case at $n<2$ (simply return n). I suggest you add another if-condition for $n<k$, at first trying $k<\lfloor\frac{n}{2}\rfloor$, for which the value of the function will be calculated without spawning OpenMP tasks.

One other thing is that you forgot to add the line

#pragma omp parallel


before the section

#pragma omp single nowait


Such #pragma causes all of the threads in the pool to execute the next block of code. This might shave off a little bit of the timing in the second version code and make the execution time closer to the first one.

I would also suggest the following webpage about basic OpenMP+Tasks where you might find an appropriate balance between still following the assignment and making the most out of the computation.