Overhaul the spanning tree construction strategies.
authorRamprasad Venkataraman <ramv@illinois.edu>
Thu, 26 Nov 2009 15:23:21 +0000 (09:23 -0600)
committerRamprasad Venkataraman <ramv@wisdom.site>
Mon, 30 Nov 2009 18:35:59 +0000 (12:35 -0600)
- Original 3D torus strategy reduces just the total hops to span all tree members. Rename to clarify
- Add new strategy for 3D meshes/torii that will also reduce the bytes on the network
- Add node-aware strategies that should construct reasonably node-aware trees on all machines
- Default tree construction algorithm on typical clusters etc. is now node-aware
- Fix comlib usage and dependancies

src/ck-com/OneTimeMulticastStrategy.C
src/scripts/Make.depends
src/util/spanningTreeStrategy.h
src/util/spanningTreeVertex.h [new file with mode: 0644]
src/util/treeStrategy_3dTorus_minBytesHops.h [new file with mode: 0644]
src/util/treeStrategy_3dTorus_minHops.h [moved from src/util/treeStrategy_3dTorus.h with 69% similarity]
src/util/treeStrategy_nodeAware_minBytes.h [new file with mode: 0644]
src/util/treeStrategy_nodeAware_minGens.h [new file with mode: 0644]
src/util/treeStrategy_topoUnaware.h

