* Q: tasks and recursion, binary tree
@ 2015-05-06 11:13 gautier_niouzes
2015-05-06 12:27 ` Bob Duff
0 siblings, 1 reply; 2+ messages in thread
From: gautier_niouzes @ 2015-05-06 11:13 UTC (permalink / raw)
Hello,
I'm trying to parallelize a binary tree traversal - in a simple way (my hope). But it doesn't work as I'd expect and I am wondering why.
Side note: an idea in the code below is to switch to a sequential recursion from a certain depth N in order to limit the total number of active tasks.
The variable "count" counts the number of nodes processed. The correct number is 598 in my example. However I get this (sometimes the total is random!):
N count
0 598 (sequential)
1 345
2 220
3 15..77
4 93..94
5 63..93
6 133..140
7 257..264
8 510
>=9 597..598 (fully parallel: max depth is 9)
type Dir_node;
type p_Dir_node is access Dir_node;
type Dir_node is record
left, right: p_Dir_node;
-- node contents here
end record;
procedure Traverse_private( z: Zip_info ) is
count: Natural:= 0;
pragma Volatile(count);
procedure Traverse( p: p_Dir_node; depth: Natural ) is
procedure Parallel is
task T_left;
task body T_left is
begin
Traverse(p.left, depth + 1);
end;
task T_right;
task body T_right is
begin
Traverse(p.right, depth + 1);
end;
begin
count:= count + 1;
Action_private(p.all);
end Parallel;
begin
if p = null then
return;
end if;
if depth >= N then
Traverse(p.left, depth + 1);
count:= count + 1;
Action_private(p.all);
Traverse(p.right, depth + 1);
else
Parallel;
end if;
end Traverse;
begin
Traverse(z.dir_binary_tree, 0);
Ada.Text_IO.put_line(count'img);
end Traverse_private;
Any clue ?
TIA
_________________________
Gautier's Ada programming
http://gautiersblog.blogspot.com/search/label/Ada
NB: follow the above link for a valid e-mail address
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: Q: tasks and recursion, binary tree
2015-05-06 11:13 Q: tasks and recursion, binary tree gautier_niouzes
@ 2015-05-06 12:27 ` Bob Duff
0 siblings, 0 replies; 2+ messages in thread
From: Bob Duff @ 2015-05-06 12:27 UTC (permalink / raw)
gautier_niouzes@hotmail.com writes:
> count: Natural:= 0;
> pragma Volatile(count);
...
> count:= count + 1;
You need an atomic increment. Volatile doesn't do that (see the RM for
what it actually does). Pragma Atomic doesn't do that either.
So the code has a data race, which makes it erroneous, which means
anything could happen (the program might crash, or might get wrong
answers, or might get correct answers).
You could create a protected object that encapsulates Count.
Or with GNAT you could look at System.Atomic_Counters.
- Bob
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2015-05-06 12:27 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-05-06 11:13 Q: tasks and recursion, binary tree gautier_niouzes
2015-05-06 12:27 ` Bob Duff
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox