Spanning trees: Dont count on-node subtree against maxBranches
[charm.git] / src / util / treeStrategy_nodeAware_minBytes.h
1 #include "charm++.h"
2 #include <algorithm>
3
4 #ifndef TREE_STRATEGY_NODE_AWARE_MIN_BYTES
5 #define TREE_STRATEGY_NODE_AWARE_MIN_BYTES
6 namespace topo {
7
8 /// Implementation artifacts shouldnt pollute topo::
9 namespace impl {
10     template <typename Iterator>
11     SpanningTreeVertex* buildNextGen_nodeAware_minBytes(const vtxType parentPE, const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2);
12 }
13
14 /** A concrete tree builder that is aware of cpu topology (ie, node aware) while constructing
15  * spanning trees.
16  *
17  * Minimizes the total bytes on the network by constructing separate sub-tree(s) for same-node PEs.
18  * Uses the cpuTopology API defined in charm. Hence, should be node-aware in all environments.
19  *
20  * Note that this node awareness has nothing to do with charm smp builds. Rather, its about
21  * minimizing the number of messages that arrive or leave a single physical machine node for
22  * a multicast / reduction.
23  */
24 template <typename Iterator,typename ValueType = typename std::iterator_traits<Iterator>::value_type>
25 class SpanningTreeStrategy_nodeAware_minBytes: public SpanningTreeStrategy<Iterator>
26 {
27     public:
28         inline virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
29         { return impl::buildNextGen_nodeAware_minBytes(*firstVtx, firstVtx,beyondLastVtx,maxBranches); }
30 };
31
32
33
34 /** Partial specialization when input is a container of SpanningTreeVertices.
35  *
36  * Exactly the same as the default implementation, except that this stores the results in the parent
37  * vertex (in the container) too
38  */
39 template <typename Iterator>
40 class SpanningTreeStrategy_nodeAware_minBytes<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_nodeAware_minBytes((*firstVtx).id,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     /**
59      * Separates on-node PEs into separate sub-tree(s) and then builds a dumb spanning tree for the off-node PEs
60      */
61     template <typename Iterator>
62     SpanningTreeVertex* buildNextGen_nodeAware_minBytes(const vtxType parentPE, const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
63     {
64         /// ------------- Obtain a list of all PEs on this physical machine node -------------
65         CkAssert(parentPE < CkNumPes() );
66         int numOnNode, *pesOnNode;
67         CmiGetPesOnPhysicalNode(CmiPhysicalNodeID(parentPE),&pesOnNode,&numOnNode);
68
69         /// ------------- Identify the PEs that are on the same node as the tree root ------------- 
70         /// The number of local destinations (same node PEs) and the number of branches that will span these destinations
71         int numLocalDestinations = 0, numLocalBranches = 0;
72         /// The object that will hold the final results
73         SpanningTreeVertex *parent = 0;
74         /// 
75         Iterator itr = firstVtx, lastLocal = firstVtx;
76
77         /// Scan the tree members until we identify all possible same node PEs or run out of tree members
78         while ( numLocalDestinations < numOnNode -1 && itr != beyondLastVtx)
79         {
80             /// Try to find the next same-node PE
81             #if ! CMK_CC_PGCC
82             itr = std::find_first_of(++itr,beyondLastVtx,pesOnNode,pesOnNode + numOnNode);
83             #else
84             itr = std::find_first_of(++itr,beyondLastVtx,pesOnNode,pesOnNode + numOnNode,vtxEqual());
85             #endif
86             /// If such a PE was found...
87             if (itr != beyondLastVtx)
88             {
89                 numLocalDestinations++;
90                 if (itr != ++lastLocal)
91                     std::iter_swap(itr,lastLocal);
92             }
93         }
94
95         /// ------------- Construct a generation in the tree with local sub-tree(s) if necessary ------------- 
96         /// If there are any local vertices at all
97         if (numLocalDestinations > 0)
98         {
99             /// Determine how many branches can be used to span the local destinations
100             int numRemoteDestinations = std::distance(firstVtx,beyondLastVtx) -1 - numLocalDestinations; ///< @warning: This is O(treeSize) for Iterator != random iterator
101             numLocalBranches = (numRemoteDestinations >= maxBranches)? 1 : (maxBranches - numRemoteDestinations);
102
103             /// Distribute the local destination vertices amongst numLocalBranches branches
104             Iterator beyondLastLocal = lastLocal;
105             parent = buildNextGen_topoUnaware(firstVtx,++beyondLastLocal,numLocalBranches);
106
107             /// Construct a topo-unaware tree for the rest (off-node PEs) of the vertices
108             SpanningTreeVertex *remoteSubTrees = buildNextGen_topoUnaware(lastLocal,beyondLastVtx,maxBranches); ///< Abuse the interface by faking lastLocal as the tree root
109
110             /// Append the remote sub-tree info to the result object
111             for (int i=0, n=remoteSubTrees->childIndex.size(); i< n; i++)
112                 parent->childIndex.push_back(remoteSubTrees->childIndex[i] + numLocalDestinations);
113             delete remoteSubTrees;
114         }
115         else
116             parent = buildNextGen_topoUnaware(firstVtx,beyondLastVtx,maxBranches);
117
118         /// Return the output structure
119         return parent;
120     }
121 } // end namespace impl
122
123 } // end namespace topo
124 #endif // TREE_STRATEGY_NODE_AWARE_MIN_BYTES
125