src/util/spanningTreeVertex.h

   1 #ifndef SPANNING_TREE_VERTEX
   2 #define SPANNING_TREE_VERTEX
   3
   4 #include "TopoManager.h"
   5 #define __DEBUG_SPANNING_TREE_ 0
   6
   7 namespace topo {
   8
   9 /// Alias for the actual data type of a vertex id (PE/node number)
  10 typedef int vtxType;
  11
  12 /**
  13  * Contains indices to direct children. childIndex[i]+1 and childIndex[i+1] are the first and
  14  * beyondLast indices of the sub-tree members of the child at childIndex[i].
  15  * @note: We're using a (vertex, edge) terminology to talk about spanning trees. Consciously staying
  16  * away from using "node" to avoid ambiguity with machine nodes and PEs. This is inspite of the fact
  17  * that typically a vertex of a spanning tree is a machine node / PE.
  18  */
  19 class SpanningTreeVertex
  20 {
  21     public:
  22         /// The id (PE) of the vertex
  23         vtxType id;
  24         /// The parent of this vertex. Uncomment if needed
  25         // vtxType parent;
  26         /// The machine coordinates of this vertex
  27         std::vector<int> X;
  28         /// Relative distance (in the container) from the position of this vertex to direct children (and their sub-tree members)
  29         std::vector<int> childIndex;
  30         /// Constructor
  31         SpanningTreeVertex(const vtxType _id=-1): id(_id) {}
  32
  33         inline bool sameCoordinates(const SpanningTreeVertex &v) const
  34         { return (X == v.X); }
  35
  36     /// Overload == and < to keep users happy. Note: not member functions
  37     ///@{
  38     inline friend bool operator== (const SpanningTreeVertex &obj, const vtxType vtxID)
  39     { return (obj.id == vtxID); }
  40
  41     inline friend bool operator== (const vtxType vtxID, const SpanningTreeVertex &obj)
  42     { return (obj.id == vtxID); }
  43
  44     inline friend bool operator< (const SpanningTreeVertex &obj, const vtxType vtxID)
  45     { return (obj.id < vtxID); }
  46
  47     inline friend bool operator< (const vtxType vtxID, const SpanningTreeVertex &obj)
  48     { return (vtxID < obj.id); }
  49     ///@}
  50
  51     /// Stream inserter. Note: not a member function
  52     friend std::ostream& operator<< (std::ostream &out, const SpanningTreeVertex &obj)
  53     {
  54         out<<" "<<obj.id;
  55         if (obj.X.size()>0)
  56         {
  57             out<<"("<<obj.X[0];
  58             for (int i=1,cSize=obj.X.size(); i<cSize; i++)
  59                 out<<","<<obj.X[i];
  60             out<<") ";
  61         }
  62         return out;
  63     }
  64 };
  65
  66 inline int getProcID(const vtxType vtx) { return vtx; }
  67 inline int getProcID(const SpanningTreeVertex &vtx) { return vtx.id; }
  68
  69 /// Return the number of hops (on the machine network) between two vertices in the tree
  70 inline int numHops(const SpanningTreeVertex &vtx1, const SpanningTreeVertex &vtx2)
  71 {
  72     /// Assert that the dimensions of the coordinate vectors of the two vertices are the same
  73     //CkAssert(vtx1.X.size() == vtx2.X.size());
  74
  75   return TopoManager::getTopoManager()->getHopsBetweenRanks(getProcID(vtx1), getProcID(vtx2));
  76 }
  77
  78 /// Pick the vertex closes to the parent in the given range
  79 template <typename Iterator>
  80 inline Iterator pickClosest(const SpanningTreeVertex &parent, const Iterator start, const Iterator end)
  81 {
  82     /// @todo: Static assert that Iterator::value_type == SpanningTreeVertex
  83     Iterator itr     = start;
  84     Iterator closest = itr++;
  85     int      minHops = numHops(parent,*closest);
  86     /// Loop thro the range and identify the vertex closest to the parent
  87     for (; itr != end; itr++)
  88     {
  89         int hops = numHops(parent,*itr);
  90         if (hops < minHops)
  91         {
  92             closest = itr;
  93             minHops = hops;
  94         }
  95     }
  96     return closest;
  97 }
  98
  99 } // end namespace topo
 100
 101 #endif // SPANNING_TREE_VERTEX
 102