Merge branch 'charm' of charmgit:charm into charm
[charm.git] / src / util / treeStrategy_3dTorus_minHops.h
1 #include <algorithm>
2 #include "charm++.h"
3
4 #ifndef TREE_STRATEGY_3D_TORUS_MIN_HOPS
5 #define TREE_STRATEGY_3D_TORUS_MIN_HOPS
6 namespace topo {
7
8 /** A concrete tree builder for use on machines with a 3D Torus topology. Naturally, can also work with
9  * 3D meshes (portions of the torus).
10  *
11  * Reduces hop-bytes by trying to reduce the total number of hops across the tree. Is implicitly
12  * node-aware as on-node PEs will have a distance of zero and will end up as direct children in the
13  * spanning tree. Does not pay any attention to reducing the number of bytes on the network by
14  * minimizing inter-node traffic. For that, refer to SpanningTreeStrategy_3dTorus_minBytesHops.
15  *
16  * Specialized and implemented only for data type in input container = vtxType / SpanningTreeVertex.
17  * @note: If its a container of SpanningTreeVertices, the next gen info is stored in the parent
18  * element and a copy of the parent is also returned.
19  */
20 template <typename Iterator,typename ValueType = typename std::iterator_traits<Iterator>::value_type>
21 class SpanningTreeStrategy_3dTorus_minHops: public SpanningTreeStrategy<Iterator>
22 {
23     public:
24         virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2) = 0;
25 };
26
27
28
29 /** Partial specialization for scenario for a container of SpanningTreeVertices
30  */
31 template <typename Iterator>
32 class SpanningTreeStrategy_3dTorus_minHops<Iterator,SpanningTreeVertex>: public SpanningTreeStrategy<Iterator>
33 {
34     public:
35         virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2);
36 };
37
38
39
40 /** Partial specialization for scenario when a container of vtxTypes is input.
41  *
42  * Simply builds a container of SpanningTreeVertices from the input data and delegates the actual
43  * tree building to another specialization.
44  */
45 template <typename Iterator>
46 class SpanningTreeStrategy_3dTorus_minHops<Iterator,vtxType>: public SpanningTreeStrategy<Iterator>
47 {
48     public:
49         virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
50         {
51             /// Create a container of SpanningTreeVertices from the input container and fill it with vertex IDs
52             std::vector<SpanningTreeVertex> tree;
53             for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
54                 tree.push_back( SpanningTreeVertex(*itr) );
55             /// Instantiate the real builder and let it build the next generation
56             SpanningTreeStrategy_3dTorus_minHops< std::vector<SpanningTreeVertex>::iterator > theRealBuilder;
57             SpanningTreeVertex *result = theRealBuilder.buildNextGen(tree.begin(),tree.end(),maxBranches);
58             /// Copy the reordered vertex indices back into the user's data structure
59             int indx=0;
60             for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
61             {
62                 *itr = tree[indx].id;
63                 indx++;
64             }
65             /// Return information about the parent vertex (which contains child indices etc)
66             return result;
67         }
68 };
69
70
71
72 namespace impl {
73 /**
74  * Utility class to partition the bounding box of a spanning (sub)tree on a 3D mesh machine and 
75  * divide that into the necessary number of branches
76  */
77 template <typename Iterator>
78 class TreeBoundingBoxOn3dTorus
79 {
80     public:
81         /// Partition the range along the longest dimension into numPartitions parts
82         void partition(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions);
83
84     protected:
85         /// Bisect the range along the longest dimension
86         void bisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions);
87         /// Trisect the range along the longest dimension
88         void trisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions);
89         /// Returns the dimension along which the bounding box of a range of vertices has the longest side
90         int findMaxSpreadDimension(const Iterator start, const Iterator end);
91         /// Configure a lessThan functor to compare vertices
92         class lessThan
93         {
94             public:
95                 lessThan(const int _dim): dim(_dim) {}
96                 inline bool operator() (const SpanningTreeVertex &a, const SpanningTreeVertex &b)
97                 {
98                     return (a.X[dim] < b.X[dim]);
99                 }
100             private:
101                 const int dim;
102         };
103 };
104 } // end namespace impl
105
106 } // end namespace topo
107
108
109 #include "TopoManager.h"
110
111 namespace topo {
112
113 template <typename Iterator>
114 SpanningTreeVertex* SpanningTreeStrategy_3dTorus_minHops<Iterator,SpanningTreeVertex>::buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
115 {
116     // if (maxBranches < 1) throw;
117     CkAssert(maxBranches >= 1);
118     /// Check validity and ranges etc.
119     const int numDescendants = std::distance(firstVtx,beyondLastVtx) - 1;
120     // if (numDescendants < 0) throw;
121     CkAssert(numDescendants >= 0);
122     /// If the parent vertex already has a(n older) list of children, clear it
123     (*firstVtx).childIndex.clear();
124     (*firstVtx).childIndex.reserve(maxBranches);
125
126     /// Get a handle on a TopoManager. @note: Avoid this per-call instantiation cost by using an instance manager? Ideally, TopoManager should be a singleton.
127     TopoManager aTopoMgr;
128     /// Find the machine coordinates of each vertex
129     for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
130     {
131         (*itr).X.reserve(3);
132         (*itr).X.assign(3,0);
133         aTopoMgr.rankToCoordinates( (*itr).id, (*itr).X[0], (*itr).X[1], (*itr).X[2] );
134     }
135     ///@todo: If the machine coordinates are already stored in the vertices, do we want to find them again?
136
137     /// Partition the vertex bounding box into maxBranches portions
138     Iterator firstDescendant = firstVtx;
139     impl::TreeBoundingBoxOn3dTorus<Iterator> treePart;
140     treePart.partition(firstVtx,++firstDescendant,beyondLastVtx,maxBranches);
141
142     /// Identify the closest member in each subtree and put it at the corresponding childIndex location
143     for (int i=0, numChildren=(*firstVtx).childIndex.size(); i<numChildren; i++)
144     {
145         Iterator rangeStart = firstVtx;
146         std::advance(rangeStart,(*firstVtx).childIndex[i]);
147         Iterator rangeEnd   = firstVtx;
148         if (i+1 == numChildren)
149             rangeEnd = beyondLastVtx;
150         else
151             std::advance(rangeEnd, (*firstVtx).childIndex[i+1] );
152         Iterator closestItr = pickClosest(*firstVtx,rangeStart,rangeEnd);
153         std::iter_swap(rangeStart,closestItr);
154     }
155     /// Return a copy of the parent in keeping with the generic interface
156     return (new SpanningTreeVertex(*firstVtx) );
157 }
158
159
160
161 namespace impl {
162
163 template <typename Iterator>
164 inline void TreeBoundingBoxOn3dTorus<Iterator>::partition(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions)
165 {
166     /// Find the number of vertices in the range
167     int numVertices = std::distance(start,end);
168     /// If further partitioning is needed and there are vertices left to partition
169     if ( (numPartitions > 1) && (numVertices > 1) )
170     {
171         if (numPartitions % 3 == 0)
172             trisect(parent,start,end,numPartitions);
173         else
174             bisect (parent,start,end,numPartitions);
175     }
176     /// else, just register the remaining vertex(ices) as a sub-tree
177     else if ( (numPartitions >= 1) && (numVertices >= 1) )
178     {
179         int indx = std::distance(parent,start);
180         (*parent).childIndex.push_back(indx);
181     }
182     /// else if there are no vertices left, do nothing
183     else if (numVertices == 0)
184     {
185     }
186     /// else, if there are vertices remaining but no partitions to put them in
187     else if ( (numVertices >= 0) && (numPartitions == 0) )
188         CkAbort("\nThere are vertices left but no remaining partitions to put them in.");
189     /// fall through case. Should never get here unless something is wrong
190     else
191         CkAbort("\nPartitioning fell through to the default case (which it never should). Check the logic in this routine.");
192 }
193
194
195
196 template <typename Iterator>
197 void TreeBoundingBoxOn3dTorus<Iterator>::bisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions)
198 {
199     /// Find the number of vertices in the range
200     int numVertices = std::distance(start,end);
201     /// Find the dimension along which to bisect the bounding box
202     int maxSpreadDim = findMaxSpreadDimension(start,end);
203     /// Pin the location of the median element
204     Iterator median = start;
205     std::advance(median,numVertices/2);
206     /// Bisect the vertex list at the median element
207     std::nth_element( start, median, end, lessThan(maxSpreadDim) );
208     /// Partition the two pieces as necessary
209     int numLeft = numPartitions/2;
210     partition(parent, start, median, numLeft);
211     partition(parent, median, end, numPartitions - numLeft);
212 }
213
214
215
216 template <typename Iterator>
217 void TreeBoundingBoxOn3dTorus<Iterator>::trisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions)
218 {
219     /// If the number of partitions left really can be trisected, then do it
220     if (numPartitions % 3 == 0)
221     {
222         /// Find the number of vertices in the range
223         int numVertices = std::distance(start,end);
224         /// Find the dimension along which to bisect the bounding box
225         int maxSpreadDim = findMaxSpreadDimension(start,end);
226         /// Pin the location of the 1/3 and 2/3 elements
227         Iterator oneThird = start;
228         std::advance(oneThird,numVertices/3);
229         Iterator twoThird = oneThird;
230         std::advance(twoThird,numVertices/3);
231         /// Trisect the vertex list at the median element
232         std::nth_element( start,    oneThird, end, lessThan(maxSpreadDim) );
233         std::nth_element( oneThird, twoThird, end, lessThan(maxSpreadDim) );
234         /// Partition the three pieces further
235         int numLeft = numPartitions/3;
236         partition(parent, start,    oneThird, numLeft);
237         partition(parent, oneThird, twoThird, numLeft);
238         partition(parent, twoThird, end,      numLeft);
239     }
240     /// else simply call partition to let it handle things
241     else
242         partition(parent, start, end, numPartitions);
243 }
244
245
246
247 template <typename Iterator>
248 int TreeBoundingBoxOn3dTorus<Iterator>::findMaxSpreadDimension(const Iterator start, const Iterator end)
249 {
250     int nDims = (*start).X.size();
251     std::vector<int> min, max, spread;
252     min.reserve(nDims);
253     max.reserve(nDims);
254     spread.reserve(nDims);
255     /// Find the min and max coordinates along each dimension of the bounding box
256     min = max = (*start).X;
257     for (Iterator itr = start; itr != end; itr++)
258     {
259         /// @todo: Assert that the dimensions of the coordinate vectors of the this vertex are the same as the parent's
260         for (int i=0; i<nDims; i++)
261         {
262             if ( (*itr).X[i] < min[i] )
263                 min[i] = (*itr).X[i];
264             if ( (*itr).X[i] > max[i] )
265                 max[i] = (*itr).X[i];
266         }
267     }
268     /// Identify the dimension of the maximum spread in coordinates
269     int maxSpread = abs(max[0] - min[0]);
270     int maxSpreadDimension = 0;
271     for (int i=1; i<nDims; i++)
272     {
273         int spread = abs(max[i] - min[i]);
274         if (maxSpread < spread )
275         {
276             maxSpread = spread;
277             maxSpreadDimension = i;
278         }
279     }
280     return maxSpreadDimension;
281 }
282
283 } // end namespace impl
284
285 } // end namespace topo
286 #endif // TREE_STRATEGY_3D_TORUS_MIN_HOPS
287