From: gautier_niouzes@hotmail.com
Subject: Q: tasks and recursion, binary tree
Date: Wed, 6 May 2015 04:13:44 -0700 (PDT)
Date: 2015-05-06T04:13:44-07:00 [thread overview]
Message-ID: <4a618fc7-a443-4ce3-884f-bd40b359dcd4@googlegroups.com> (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
next reply other threads:[~2015-05-06 11:13 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-05-06 11:13 gautier_niouzes [this message]
2015-05-06 12:27 ` Q: tasks and recursion, binary tree Bob Duff
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox