From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM
	autolearn=unavailable autolearn_force=no version=3.4.4
X-Received: by 10.43.77.3 with SMTP id zg3mr3103966icb.20.1430910824555;
        Wed, 06 May 2015 04:13:44 -0700 (PDT)
X-Received: by 10.140.105.133 with SMTP id c5mr376894qgf.28.1430910824419;
 Wed, 06 May 2015 04:13:44 -0700 (PDT)
Path: 
 eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!news.glorb.com!m20no8779709iga.0!news-out.google.com!t92ni172qga.1!nntp.google.com!z60no5605510qgd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Wed, 6 May 2015 04:13:44 -0700 (PDT)
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=57.79.21.1;
 posting-account=gRqrnQkAAAAC_02ynnhqGk1VRQlve6ZG
NNTP-Posting-Host: 57.79.21.1
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <4a618fc7-a443-4ce3-884f-bd40b359dcd4@googlegroups.com>
Subject: Q: tasks and recursion, binary tree
From: gautier_niouzes@hotmail.com
Injection-Date: Wed, 06 May 2015 11:13:44 +0000
Content-Type: text/plain; charset=ISO-8859-1
Xref: news.eternal-september.org comp.lang.ada:25737
Date: 2015-05-06T04:13:44-07:00
List-Id: <comp.lang.ada>

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