0
$\begingroup$

I have this method which computes the Fibonacci function:

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

    #pragma omp task shared (i)
    {
        i = p_fib(n-1);
    }
    #pragma omp task shared (j)
    {
        j = p_fib(n-2);
    }        
    #pragma omp taskwait

    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);
        }
    }
    #pragma omp taskwait

    return (i+j);
}

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Anton Menshov Apr 2 '17 at 16:24
  • $\begingroup$ So I am trying it with the n=35 and threadNumber=4, so while I increase the thread number the timing increases $\endgroup$ – N.Der Apr 2 '17 at 16:27
  • $\begingroup$ 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. $\endgroup$ – Brian Borchers Apr 2 '17 at 16:36
  • $\begingroup$ 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 $\endgroup$ – N.Der Apr 2 '17 at 16:38
  • $\begingroup$ 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. $\endgroup$ – Kirill Apr 2 '17 at 17:45
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.