Page 1 of 1

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

PostPosted: Tue Jan 03, 2017 11:44 pm
by siegmar_gross
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

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

PostPosted: Wed Jan 11, 2017 10:12 am
by hhj
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