Q: tasks and recursion, binary tree

Q: tasks and recursion, binary tree

[gautier_niouzes]

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 

Re: Q: tasks and recursion, binary tree

[Bob Duff]

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