Fixed a bug in creating charm SMP node-aware spanning tree. The bug is that
[charm.git] / src / util / treeStrategy_topoUnaware.h
1 #include "charm++.h"
2
3 #include <map>
4
5 #ifndef TREE_STRATEGY_TOPO_UNAWARE
6 #define TREE_STRATEGY_TOPO_UNAWARE
7 namespace topo {
8
9 /// Implementation artifacts shouldnt pollute topo::
10 namespace impl {
11     template <typename Iterator>
12     SpanningTreeVertex* buildNextGen_topoUnaware(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches);
13 }
14
15 /** A concrete tree builder that is NOT topology aware. 
16  *
17  * Randomly selects child vertices and sub-trees etc. It should hence be, resource-wise, quite 
18  * cheap. Use in situations when topology info is not available or a topo-aware tree build is 
19  * costly (eg. early generations of really large multicast trees). 
20  *
21  * Technically, you are supposed to pass in a container of PEs or SpanningTreeVertices. However, 
22  * since this class simply chops up the indices and makes no assumptions on the data in the container, 
23  * it is possible to abuse this and randomly divvy up any container across numBranches.
24  */
25 template <typename Iterator,typename ValueType = typename std::iterator_traits<Iterator>::value_type>
26 class SpanningTreeStrategy_topoUnaware: public SpanningTreeStrategy<Iterator>
27 {
28     public:
29         inline virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
30         { return impl::buildNextGen_topoUnaware(firstVtx,beyondLastVtx,maxBranches); }
31 };
32
33
34
35 /** Partial specialization when input is a container of SpanningTreeVertices. 
36  *
37  * Simply stores the results in the parent vertex (in the container) too 
38  */
39 template <typename Iterator>
40 class SpanningTreeStrategy_topoUnaware<Iterator,SpanningTreeVertex>: public SpanningTreeStrategy<Iterator> 
41 {
42     public:
43         inline virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
44         {
45             /// Clear any existing list of children
46             (*firstVtx).childIndex.clear();
47             /// Build the next generation
48             SpanningTreeVertex *parent = impl::buildNextGen_topoUnaware(firstVtx,beyondLastVtx,maxBranches);
49             /// Copy the results into the parent vertex too
50             *firstVtx = *parent;
51             /// Return the results
52             return parent;
53         }
54 };
55
56
57 namespace impl {
58     template <typename Iterator>
59     SpanningTreeVertex* buildNextGen_topoUnaware(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
60     {
61         ///Invalid inputs are not exceptions. They are just no-ops
62         if (maxBranches < 1 || firstVtx == beyondLastVtx) return new SpanningTreeVertex();
63
64         /// Return data holds the parent vertex info [and child info, if there are any]
65         SpanningTreeVertex *parent = new SpanningTreeVertex(*firstVtx);
66
67         //key is the node id, and the mapped value is the local index
68         std::map<int, int> nodesMap;
69         #if CMK_SMP     
70                 int localIndex = 1; //relative to the root
71                 for(Iterator vtx=firstVtx+1; vtx!=beyondLastVtx; vtx++, localIndex++){
72                         int nid = CmiNodeOf(topo::getProcID(*vtx));
73                         if(nodesMap.find(nid) == nodesMap.end()){
74                                 //encounter a new node id
75                                 nodesMap[nid] = localIndex;
76                         }
77                 }
78                 int totalNodes = nodesMap.size();
79                 //check whether the building of this tree is for procs on remote SMP nodes.
80                 //NOW: just use the condition whether the "parent" nid is same with (firstVtx+1)
81                 int pnid = CmiNodeOf(topo::getProcID(*firstVtx));
82                 int fnid = CmiNodeOf(topo::getProcID(*(firstVtx+1)));
83                 int forRemoteNodes = (pnid != fnid);
84         #else
85                 //in non-SMP case, just to fake there's no SMP nodes so the work flow of spanning tree 
86                 //creation is correct
87                 int totalNodes = 0;
88                 int forRemoteNodes=0;
89         #endif
90                 
91                 if(totalNodes <= 1 && !forRemoteNodes){
92                         /// Compute the number of vertices in each branch
93                         const int numDescendants = std::distance(firstVtx,beyondLastVtx) - 1;
94                         int numInSubTree = numDescendants / maxBranches;
95                         int remainder    = numDescendants % maxBranches;
96
97                         /// Push the appropriate relative distances (from the tree root) into the container of child indices
98                         for (int i=0, indx=1; (i<maxBranches && indx<=numDescendants); i++, indx += numInSubTree)
99                         {
100                                 parent->childIndex.push_back(indx);
101                                 /// Distribute any remainder vertices as evenly as possible amongst all the branches 
102                                 if (remainder-- > 0) indx++;
103                         }       
104                 }else{
105                         int *nidLocalIdx = new int[totalNodes];
106                         std::map<int, int>::iterator it;                
107                         int lIdx;
108                         for(it=nodesMap.begin(), lIdx=0; it!=nodesMap.end(); it++, lIdx++)
109                                 nidLocalIdx[lIdx] = (*it).second;
110                         
111                         /// Compute the number of vertices in each branch
112                         const int numDescendants = totalNodes;
113                         int numInSubTree = numDescendants / maxBranches;
114                         int remainder    = numDescendants % maxBranches;
115
116                         /// Push the appropriate relative distances (from the tree root) into the container of child indices
117                         for (int i=0, indx=0; (i<maxBranches && indx<numDescendants); i++, indx += numInSubTree)
118                         {
119                                 parent->childIndex.push_back(nidLocalIdx[indx]);
120                                 /// Distribute any remainder vertices as evenly as possible amongst all the branches 
121                                 if (remainder-- > 0) indx++;
122                         }
123                         delete [] nidLocalIdx;
124                 }
125         /// Return the output structure
126         return parent;
127     }   
128 }
129
130 } // end namespace topo
131 #endif // TREE_STRATEGY_TOPO_UNAWARE
132