example tasking.2.c doesn't work as expected

Discuss the OpenMP Examples document, updated for OpenMP 4.5

example tasking.2.c doesn't work as expected

Postby siegmar_gross » Tue Jan 03, 2017 11:44 pm

Hi,

I tried to use the example "tasking.2.c" from "OpenMP 4.5 Examples"
(page 53) to print a binary tree in postfix order. Unfortunately I
get different results for different runs (I called the function eight
times).

Sequence of numbers added to the binary tree.
50 56 46 6 27 67 65 92 90 27

Printing all values post-order example. Root = 50
((((()()(()(()()27)((()()65)(()()()6)46)90)92)67)56)50)
(((()(()(()(()()((()()(()27)()6)()46)65)90)92)67)56)50)
(((()((((()()()65)()()90)(()(()()92)()27)67)56)6)46)50)
((((()(()()()()((27)(6)(()()46)()()()90)92)65)67)56)50)
((((()()(((()()()(65)()(()()()()90)27)92)6)67)46)56)50)
(((()((()()(65)(()(()(()()27)6)()()46)()90)92)67)56)50)
((((()(()()27)()()(((()6)()46)65)(()()()90)92)67)56)50)
((((()()()((()(()27)6)()((46)()()()()65)90)92)67)56)50)

I get a postfix order if I add one more taskwait directive.

Printing all values post-order. Root = 50
(((()(()()27)6)()46)(()((()()65)((()()90)()92)67)56)50)
(((()(()()27)6)()46)(()((()()65)((()()90)()92)67)56)50)
(((()(()()27)6)()46)(()((()()65)((()()90)()92)67)56)50)
(((()(()()27)6)()46)(()((()()65)((()()90)()92)67)56)50)
(((()(()()27)6)()46)(()((()()65)((()()90)()92)67)56)50)
(((()(()()27)6)()46)(()((()()65)((()()90)()92)67)56)50)
(((()(()()27)6)()46)(()((()()65)((()()90)()92)67)56)50)
(((()(()()27)6)()46)(()((()()65)((()()90)()92)67)56)50)

Do I misunderstand something or is the example code in the
document not correct? In my opinion one taskwait directive
isn't enough because you only wait for the completion of
both subtrees but the execution order of the subtrees isn't
fixed. With an additonal taskwait directive the execution
order of the subtrees is fixed as well.


void print_tree_post_order_example (struct node *root)
{
if (root != NULL)
{
printf ("(");
#pragma omp task firstprivate(root)
{
print_tree_post_order_example (root->left);
}
#pragma omp task firstprivate(root)
{
print_tree_post_order_example (root->right);
}
#pragma omp taskwait
printf ("%d)", root->value);
}
else
{
printf ("()");
}
}


void print_tree_post_order (struct node *root)
{
if (root != NULL)
{
printf ("(");
#pragma omp task firstprivate(root)
{
print_tree_post_order (root->left);
}
#pragma omp taskwait
#pragma omp task firstprivate(root)
{
print_tree_post_order (root->right);
}
#pragma omp taskwait
printf ("%d)", root->value);
}
else
{
printf ("()");
}
}


I would be grateful if somebody can and will answer my above
question. Thank you very much for any answer in advance.


Kind regards

Siegmar
siegmar_gross
 
Posts: 1
Joined: Tue Jan 03, 2017 6:07 am

Re: example tasking.2.c doesn't work as expected

Postby hhj » Wed Jan 11, 2017 10:12 am

The "tasking.2.c" example is a parallel tree traversal example using tasks. The parallelism comes from the fact that the left and right branches can be executed in parallel, which means that the order of left and right branch executions may be different from different runs. This is in a sense different from the sequential "postorder" traversal. We could add a note for this fact. Adding an extra taskwait as you suggested essentially serializes the execution, thus giving the reproducible run-to-run results, but you lose the parallelism.

Hope this explanation makes sense.

-Henry
hhj
 
Posts: 17
Joined: Thu May 01, 2008 11:59 am


Return to OpenMP 4.5 Examples Discussion

Who is online

Users browsing this forum: No registered users and 1 guest