Changeset 923
- Timestamp:
- 08/26/16 15:07:20 (7 years ago)
- Location:
- XIOS/trunk/extern/remap/src
- Files:
-
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
XIOS/trunk/extern/remap/src/elt.hpp
r688 r923 68 68 k++; 69 69 else 70 cout << "Removed edge " << k << " due to zero length (coinciding endpoints)." << endl;70 /* cout << "Removed edge " << k << " due to zero length (coinciding endpoints)." << endl */ ; 71 71 } 72 72 n = k; -
XIOS/trunk/extern/remap/src/mapper.cpp
r844 r923 468 468 mpiRoute.init(routes); 469 469 int nRecv = mpiRoute.getTotalSourceElement(); 470 470 // cout << mpiRank << " NRECV " << nRecv << "(" << routes.size() << ")"<< endl; 471 471 472 472 int *nbSendNode = new int[mpiSize]; -
XIOS/trunk/extern/remap/src/node.cpp
r694 r923 263 263 if (la == lb - 1) 264 264 { 265 265 node->child.push_back(thIs); 266 266 thIs->parent = node; 267 if (node->child.size() > MAX_NODE_SZ) // with us as additional child `node` is now too large :( 268 return (node->reinserted || node->parent == NULL) ? 269 split(node) : reinsert(node); 267 if (node->child.size() > MAX_NODE_SZ && node->tree->canSplit() ) // with us as additional child `node` is now too large :( 268 return (node->reinserted || node->parent == NULL) ? split(node) : reinsert(node); 270 269 } 271 270 else // la < lb - 1 … … 281 280 node->inflate(chd); 282 281 } 283 return q; 282 283 284 return q; 284 285 } 285 286 … … 296 297 if (thIs->child.size() - out < MIN_NODE_SZ) out = thIs->child.size() - MIN_NODE_SZ; 297 298 299 298 300 /* transfere out children from us to a new node q which will be returned */ 299 301 NodePtr q = new Node; … … 312 314 thIs->reinserted = true; // avoid infinite loop of reinserting the same node, by marking it as reinserted and stop if same node arrives at same place again 313 315 thIs->tree->ri = 1; 316 314 317 return q; 315 318 } … … 318 321 leading to faster look-up times because of less redundancies between nodes. 319 322 TODO cite paper for Slim SS-tree */ 320 void slim2(NodePtr thIs, int level )323 void slim2(NodePtr thIs, int level, int minNodeSize) 321 324 { 322 325 bool out; … … 328 331 if (thIs->level==level) 329 332 { 333 /* 330 334 out = false; 331 335 while (!out) 332 336 { 333 / * remove child which is farthest away from the centre and try to reinsert it into the tree */337 // remove child which is farthest away from the centre and try to reinsert it into the tree 334 338 double distMax = 0; 335 339 int itMax = -1; 340 336 341 for (int i = 0; i < thIs->child.size(); i++) 337 342 { … … 351 356 out = true; 352 357 353 if (thIs->child.size() < MIN_NODE_SZ) out = true; 354 } 355 356 if (thIs->child.size() < MIN_NODE_SZ && thIs->level < thIs->tree->root->level) 358 if (thIs->child.size() < minNodeSize) out = true; 359 } 360 */ 361 if (thIs->tree-> isActiveOkSplit && thIs->tree->levelSize[thIs->tree->assignLevel] <= thIs->tree->keepNodes) 362 { 363 364 return ; 365 } 366 for (int i = 0; i < thIs->child.size(); i++) 367 { 368 std::vector<NodePtr> before; 369 if (transferNode(thIs->tree->root, thIs, thIs->child[i])) 370 { 371 before=thIs->child ; 372 thIs->child.erase(thIs->child.begin()+i); 373 i--; 374 } 375 } 376 377 378 if (thIs->child.size() < minNodeSize && thIs->level < thIs->tree->root->level) 357 379 { 358 380 thIs->tree->decreaseLevelSize(thIs->level); … … 401 423 else thIs->update(); 402 424 } 425 403 426 } 404 427 … … 409 432 if (thIs->level == parent->level) 410 433 { 411 if ( thIs->child.size() < MAX_NODE_SZ&& thIs->child.size() >= MIN_NODE_SZ)434 if ( (thIs->child.size() < MAX_NODE_SZ || thIs->tree->isActiveOkSplit) && thIs->child.size() >= MIN_NODE_SZ) 412 435 { 413 436 insert(node, thIs); … … 450 473 q->child.resize(MAX_NODE_SZ/2 + 1); 451 474 assert(thIs->child.size() == MAX_NODE_SZ+1); 452 thIs->tree->ref = q->child[0] =thIs->closest(thIs->child, FARTHEST); // farthest from centre475 thIs->tree->ref = thIs->closest(thIs->child, FARTHEST); // farthest from centre 453 476 std::sort(thIs->child.begin(), thIs->child.end(), compareDist); 454 for (int i = 1; i < MAX_NODE_SZ+1; i++)477 for (int i = 0; i < MAX_NODE_SZ+1; i++) 455 478 assert(thIs->child[i]->parent == thIs); 456 for (int i = 1; i < MAX_NODE_SZ/2 + 1; i++)479 for (int i = 0; i < MAX_NODE_SZ/2 + 1; i++) 457 480 q->child[i] = thIs->child[i]; 458 481 for (int i = MAX_NODE_SZ/2+1; i<MAX_NODE_SZ+1; i++) … … 464 487 p->update(); 465 488 q->update(); 466 489 467 490 if (squaredist(thIs->centre, q->centre) < squaredist(thIs->centre, p->centre)) 468 491 swap(p, q); … … 487 510 thIs->tree->push_front(q); 488 511 } // push_front? 489 return q; 512 513 return q; 490 514 } 491 515 … … 564 588 } 565 589 590 void Node::checkParent(void) 591 { 592 int childSize = child.size() ; 593 594 for (int i = 0; i < childSize; i++) 595 assert(child[i]->parent == this); 596 597 if (level>0) for (int i = 0; i < childSize; i++) child[i]->checkParent() ; 598 } 599 566 600 void Node::printChildren() 567 601 { … … 682 716 } 683 717 684 } 718 void Node::getNodeLevel(int assignLevel, std::list<NodePtr>& NodeList) 719 { 720 if (level==assignLevel) NodeList.push_back(this) ; 721 else if (level>0) for (int i = 0; i < child.size(); i++) child[i]->getNodeLevel(assignLevel,NodeList) ; 722 return ; 723 } 724 725 bool Node::removeDeletedNodes(int assignLevel) 726 { 727 std::vector<NodePtr> newChild ; 728 729 if (level==assignLevel+1) 730 { 731 bool isUpdate=false ; 732 for (int i = 0; i < child.size(); i++) 733 { 734 if (child[i]->toDelete) 735 { 736 isUpdate=true ; 737 for (int j = 0; j < child[i]->child.size(); j++) tree->push_back(child[i]->child[j]) ; 738 tree->decreaseLevelSize(assignLevel) ; 739 delete child[i] ; 740 } 741 else newChild.push_back(child[i]) ; 742 } 743 744 if (isUpdate) 745 { 746 child=newChild ; 747 update() ; 748 return true ; 749 } 750 else return false ; 751 } 752 else 753 { 754 bool isUpdate=false ; 755 for (int i = 0; i < child.size(); i++) isUpdate |= child[i]->removeDeletedNodes(assignLevel) ; 756 if (isUpdate) update() ; 757 return isUpdate ; 758 } 759 } 760 761 } -
XIOS/trunk/extern/remap/src/node.hpp
r688 r923 128 128 void *data; 129 129 int route; 130 131 Node() : level(0), leafCount(1), centre(ORIGIN), radius(0), reinserted(false), updateCount(0) {} 130 bool toDelete ; 131 132 Node() : level(0), leafCount(1), centre(ORIGIN), radius(0), reinserted(false), updateCount(0), toDelete(false) {} 132 133 Node(const Coord& centre, double radius, void *data) 133 : level(0), leafCount(1), centre(centre), radius(radius), reinserted(false), updateCount(0), data(data) {}134 : level(0), leafCount(1), centre(centre), radius(radius), reinserted(false), updateCount(0), data(data), toDelete(false) {} 134 135 135 136 //#ifdef DEBUG … … 191 192 bool isInside(Node &node); 192 193 int incluCheck(); 194 void checkParent(void) ; 193 195 void printChildren(); 194 196 void assignRoute(std::vector<int>::iterator& rank, int level); … … 198 200 void routingIntersecting(std::vector<Node>* routingList, NodePtr node); 199 201 void routeIntersection(std::vector<int>& routes, NodePtr node); 200 201 void free_descendants(); 202 void getNodeLevel(int level,std::list<NodePtr>& NodeList) ; 203 bool removeDeletedNodes(int assignLevel) ; 204 void free_descendants(); 202 205 }; 203 206 … … 207 210 NodePtr reinsert(NodePtr); 208 211 NodePtr insert(NodePtr, NodePtr); 209 void slim2(NodePtr thIs, int level );212 void slim2(NodePtr thIs, int level, int minNodeSize=MIN_NODE_SZ); 210 213 211 214 } -
XIOS/trunk/extern/remap/src/parallel_tree.cpp
r898 r923 114 114 } 115 115 116 CParallelTree::CParallelTree(MPI_Comm comm) : communicator(comm), cascade(MIN_NODE_SZ*MIN_NODE_SZ, comm) 116 //CParallelTree::CParallelTree(MPI_Comm comm) : communicator(comm), cascade(MIN_NODE_SZ*MIN_NODE_SZ, comm) 117 CParallelTree::CParallelTree(MPI_Comm comm) : communicator(comm), cascade(MAX_NODE_SZ*MAX_NODE_SZ*2, comm) 117 118 { 118 119 treeCascade.reserve(cascade.num_levels); … … 188 189 189 190 /* unpack */ 191 /* 190 192 randomArray.resize(nrecv); 191 193 randomizeArray(randomArray); 192 194 tree.leafs.resize(nrecv); 193 195 index = 0; 194 for (int i = 0; i < nrecv; i++) 196 197 198 for (int i = 0; i < nrecv; i++) 195 199 { 196 200 Coord x = *(Coord *)(&recvBuffer[index]); … … 201 205 202 206 } 207 */ 208 209 randomArray.resize(blocSize); 210 randomizeArray(randomArray); 211 tree.leafs.resize(blocSize); 212 index = 0; 213 214 size_t s=(sizeof(Coord)/sizeof(*recvBuffer)+1)*nrecv ; 215 216 for (int i = 0; i < blocSize; i++) 217 { 218 Coord x = *(Coord *)(&recvBuffer[index%s]); 219 index += sizeof(Coord)/sizeof(*recvBuffer); 220 double radius = recvBuffer[index%s]; 221 index++ ; 222 tree.leafs[randomArray[i]].centre = x; 223 tree.leafs[randomArray[i]].radius = radius; 224 225 } 226 203 227 204 228 delete [] recvBuffer; … … 206 230 CTimer::get("buildSampleTree(local)").resume(); 207 231 tree.build(tree.leafs); 208 cout << "SampleTree build : assign Level " << assignLevel << " nb Nodes : " << tree.levelSize[assignLevel] << endl;232 // cout << "SampleTree build : assign Level " << assignLevel << " nb Nodes : " << tree.levelSize[assignLevel] << endl; 209 233 CTimer::get("buildSampleTree(local)").suspend(); 210 234 CTimer::get("buildSampleTree(local)").print(); … … 214 238 if (!ok) 215 239 { 216 cerr << comm.rank << ": PROBLEM: (node assign)" << tree.levelSize[assignLevel] << " != " << comm.group_size << " (keepNodes)" << endl; 240 cerr << comm.rank << ": PROBLEM: (node assign)" << tree.levelSize[assignLevel] << " != " << comm.group_size << " (keepNodes)" 241 << " node size : "<<node.size()<<" bloc size : "<<blocSize<<" total number of leaf : "<<tree.leafs.size()<<endl ; 217 242 /* 218 243 MPI_Allreduce(&ok, &allok, 1, MPI_INT, MPI_PROD, communicator); … … 224 249 MPI_Abort(MPI_COMM_WORLD,-1) ; 225 250 } 251 /* 226 252 cout<<"*******************************************"<<endl ; 227 253 cout<<"******* Sample Tree output *********"<<endl ; … … 230 256 231 257 cout<<"*******************************************"<<endl ; 232 258 */ 233 259 234 260 assert(tree.root->incluCheck() == 0); -
XIOS/trunk/extern/remap/src/tree.cpp
r694 r923 8 8 #include <time.h> /* time */ 9 9 #include <vector> 10 #include <list> 10 11 #include <set> 11 12 … … 20 21 using namespace std; 21 22 23 /* 22 24 CBasicTree::CBasicTree() : ri(0), levelSize(MAX_LEVEL_SIZE), root(NULL) 23 25 { 24 26 } 27 */ 25 28 26 29 void CBasicTree::routeNodes(vector<int>& route, vector<Node>& nodes, int assignLevel) … … 51 54 void CBasicTree::slim(int nbIts) 52 55 { 53 //if (!isSampleTree)54 56 for (int i = 0; i < nbIts; i++) 55 57 { 56 58 for (int level = root->level - 1; level > 0; level--) 57 59 { 58 cout<<"before Slim2 Level "<<level<< " levelSize[assignLevel] :"<<levelSize[2]<<endl ;59 60 slim2(root, level); 60 cout<<"after Slim2 Level "<<level<< " levelSize[assignLevel] :"<<levelSize[2]<<endl ;61 61 ri = 0; 62 62 emptyPool(); 63 cout<<"after empty pool "<<level<< " levelSize[assignLevel] :"<<levelSize[2]<<endl ;64 65 63 } 66 64 67 65 for (int level = 2; level < root->level; level++) 68 66 { 69 cout<<"before Slim2 Level "<<level<< " levelSize[assignLevel] :"<<levelSize[2]<<endl ;70 67 slim2(root, level); 71 cout<<"after Slim2 Level "<<level<< " levelSize[assignLevel] :"<<levelSize[2]<<endl ;72 68 ri = 0; 73 69 emptyPool(); 74 cout<<"after empty pool "<<level<< " levelSize[assignLevel] :"<<levelSize[2]<<endl ; 75 } 76 } 77 } 70 } 71 } 72 } 73 74 78 75 79 76 void CBasicTree::insertNode(NodePtr node) … … 141 138 { 142 139 root = new Node; 143 if (level > 1) cout << " newRoot level " << level << endl;140 // if (level > 1) cout << " newRoot level " << level << endl; 144 141 root->level = level; 145 142 root->parent = 0; … … 186 183 int i ; 187 184 188 cout<<"CSampleTree::insertNodes : nb node to be inserted : "<<nodes.size()<<endl ;185 // cout<<"CSampleTree::insertNodes : nb node to be inserted : "<<nodes.size()<<endl ; 189 186 for (i = 0; i < nodes.size(); i++) 190 187 { 191 // cout<<"insert new node"<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ;192 188 insertNode(&nodes[i]); 193 // cout<<"new node inserted"<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ;194 189 195 190 if (root->leafCount > stepSlim && levelSize[assignLevel] < keepNodes-2) // time for slim down … … 202 197 if (levelSize[assignLevel] == keepNodes-2 && first1) 203 198 { 204 cout<<"assign Level : "<<assignLevel<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ;205 199 slim(); 206 cout<<"assign Level : "<<assignLevel<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ; 200 first1 = false; 201 } 202 203 if (levelSize[assignLevel] == keepNodes-1 && first2) 204 { 207 205 slim(); 208 cout<<"assign Level : "<<assignLevel<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ;209 slim();210 cout<<"assign Level : "<<assignLevel<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ;211 first1 = false;212 }213 214 if (levelSize[assignLevel] == keepNodes-1 && first2)215 {216 cout<<"assign Level : "<<assignLevel<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ;217 slim();218 cout<<"assign Level : "<<assignLevel<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ;219 206 first2=false ; 220 207 } 221 208 222 if (levelSize[assignLevel] > keepNodes) 223 { 224 cout<<"assign Level : "<<assignLevel<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ; 225 slim(); 226 cout<<"assign Level : "<<assignLevel<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ; 227 } 228 if (levelSize[assignLevel] >= keepNodes) 229 { 230 cout<<"assign Level : "<<assignLevel<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ; 209 if (levelSize[assignLevel] >= keepNodes) slim(); 210 if (levelSize[assignLevel] > keepNodes) slim(); 211 if (levelSize[assignLevel] > keepNodes) slimAssignedLevel() ; 212 213 if (levelSize[assignLevel] >= keepNodes) 214 { 215 if (levelSize[assignLevel] > keepNodes) 216 { 217 // cout<<"assign Level : "<<assignLevel<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ; 218 removeExtraNode() ; 219 } 231 220 break ; 232 221 } 233 222 } 234 cout << "SampleTree build : nb Node inserted : " << i << endl; 235 236 } 237 238 } 223 // cout << "SampleTree build : nb Node inserted : " << i << endl; 224 225 } 226 227 void CSampleTree::slimAssignedLevel() 228 { 229 for(int i=MIN_NODE_SZ;i<=MAX_NODE_SZ;i++) 230 { 231 int levelSizeOrigin=levelSize[assignLevel] ; 232 slim2(root, assignLevel,i); 233 ri = 0; 234 int levelSizeBefore=levelSize[assignLevel] ; 235 isActiveOkSplit=true ; 236 emptyPool(); 237 // cout<<"assign Level : "<<assignLevel<<" MinNodeSize :"<<i<< " levelSize[assignLevel] : "<<levelSizeOrigin<<"->"<<levelSizeBefore<<"->" <<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<" "<<"CanSplit " <<canSplit()<<endl ; 238 if (levelSize[assignLevel]<=keepNodes) break ; 239 } 240 241 } 242 243 void CSampleTree::removeExtraNode(void) 244 { 245 std::list<NodePtr> nodeList ; 246 std::list<NodePtr>::iterator it1,it2, rm ; 247 248 root->getNodeLevel(assignLevel,nodeList) ; 249 double dist,minDist ; 250 251 252 for (int n=0; n<levelSize[assignLevel]-keepNodes ; ++n) 253 { 254 minDist=-1 ; 255 for(it1=nodeList.begin();it1!=nodeList.end();++it1) 256 { 257 dist=0 ; 258 for(it2=nodeList.begin();it2!=nodeList.end();++it2) dist+=arcdist((*it1)->centre,(*it2)->centre) ; 259 if (minDist > dist || minDist < 0.) 260 { 261 minDist=dist ; 262 rm=it1 ; 263 } 264 } 265 (*rm)->toDelete=true ; 266 nodeList.erase(rm) ; 267 268 } 269 root->removeDeletedNodes(assignLevel) ; 270 isActiveOkSplit=true ; 271 emptyPool(); 272 } 273 274 } -
XIOS/trunk/extern/remap/src/tree.hpp
r688 r923 10 10 11 11 using namespace std; 12 extern const int MAX_LEVEL_SIZE ; 12 13 13 14 class CBasicTree … … 21 22 vector<Node> leafs; /** leafs are stored in vector for easy access and rest of the tree nodes as separate allocations, only reachable through tree traversal */ 22 23 23 CBasicTree() ;24 CBasicTree() : ri(0), levelSize(MAX_LEVEL_SIZE), root(NULL), isAssignedLevel(false), okSplit(true), isActiveOkSplit(false) {} 24 25 ~CBasicTree(); 25 26 void build(vector<Node>& nodes); … … 38 39 void output(ostream& flux, int level) ; 39 40 41 int keepNodes; 42 bool isAssignedLevel ; 43 int assignLevel; 44 bool isActiveOkSplit ; 45 bool canSplit(void) 46 { 47 if (isActiveOkSplit && levelSize[assignLevel] >= keepNodes ) okSplit=false ; 48 return okSplit ; 49 } 50 51 40 52 private: 41 53 deque<NodePtr > pool; 42 void emptyPool(); 43 54 55 bool okSplit ; 56 57 protected: 58 void emptyPool(); 59 CBasicTree(int keepNodes_, int assignLevel_) : ri(0), levelSize(MAX_LEVEL_SIZE), root(NULL), keepNodes(keepNodes_), assignLevel(assignLevel_), isAssignedLevel(true), okSplit(true), isActiveOkSplit(false) {} 44 60 }; 45 61 … … 52 68 class CSampleTree : public CBasicTree 53 69 { 54 int keepNodes; 55 int assignLevel; 70 56 71 public: 57 CSampleTree(int keepNodes, int assignLevel) : keepNodes(keepNodes), assignLevel(assignLevel) {} 58 72 CSampleTree(int keepNodes_, int assignLevel_) : CBasicTree(keepNodes_,assignLevel_) {} 73 void slimAssignedLevel() ; 74 void removeExtraNode(void) ; 59 75 void insertNodes(vector<Node>& nodes); 60 76 };
Note: See TracChangeset
for help on using the changeset viewer.