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