Spanning trees: Dont count on-node subtree against maxBranches
authorRamprasad Venkataraman <ramv@illinois.edu>
Thu, 21 Oct 2010 18:27:02 +0000 (13:27 -0500)
committerRamprasad Venkataraman <ramv@illinois.edu>
Thu, 21 Oct 2010 18:27:02 +0000 (13:27 -0500)
Strategies that try to minimize the total bytes on the network use one sub-tree
for the on-node PEs. This used to count against the maximum allowed branching
factor specified for the spanning tree. However, in the case of binary trees
(maxBranches=2), this caused excessively deep trees as the inter-node tree was
effectively a chain! Fix this by not counting the local branch against the
allowed maximum branching factor (maxBranches).

As before, if there are not enough off-node children, the strategies will use
as many branches for local destinations as possible.

src/util/treeStrategy_3dTorus_minBytesHops.h
src/util/treeStrategy_nodeAware_minBytes.h

index f86745bd6bebaadba8e16d25fccb9b55c53cc886..354988cbb6590c3af358552247d4e97fe0d5576c 100644 (file)
@@ -113,7 +113,7 @@ SpanningTreeVertex* SpanningTreeStrategy_3dTorus_minBytesHops<Iterator,SpanningT
     /// If there are any local vertices at all
     if (numLocalDestinations > 0)
     {
-        numLocalBranches = (numRemoteDestinations >= maxBranches-1)? 1 : (maxBranches - numRemoteDestinations);
+        numLocalBranches = (numRemoteDestinations >= maxBranches)? 1 : (maxBranches - numRemoteDestinations);
         /// Distribute the local destination vertices amongst numLocalBranches branches
         SpanningTreeVertex *localTree = impl::buildNextGen_topoUnaware(firstVtx,beyondLastLocal,numLocalBranches);
         /// Append the local tree info to the child info
@@ -125,7 +125,7 @@ SpanningTreeVertex* SpanningTreeStrategy_3dTorus_minBytesHops<Iterator,SpanningT
 
     /// Partition the remote-vertex bounding box into the remaining number of branches
     impl::TreeBoundingBoxOn3dTorus<Iterator> treePart;
-    treePart.partition(firstVtx,beyondLastLocal,beyondLastVtx,maxBranches-numLocalBranches);
+    treePart.partition(firstVtx,beyondLastLocal,beyondLastVtx,maxBranches);
 
     /// Identify the closest member in each remote branch and put it at the corresponding childIndex location
     for (int i=numLocalBranches, numChildren=(*firstVtx).childIndex.size(); i<numChildren; i++)
index ed4f002fcc92b2f2fa117a97477ed055799fca94..1cadda2709734d72a9d0cc1f5746b2710f799cdc 100644 (file)
@@ -98,14 +98,14 @@ namespace impl {
         {
             /// Determine how many branches can be used to span the local destinations
             int numRemoteDestinations = std::distance(firstVtx,beyondLastVtx) -1 - numLocalDestinations; ///< @warning: This is O(treeSize) for Iterator != random iterator
-            numLocalBranches = (numRemoteDestinations >= maxBranches-1)? 1 : (maxBranches - numRemoteDestinations);
+            numLocalBranches = (numRemoteDestinations >= maxBranches)? 1 : (maxBranches - numRemoteDestinations);
 
             /// Distribute the local destination vertices amongst numLocalBranches branches
             Iterator beyondLastLocal = lastLocal;
             parent = buildNextGen_topoUnaware(firstVtx,++beyondLastLocal,numLocalBranches);
 
             /// Construct a topo-unaware tree for the rest (off-node PEs) of the vertices
-            SpanningTreeVertex *remoteSubTrees = buildNextGen_topoUnaware(lastLocal,beyondLastVtx,maxBranches-numLocalBranches); ///< Abuse the interface by faking lastLocal as the tree root
+            SpanningTreeVertex *remoteSubTrees = buildNextGen_topoUnaware(lastLocal,beyondLastVtx,maxBranches); ///< Abuse the interface by faking lastLocal as the tree root
 
             /// Append the remote sub-tree info to the result object
             for (int i=0, n=remoteSubTrees->childIndex.size(); i< n; i++)