Merge branch 'charm' of charmgit:charm into charm
[charm.git] / src / util / spanningTreeStrategy.h
1 #include <iostream>
2 #include <vector>
3 #include <iterator>
4
5 #include "conv-config.h"
6 #include "spanningTreeVertex.h"
7
8 #ifndef SPANNING_TREE_STRATEGY
9 #define SPANNING_TREE_STRATEGY
10
11 #if ! CMK_HAS_ITERATOR_TRAITS
12 namespace std {
13
14 template <class Iterator>
15   struct iterator_traits {
16     typedef typename Iterator::iterator_category iterator_category;
17     typedef typename Iterator::value_type        value_type;
18     typedef typename Iterator::difference_type   difference_type;
19     typedef typename Iterator::pointer           pointer;
20     typedef typename Iterator::reference         reference;
21   };
22
23   template <class T>
24   struct iterator_traits<T*> {
25     typedef random_access_iterator_tag iterator_category;
26     typedef T                          value_type;
27     typedef ptrdiff_t                  difference_type;
28     typedef T*                         pointer;
29     typedef T&                         reference;
30   };
31
32 }
33
34 #endif
35
36 #if ! CMK_HAS_STD_DISTANCE
37 namespace std {
38
39 template <class Iterator>
40 int distance(Iterator first, Iterator last)
41 {
42   int n=0;
43   while (first!=last)
44   {
45        ++first;
46        ++n;
47   }
48
49   return n;
50 }
51 }
52 #endif
53
54 /**
55  * @file: This header includes utility routines and several strategies for constructing spanning trees for msg delivery.
56  *
57  * Multicasts and reductions can be efficiently implemented by propogating the message(s) along spanning trees
58  * that are constructed using as much information about the machine as possible. Libraries that implement any
59  * multicast/redn algorithms can use this header to easily generate a spanning tree from a list of target PEs.
60  *
61  * Client code does not have to worry about machine specifics and any tree generation algorithms. Generated spanning
62  * trees will be based on the best available information (node-awareness, network-topo awareness etc.).
63  *
64  * The focus remains on distributed logic that generates efficient (for practical purposes) spanning trees and not
65  * theoretical MSTs (minimum spanning trees) etc. Hence the intented use is to supply a list of PEs as input and
66  * obtain info about the immediate next generation of vertices in the tree and the members of each of their
67  * respective sub-trees. As an afterthought, the API includes calls that will generate a complete spanning tree
68  * from the input too. However, no guarantees are currently made about the efficiency of this use.
69  *
70  * Usage:
71  *       Simple use cases shouldn't have to worry about anything beyond the self-explanatory functions:
72  *       buildSpanningTreeGeneration()
73  *       buildSpanningTree()
74  *
75  *       SpanningTreeVertex is a data structure that facilitates input/output, although input can be any container
76  *       (C arrays, vectors etc.) of PEs
77  *
78  *       Another routine to be aware of is a factory method that is used behind the scenes to obtain what appears
79  *       to be the best strategy for building trees given the current machine/input etc: getSpanningTreeStrategy().
80  *
81  *       Users can override this choice by specifying a strategy when calling one of the build routines. A list of
82  *       strategies should be apparent from the headers included near the bottom of this file.
83  */
84
85
86 //-------------------------------- Declarations of the main entities in this file --------------------------------
87
88 /// This namespace contains network topology related classes and utilities
89 namespace topo {
90
91 /// Alias for the actual data type of a vertex id (PE/node number)
92 typedef int vtxType;
93
94 /// Container returned by a SpanningTreeStrategy holding information about a vertex in the tree and its children
95 class SpanningTreeVertex;
96
97 /// Base class for all the spanning tree build strategies
98 template <typename Iterator,typename ValueType = typename std::iterator_traits<Iterator>::value_type>
99 class SpanningTreeStrategy;
100
101 /// Builds one generation of the spanning tree given a container of vertices with the tree root as the first element in the container
102 template <typename Iterator>
103 SpanningTreeVertex* buildSpanningTreeGeneration
104 (const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2, SpanningTreeStrategy<Iterator> *bldr = 0);
105
106 /// Builds the complete spanning tree given a container of vertices with the tree root as the first element in the container
107 template <typename Iterator>
108 void buildSpanningTree
109 (const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2, SpanningTreeStrategy<Iterator> *bldr = 0);
110
111 /// Tiny factory method that returns a tree construction strategy that it thinks is best (based on inputs, the machine's network topology info etc)
112 template <typename Iterator>
113 SpanningTreeStrategy<Iterator>* getSpanningTreeStrategy
114 (const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches);
115
116 } // end namespace topo
117
118
119
120 //--------------------------------  Class and function definitions --------------------------------
121 namespace topo {
122
123 /** The spanning tree build strategy interface. Partitions and reorders a collection of tree members, and returns information about children and their sub-trees.
124  *
125  * @warning: User code should only specify typename Iterator. ValType is automatically given the
126  * default value based on Iterator and should not be specified by the user.
127  *
128  * @todo: If compile-time asserts become available in the charm world, then assert that ValType is
129  * nothing illegal in the appropriate subclasses. Better still, (if possible) let the subclass remain
130  * abstract and implement buildNextGen only for the appropriate partial specializations of ValType.
131  */
132 template <typename Iterator,typename ValueType>
133 class SpanningTreeStrategy
134 {
135     public:
136         /// Concrete builders should implement this (preferably only for the appropriate specializations)
137         virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2) = 0;
138 };
139
140
141
142
143 /** Facade function to hide all the template muck for the mainstream usecases.
144  *
145  * Use when you're happy with the default spanning tree strategy. This should hide the very existence
146  * of all this template stuff for the default use-cases.
147  *
148  * For scenarios, where you want to specify the tree building strategy, you need to supply a strategy
149  * object. In this case, instantiate a strategy object manually (the factory method
150  * getSpanningTreeStrategy() will give you what it thinks is best) and plug it into this function
151  * call.
152  *
153  * Its advisable to use this facade even when explicitly specifying a strategy object, as this leaves
154  * room for future additions to the procedure without affecting the user code
155  */
156 template <typename Iterator>
157 inline SpanningTreeVertex* buildSpanningTreeGeneration(const Iterator firstVtx,
158                                                        const Iterator beyondLastVtx,
159                                                        const int maxBranches,
160                                                        SpanningTreeStrategy<Iterator> *bldr
161                                                       )
162 {
163     /// If no strategy is passed in, instantiate one
164     if (bldr == 0) bldr = getSpanningTreeStrategy(firstVtx,beyondLastVtx,maxBranches);
165     return bldr->buildNextGen(firstVtx,beyondLastVtx,maxBranches);
166 }
167
168
169
170
171 /// Nested namespace to prevent the implementation muck from polluting topo::
172 namespace impl {
173
174 /// Tag dispatched function that does the actual work of building the spanning complete tree
175 template <typename Iterator>
176 void buildSpanningTree(SpanningTreeVertex* dispatchTag,
177                        const Iterator firstVtx,
178                        const Iterator beyondLastVtx,
179                        const int maxBranches,
180                        SpanningTreeStrategy<Iterator> *bldr
181                       )
182 {
183     /// Build a tree only if there are any vertices in the input range
184     if (firstVtx < beyondLastVtx)
185     {
186         /// Build the next generation of the tree rooted at *firstVtx
187         SpanningTreeVertex *tmp = buildSpanningTreeGeneration(firstVtx,beyondLastVtx,maxBranches,bldr);
188         /// Delete the copy of firstVtx that gets returned from the call
189         delete tmp;
190
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     /// If no strategy is passed in, instantiate one
226     if (bldr == 0) bldr = getSpanningTreeStrategy(firstVtx,beyondLastVtx,maxBranches);
227     /// Create a tag
228     typename std::iterator_traits<Iterator>::value_type *tag = 0;
229     /// Delegate the work
230     impl::buildSpanningTree(tag,firstVtx,beyondLastVtx,maxBranches,bldr);
231 }
232
233 } // end namespace topo
234
235
236
237 /** @note: Concrete strategy implementations depend on the definitions in this file. Hence
238  * its necessary that user code include this file and not just any of the individual strategy
239  * headers that follow.
240  */
241 #include "treeStrategy_topoUnaware.h"
242 #include "treeStrategy_nodeAware_minGens.h"
243 #include "treeStrategy_nodeAware_minBytes.h"
244 #include "treeStrategy_3dTorus_minHops.h"
245 #include "treeStrategy_3dTorus_minBytesHops.h"
246
247 namespace topo {
248
249 /**
250  * Simply uses machine specific preprocessor macros to return an appropriate strategy.
251  * Expects that these macros will be available in the current compilation unit thanks to charm innards.
252  *
253  * Reserves the right to use other heuristics (based on the input data) to select a strategy, if such 
254  * needs arise in the future.
255  *
256  * @note: The list of machine macros here should sync with the ones that TopoManager is aware of.
257  */
258 template <typename Iterator>
259 inline SpanningTreeStrategy<Iterator>* getSpanningTreeStrategy(const Iterator firstVtx,
260                                                                const Iterator beyondLastVtx,
261                                                                const int maxBranches)
262 {
263     #if CMK_BLUEGENEL || CMK_BLUEGENEP
264         return ( new SpanningTreeStrategy_3dTorus_minBytesHops<Iterator>() );
265     #elif XT3_TOPOLOGY || XT4_TOPOLOGY || XT5_TOPOLOGY
266         return ( new SpanningTreeStrategy_3dTorus_minBytesHops<Iterator>() );
267     #else
268         /// Nested, utility class to let us to use the parent PE for different Iterator::value_types
269         class NumOnNode
270         {
271             public:
272                 inline int operator() (const vtxType vtx)             { return CmiNumPesOnPhysicalNode( CmiPhysicalNodeID(vtx) ); }
273                 inline int operator() (const SpanningTreeVertex &vtx) { return CmiNumPesOnPhysicalNode( CmiPhysicalNodeID(vtx.id) ); }
274         } findNumPEsOnNode;
275
276         /// Find the number of PEs on the same node as the parent vertex (max possible on-node destinations)
277         int numPEsOnNode = findNumPEsOnNode(*firstVtx);
278
279         /// If minimizing tree generations may be more beneficial than reducing inter-node traffic
280         if (numPEsOnNode <= 4 && maxBranches < 4)
281             return ( new SpanningTreeStrategy_nodeAware_minGens<Iterator>() );
282         else
283             return ( new SpanningTreeStrategy_nodeAware_minBytes<Iterator>() );
284     #endif
285 }
286
287 } // end namespace topo
288
289 #endif // SPANNING_TREE_STRATEGY
290