Openmp Tasks for Recursion

Question

I am new to Openmp programming and I have a question regarding task parallelism on recursions

Let's consider this demo C code:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <omp.h>

struct timeval t1, t2;

void recursive_task(int level)
{   
    //printf("%d\n", level);
    
    if (level == 0){
        usleep(1000);
        return;
    }
    else
    {
        recursive_task(level-1);

        #pragma omp task
        {
             recursive_task(level-1);
        }
        
        #pragma omp task
        {
             recursive_task(level-1);
        }
        
        #pragma omp taskwait
        
        recursive_task(level-1);
    }
}

int main()
{
    double time;

    gettimeofday(&t1, 0);

#pragma omp parallel
    {
#pragma omp single
        {
            recursive_task(7);
        }
    }

    gettimeofday(&t2, 0);

    time = (double)((t2.tv_sec - t1.tv_sec) * 1000000 + t2.tv_usec - t1.tv_usec) / 1000000;
    printf("%.4f\n", time);

    return 0;
}

Each level of recursion does 4 calls, where only the 2nd and the 3rd call can run actually in parallel.

Now i tried this different version:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <omp.h>

struct timeval t1, t2;

void recursive_task(int level)
{   
    //printf("%d\n", level);
    
    if (level == 0){
        usleep(1000);
        return;
    }
    else
    {
        #pragma omp task if(0)
        {
            recursive_task(level-1);

            #pragma omp task
            {
                recursive_task(level-1);
            }
        
            recursive_task(level-1);

            #pragma omp taskwait
            
            recursive_task(level-1);
        }
    }
}

int main()
{
    double time;

    gettimeofday(&t1, 0);

#pragma omp parallel
    {
#pragma omp single
        {
            recursive_task(7);
        }
    }

    gettimeofday(&t2, 0);

    time = (double)((t2.tv_sec - t1.tv_sec) * 1000000 + t2.tv_usec - t1.tv_usec) / 1000000;
    printf("%.4f\n", time);

    return 0;
}

The execution also seems to follow the correct ordering of the calls (i think it has to do with if(0) clause).

However what suprised me is that the second one is faster than the first one. I executed with 8 threads and the times where 4.4 seconds for the first approach and 3.4 seconds for the second approach!

What is the main difference that makes the second code faster?

Answer 1

The point is impacts #pragma omp taskwait waits the completion of child tasks of the current task and the current task is not the same when there are tasks created with #pragma omp task if(0). This means that having no later directive results in an over-synchronization causing a higher execution time (certainly due to less parallelism). Indeed, the #pragma omp taskwait directive waits for more tasks in this case (especially true tasks without the if(0)).

---

Example with 2 levels

To better understand what happens, we can analyze what the function exactly do at the level 2 (and increase the delay to 10_000 so we can see any difference at run time). Here is the flatten code:

void recursive_task_level2()
{
    #pragma omp task if(0)
    {
        #pragma omp task if(0)
        {
            usleep(10000);

            #pragma omp task
            usleep(10000);
        
            usleep(10000);

            #pragma omp taskwait
            
            usleep(10000);
        }

        #pragma omp task // <----- [A] WAITED TASK
        {
            #pragma omp task if(0)
            {
                usleep(10000);

                #pragma omp task
                usleep(10000);
            
                usleep(10000);

                #pragma omp taskwait
                
                usleep(10000);
            }
        }
    
        #pragma omp task if(0) // <----- [B] IMPORTANT ONE
        {
            usleep(10000);

            #pragma omp task
            usleep(10000);
        
            usleep(10000);

            #pragma omp taskwait // <----- [C]
            
            usleep(10000);
        }

        #pragma omp taskwait
        
        #pragma omp task if(0)
        {
            usleep(10000);

            #pragma omp task
            usleep(10000);
        
            usleep(10000);

            #pragma omp taskwait
            
            usleep(10000);
        }
    }
}

Here is the idea: if [B] is present, then [C] does not wait for [A] because it is not a child task anymore; however, if [B] is not present, then [C] wait for [A], that is, before waiting 10 ms.

This effect is confirmed by running this code both with/without [B] and with/without all other #pragma omp task if(0). In this case, the only directive that matters is [B] and commenting [B] does increase the execution time by precisely 10 ms (92 vs 102 ms). This proves the hypothesis is true.

With more levels, the amount of parallelism is strongly reduced due to the over-syncronization and the additional time should also be accumulated on the critical path (certainly exponentially) resulting in a huge execution overhead.

---

Solutions

To avoid waiting on more task than expected, you can:

• create tasks in #pragma omp taskgroup section so all tasks created in the group (and there children recursively) are waited at the end of the section.
• use task dependencies so tasks only wait what is strictly needed; note that taskwait also support dependency so you can wait just a subset of the tasks created in the current task.
• use #pragma omp task if(0) so to control what tasks are waited by #pragma omp taskwait; see the @Joachim's answer; though the intent is rather counter-intuitive for readers (people expect this to have no impact).

Be aware that task dependencies only work on sibling tasks (i.e. tasks create in a same parent task): you cannot create a dependency between a task and the children of a sibling task (or even sibling tasks of the parent tasks of a given tasks). This is a rather-strong limitation when you use recursive tasking.

Also be aware that dependencies often introduce a small overhead (typically dependent of the number of dependencies).