Spanning trees: Dont count on-node subtree against maxBranches
[charm.git] / src / util / treeStrategy_3dTorus_minBytesHops.h
1 #include <algorithm>
2 #include "charm++.h"
3
4 #ifndef TREE_STRATEGY_3D_TORUS_MIN_BYTES_HOPS
5 #define TREE_STRATEGY_3D_TORUS_MIN_BYTES_HOPS
6 namespace topo {
7
8 /** A concrete tree builder for use on machines with a 3D Torus topology. Naturally, can also work
9  * with 3D meshes (portions of the torus).
10  *
11  * Reduces the total number of bytes that reach the network (ie reduces inter-node traffic) by
12  * building separate sub-trees to span intra-node PEs, and then reduces the total number of hops
13  * across the whole tree. Hence, should be more effictive than the strategy that reduces hops alone,
14  * but possibly at the expense of perfect balance in the spanning tree.
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_minBytesHops: 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 when input is a container of SpanningTreeVertices
30  */
31 template <typename Iterator>
32 class SpanningTreeStrategy_3dTorus_minBytesHops<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 when input is a container of vtxTypes.
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_minBytesHops<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_minBytesHops< 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 } // end namespace topo
71
72
73 #include "TopoManager.h"
74
75 namespace topo {
76
77 template <typename Iterator>
78 SpanningTreeVertex* SpanningTreeStrategy_3dTorus_minBytesHops<Iterator,SpanningTreeVertex>::buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
79 {
80     /// If the parent vertex already has a(n older) list of children, clear it
81     (*firstVtx).childIndex.clear();
82     (*firstVtx).childIndex.reserve(maxBranches);
83
84     /// Get a handle on a TopoManager. @note: Avoid this per-call instantiation cost by using an instance manager? Ideally, TopoManager should be a singleton.
85     TopoManager aTopoMgr;
86     /// The number of vertices in the tree that require network traversal
87     int numLocalDestinations = -1, numRemoteDestinations = 0;
88     Iterator beyondLastLocal = firstVtx;
89
90     /// Find the machine coordinates of each vertex and also collate the local destination vertices
91     for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
92     {
93         (*itr).X.reserve(3);
94         (*itr).X.assign(3,0);
95         ///@todo: If the machine coordinates are already stored in the vertices, do we want to find them again?
96         aTopoMgr.rankToCoordinates( (*itr).id, (*itr).X[0], (*itr).X[1], (*itr).X[2] );
97         /// If this is a not a local node (separated by the network from the tree root)
98         if (numHops(*firstVtx,*itr) > 0)
99             numRemoteDestinations++;
100         else
101         {
102             numLocalDestinations++;
103             /// Collate it near the top of the container
104             if (itr != beyondLastLocal)
105                 std::iter_swap(beyondLastLocal,itr);
106             /// Increment iterator to reflect new range of on-node vertices
107             beyondLastLocal++;
108         }
109     }
110
111     /// The number of branches that can be devoted to local destinations (vertices on the same node)
112     int numLocalBranches = 0;
113     /// If there are any local vertices at all
114     if (numLocalDestinations > 0)
115     {
116         numLocalBranches = (numRemoteDestinations >= maxBranches)? 1 : (maxBranches - numRemoteDestinations);
117         /// Distribute the local destination vertices amongst numLocalBranches branches
118         SpanningTreeVertex *localTree = impl::buildNextGen_topoUnaware(firstVtx,beyondLastLocal,numLocalBranches);
119         /// Append the local tree info to the child info
120         for (int i=0,n=localTree->childIndex.size(); i<n; i++)
121             firstVtx->childIndex.push_back( localTree->childIndex[i] );
122         /// Intermediate results no longer needed
123         delete localTree;
124     }
125
126     /// Partition the remote-vertex bounding box into the remaining number of branches
127     impl::TreeBoundingBoxOn3dTorus<Iterator> treePart;
128     treePart.partition(firstVtx,beyondLastLocal,beyondLastVtx,maxBranches);
129
130     /// Identify the closest member in each remote branch and put it at the corresponding childIndex location
131     for (int i=numLocalBranches, numChildren=(*firstVtx).childIndex.size(); i<numChildren; i++)
132     {
133         Iterator rangeStart = firstVtx;
134         std::advance(rangeStart,(*firstVtx).childIndex[i]);
135         Iterator rangeEnd   = firstVtx;
136         if (i+1 == numChildren)
137             rangeEnd = beyondLastVtx;
138         else
139             std::advance(rangeEnd, (*firstVtx).childIndex[i+1] );
140         Iterator closestItr = pickClosest(*firstVtx,rangeStart,rangeEnd);
141         std::iter_swap(rangeStart,closestItr);
142     }
143     /// Return a copy of the parent in keeping with the generic interface
144     return (new SpanningTreeVertex(*firstVtx) );
145 }
146
147 } // end namespace topo
148 #endif // TREE_STRATEGY_3D_TORUS_MIN_BYTES_HOPS
149