00001
00004 #ifndef __SPANNING_TREE_H_
00005 #define __SPANNING_TREE_H_
00006
00007 #if defined(__cplusplus)
00008 extern "C" {
00009 #endif
00010
00017 void getNodeTopoTreeEdges(int node, int rootNode, int *nodes, int numnodes, unsigned int bfactor,
00018 int *parent, int *child_count, int **children);
00019
00026 void getPETopoTreeEdges(int pe, int rootPE, int *pes, int numpes, unsigned int bfactor,
00027 int *parent, int *child_count, int **children);
00028
00030 void get_topo_tree_nbs(int root, int *parent, int *child_count, int **children);
00031
00032 #if defined(__cplusplus)
00033 }
00034 #endif
00035
00036
00037
00038 #if defined __cplusplus && !defined CONVERSE_MACHINE_BROADCAST_C_
00039 #include "charm++.h"
00040 #include <vector>
00041
00047 template <typename Iterator>
00048 class SpanningTreeGenerator {
00049 public:
00064 virtual int buildSpanningTree(Iterator start, Iterator end,
00065 unsigned int maxBranches) = 0;
00066
00068 virtual int subtreeSize(int subtree) = 0;
00069
00071 virtual Iterator begin(int subtree) = 0;
00072
00074 virtual Iterator end(int subtree) = 0;
00075
00076 };
00077
00078
00079
00080 class TopoManager;
00081
00088 CmiSpanningTreeInfo *ST_RecursivePartition_getTreeInfo(int root);
00089
00106 template <typename Iterator>
00107 class ST_RecursivePartition : public SpanningTreeGenerator<Iterator> {
00108 public:
00109
00116 ST_RecursivePartition(bool nodeTree=true, bool preSorted=false);
00117
00123 virtual int buildSpanningTree(Iterator start, Iterator end, unsigned int maxBranches);
00124
00125 inline virtual int subtreeSize(int subtree) {
00126 #if CMK_ERROR_CHECKING
00127 return std::distance(children.at(subtree), children.at(subtree+1));
00128 #else
00129 return std::distance(children[subtree], children[subtree+1]);
00130 #endif
00131 }
00132
00133 inline virtual Iterator begin(int subtree) {
00134 #if CMK_ERROR_CHECKING
00135 return children.at(subtree);
00136 #else
00137 return children[subtree];
00138 #endif
00139 }
00140
00141 inline virtual Iterator end(int subtree) {
00142 #if CMK_ERROR_CHECKING
00143 return children.at(subtree+1);
00144 #else
00145 return children[subtree+1];
00146 #endif
00147 }
00148
00149 private:
00150
00151 class PhyNode;
00152 class PhyNodeCompare;
00153
00154 void initPhyNodes(Iterator start, Iterator end,
00155 std::vector<PhyNode> &phynodes) const;
00156 void build(std::vector<PhyNode*> &phyNodes, Iterator start, unsigned int maxBranches);
00157 void partition(std::vector<PhyNode*> &nodes, int start, int end,
00158 int numPartitions, std::vector<int> &children) const;
00159 void chooseSubtreeRoots(std::vector<PhyNode*> &phyNodes,
00160 std::vector<int> &children) const;
00161 void bisect(std::vector<PhyNode*> &nodes, int start, int end,
00162 int numPartitions, std::vector<int> &children) const;
00163 void trisect(std::vector<PhyNode*> &nodes, int start, int end,
00164 int numPartitions, std::vector<int> &children) const;
00165 int maxSpreadDimension(std::vector<PhyNode*> &nodes, int start, int end) const;
00166 #if XE6_TOPOLOGY
00167 void translateCoordinates(std::vector<PhyNode> &nodes) const;
00168 #endif
00169 void withinPhyNodeTree(PhyNode &rootPhyNode, int bfactor, Iterator &pos);
00170
00171 std::vector<Iterator> children;
00172 bool nodeTree;
00173 bool preSorted;
00174 TopoManager *tmgr;
00175 };
00176
00177 #endif
00178 #endif
1.5.5