index 843168122d101b588b23321e41a964a614b83b75..0f7319a5967b25064dd5b2a796f3168cb9b79dd2 100644 (file)
@@ -936,7 +936,7 @@ void OneTimeTopoTreeMulticastStrategy::determineNextHopPEs(const int totalDestPE
         tree.push_back( topo::SpanningTreeVertex(destPEs[i].pe) );
 
     /// Build the complete spanning tree
-    topo::buildSpanningTree(tree.begin(),tree.end(),degree,topo::getSpanningTreeStrategy<std::vector<topo::SpanningTreeVertex>::iterator>());
+    topo::buildSpanningTree(tree.begin(),tree.end(),degree);
 
     /// Identify this PE in the tree and find immediate children
     int peIdx = -1;
index 4b9f0a55f56bb79ce89d8dd4a33315365d2ade04..75c0ceaaee72ce966495577e137b4be18dd69760 100644 (file)
@@ -2072,8 +2072,11 @@ OneTimeMulticastStrategy.o: OneTimeMulticastStrategy.C \
   CkCheckpoint.decl.h ckevacuation.h ckarrayreductionmgr.h trace.h \
   conv-trace.h trace-bluegene.h envelope.h convcomlibstrategy.h \
   ComlibLearner.h ComlibArrayListener.h ComlibStats.h comlib.decl.h \
-  ComlibSectionInfo.h TopoManager.h spanningTreeStrategy.h \
-  treeStrategy_topoUnaware.h treeStrategy_3dTorus.h
+  ComlibSectionInfo.h TopoManager.h \
+  spanningTreeStrategy.h spanningTreeVertex.h \
+  treeStrategy_3dTorus_minBytesHops.h treeStrategy_3dTorus_minHops.h \
+  treeStrategy_nodeAware_minBytes.h treeStrategy_nodeAware_minGens.h \
+  treeStrategy_topoUnaware.h
        $(CHARMC) -c -I. OneTimeMulticastStrategy.C
 
 EachToManyMulticastStrategy.o: EachToManyMulticastStrategy.C \
index 2bfb2965299db2cf8afae18f691cb96a2f688212..03fb28cea4bdfd2ff92fa6721234f6af12e4f14a 100644 (file)
@@ -3,11 +3,12 @@
 #include <iterator>
 
 #include "conv-config.h"
+#include "spanningTreeVertex.h"
 
 #ifndef SPANNING_TREE_STRATEGY
 #define SPANNING_TREE_STRATEGY
 
-#if ! CMK_HAS_ITERATOR_TRAITS 
+#if ! CMK_HAS_ITERATOR_TRAITS
 namespace std {
 
 template <class Iterator>
@@ -32,7 +33,7 @@ template <class Iterator>
 
 #endif
 
-#if ! CMK_HAS_STD_DISTANCE 
+#if ! CMK_HAS_STD_DISTANCE
 namespace std {
 
 template <class Iterator>
@@ -50,6 +51,38 @@ int distance(Iterator first, Iterator last)
 }
 #endif
 
+/**
+ * @file: This header includes utility routines and several strategies for constructing spanning trees for msg delivery.
+ *
+ * Multicasts and reductions can be efficiently implemented by propogating the message(s) along spanning trees
+ * that are constructed using as much information about the machine as possible. Libraries that implement any
+ * multicast/redn algorithms can use this header to easily generate a spanning tree from a list of target PEs.
+ *
+ * Client code does not have to worry about machine specifics and any tree generation algorithms. Generated spanning
+ * trees will be based on the best available information (node-awareness, network-topo awareness etc.).
+ *
+ * The focus remains on distributed logic that generates efficient (for practical purposes) spanning trees and not
+ * theoretical MSTs (minimum spanning trees) etc. Hence the intented use is to supply a list of PEs as input and
+ * obtain info about the immediate next generation of vertices in the tree and the members of each of their
+ * respective sub-trees. As an afterthought, the API includes calls that will generate a complete spanning tree
+ * from the input too. However, no guarantees are currently made about the efficiency of this use.
+ *
+ * Usage:
+ *       Simple use cases shouldn't have to worry about anything beyond the self-explanatory functions:
+ *       buildSpanningTreeGeneration()
+ *       buildSpanningTree()
+ *
+ *       SpanningTreeVertex is a data structure that facilitates input/output, although input can be any container
+ *       (C arrays, vectors etc.) of PEs
+ *
+ *       Another routine to be aware of is a factory method that is used behind the scenes to obtain what appears
+ *       to be the best strategy for building trees given the current machine/input etc: getSpanningTreeStrategy().
+ *
+ *       Users can override this choice by specifying a strategy when calling one of the build routines. A list of
+ *       strategies should be apparent from the headers included near the bottom of this file.
+ */
+
+
 //-------------------------------- Declarations of the main entities in this file --------------------------------
 
 /// This namespace contains network topology related classes and utilities
@@ -65,19 +98,20 @@ class SpanningTreeVertex;
 template <typename Iterator,typename ValueType = typename std::iterator_traits<Iterator>::value_type>
 class SpanningTreeStrategy;
 
-/// Tiny factory method that returns an appropriate spanning tree builder based on the machine network topology information (if available)
-template <typename Iterator>
-SpanningTreeStrategy<Iterator>* getSpanningTreeStrategy();
-
 /// Builds one generation of the spanning tree given a container of vertices with the tree root as the first element in the container
 template <typename Iterator>
 SpanningTreeVertex* buildSpanningTreeGeneration
-(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2, SpanningTreeStrategy<Iterator> *bldr = getSpanningTreeStrategy<Iterator>());
+(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2, SpanningTreeStrategy<Iterator> *bldr = 0);
 
 /// Builds the complete spanning tree given a container of vertices with the tree root as the first element in the container
 template <typename Iterator>
 void buildSpanningTree
-(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2, SpanningTreeStrategy<Iterator> *bldr = getSpanningTreeStrategy<Iterator>());
+(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2, SpanningTreeStrategy<Iterator> *bldr = 0);
+
+/// Tiny factory method that returns a tree construction strategy that it thinks is best (based on inputs, the machine's network topology info etc)
+template <typename Iterator>
+SpanningTreeStrategy<Iterator>* getSpanningTreeStrategy
+(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches);
 
 } // end namespace topo
 
@@ -86,51 +120,12 @@ void buildSpanningTree
 //--------------------------------  Class and function definitions --------------------------------
 namespace topo {
 
-/** 
- * Contains indices to direct children. childIndex[i]+1 and childIndex[i+1] are the first and 
- * beyondLast indices of the sub-tree members of the child at childIndex[i]. 
- * @note: We're using a (vertex, edge) terminology to talk about spanning trees. Consciously staying 
- * away from using "node" to avoid ambiguity with machine nodes and PEs. This is inspite of the fact 
- * that typically a vertex of a spanning tree is a machine node / PE.
- */
-class SpanningTreeVertex
-{
-    public:
-        /// The id (PE) of the vertex 
-        vtxType id;
-        /// The parent of this vertex. Uncomment if needed
-        // vtxType parent;
-        /// The machine coordinates of this vertex
-        std::vector<int> X; 
-        /// Relative distance (in the container) from the position of this vertex to direct children (and their sub-tree members)
-        std::vector<int> childIndex;
-        /// Constructor
-        SpanningTreeVertex(const vtxType _id=-1): id(_id) {}
-
-    /// Stream inserter. Note: not a member function
-    friend std::ostream& operator<< (std::ostream &out, const SpanningTreeVertex &obj)
-    {
-        out<<" "<<obj.id;
-        if (obj.X.size()>0) 
-        {
-            out<<"("<<obj.X[0];
-            for (int i=1,cSize=obj.X.size(); i<cSize; i++)
-                out<<","<<obj.X[i];
-            out<<") ";
-        }
-        return out;
-    }
-};
-
-
-
-
 /** The spanning tree build strategy interface. Partitions and reorders a collection of tree members, and returns information about children and their sub-trees.
  *
- * @warning: User code should only specify typename Iterator. ValType is automatically given the 
- * default value based on Iterator and should not be specified by the user. 
+ * @warning: User code should only specify typename Iterator. ValType is automatically given the
+ * default value based on Iterator and should not be specified by the user.
  *
- * @todo: If compile-time asserts become available in the charm world, then assert that ValType is 
+ * @todo: If compile-time asserts become available in the charm world, then assert that ValType is
  * nothing illegal in the appropriate subclasses. Better still, (if possible) let the subclass remain
  * abstract and implement buildNextGen only for the appropriate partial specializations of ValType.
  */
@@ -145,26 +140,28 @@ class SpanningTreeStrategy
 
 
 
-/** Facade function to hide all the template muck for the mainstream usecases. 
+/** Facade function to hide all the template muck for the mainstream usecases.
  *
  * Use when you're happy with the default spanning tree strategy. This should hide the very existence
- * of all this template stuff for the default use-cases. 
+ * of all this template stuff for the default use-cases.
  *
  * For scenarios, where you want to specify the tree building strategy, you need to supply a strategy
- * object. In this case, instantiate a strategy object manually (the factory method 
- * getSpanningTreeStrategy() will give you what it thinks is best) and plug it into this function 
+ * object. In this case, instantiate a strategy object manually (the factory method
+ * getSpanningTreeStrategy() will give you what it thinks is best) and plug it into this function
  * call.
  *
  * Its advisable to use this facade even when explicitly specifying a strategy object, as this leaves
  * room for future additions to the procedure without affecting the user code
  */
 template <typename Iterator>
-inline SpanningTreeVertex* buildSpanningTreeGeneration(const Iterator firstVtx, 
-                                                       const Iterator beyondLastVtx, 
-                                                       const int maxBranches, 
-                                                       SpanningTreeStrategy<Iterator> *bldr 
+inline SpanningTreeVertex* buildSpanningTreeGeneration(const Iterator firstVtx,
+                                                       const Iterator beyondLastVtx,
+                                                       const int maxBranches,
+                                                       SpanningTreeStrategy<Iterator> *bldr
                                                       )
 {
+    /// If no strategy is passed in, instantiate one
+    if (bldr == 0) bldr = getSpanningTreeStrategy(firstVtx,beyondLastVtx,maxBranches);
     return bldr->buildNextGen(firstVtx,beyondLastVtx,maxBranches);
 }
 
@@ -179,15 +176,18 @@ template <typename Iterator>
 void buildSpanningTree(SpanningTreeVertex* dispatchTag,
                        const Iterator firstVtx,
                        const Iterator beyondLastVtx,
-                       const int maxBranches=2,
-                       SpanningTreeStrategy<Iterator> *bldr = getSpanningTreeStrategy<Iterator>()
+                       const int maxBranches,
+                       SpanningTreeStrategy<Iterator> *bldr
                       )
 {
     /// Build a tree only if there are any vertices in the input range
     if (firstVtx < beyondLastVtx)
     {
         /// Build the next generation of the tree rooted at *firstVtx
-        buildSpanningTreeGeneration(firstVtx,beyondLastVtx,maxBranches,bldr);
+        SpanningTreeVertex *tmp = buildSpanningTreeGeneration(firstVtx,beyondLastVtx,maxBranches,bldr);
+        /// Delete the copy of firstVtx that gets returned from the call
+        delete tmp;
+
         int numChildren = (*firstVtx).childIndex.size();
         /// For each direct child...
         for (int i=0; i< numChildren; i++)
@@ -205,14 +205,14 @@ void buildSpanningTree(SpanningTreeVertex* dispatchTag,
     }
 }
 
-} // end namespace impl 
-  
+} // end namespace impl
 
 
 
 /**
  * Facade function to build a complete spanning tree given an input container of SpanningTreeVertex-es
- * Uses tag-dispatching to ensure at compile-time that the input container holds only SpanningTreeVertex 
+ * Uses tag-dispatching to ensure at compile-time that the input container holds only SpanningTreeVertex
  * and nothing else.
  */
 template <typename Iterator>
@@ -222,7 +222,11 @@ inline void buildSpanningTree(const Iterator firstVtx,
                               SpanningTreeStrategy<Iterator> *bldr
                              )
 {
+    /// If no strategy is passed in, instantiate one
+    if (bldr == 0) bldr = getSpanningTreeStrategy(firstVtx,beyondLastVtx,maxBranches);
+    /// Create a tag
     typename std::iterator_traits<Iterator>::value_type *tag = 0;
+    /// Delegate the work
     impl::buildSpanningTree(tag,firstVtx,beyondLastVtx,maxBranches,bldr);
 }
 
@@ -230,27 +234,53 @@ inline void buildSpanningTree(const Iterator firstVtx,
 
 
 
+/** @note: Concrete strategy implementations depend on the definitions in this file. Hence
+ * its necessary that user code include this file and not just any of the individual strategy
+ * headers that follow.
+ */
 #include "treeStrategy_topoUnaware.h"
-#include "treeStrategy_3dTorus.h"
+#include "treeStrategy_nodeAware_minGens.h"
+#include "treeStrategy_nodeAware_minBytes.h"
+#include "treeStrategy_3dTorus_minHops.h"
+#include "treeStrategy_3dTorus_minBytesHops.h"
+
 namespace topo {
 
 /**
  * Simply uses machine specific preprocessor macros to return an appropriate strategy.
  * Expects that these macros will be available in the current compilation unit thanks to charm innards.
- * Could potentially also use other heuristics to decide on the best strategy, but that might be possible 
- * only if it has some more input information to use.
+ *
+ * Reserves the right to use other heuristics (based on the input data) to select a strategy, if such 
+ * needs arise in the future.
  *
  * @note: The list of machine macros here should sync with the ones that TopoManager is aware of.
  */
 template <typename Iterator>
-inline SpanningTreeStrategy<Iterator>* getSpanningTreeStrategy() 
+inline SpanningTreeStrategy<Iterator>* getSpanningTreeStrategy(const Iterator firstVtx,
+                                                               const Iterator beyondLastVtx,
+                                                               const int maxBranches)
 {
     #if CMK_BLUEGENEL || CMK_BLUEGENEP
-        return ( new SpanningTreeStrategy_3dTorus<Iterator>() );
+        return ( new SpanningTreeStrategy_3dTorus_minBytesHops<Iterator>() );
     #elif XT3_TOPOLOGY || XT4_TOPOLOGY || XT5_TOPOLOGY
-        return ( new SpanningTreeStrategy_3dTorus<Iterator>() );
+        return ( new SpanningTreeStrategy_3dTorus_minBytesHops<Iterator>() );
     #else
-        return ( new SpanningTreeStrategy_topoUnaware<Iterator>() );
+        /// Nested, utility class to let us to use the parent PE for different Iterator::value_types
+        class NumOnNode
+        {
+            public:
+                inline int operator() (const vtxType vtx)             { return CmiNumPesOnPhysicalNode( CmiPhysicalNodeID(vtx) ); }
+                inline int operator() (const SpanningTreeVertex &vtx) { return CmiNumPesOnPhysicalNode( CmiPhysicalNodeID(vtx.id) ); }
+        } findNumPEsOnNode;
+
+        /// Find the number of PEs on the same node as the parent vertex (max possible on-node destinations)
+        int numPEsOnNode = findNumPEsOnNode(*firstVtx);
+
+        /// If minimizing tree generations may be more beneficial than reducing inter-node traffic
+        if (numPEsOnNode <= 4 && maxBranches < 4)
+            return ( new SpanningTreeStrategy_nodeAware_minGens<Iterator>() );
+        else
+            return ( new SpanningTreeStrategy_nodeAware_minBytes<Iterator>() );
     #endif
 }
 
diff --git a/src/util/spanningTreeVertex.h b/src/util/spanningTreeVertex.h
new file mode 100644 (file)
index 0000000..a169937
--- /dev/null
@@ -0,0 +1,100 @@
+#ifndef SPANNING_TREE_VERTEX
+#define SPANNING_TREE_VERTEX
+
+namespace topo {
+
+/// Alias for the actual data type of a vertex id (PE/node number)
+typedef int vtxType;
+
+/**
+ * Contains indices to direct children. childIndex[i]+1 and childIndex[i+1] are the first and
+ * beyondLast indices of the sub-tree members of the child at childIndex[i].
+ * @note: We're using a (vertex, edge) terminology to talk about spanning trees. Consciously staying
+ * away from using "node" to avoid ambiguity with machine nodes and PEs. This is inspite of the fact
+ * that typically a vertex of a spanning tree is a machine node / PE.
+ */
+class SpanningTreeVertex
+{
+    public:
+        /// The id (PE) of the vertex
+        vtxType id;
+        /// The parent of this vertex. Uncomment if needed
+        // vtxType parent;
+        /// The machine coordinates of this vertex
+        std::vector<int> X;
+        /// Relative distance (in the container) from the position of this vertex to direct children (and their sub-tree members)
+        std::vector<int> childIndex;
+        /// Constructor
+        SpanningTreeVertex(const vtxType _id=-1): id(_id) {}
+
+    /// Overload == and < to keep users happy. Note: not member functions
+    ///@{
+    inline friend bool operator== (const SpanningTreeVertex &obj, const int vtxID)
+    { return (obj.id == vtxID); }
+
+    inline friend bool operator== (const int vtxID, const SpanningTreeVertex &obj)
+    { return (obj.id == vtxID); }
+
+    inline friend bool operator< (const SpanningTreeVertex &obj, const int vtxID)
+    { return (obj.id < vtxID); }
+
+    inline friend bool operator< (const int vtxID, const SpanningTreeVertex &obj)
+    { return (vtxID < obj.id); }
+    ///@}
+
+    /// Stream inserter. Note: not a member function
+    friend std::ostream& operator<< (std::ostream &out, const SpanningTreeVertex &obj)
+    {
+        out<<" "<<obj.id;
+        if (obj.X.size()>0)
+        {
+            out<<"("<<obj.X[0];
+            for (int i=1,cSize=obj.X.size(); i<cSize; i++)
+                out<<","<<obj.X[i];
+            out<<") ";
+        }
+        return out;
+    }
+};
+
+
+
+/// Return the number of hops (on the machine network) between two vertices in the tree
+inline int numHops(const SpanningTreeVertex &vtx1, const SpanningTreeVertex &vtx2)
+{
+    /// Assert that the dimensions of the coordinate vectors of the two vertices are the same
+    //CkAssert(vtx1.X.size() == vtx2.X.size());
+
+    int nHops = 0;
+    for (int i=0, nDims=vtx1.X.size(); i<nDims; i++)
+        nHops += abs( vtx1.X[i] - vtx2.X[i] );
+    return nHops;
+}
+
+
+
+/// Pick the vertex closes to the parent in the given range
+template <typename Iterator>
+inline Iterator pickClosest(const SpanningTreeVertex &parent, const Iterator start, const Iterator end)
+{
+    /// @todo: Static assert that Iterator::value_type == SpanningTreeVertex
+    Iterator itr     = start;
+    Iterator closest = itr++;
+    int      minHops = numHops(parent,*closest); // aTopoMgr.getHopsBetweenRanks( parentPE, (*closest).id );
+    /// Loop thro the range and identify the vertex closest to the parent
+    for (; itr != end; itr++)
+    {
+        int hops = numHops(parent,*itr); //aTopoMgr.getHopsBetweenRanks( parentPE, (*itr).id );
+        if (hops < minHops)
+        {
+            closest = itr;
+            minHops = hops;
+        }
+    }
+    return closest;
+}
+
+} // end namespace topo
+
+#endif // SPANNING_TREE_VERTEX
+
diff --git a/src/util/treeStrategy_3dTorus_minBytesHops.h b/src/util/treeStrategy_3dTorus_minBytesHops.h
new file mode 100644 (file)
index 0000000..5e9a63a
--- /dev/null
@@ -0,0 +1,150 @@
+#include <algorithm>
+#include "charm++.h"
+
+#ifndef TREE_STRATEGY_3D_TORUS_MIN_BYTES_HOPS
+#define TREE_STRATEGY_3D_TORUS_MIN_BYTES_HOPS
+namespace topo {
+
+/** A concrete tree builder for use on machines with a 3D Torus topology. Naturally, can also work
+ * with 3D meshes (portions of the torus).
+ *
+ * Reduces the total number of bytes that reach the network (ie reduces inter-node traffic) by
+ * building separate sub-trees to span intra-node PEs, and then reduces the total number of hops
+ * across the whole tree. Hence, should be more effictive than the strategy that reduces hops alone,
+ * but possibly at the expense of perfect balance in the spanning tree.
+ *
+ * Specialized and implemented only for data type in input container = vtxType / SpanningTreeVertex.
+ * @note: If its a container of SpanningTreeVertices, the next gen info is stored in the parent
+ * element and a copy of the parent is also returned.
+ */
+template <typename Iterator,typename ValueType = typename std::iterator_traits<Iterator>::value_type>
+class SpanningTreeStrategy_3dTorus_minBytesHops: public SpanningTreeStrategy<Iterator>
+{
+    public:
+        virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2) = 0;
+};
+
+
+
+/** Partial specialization when input is a container of SpanningTreeVertices
+ */
+template <typename Iterator>
+class SpanningTreeStrategy_3dTorus_minBytesHops<Iterator,SpanningTreeVertex>: public SpanningTreeStrategy<Iterator>
+{
+    public:
+        virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2);
+};
+
+
+
+/** Partial specialization when input is a container of vtxTypes.
+ *
+ * Simply builds a container of SpanningTreeVertices from the input data and delegates the actual
+ * tree building to another specialization.
+ */
+template <typename Iterator>
+class SpanningTreeStrategy_3dTorus_minBytesHops<Iterator,vtxType>: public SpanningTreeStrategy<Iterator>
+{
+    public:
+        virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
+        {
+            /// Create a container of SpanningTreeVertices from the input container and fill it with vertex IDs
+            std::vector<SpanningTreeVertex> tree;
+            for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
+                tree.push_back( SpanningTreeVertex(*itr) );
+            /// Instantiate the real builder and let it build the next generation
+            SpanningTreeStrategy_3dTorus_minBytesHops< std::vector<SpanningTreeVertex>::iterator > theRealBuilder;
+            SpanningTreeVertex *result = theRealBuilder.buildNextGen(tree.begin(),tree.end(),maxBranches);
+            /// Copy the reordered vertex indices back into the user's data structure
+            int indx=0;
+            for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
+            {
+                *itr = tree[indx].id;
+                indx++;
+            }
+            /// Return information about the parent vertex (which contains child indices etc)
+            return result;
+        }
+};
+
+} // end namespace topo
+
+
+#include "TopoManager.h"
+
+namespace topo {
+
+template <typename Iterator>
+SpanningTreeVertex* SpanningTreeStrategy_3dTorus_minBytesHops<Iterator,SpanningTreeVertex>::buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
+{
+    // if (maxBranches < 1) throw;
+    CkAssert(maxBranches >= 1);
+    /// Check validity and ranges etc.
+    const int numDescendants = std::distance(firstVtx,beyondLastVtx) - 1;
+    // if (numDescendants < 0) throw;
+    CkAssert(numDescendants >= 0);
+    /// If the parent vertex already has a(n older) list of children, clear it
+    (*firstVtx).childIndex.clear();
+    (*firstVtx).childIndex.reserve(maxBranches);
+
+    /// Get a handle on a TopoManager. @note: Avoid this per-call instantiation cost by using an instance manager? Ideally, TopoManager should be a singleton.
+    TopoManager aTopoMgr;
+    /// The number of vertices in the tree that require network traversal
+    int numLocalDestinations = -1, numRemoteDestinations = 0;
+    Iterator firstDescendant = firstVtx, beyondLastLocal = firstVtx;
+
+    /// Find the machine coordinates of each vertex and also collate the local destination vertices
+    for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
+    {
+        (*itr).X.reserve(3);
+        (*itr).X.assign(3,0);
+        ///@todo: If the machine coordinates are already stored in the vertices, do we want to find them again?
+        aTopoMgr.rankToCoordinates( (*itr).id, (*itr).X[0], (*itr).X[1], (*itr).X[2] );
+        /// If this is a not a local node (separated by the network from the tree root)
+        if (numHops(*firstVtx,*itr) > 0)
+            numRemoteDestinations++;
+        else
+        {
+            numLocalDestinations++;
+            /// Collate it near the top of the container
+            if (itr != beyondLastLocal)
+                std::iter_swap(beyondLastLocal,itr);
+            /// Increment iterator to reflect new range of on-node vertices
+            beyondLastLocal++;
+        }
+    }
+
+    /// The number of branches that can be devoted to local destinations (vertices on the same node)
+    int numLocalBranches = 0;
+    /// If there are any local vertices at all
+    if (numLocalDestinations > 0)
+    {
+        numLocalBranches = (numRemoteDestinations >= maxBranches-1)? 1 : (maxBranches - numRemoteDestinations);
+        /// Distribute the local destination vertices amongst numLocalBranches branches
+        impl::buildNextGen_topoUnaware(firstVtx,beyondLastLocal,numLocalBranches);
+    }
+
+    /// Partition the remote-vertex bounding box into the remaining number of branches
+    impl::TreeBoundingBoxOn3dTorus<Iterator> treePart;
+    treePart.partition(firstVtx,beyondLastLocal,beyondLastVtx,maxBranches-numLocalBranches);
+
+    /// 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++)
+    {
+        Iterator rangeStart = firstVtx;
+        std::advance(rangeStart,(*firstVtx).childIndex[i]);
+        Iterator rangeEnd   = firstVtx;
+        if (i+1 == numChildren)
+            rangeEnd = beyondLastVtx;
+        else
+            std::advance(rangeEnd, (*firstVtx).childIndex[i+1] );
+        Iterator closestItr = pickClosest(*firstVtx,rangeStart,rangeEnd);
+        std::iter_swap(rangeStart,closestItr);
+    }
+    /// Return a copy of the parent in keeping with the generic interface
+    return (new SpanningTreeVertex(*firstVtx) );
+}
+
+} // end namespace topo
+#endif // TREE_STRATEGY_3D_TORUS_MIN_BYTES_HOPS
+
similarity index 69%
rename from src/util/treeStrategy_3dTorus.h
rename to src/util/treeStrategy_3dTorus_minHops.h
index 33b13492e68752a7ae35c1b71198f918ca5df063..9499f432713e544c672e37f2790c1a4a239b6bce 100644 (file)
@@ -1,19 +1,24 @@
 #include <algorithm>
 #include "charm++.h"
 
-#ifndef TREE_STRATEGY_3D_TORUS
-#define TREE_STRATEGY_3D_TORUS
+#ifndef TREE_STRATEGY_3D_TORUS_MIN_HOPS
+#define TREE_STRATEGY_3D_TORUS_MIN_HOPS
 namespace topo {
 
-/** A concrete tree builder for use on machines with a 3D Torus topology. Naturally, can also work with 3D meshes (portions of the torus)
+/** A concrete tree builder for use on machines with a 3D Torus topology. Naturally, can also work with
+ * 3D meshes (portions of the torus).
  *
- * Specialized and implemented only for data type in input container = vtxType / SpanningTreeVertex. 
- * @warning: If its a container of SpanningTreeVertices, the generation info is stored in the parent 
- * element and a pointer to the parent is returned. Do not free this returned pointer as it will 
- * mess up the input container.
+ * Reduces hop-bytes by trying to reduce the total number of hops across the tree. Is implicitly
+ * node-aware as on-node PEs will have a distance of zero and will end up as direct children in the
+ * spanning tree. Does not pay any attention to reducing the number of bytes on the network by
+ * minimizing inter-node traffic. For that, refer to SpanningTreeStrategy_3dTorus_minBytesHops.
+ *
+ * Specialized and implemented only for data type in input container = vtxType / SpanningTreeVertex.
+ * @note: If its a container of SpanningTreeVertices, the next gen info is stored in the parent
+ * element and a copy of the parent is also returned.
  */
 template <typename Iterator,typename ValueType = typename std::iterator_traits<Iterator>::value_type>
-class SpanningTreeStrategy_3dTorus: public SpanningTreeStrategy<Iterator>
+class SpanningTreeStrategy_3dTorus_minHops: public SpanningTreeStrategy<Iterator>
 {
     public:
         virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2) = 0;
@@ -21,50 +26,24 @@ class SpanningTreeStrategy_3dTorus: public SpanningTreeStrategy<Iterator>
 
 
 
-/** Partial specialization for scenario for a container of SpanningTreeVertices 
+/** Partial specialization for scenario for a container of SpanningTreeVertices
  */
 template <typename Iterator>
-class SpanningTreeStrategy_3dTorus<Iterator,SpanningTreeVertex>: public SpanningTreeStrategy<Iterator> 
+class SpanningTreeStrategy_3dTorus_minHops<Iterator,SpanningTreeVertex>: public SpanningTreeStrategy<Iterator>
 {
     public:
         virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2);
-
-    protected:
-        /// Partition the range along the longest dimension into numPartitions parts
-        void partition      (const Iterator parent, const Iterator start, const Iterator end, const int numPartitions);
-        /// Bisect the range along the longest dimension
-        void bisect         (const Iterator parent, const Iterator start, const Iterator end, const int numPartitions);
-        /// Trisect the range along the longest dimension
-        void trisect        (const Iterator parent, const Iterator start, const Iterator end, const int numPartitions);
-        /// Pick the vertex closes to the parent in the given range
-        Iterator pickClosest(const Iterator parent, const Iterator start, const Iterator end);
-        /// Returns the dimension along which the bounding box of a range of vertices has the longest side
-        int findMaxSpreadDimension (const Iterator start, const Iterator end);
-        /// Return the number of hops (on the machine network) between two vertices in the tree
-        int numHops (const Iterator vtx1, const Iterator vtx2);
-        /// Configure a lessThan functor to compare vertices
-        class lessThan
-        {
-            public:
-                lessThan(const int _dim): dim(_dim) {}
-                inline bool operator() (const SpanningTreeVertex &a, const SpanningTreeVertex &b)
-                {
-                    return (a.X[dim] < b.X[dim]);
-                }
-            private:
-                const int dim;
-        };
 };
 
 
 
-/** Partial specialization for scenario when a container of vtxTypes is input. 
+/** Partial specialization for scenario when a container of vtxTypes is input.
  *
- * Simply builds a container of SpanningTreeVertices from the input data and delegates the actual 
+ * Simply builds a container of SpanningTreeVertices from the input data and delegates the actual
  * tree building to another specialization.
  */
 template <typename Iterator>
-class SpanningTreeStrategy_3dTorus<Iterator,vtxType>: public SpanningTreeStrategy<Iterator> 
+class SpanningTreeStrategy_3dTorus_minHops<Iterator,vtxType>: public SpanningTreeStrategy<Iterator>
 {
     public:
         virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
@@ -74,7 +53,7 @@ class SpanningTreeStrategy_3dTorus<Iterator,vtxType>: public SpanningTreeStrateg
             for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
                 tree.push_back( SpanningTreeVertex(*itr) );
             /// Instantiate the real builder and let it build the next generation
-            SpanningTreeStrategy_3dTorus< std::vector<SpanningTreeVertex>::iterator > theRealBuilder;
+            SpanningTreeStrategy_3dTorus_minHops< std::vector<SpanningTreeVertex>::iterator > theRealBuilder;
             SpanningTreeVertex *result = theRealBuilder.buildNextGen(tree.begin(),tree.end(),maxBranches);
             /// Copy the reordered vertex indices back into the user's data structure
             int indx=0;
@@ -90,8 +69,99 @@ class SpanningTreeStrategy_3dTorus<Iterator,vtxType>: public SpanningTreeStrateg
 
 
 
+namespace impl {
+/**
+ * Utility class to partition the bounding box of a spanning (sub)tree on a 3D mesh machine and 
+ * divide that into the necessary number of branches
+ */
+template <typename Iterator>
+class TreeBoundingBoxOn3dTorus
+{
+    public:
+        /// Partition the range along the longest dimension into numPartitions parts
+        void partition(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions);
+
+    protected:
+        /// Bisect the range along the longest dimension
+        void bisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions);
+        /// Trisect the range along the longest dimension
+        void trisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions);
+        /// Returns the dimension along which the bounding box of a range of vertices has the longest side
+        int findMaxSpreadDimension(const Iterator start, const Iterator end);
+        /// Configure a lessThan functor to compare vertices
+        class lessThan
+        {
+            public:
+                lessThan(const int _dim): dim(_dim) {}
+                inline bool operator() (const SpanningTreeVertex &a, const SpanningTreeVertex &b)
+                {
+                    return (a.X[dim] < b.X[dim]);
+                }
+            private:
+                const int dim;
+        };
+};
+} // end namespace impl
+
+} // end namespace topo
+
+
+#include "TopoManager.h"
+
+namespace topo {
+
 template <typename Iterator>
-inline void SpanningTreeStrategy_3dTorus<Iterator,SpanningTreeVertex>::partition(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions)
+SpanningTreeVertex* SpanningTreeStrategy_3dTorus_minHops<Iterator,SpanningTreeVertex>::buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
+{
+    // if (maxBranches < 1) throw;
+    CkAssert(maxBranches >= 1);
+    /// Check validity and ranges etc.
+    const int numDescendants = std::distance(firstVtx,beyondLastVtx) - 1;
+    // if (numDescendants < 0) throw;
+    CkAssert(numDescendants >= 0);
+    /// If the parent vertex already has a(n older) list of children, clear it
+    (*firstVtx).childIndex.clear();
+    (*firstVtx).childIndex.reserve(maxBranches);
+
+    /// Get a handle on a TopoManager. @note: Avoid this per-call instantiation cost by using an instance manager? Ideally, TopoManager should be a singleton.
+    TopoManager aTopoMgr;
+    /// Find the machine coordinates of each vertex
+    for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
+    {
+        (*itr).X.reserve(3);
+        (*itr).X.assign(3,0);
+        aTopoMgr.rankToCoordinates( (*itr).id, (*itr).X[0], (*itr).X[1], (*itr).X[2] );
+    }
+    ///@todo: If the machine coordinates are already stored in the vertices, do we want to find them again?
+
+    /// Partition the vertex bounding box into maxBranches portions
+    Iterator firstDescendant = firstVtx;
+    impl::TreeBoundingBoxOn3dTorus<Iterator> treePart;
+    treePart.partition(firstVtx,++firstDescendant,beyondLastVtx,maxBranches);
+
+    /// Identify the closest member in each subtree and put it at the corresponding childIndex location
+    for (int i=0, numChildren=(*firstVtx).childIndex.size(); i<numChildren; i++)
+    {
+        Iterator rangeStart = firstVtx;
+        std::advance(rangeStart,(*firstVtx).childIndex[i]);
+        Iterator rangeEnd   = firstVtx;
+        if (i+1 == numChildren)
+            rangeEnd = beyondLastVtx;
+        else
+            std::advance(rangeEnd, (*firstVtx).childIndex[i+1] );
+        Iterator closestItr = pickClosest(*firstVtx,rangeStart,rangeEnd);
+        std::iter_swap(rangeStart,closestItr);
+    }
+    /// Return a copy of the parent in keeping with the generic interface
+    return (new SpanningTreeVertex(*firstVtx) );
+}
+
+
+
+namespace impl {
+
+template <typename Iterator>
+inline void TreeBoundingBoxOn3dTorus<Iterator>::partition(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions)
 {
     /// Find the number of vertices in the range
     int numVertices = std::distance(start,end);
@@ -124,11 +194,11 @@ inline void SpanningTreeStrategy_3dTorus<Iterator,SpanningTreeVertex>::partition
 
 
 template <typename Iterator>
-void SpanningTreeStrategy_3dTorus<Iterator,SpanningTreeVertex>::bisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions)
+void TreeBoundingBoxOn3dTorus<Iterator>::bisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions)
 {
     /// Find the number of vertices in the range
     int numVertices = std::distance(start,end);
-    /// Find the dimension along which to bisect the bounding box 
+    /// Find the dimension along which to bisect the bounding box
     int maxSpreadDim = findMaxSpreadDimension(start,end);
     /// Pin the location of the median element
     Iterator median = start;
@@ -144,14 +214,14 @@ void SpanningTreeStrategy_3dTorus<Iterator,SpanningTreeVertex>::bisect(const Ite
 
 
 template <typename Iterator>
-void SpanningTreeStrategy_3dTorus<Iterator,SpanningTreeVertex>::trisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions)
+void TreeBoundingBoxOn3dTorus<Iterator>::trisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions)
 {
     /// If the number of partitions left really can be trisected, then do it
     if (numPartitions % 3 == 0)
     {
         /// Find the number of vertices in the range
         int numVertices = std::distance(start,end);
-        /// Find the dimension along which to bisect the bounding box 
+        /// Find the dimension along which to bisect the bounding box
         int maxSpreadDim = findMaxSpreadDimension(start,end);
         /// Pin the location of the 1/3 and 2/3 elements
         Iterator oneThird = start;
@@ -175,31 +245,10 @@ void SpanningTreeStrategy_3dTorus<Iterator,SpanningTreeVertex>::trisect(const It
 
 
 template <typename Iterator>
-inline Iterator SpanningTreeStrategy_3dTorus<Iterator,SpanningTreeVertex>::pickClosest(const Iterator parent, const Iterator start, const Iterator end)
-{
-    Iterator itr     = start;
-    Iterator closest = itr++;
-    int      minHops = numHops(parent,closest); // aTopoMgr.getHopsBetweenRanks( parentPE, (*closest).id ); 
-    /// Loop thro the range and identify the vertex closest to the parent
-    for (; itr != end; itr++)
-    {
-        int hops = numHops(parent,itr); //aTopoMgr.getHopsBetweenRanks( parentPE, (*itr).id );
-        if (hops < minHops)
-        {
-            closest = itr;
-            minHops = hops;
-        }
-    }
-    return closest;
-}
-
-
-
-template <typename Iterator>
-int SpanningTreeStrategy_3dTorus<Iterator,SpanningTreeVertex>::findMaxSpreadDimension(const Iterator start, const Iterator end)
+int TreeBoundingBoxOn3dTorus<Iterator>::findMaxSpreadDimension(const Iterator start, const Iterator end)
 {
     int nDims = (*start).X.size();
-    std::vector<int> min, max, spread; 
+    std::vector<int> min, max, spread;
     min.reserve(nDims);
     max.reserve(nDims);
     spread.reserve(nDims);
@@ -231,66 +280,8 @@ int SpanningTreeStrategy_3dTorus<Iterator,SpanningTreeVertex>::findMaxSpreadDime
     return maxSpreadDimension;
 }
 
-
-
-template <typename Iterator>
-inline int SpanningTreeStrategy_3dTorus<Iterator,SpanningTreeVertex>::numHops(const Iterator vtx1, const Iterator vtx2)
-{
-    /// @todo: Assert that the dimensions of the coordinate vectors of the two vertices are the same
-    int nHops = 0; 
-    for (int i=0, nDims=(*vtx1).X.size(); i<nDims; i++)
-        nHops += abs( (*vtx1).X[i] - (*vtx2).X[i] );
-    return nHops;
-}
-
-} // end namespace topo
-
-#include "TopoManager.h"
-
-namespace topo {
-
-template <typename Iterator>
-SpanningTreeVertex* SpanningTreeStrategy_3dTorus<Iterator,SpanningTreeVertex>::buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
-{
-    // if (maxBranches < 1) throw;
-    CkAssert(maxBranches >= 1);
-    /// Check validity and ranges etc.
-    const int numDescendants = std::distance(firstVtx,beyondLastVtx) - 1;
-    // if (numDescendants < 0) throw;
-    CkAssert(numDescendants >= 0);
-    /// If the parent vertex already has a(n older) list of children, clear it
-    (*firstVtx).childIndex.clear();
-    (*firstVtx).childIndex.reserve(maxBranches);
-    /// Get a handle on a TopoManager. @note: Avoid this per-call instantiation cost by using an instance manager? Ideally, TopoManager should be a singleton.
-    TopoManager aTopoMgr;
-    /// Find the machine coordinates of each vertex
-    for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
-    {
-        (*itr).X.reserve(3);
-        (*itr).X.assign(3,0);
-        aTopoMgr.rankToCoordinates( (*itr).id, (*itr).X[0], (*itr).X[1], (*itr).X[2] );
-    }
-    ///@todo: If the machine coordinates are already stored in the vertices, do we want to find them again?
-    /// Partition the vertex bounding box into maxBranches portions
-    Iterator firstDescendant = firstVtx;
-    partition(firstVtx,++firstDescendant,beyondLastVtx,maxBranches);
-    /// Identify the closest member in each portion and put it at the corresponding childIndex location
-    for (int i=0, numChildren=(*firstVtx).childIndex.size(); i<numChildren; i++)
-    {
-        Iterator rangeStart = firstVtx;
-        std::advance(rangeStart,(*firstVtx).childIndex[i]);
-        Iterator rangeEnd   = firstVtx;
-        if (i+1 == numChildren) 
-            rangeEnd = beyondLastVtx;
-        else
-            std::advance(rangeEnd, (*firstVtx).childIndex[i+1] );
-        Iterator closestItr = pickClosest(firstVtx,rangeStart,rangeEnd);
-        std::iter_swap(rangeStart,closestItr);
-    }
-    /// Return a copy of the parent in keeping with the generic interface
-    return (new SpanningTreeVertex(*firstVtx) );
-}
+} // end namespace impl
 
 } // end namespace topo
-#endif // TREE_STRATEGY_3D_TORUS
+#endif // TREE_STRATEGY_3D_TORUS_MIN_HOPS
 
diff --git a/src/util/treeStrategy_nodeAware_minBytes.h b/src/util/treeStrategy_nodeAware_minBytes.h
new file mode 100644 (file)
index 0000000..1646754
--- /dev/null
@@ -0,0 +1,119 @@
+#include "charm++.h"
+#include <algorithm>
+
+#ifndef TREE_STRATEGY_NODE_AWARE_MIN_BYTES
+#define TREE_STRATEGY_NODE_AWARE_MIN_BYTES
+namespace topo {
+
+/// Implementation artifacts shouldnt pollute topo::
+namespace impl {
+    template <typename Iterator>
+    SpanningTreeVertex* buildNextGen_nodeAware_minBytes(const vtxType parentPE, const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2);
+}
+
+/** A concrete tree builder that is aware of cpu topology (ie, node aware) while constructing
+ * spanning trees.
+ *
+ * Minimizes the total bytes on the network by constructing separate sub-tree(s) for same-node PEs.
+ * Uses the cpuTopology API defined in charm. Hence, should be node-aware in all environments.
+ *
+ * Note that this node awareness has nothing to do with charm smp builds. Rather, its about
+ * minimizing the number of messages that arrive or leave a single physical machine node for
+ * a multicast / reduction.
+ */
+template <typename Iterator,typename ValueType = typename std::iterator_traits<Iterator>::value_type>
+class SpanningTreeStrategy_nodeAware_minBytes: public SpanningTreeStrategy<Iterator>
+{
+    public:
+        inline virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
+        { return impl::buildNextGen_nodeAware_minBytes(*firstVtx, firstVtx,beyondLastVtx,maxBranches); }
+};
+
+
+
+/** Partial specialization when input is a container of SpanningTreeVertices.
+ *
+ * Exactly the same as the default implementation, except that this stores the results in the parent
+ * vertex (in the container) too
+ */
+template <typename Iterator>
+class SpanningTreeStrategy_nodeAware_minBytes<Iterator,SpanningTreeVertex>: public SpanningTreeStrategy<Iterator>
+{
+    public:
+        inline virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
+        {
+            /// Clear any existing list of children
+            (*firstVtx).childIndex.clear();
+            /// Build the next generation
+            SpanningTreeVertex *parent = impl::buildNextGen_nodeAware_minBytes((*firstVtx).id,firstVtx,beyondLastVtx,maxBranches);
+            /// Copy the results into the parent vertex too
+            *firstVtx = *parent;
+            /// Return the results
+            return parent;
+        }
+};
+
+
+namespace impl {
+    /**
+     * Separates on-node PEs into separate sub-tree(s) and then builds a dumb spanning tree for the off-node PEs
+     */
+    template <typename Iterator>
+    SpanningTreeVertex* buildNextGen_nodeAware_minBytes(const vtxType parentPE, const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
+    {
+        /// ------------- Obtain a list of all PEs on this physical machine node -------------
+        int numOnNode, *pesOnNode;
+        CmiGetPesOnPhysicalNode(CmiPhysicalNodeID(parentPE),&pesOnNode,&numOnNode);
+
+        /// ------------- Identify the PEs that are on the same node as the tree root ------------- 
+        /// The number of local destinations (same node PEs) and the number of branches that will span these destinations
+        int numLocalDestinations = 0, numLocalBranches = 0;
+        /// The object that will hold the final results
+        SpanningTreeVertex *parent = 0;
+        /// 
+        Iterator itr = firstVtx, beyondLastLocal = firstVtx;
+
+        /// Scan the tree members until we identify all possible same node PEs or run out of tree members
+        while ( numLocalDestinations < numOnNode -1 && itr != beyondLastVtx)
+        {
+            /// Try to find the next same-node PE
+            itr = std::find_first_of(++itr,beyondLastVtx,pesOnNode,pesOnNode + numOnNode);
+            /// If such a PE was found...
+            if (itr != beyondLastVtx)
+            {
+                numLocalDestinations++;
+                if (itr != ++beyondLastLocal)
+                    std::iter_swap(itr,beyondLastLocal);
+            }
+        }
+
+        /// ------------- Construct a generation in the tree with local sub-tree(s) if necessary ------------- 
+        /// If there are any local vertices at all
+        if (numLocalDestinations > 0)
+        {
+            /// Determine how many branches can be used to span the local destinations
+            int numRemoteDestinations = std::distance(firstVtx,beyondLastVtx) - numLocalDestinations; ///< @warning: This is O(treeSize) for Iterator != random iterator
+            numLocalBranches = (numRemoteDestinations >= maxBranches-1)? 1 : (maxBranches - numRemoteDestinations);
+
+            /// Distribute the local destination vertices amongst numLocalBranches branches
+            parent = buildNextGen_topoUnaware(firstVtx,++beyondLastLocal,numLocalBranches);
+
+            /// Construct a topo-unaware tree for the rest (off-node PEs) of the vertices
+            SpanningTreeVertex *remoteSubTrees = buildNextGen_topoUnaware(beyondLastLocal,beyondLastVtx,maxBranches-numLocalBranches);
+
+            /// Append the remote sub-tree info to the result object
+            for (int i=0, n=remoteSubTrees->childIndex.size(); i< n; i++)
+                parent->childIndex.push_back(remoteSubTrees->childIndex[i] + numLocalDestinations);
+            delete remoteSubTrees;
+        }
+        else
+            parent = buildNextGen_topoUnaware(firstVtx,beyondLastVtx,maxBranches);
+
+        /// Return the output structure
+        return parent;
+    }
+} // end namespace impl
+
+} // end namespace topo
+#endif // TREE_STRATEGY_NODE_AWARE_MIN_BYTES
+
diff --git a/src/util/treeStrategy_nodeAware_minGens.h b/src/util/treeStrategy_nodeAware_minGens.h
new file mode 100644 (file)
index 0000000..a5a8b61
--- /dev/null
@@ -0,0 +1,118 @@
+#include "charm++.h"
+#include <algorithm>
+
+#ifndef TREE_STRATEGY_NODE_AWARE_MIN_GENS
+#define TREE_STRATEGY_NODE_AWARE_MIN_GENS
+namespace topo {
+
+/// Implementation artifacts shouldnt pollute topo::
+namespace impl {
+    template <typename Iterator>
+    SpanningTreeVertex* buildNextGen_nodeAware_minGens(const vtxType parentPE, const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2);
+}
+
+/** A concrete tree builder that is aware of cpu topology (ie, node aware) while constructing
+ * spanning trees.
+ *
+ * First generates a balanced spanning tree and then promotes any PEs on the same node
+ * (up to a maximum of maxBranches) as direct children. Uses the cpuTopology API defined in
+ * charm. Hence, should be node-aware in all environments.
+ *
+ * The algorithm prioritizes balance over minimizing inter-node traffic. By ensuring that the 
+ * tree is as balanced as it can be, we can reduce the number of generations taken to span all
+ * the tree vertices.
+ */
+template <typename Iterator,typename ValueType = typename std::iterator_traits<Iterator>::value_type>
+class SpanningTreeStrategy_nodeAware_minGens: public SpanningTreeStrategy<Iterator>
+{
+    public:
+        inline virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
+        { return impl::buildNextGen_nodeAware_minGens(*firstVtx, firstVtx,beyondLastVtx,maxBranches); }
+};
+
+
+
+/** Partial specialization for the scenario of a container of SpanningTreeVertices.
+ *
+ * Exactly the same as the default implementation, except that this stores the results in the parent
+ * vertex (in the container) too
+ */
+template <typename Iterator>
+class SpanningTreeStrategy_nodeAware_minGens<Iterator,SpanningTreeVertex>: public SpanningTreeStrategy<Iterator>
+{
+    public:
+        inline virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
+        {
+            /// Clear any existing list of children
+            (*firstVtx).childIndex.clear();
+            /// Build the next generation
+            SpanningTreeVertex *parent = impl::buildNextGen_nodeAware_minGens((*firstVtx).id,firstVtx,beyondLastVtx,maxBranches);
+            /// Copy the results into the parent vertex too
+            *firstVtx = *parent;
+            /// Return the results
+            return parent;
+        }
+};
+
+
+namespace impl {
+    /**
+     * Common implementation for all value_types. The differences (obtaining the parent PE) for
+     * different value_types are handled at the call location itself.
+     *
+     * Simply generates a balanced tree in a topo unaware manner and then promotes any same node PEs as direct children
+     */
+    template <typename Iterator>
+    SpanningTreeVertex* buildNextGen_nodeAware_minGens(const vtxType parentPE, const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
+    {
+        /// Construct the next generation in a blind, aware-of-nothing manner
+        SpanningTreeVertex *parent = impl::buildNextGen_topoUnaware(firstVtx,beyondLastVtx,maxBranches);
+
+        /// Obtain a list of all PEs on this physical machine node
+        int numOnNode, *pesOnNode;
+        CmiGetPesOnPhysicalNode(CmiPhysicalNodeID(parentPE),&pesOnNode,&numOnNode);
+
+        /// Find any (upto maxBranches) tree members that are on the same node and make them the direct children
+        if (numOnNode > 0)
+        {
+            Iterator itr = firstVtx;
+            int brNum = 0, numBranches = parent->childIndex.size();
+            /// Scan the tree members until we identify same node PEs for all direct children or run out of tree members
+            while ( brNum < numBranches && itr != beyondLastVtx)
+            {
+                std::vector<int>::iterator isChild;
+                /// Search the tree members for a PE on this node that is not already a direct child
+                do {
+                    itr = std::find_first_of(++itr,beyondLastVtx,pesOnNode,pesOnNode + numOnNode);
+                    int dist = std::distance(firstVtx,itr);
+                    /// Check if this vertex is already a direct child
+                    isChild = std::find(parent->childIndex.begin(),parent->childIndex.end(),dist);
+                } while (itr != beyondLastVtx && isChild != parent->childIndex.end());
+
+                Iterator childLoc;
+                int *pos;
+                /// Search the child locations for the first slot that does not have a same-node PE
+                do {
+                    childLoc = firstVtx;
+                    std::advance(childLoc,parent->childIndex[brNum]);
+                    /// Check if this child is already on the same node
+                    pos = std::find(pesOnNode,pesOnNode+numOnNode,*childLoc);
+                } while( pos < (numOnNode+pesOnNode) && ++brNum < numBranches );
+
+                /// If a same-node PE is found and a child slot without a same-node PE exists
+                if (itr != beyondLastVtx && brNum < numBranches)
+                {
+                    std::iter_swap(itr,childLoc);
+                    brNum++;
+                }
+            }
+        }
+
+        /// Return the output structure
+        return parent;
+    }
+} // end namespace impl
+
+} // end namespace topo
+#endif // TREE_STRATEGY_NODE_AWARE_MIN_GENS
+
index e223adc600987bc15cf3cdd23067428fd45fcfce..0032d4796f26bac8ab6f0ca9384411d8bfffa2fa 100644 (file)
@@ -4,6 +4,12 @@
 #define TREE_STRATEGY_TOPO_UNAWARE
 namespace topo {
 
+/// Implementation artifacts shouldnt pollute topo::
+namespace impl {
+    template <typename Iterator>
+    SpanningTreeVertex* buildNextGen_topoUnaware(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches);
+}
+
 /** A concrete tree builder that is NOT topology aware. 
  *
  * Randomly selects child vertices and sub-trees etc. It should hence be, resource-wise, quite 
@@ -18,69 +24,65 @@ template <typename Iterator,typename ValueType = typename std::iterator_traits<I
 class SpanningTreeStrategy_topoUnaware: public SpanningTreeStrategy<Iterator>
 {
     public:
-        virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
-        {
-            // if (maxBranches < 1) throw;
-            CkAssert(maxBranches >= 1);
-            /// Create the output data structure
-            SpanningTreeVertex *parent = new SpanningTreeVertex(*firstVtx);
-            /// Check validity and ranges etc.
-            const int numDescendants = std::distance(firstVtx,beyondLastVtx) - 1;
-            // if (numDescendants < 0) throw;
-            CkAssert(numDescendants >= 0);
-            /// Compute the number of vertices in each branch
-            int numInSubTree = numDescendants / maxBranches; 
-            int remainder    = numDescendants % maxBranches; 
-            /// Push the appropriate indices into the container of child indices
-            for (int i=0, indx=1; (i<maxBranches && indx<=numDescendants); i++, indx += numInSubTree)
-            {
-                parent->childIndex.push_back(indx);
-                /// Distribute any remainder vertices as evenly as possible amongst all the branches 
-                if (remainder-- > 0) indx++;
-            }
-            /// Return the output structure
-            return parent;
-        }
+        inline virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
+        { return impl::buildNextGen_topoUnaware(firstVtx,beyondLastVtx,maxBranches); }
 };
 
 
 
-
-/** Partial specialization for the scenario of a container of SpanningTreeVertices. 
+/** Partial specialization when input is a container of SpanningTreeVertices. 
  *
- * Exactly the same as the default implementation, except that this stores the results in the parent vertex (in the container) too 
+ * Simply stores the results in the parent vertex (in the container) too 
  */
 template <typename Iterator>
 class SpanningTreeStrategy_topoUnaware<Iterator,SpanningTreeVertex>: public SpanningTreeStrategy<Iterator> 
 {
     public:
-        virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
+        inline virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
         {
-            // if (maxBranches < 1) throw;
-            CkAssert(maxBranches >= 1);
-            /// Check validity and ranges etc.
-            const int numDescendants = std::distance(firstVtx,beyondLastVtx) - 1;
-            // if (numDescendants < 0) throw;
-            CkAssert(numDescendants >= 0);
             /// Clear any existing list of children
             (*firstVtx).childIndex.clear();
-            /// Compute the number of vertices in each branch
-            int numInSubTree = numDescendants / maxBranches; 
-            int remainder    = numDescendants % maxBranches;
-            /// Push the appropriate indices into the container of child indices
-            for (int i=0, indx=1; (i<maxBranches && indx<=numDescendants); i++, indx += numInSubTree)
-            {
-                (*firstVtx).childIndex.push_back(indx); 
-                /// Distribute any remainder vertices as evenly as possible amongst all the branches 
-                if (remainder-- > 0) indx++;
-            }
-            /// Create the output data structure
-            SpanningTreeVertex *parent = new SpanningTreeVertex(*firstVtx);
-            /// Return the output structure
+            /// Build the next generation
+            SpanningTreeVertex *parent = impl::buildNextGen_topoUnaware(firstVtx,beyondLastVtx,maxBranches);
+            /// Copy the results into the parent vertex too
+            *firstVtx = *parent;
+            /// Return the results
             return parent;
         }
 };
 
+
+namespace impl {
+    template <typename Iterator>
+    SpanningTreeVertex* buildNextGen_topoUnaware(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
+    {
+        // if (maxBranches < 1) throw;
+        CkAssert(maxBranches >= 1);
+        /// Check validity and ranges etc.
+        const int numDescendants = std::distance(firstVtx,beyondLastVtx) - 1;
+        // if (numDescendants < 0) throw;
+        CkAssert(numDescendants >= 0);
+
+        /// Create the output data structure
+        SpanningTreeVertex *parent = new SpanningTreeVertex(*firstVtx);
+
+        /// Compute the number of vertices in each branch
+        int numInSubTree = numDescendants / maxBranches;
+        int remainder    = numDescendants % maxBranches;
+
+        /// Push the appropriate relative distances (from the tree root) into the container of child indices
+        for (int i=0, indx=1; (i<maxBranches && indx<=numDescendants); i++, indx += numInSubTree)
+        {
+            parent->childIndex.push_back(indx);
+            /// Distribute any remainder vertices as evenly as possible amongst all the branches 
+            if (remainder-- > 0) indx++;
+        }
+
+        /// Return the output structure
+        return parent;
+    }
+}
+
 } // end namespace topo
 #endif // TREE_STRATEGY_TOPO_UNAWARE