Using of tasks in openmp for recursive calls

General OpenMP discussion

Using of tasks in openmp for recursive calls

Postby xkoda » Fri Mar 02, 2012 4:18 pm

This is sample program using openmp tasks. In the specs it mentioned that as we encounter a task in a parallel region it will assigned to a thread.

Now I was not able to figure out what happens in this scenario. In each recursive call a task is being created. Each task will have it own stack space and will be destroyed when the task is completed. Can you explain how the values in the recursive calls are preseved even though the variables are shared ?
(to be more specific in sequential execution every thing is preserved in stack. But here the stack gets destroyed after task completion)

Code: Select all
#include "stdio.h"

int com_fib(int n)
{
int f,fn2,fn1;
// f(n) = f(n-1) + f(n-2)
if(n == 0||n == 1) return n;
if ( n < 20 ) return(com_fib(n-1) + com_fib(n-2));

#pragma omp task shared(fn1)
{ fn1 = com_fib(n-1); }

#pragma omp task shared(fn2)
{ fn2 = com_fib(n-2); }

#pragma omp taskwait
f = fn1 + fn1;

return f;
}

void main(int argc, char *argv[])
{
int result;
// printf("arg is %d\n", atoi(argv[1]) );
#pragma omp parallel
{
    #pragma omp single nowait
    {
        result = com_fib(atoi(argv[1]));
    } // End of single
} // End of parallel region
printf("Fib is %d\n", result);

}



Thanks in advance
xkoda
 
Posts: 2
Joined: Fri Mar 02, 2012 4:12 pm

Re: Using of tasks in openmp for recursive calls

Postby james » Wed Mar 07, 2012 10:03 am

Code: Select all
int com_fib(int n)
{
  int f,fn2,fn1;

  if(n == 0||n == 1) return n;
  if ( n < 20 ) return(com_fib(n-1) + com_fib(n-2));

#pragma omp task shared(fn1)
  { fn1 = com_fib(n-1); }

#pragma omp task shared(fn2)
  { fn2 = com_fib(n-2); }

#pragma omp taskwait
  f = fn1 + fn1;

return f;
}


Why do you think the stack objects are preserved? The recursive calls destroy there stack before the task returns. This is no different than the way the serial version of the code. There is no need to maintain any stack space in the recursive calls. The taskwait at the end of the routine ensures that the task waits for the return values of its contained tasks. The only value that needs to be maintained out of the task is the result variable, fn1 and fn2. Once the child tasks return the taskwait at the end of the routine completes, this allows that task to compute its part of the computation and then return that value. If you change the code to this:
Code: Select all
void com_fib(int n, int *result)
{
  int f,fn2,fn1;

  if(n == 0||n == 1) return n;
  if ( n < 20 ) {
      com_fib(n-1, &fn1 );
      com_fib(n-2, &fn2 );
      *result = fn1+fn2;
      return;
  }

#pragma omp task
  { com_fib(n-1, &fn1); }

#pragma omp task
  { com_fib(n-2, &fn2); }

#pragma omp taskwait
  *result = fn1 + fn1;

  return;
}


Now the only thing that ensures that the stack variables fn1 and fn2 are not destroyed is the taskwait. If the taskwait were not there than chaos would ensure, not just in the fact that the result is computed before the task complete but because the pointers sent into the tasks may no longer have the correct data associated with them.
james
 
Posts: 53
Joined: Fri May 16, 2008 9:27 am

Re: Using of tasks in openmp for recursive calls

Postby xkoda » Thu Mar 08, 2012 9:52 pm

Thanks allot for the explanation. I was not thinking about "tasks waiting for return results"
Now its crystal clear :)
xkoda
 
Posts: 2
Joined: Fri Mar 02, 2012 4:12 pm


Return to Using OpenMP

Who is online

Users browsing this forum: Yahoo [Bot] and 1 guest