How to parallel a recursive function using OpenMP in C++

Question

This is a problem regarding how to solve a recursive function using "tasks" instruction. I'll appreciate it, if you can help me solve the problem giving your ideas. The issue is:

For the piece of code coming below, a recursive function named func() is called somewhere inside the main(). As you can see, there are 2 variables inside the recursive function (var1 and var2) that control the number of successive recursive calls. Normally the value of var1 is bigger and var2 will hardly get 0 value from boo(). So, func() will be called successively many times to finally get stopped and return a True/false value, thus we need to parallelize it using OpenMp to reduce its running time.

What I'm trying to apply is "#pragma omp task" instruction, since I know it's the best way OpenMp suggests to parallelize the recursive functions. But this example seems somehow different from routine recursive functions like fibonacci that recursive function fib() was called twice inside itself ( i.e. x = fib(n-1) and y = fib(n-2) inside fib(n) ), and we could simply define two tasks and assign each recursive call to one of them. But in the example below it seems confusing for me how to define the tasks. Can i define N tasks inside the loop before calling a new func()? How? Of course, it's highly welcome if there is another method (rather than using "tasks") to efficiently parallelize this piece of code:

bool func()
{
     if(var1 == 0) return True;
     else
     {
          // Do few things, then:
          for(int i=0; i<N; i++)
          {
               // Do few things, then:
               boo();    // var2 can changes from 0 to 1 and vise versa here after running boo().
               var1--;   // var1 has a global positive value at the beginning that is reduced in every iteration of each calling to finally get 0 for stopping recursive calls
               if(!var2)
                    if(func())
                         return True;
               var1++;
               // Do few more things
          }
          // Do few things, then:
          return False;
     }
}

main()
{
     // some initialization
     // few things to do, then:
     func();
     // few thing to show the results
}

Are var1 and var2 global variables (shared by recursive function calls)? — Jérôme Richard
– Jérôme Richard, Commented Apr 30, 2020 at 19:10
Yes @JérômeRichard , exactly. They are global variables shared with func() — PSK
– PSK, Commented Apr 30, 2020 at 22:15
Mixing recursive function with global variables generally makes parallelization tricky. In the worse case, it prevents any possible parallelism. In the best case, it introduces costly (implicit/explicit) synchronizations and salability problems which is the source of performance issues. Here, if var2 switch between 0 and 1 in boo based on its previous state and in a non predictable way, your code is probably sequential and thus cannot be parallelized. I advise you to redesign your algorithm to exclude global variables, and then think about which part of the algorithm could run in parallel. — Jérôme Richard
– Jérôme Richard, Commented May 1, 2020 at 13:20
Thank @JérômeRichard, I got your points and tried to solve it. I think I have to add more few explanation about code intention to make it more understandable what I'm going to do: — PSK
– PSK, Commented May 14, 2020 at 15:19
There is a shared 2D matrix that our algorithm is going to fill its elements with integer values. The function boo() does some changes on the values of some elements and at the end checks if all matrix elements have been filled or not yet. If yes, it makes var2 as 0, otherwise it leaves var2 with its prior value 1 (Thus at the most time of running var2 is 1 and it gets 0 only when matrix is filled totally). But it’s a kind of game and our algorithm can fill the matrix wrongly, so it should go back to its last state and return the changes to their previous states ... — PSK
– PSK, Commented May 14, 2020 at 15:24

PSK · Accepted Answer · 2020-05-14 16:22:56Z

A parallelized form of code is something like piece of code below. Two main problems commented in top lines of code:

// First problem is how to apply a critical scope at the presence of such an if() statement below.
// Second, how to pull 2 return statements inside the #pragma omp parallel out of the parallel zone.


bool func()
{
    if(var1 == 0) return True;
    else
    {
        // Do few things
        #pragma omp parallel
        {
            #pragma omp for
                for(int i=0; i<N; i++)
                {
                    // Do few things
                    #pragma omp critical
                    {
                        boo();
                        var1--;
                        if(!var2)
                    }   // the critical scope should end here, but does it seem logical/feasible right after if condition?  
                            if(func())
                                    return True;
                        var1++;
                    // Do few more things
                }
                // Do few things, then:
                return False;
        }

    }
}

main()
{
     func();
}

Collectives™ on Stack Overflow

How to parallel a recursive function using OpenMP in C++

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related