Problem in Parallelizing the recursion

[Anupam_Dev1]

hi, i m new to openmp programming. I have written few codes on strassen's matrix multiplication and others but I m facing the problem parallelizing the code for the binary tree traversals of inorder,preorder and post order.

If any one knows beter how to parallelize the recursive functions please help me.

the code snippet is here

main(){


#pragma omp parallel
{
#pragma omp sections
{
#pragma omp section
inorder(t)
}
}
}//end of main

inorder(node *t)
{
...
.....
}

[TimP]

Did you read Robert's post http://software.intel.com/en-us/forums/showthread.php?t=66278 ?
Recursion, generally speaking, may best be parallelized where it is possible to define independent recursive tasks, or, better yet, identical recursive processes on multiple (hundreds of) data.

[Anupam_Dev1]

@tim
thanx for u reply

i m able to parallelize the traversal running on two threads but the final result is coming out to be incorrect. It is a problem of data sharing and data race i think; if u can tell me any posts related to the problems of data sharing and data race.

[jimdempseyatthecove]

Your code snippet, as written, has no indication that parallel recursion will be used. The main() call of inorder(...) is being performed by 1 thread. Possibly something like as follows is what you are trying to do.

main(){

inorder(head)

}//end of main

inorder(node *t)
{
if(canSplitThis())
{
#pragma omp parallel numthreads(2)
{
#pragma omp sections
{
#pragma omp section
inorder(head->left)
#pragma omp section
inorder(head->right)
}
}
}
...
.....
}

Note, it will be your responsibility to assure thread-safe programming practices are followed (atomics or critical sections etc...)

Jim Dempsey

[robert-reed]

You might be able to get some concurrent work from the pre-order traversal of the trees, but one thing you're running into is the inherently serial nature of the algorithms you want to code. Each of these traversal sequences by their natureimpose a serial ordering upon the nodes, so it might be pretty hard to find much parallel work merely in their traversal. Only if there was significant work associated with the processing of each node might there be enough work to support multiple threads. Consider tree traversal as described in Wikipedia: The order of traversal imposes a strict dependence order that invests the entire tree--those dependence relations impose a cost that would likely soak up any scaling that local concurrency might provide. Even in the pre-order case, the restriction that processing of the "left" subtree must occur before processing of the "right" substree imposes a communications requirement between whatever multiple threads might be pulled in to perform the task. However, relaxing the strict node processing order across the subtrees, the post-order traversal is basically a parallel-reduce--threads can join in on the tree traversal to get to the leaf nodes and then rendezvous with each other to pass their partial results back to the root.