Fixed a minor bug if there're no actual PEs to be built into a spanning tree
[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         //Containing no actual nodes to be built
68         if(firstVtx+1 == beyondLastVtx) return parent;
69
70         //key is the node id, and the mapped value is the local index
71         std::map<int, int> nodesMap;
72         #if CMK_SMP     
73                 int localIndex = 1; //relative to the root
74                 for(Iterator vtx=firstVtx+1; vtx!=beyondLastVtx; vtx++, localIndex++){
75                         int nid = CmiNodeOf(topo::getProcID(*vtx));
76                         if(nodesMap.find(nid) == nodesMap.end()){
77                                 //encounter a new node id
78                                 nodesMap[nid] = localIndex;
79                         }
80                 }
81                 int totalNodes = nodesMap.size();
82                 //check whether the building of this tree is for procs on remote SMP nodes.
83                 //NOW: just use the condition whether the "parent" nid is same with (firstVtx+1)
84                 int pnid = CmiNodeOf(topo::getProcID(*firstVtx));
85                 int fnid = CmiNodeOf(topo::getProcID(*(firstVtx+1)));
86                 int forRemoteNodes = (pnid != fnid);
87         #else
88                 //in non-SMP case, just to fake there's no SMP nodes so the work flow of spanning tree 
89                 //creation is correct
90                 int totalNodes = 0;
91                 int forRemoteNodes=0;
92         #endif
93                 
94                 if(totalNodes <= 1 && !forRemoteNodes){
95                         /// Compute the number of vertices in each branch
96                         const int numDescendants = std::distance(firstVtx,beyondLastVtx) - 1;
97                         int numInSubTree = numDescendants / maxBranches;
98                         int remainder    = numDescendants % maxBranches;
99
100                         /// Push the appropriate relative distances (from the tree root) into the container of child indices
101                         for (int i=0, indx=1; (i<maxBranches && indx<=numDescendants); i++, indx += numInSubTree)
102                         {
103                                 parent->childIndex.push_back(indx);
104                                 /// Distribute any remainder vertices as evenly as possible amongst all the branches 
105                                 if (remainder-- > 0) indx++;
106                         }       
107                 }else{
108                         int *nidLocalIdx = new int[totalNodes];
109                         std::map<int, int>::iterator it;                
110                         int lIdx;
111                         for(it=nodesMap.begin(), lIdx=0; it!=nodesMap.end(); it++, lIdx++)
112                                 nidLocalIdx[lIdx] = (*it).second;
113                         
114                         /// Compute the number of vertices in each branch
115                         const int numDescendants = totalNodes;
116                         int numInSubTree = numDescendants / maxBranches;
117                         int remainder    = numDescendants % maxBranches;
118
119                         /// Push the appropriate relative distances (from the tree root) into the container of child indices
120                         for (int i=0, indx=0; (i<maxBranches && indx<numDescendants); i++, indx += numInSubTree)
121                         {
122                                 parent->childIndex.push_back(nidLocalIdx[indx]);
123                                 /// Distribute any remainder vertices as evenly as possible amongst all the branches 
124                                 if (remainder-- > 0) indx++;
125                         }
126                         delete [] nidLocalIdx;
127                 }
128         /// Return the output structure
129         return parent;
130     }   
131 }
132
133 } // end namespace topo
134 #endif // TREE_STRATEGY_TOPO_UNAWARE
135