[padb-devel] [padb] r156 committed - Actually generate a tree rather than a "string" of nodes when working...

[codesite-noreply at google.com]

Revision: 156
Author: apittman
Date: Tue Aug 25 08:41:34 2009
Log: Actually generate a tree rather than a "string" of nodes when working
out the connection tree.  Previously each node connected to just one
other leading to very deep messages, now it's tree_width wide (default=4)
which should keep the communication overhead down and help with the
scaling no end.

http://code.google.com/p/padb/source/detail?r=156

Modified:
  /trunk/src/padb

=======================================
--- /trunk/src/padb	Tue Aug 25 06:31:14 2009
+++ /trunk/src/padb	Tue Aug 25 08:41:34 2009
@@ -410,6 +410,8 @@
  # Option to define a list of ports used by padb.
  $conf{port_range} = undef;

+$conf{tree_width} = 4;
+
  my $norc       = 0;
  my $configfile = "/etc/padb.conf";

@@ -615,6 +617,7 @@
  $debugModes{verbose}     = undef;
  $debugModes{signon}      = undef;
  $debugModes{rmgr}        = undef;
+$debugModes{ctree}       = undef;

  sub parse_args_outer {

@@ -680,7 +683,9 @@
          }
          if ( $debugModes{all} ) {
              foreach my $mode ( keys(%debugModes) ) {
-                $debugModes{$mode} = $debugModes{all};
+                if ( not defined $debugModes{$mode} ) {
+                    $debugModes{$mode} = $debugModes{all};
+                }
              }
          }
      }
@@ -3245,11 +3250,8 @@

  }

-# For each remote process generate a tree, giving each
-# process a parent and a number of children.
-# Currently just make this a simple "ladder" but should
-# probably be a f-nomial tree.
-sub generate_comm_tree {
+# A simple "ladder" or 1-wide tree
+sub generate_comm_tree_ladder {
      my ($a)  = @_;
      my @b    = @{$a};
      my $last = "root";
@@ -3262,6 +3264,50 @@

      return \%comm_tree;
  }
+
+# Fairly simple this, walk through the hosts keeping a list
+# of joints (Those able to accept children this iteration) and
+# leaves (those able to accept children next iteration) and
+# loop until there are no more hosts left to add.
+sub generate_binary_tree {
+    my ( $a, $width ) = @_;
+    my @b    = @{$a};
+    my $last = "root";
+    my %comm_tree;
+
+    my @leaves;
+
+    my $root = shift( @{$a} );
+
+    my @joints;
+    push( @joints, $root );
+
+    $comm_tree{root}{children}[0] = $root;
+
+    while ( @{$a} ) {
+        foreach my $joint (@joints) {
+            my @children = splice( @{$a}, 0, $width );
+            if ( $#children > -1 ) {
+                push( @leaves, @children );
+                @{ $comm_tree{$joint}{children} } = @children;
+            }
+        }
+        @joints = @leaves;
+        @leaves = ();
+    }
+
+    return \%comm_tree;
+}
+
+# For each remote process generate a tree, giving each
+# process a parent and a number of children.
+# Currently just make this a simple "ladder" but should
+# probably be a f-nomial tree.
+sub generate_comm_tree {
+    my ($a) = @_;
+
+    return generate_binary_tree( $a, $conf{tree_width} );
+}

  # Called once when we have the socket details of the last child.
  sub connect_to_children {
@@ -3269,12 +3315,14 @@

      debug_log( "signon", undef, "Received last signon, connecting to  
inner" );

-    @{ $comm_data->{host_ids} } = sort( keys( %{ $comm_data->{remote} } )  
);
+    @{ $comm_data->{host_ids} } = sortn( keys( %{ $comm_data->{remote} } )  
);
      $comm_data->{connection_tree} =
        generate_comm_tree( $comm_data->{host_ids} );
+
      my $td = $comm_data->{connection_tree}->{root}{children}[0];

-    #printf("I'm connecting to $td\n");
+    debug_log( "ctree", $comm_data->{connection_tree}, "connection tree" );
+
      my $cdata;
      $cdata->{socket} = connect_to_child(
          $td,
@@ -6174,6 +6222,7 @@

  sub ping_rank {
      my ( $cargs, $vp, $pid ) = @_;
+    target_key_pair( $vp, "PING", "ACK" );
      output( $vp, "ACK" );
      return;
  }