Examples: 3D Jacobi using SDAG and Parameter marshalling, from Bigsim
[charm.git] / src / util / spanningTreeStrategy.h
1 #include <iostream>
2 #include <vector>
3 #include <iterator>
4
5 #include "conv-config.h"
6
7 #ifndef SPANNING_TREE_STRATEGY
8 #define SPANNING_TREE_STRATEGY
9
10 #if ! CMK_HAS_ITERATOR_TRAITS 
11 namespace std {
12
13 template <class Iterator>
14   struct iterator_traits {
15     typedef typename Iterator::iterator_category iterator_category;
16     typedef typename Iterator::value_type        value_type;
17     typedef typename Iterator::difference_type   difference_type;
18     typedef typename Iterator::pointer           pointer;
19     typedef typename Iterator::reference         reference;
20   };
21
22   template <class T>
23   struct iterator_traits<T*> {
24     typedef random_access_iterator_tag iterator_category;
25     typedef T                          value_type;
26     typedef ptrdiff_t                  difference_type;
27     typedef T*                         pointer;
28     typedef T&                         reference;
29   };
30
31 }
32
33 #endif
34
35 #if ! CMK_HAS_STD_DISTANCE 
36 namespace std {
37
38 template <class Iterator>
39 int distance(Iterator first, Iterator last)
40 {
41   int n=0;
42   while (first!=last)
43   {
44        ++first;
45        ++n;
46   }
47
48   return n;
49 }
50 }
51 #endif
52
53 //-------------------------------- Declarations of the main entities in this file --------------------------------
54
55 /// This namespace contains network topology related classes and utilities
56 namespace topo {
57
58 /// Alias for the actual data type of a vertex id (PE/node number)
59 typedef int vtxType;
60
61 /// Container returned by a SpanningTreeStrategy holding information about a vertex in the tree and its children
62 class SpanningTreeVertex;
63
64 /// Base class for all the spanning tree build strategies
65 template <typename Iterator,typename ValueType = typename std::iterator_traits<Iterator>::value_type>
66 class SpanningTreeStrategy;
67
68 /// Tiny factory method that returns an appropriate spanning tree builder based on the machine network topology information (if available)
69 template <typename Iterator>
70 SpanningTreeStrategy<Iterator>* getSpanningTreeStrategy();
71
72 /// Builds one generation of the spanning tree given a container of vertices with the tree root as the first element in the container
73 template <typename Iterator>
74 SpanningTreeVertex* buildSpanningTreeGeneration
75 (const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2, SpanningTreeStrategy<Iterator> *bldr = getSpanningTreeStrategy<Iterator>());
76
77 /// Builds the complete spanning tree given a container of vertices with the tree root as the first element in the container
78 template <typename Iterator>
79 void buildSpanningTree
80 (const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2, SpanningTreeStrategy<Iterator> *bldr = getSpanningTreeStrategy<Iterator>());
81
82 } // end namespace topo
83
84
85
86 //--------------------------------  Class and function definitions --------------------------------
87 namespace topo {
88
89 /** 
90  * Contains indices to direct children. childIndex[i]+1 and childIndex[i+1] are the first and 
91  * beyondLast indices of the sub-tree members of the child at childIndex[i]. 
92  * @note: We're using a (vertex, edge) terminology to talk about spanning trees. Consciously staying 
93  * away from using "node" to avoid ambiguity with machine nodes and PEs. This is inspite of the fact 
94  * that typically a vertex of a spanning tree is a machine node / PE.
95  */
96 class SpanningTreeVertex
97 {
98     public:
99         /// The id (PE) of the vertex 
100         vtxType id;
101         /// The parent of this vertex. Uncomment if needed
102         // vtxType parent;
103         /// The machine coordinates of this vertex
104         std::vector<int> X; 
105         /// Relative distance (in the container) from the position of this vertex to direct children (and their sub-tree members)
106         std::vector<int> childIndex;
107         /// Constructor
108         SpanningTreeVertex(const vtxType _id=-1): id(_id) {}
109
110     /// Stream inserter. Note: not a member function
111     friend std::ostream& operator<< (std::ostream &out, const SpanningTreeVertex &obj)
112     {
113         out<<" "<<obj.id;
114         if (obj.X.size()>0) 
115         {
116             out<<"("<<obj.X[0];
117             for (int i=1,cSize=obj.X.size(); i<cSize; i++)
118                 out<<","<<obj.X[i];
119             out<<") ";
120         }
121         return out;
122     }
123 };
124
125
126
127
128 /** The spanning tree build strategy interface. Partitions and reorders a collection of tree members, and returns information about children and their sub-trees.
129  *
130  * @warning: User code should only specify typename Iterator. ValType is automatically given the 
131  * default value based on Iterator and should not be specified by the user. 
132  *
133  * @todo: If compile-time asserts become available in the charm world, then assert that ValType is 
134  * nothing illegal in the appropriate subclasses. Better still, (if possible) let the subclass remain
135  * abstract and implement buildNextGen only for the appropriate partial specializations of ValType.
136  */
137 template <typename Iterator,typename ValueType>
138 class SpanningTreeStrategy
139 {
140     public:
141         /// Concrete builders should implement this (preferably only for the appropriate specializations)
142         virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2) = 0;
143 };
144
145
146
147
148 /** Facade function to hide all the template muck for the mainstream usecases. 
149  *
150  * Use when you're happy with the default spanning tree strategy. This should hide the very existence
151  * of all this template stuff for the default use-cases. 
152  *
153  * For scenarios, where you want to specify the tree building strategy, you need to supply a strategy
154  * object. In this case, instantiate a strategy object manually (the factory method 
155  * getSpanningTreeStrategy() will give you what it thinks is best) and plug it into this function 
156  * call.
157  *
158  * Its advisable to use this facade even when explicitly specifying a strategy object, as this leaves
159  * room for future additions to the procedure without affecting the user code
160  */
161 template <typename Iterator>
162 inline SpanningTreeVertex* buildSpanningTreeGeneration(const Iterator firstVtx, 
163                                                        const Iterator beyondLastVtx, 
164                                                        const int maxBranches, 
165                                                        SpanningTreeStrategy<Iterator> *bldr 
166                                                       )
167 {
168     return bldr->buildNextGen(firstVtx,beyondLastVtx,maxBranches);
169 }
170
171
172
173
174 /// Nested namespace to prevent the implementation muck from polluting topo::
175 namespace impl {
176
177 /// Tag dispatched function that does the actual work of building the spanning complete tree
178 template <typename Iterator>
179 void buildSpanningTree(SpanningTreeVertex* dispatchTag,
180                        const Iterator firstVtx,
181                        const Iterator beyondLastVtx,
182                        const int maxBranches=2,
183                        SpanningTreeStrategy<Iterator> *bldr = getSpanningTreeStrategy<Iterator>()
184                       )
185 {
186     /// Build a tree only if there are any vertices in the input range
187     if (firstVtx < beyondLastVtx)
188     {
189         /// Build the next generation of the tree rooted at *firstVtx
190         buildSpanningTreeGeneration(firstVtx,beyondLastVtx,maxBranches,bldr);
191         int numChildren = (*firstVtx).childIndex.size();
192         /// For each direct child...
193         for (int i=0; i< numChildren; i++)
194         {
195             /// Identify the range of vertices that are part of this subtree
196             Iterator start = firstVtx, end = firstVtx;
197             std::advance(start, (*firstVtx).childIndex[i] );
198             if (i < numChildren -1)
199                 std::advance(end, (*firstVtx).childIndex[i+1] );
200             else
201                 end = beyondLastVtx;
202             /// Build this subtree
203             buildSpanningTree(dispatchTag,start,end,maxBranches,bldr);
204         }
205     }
206 }
207
208 } // end namespace impl 
209   
210
211
212
213 /**
214  * Facade function to build a complete spanning tree given an input container of SpanningTreeVertex-es
215  * Uses tag-dispatching to ensure at compile-time that the input container holds only SpanningTreeVertex 
216  * and nothing else.
217  */
218 template <typename Iterator>
219 inline void buildSpanningTree(const Iterator firstVtx,
220                               const Iterator beyondLastVtx,
221                               const int maxBranches,
222                               SpanningTreeStrategy<Iterator> *bldr
223                              )
224 {
225     typename std::iterator_traits<Iterator>::value_type *tag = 0;
226     impl::buildSpanningTree(tag,firstVtx,beyondLastVtx,maxBranches,bldr);
227 }
228
229 } // end namespace topo
230
231
232
233 #include "treeStrategy_topoUnaware.h"
234 #include "treeStrategy_3dTorus.h"
235 namespace topo {
236
237 /**
238  * Simply uses machine specific preprocessor macros to return an appropriate strategy.
239  * Expects that these macros will be available in the current compilation unit thanks to charm innards.
240  * Could potentially also use other heuristics to decide on the best strategy, but that might be possible 
241  * only if it has some more input information to use.
242  *
243  * @note: The list of machine macros here should sync with the ones that TopoManager is aware of.
244  */
245 template <typename Iterator>
246 inline SpanningTreeStrategy<Iterator>* getSpanningTreeStrategy() 
247 {
248     #if CMK_BLUEGENEL || CMK_BLUEGENEP
249         return ( new SpanningTreeStrategy_3dTorus<Iterator>() );
250     #elif XT3_TOPOLOGY || XT4_TOPOLOGY || XT5_TOPOLOGY
251         return ( new SpanningTreeStrategy_3dTorus<Iterator>() );
252     #else
253         return ( new SpanningTreeStrategy_topoUnaware<Iterator>() );
254     #endif
255 }
256
257 } // end namespace topo
258
259 #endif // SPANNING_TREE_STRATEGY
260