Changeset 923


Ignore:
Timestamp:
08/26/16 15:07:20 (5 years ago)
Author:
ymipsl
Message:

Improve remapper :

  • increase stability for smal grid remapping
  • increase stability for large number of processes

YM

Location:
XIOS/trunk/extern/remap/src
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • XIOS/trunk/extern/remap/src/elt.hpp

    r688 r923  
    6868                                k++; 
    6969                        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 */ ; 
    7171                } 
    7272                n = k; 
  • XIOS/trunk/extern/remap/src/mapper.cpp

    r844 r923  
    468468        mpiRoute.init(routes); 
    469469        int nRecv = mpiRoute.getTotalSourceElement(); 
    470         cout << mpiRank << " NRECV " << nRecv << "(" << routes.size() << ")"<< endl; 
     470// cout << mpiRank << " NRECV " << nRecv << "(" << routes.size() << ")"<< endl; 
    471471 
    472472        int *nbSendNode = new int[mpiSize]; 
  • XIOS/trunk/extern/remap/src/node.cpp

    r694 r923  
    263263        if (la == lb - 1) 
    264264        { 
    265                 node->child.push_back(thIs); 
     265    node->child.push_back(thIs); 
    266266                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); 
    270269        } 
    271270        else // la < lb - 1 
     
    281280                node->inflate(chd); 
    282281        } 
    283         return q; 
     282 
     283 
     284  return q; 
    284285} 
    285286 
     
    296297        if (thIs->child.size() - out < MIN_NODE_SZ) out = thIs->child.size() - MIN_NODE_SZ; 
    297298 
     299   
    298300        /* transfere out children from us to a new node q which will be returned */ 
    299301        NodePtr q = new Node; 
     
    312314        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 
    313315        thIs->tree->ri = 1; 
     316 
    314317        return q; 
    315318} 
     
    318321   leading to faster look-up times because of less redundancies between nodes. 
    319322   TODO cite paper for Slim SS-tree */ 
    320 void slim2(NodePtr thIs, int level) 
     323void slim2(NodePtr thIs, int level, int minNodeSize) 
    321324{ 
    322325        bool out; 
     
    328331        if (thIs->level==level) 
    329332        { 
     333/* 
    330334                out = false; 
    331335                while (!out) 
    332336                { 
    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  
    334338                        double distMax = 0; 
    335339                        int itMax = -1; 
     340 
    336341                        for (int i = 0; i < thIs->child.size(); i++) 
    337342                        { 
     
    351356                                out = true; 
    352357 
    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) 
    357379                { 
    358380                        thIs->tree->decreaseLevelSize(thIs->level); 
     
    401423                else thIs->update(); 
    402424        } 
     425 
    403426} 
    404427 
     
    409432        if (thIs->level == parent->level) 
    410433        { 
    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) 
    412435                { 
    413436                        insert(node, thIs); 
     
    450473        q->child.resize(MAX_NODE_SZ/2 + 1); 
    451474        assert(thIs->child.size() == MAX_NODE_SZ+1); 
    452         thIs->tree->ref = q->child[0] = thIs->closest(thIs->child, FARTHEST); // farthest from centre 
     475        thIs->tree->ref = thIs->closest(thIs->child, FARTHEST); // farthest from centre 
    453476        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++) 
    455478                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++) 
    457480                q->child[i] = thIs->child[i]; 
    458481        for (int i = MAX_NODE_SZ/2+1; i<MAX_NODE_SZ+1; i++) 
     
    464487        p->update(); 
    465488        q->update(); 
    466  
     489    
    467490        if (squaredist(thIs->centre, q->centre) < squaredist(thIs->centre, p->centre)) 
    468491                swap(p, q); 
     
    487510                thIs->tree->push_front(q); 
    488511        }  // push_front? 
    489         return q; 
     512 
     513        return q; 
    490514} 
    491515 
     
    564588} 
    565589 
     590void 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   
    566600void Node::printChildren() 
    567601{ 
     
    682716} 
    683717 
    684 } 
     718void 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 
     725bool 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  
    128128        void *data; 
    129129        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) {} 
    132133        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) {} 
    134135 
    135136//#ifdef DEBUG 
     
    191192        bool isInside(Node &node); 
    192193        int incluCheck(); 
     194  void checkParent(void) ; 
    193195        void printChildren(); 
    194196        void assignRoute(std::vector<int>::iterator& rank, int level); 
     
    198200        void routingIntersecting(std::vector<Node>* routingList, NodePtr node); 
    199201        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(); 
    202205}; 
    203206 
     
    207210NodePtr reinsert(NodePtr); 
    208211NodePtr insert(NodePtr, NodePtr); 
    209 void slim2(NodePtr thIs, int level); 
     212void slim2(NodePtr thIs, int level, int minNodeSize=MIN_NODE_SZ); 
    210213 
    211214} 
  • XIOS/trunk/extern/remap/src/parallel_tree.cpp

    r898 r923  
    114114} 
    115115 
    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) 
     117CParallelTree::CParallelTree(MPI_Comm comm) : communicator(comm), cascade(MAX_NODE_SZ*MAX_NODE_SZ*2, comm) 
    117118{ 
    118119        treeCascade.reserve(cascade.num_levels); 
     
    188189 
    189190        /* unpack */ 
     191/* 
    190192        randomArray.resize(nrecv); 
    191193        randomizeArray(randomArray); 
    192194        tree.leafs.resize(nrecv); 
    193195        index = 0; 
    194         for (int i = 0; i < nrecv; i++) 
     196 
     197 
     198  for (int i = 0; i < nrecv; i++) 
    195199        { 
    196200                Coord x = *(Coord *)(&recvBuffer[index]); 
     
    201205 
    202206        } 
     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 
    203227 
    204228        delete [] recvBuffer; 
     
    206230        CTimer::get("buildSampleTree(local)").resume(); 
    207231        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; 
    209233        CTimer::get("buildSampleTree(local)").suspend(); 
    210234        CTimer::get("buildSampleTree(local)").print(); 
     
    214238        if (!ok) 
    215239  { 
    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 ; 
    217242/* 
    218243        MPI_Allreduce(&ok, &allok, 1, MPI_INT, MPI_PROD, communicator); 
     
    224249    MPI_Abort(MPI_COMM_WORLD,-1) ; 
    225250  } 
     251/* 
    226252  cout<<"*******************************************"<<endl ; 
    227253  cout<<"******* Sample Tree output        *********"<<endl ; 
     
    230256 
    231257  cout<<"*******************************************"<<endl ; 
    232  
     258*/ 
    233259 
    234260  assert(tree.root->incluCheck() == 0); 
  • XIOS/trunk/extern/remap/src/tree.cpp

    r694 r923  
    88#include <time.h>       /* time */ 
    99#include <vector> 
     10#include <list> 
    1011#include <set> 
    1112 
     
    2021using namespace std; 
    2122 
     23/* 
    2224CBasicTree::CBasicTree() : ri(0), levelSize(MAX_LEVEL_SIZE), root(NULL) 
    2325{ 
    2426} 
     27*/ 
    2528 
    2629void CBasicTree::routeNodes(vector<int>& route, vector<Node>& nodes, int assignLevel) 
     
    5154void CBasicTree::slim(int nbIts) 
    5255{ 
    53         //if (!isSampleTree) 
    5456        for (int i = 0; i < nbIts; i++) 
    5557        { 
    5658                for (int level = root->level - 1; level > 0; level--) 
    5759                { 
    58       cout<<"before Slim2 Level "<<level<< "     levelSize[assignLevel] :"<<levelSize[2]<<endl ; 
    5960                        slim2(root, level); 
    60       cout<<"after Slim2 Level "<<level<< "     levelSize[assignLevel] :"<<levelSize[2]<<endl ; 
    6161                        ri = 0; 
    6262                        emptyPool(); 
    63       cout<<"after empty pool "<<level<< "     levelSize[assignLevel] :"<<levelSize[2]<<endl ; 
    64  
    6563                } 
    6664 
    6765                for (int level = 2; level < root->level; level++) 
    6866                { 
    69       cout<<"before Slim2 Level "<<level<< "     levelSize[assignLevel] :"<<levelSize[2]<<endl ; 
    7067                        slim2(root, level); 
    71       cout<<"after Slim2 Level "<<level<< "     levelSize[assignLevel] :"<<levelSize[2]<<endl ; 
    7268                        ri = 0; 
    7369                        emptyPool(); 
    74       cout<<"after empty pool "<<level<< "     levelSize[assignLevel] :"<<levelSize[2]<<endl ; 
    75                 } 
    76         } 
    77 } 
     70                } 
     71        } 
     72} 
     73 
     74 
    7875 
    7976void CBasicTree::insertNode(NodePtr node) 
     
    141138{ 
    142139        root = new Node; 
    143         if (level > 1) cout << " newRoot level " << level << endl; 
     140        // if (level > 1) cout << " newRoot level " << level << endl; 
    144141        root->level = level; 
    145142        root->parent = 0; 
     
    186183  int i ; 
    187184   
    188   cout<<"CSampleTree::insertNodes  : nb node to be inserted : "<<nodes.size()<<endl ; 
     185//  cout<<"CSampleTree::insertNodes  : nb node to be inserted : "<<nodes.size()<<endl ; 
    189186  for (i = 0; i < nodes.size(); i++) 
    190187        { 
    191 //    cout<<"insert new node"<< "     levelSize[assignLevel] :"<<levelSize[assignLevel]<<"   keepNodes : "<<keepNodes<<endl ; 
    192188    insertNode(&nodes[i]); 
    193 //    cout<<"new node inserted"<< "     levelSize[assignLevel] :"<<levelSize[assignLevel]<<"   keepNodes : "<<keepNodes<<endl ; 
    194189 
    195190                if (root->leafCount > stepSlim && levelSize[assignLevel] < keepNodes-2) // time for slim down 
     
    202197    if (levelSize[assignLevel] == keepNodes-2 && first1) 
    203198                { 
    204       cout<<"assign Level : "<<assignLevel<< "     levelSize[assignLevel] :"<<levelSize[assignLevel]<<"   keepNodes : "<<keepNodes<<endl ; 
    205199      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                { 
    207205      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 ; 
    219206      first2=false ; 
    220207                } 
    221208 
    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      } 
    231220      break ; 
    232221                } 
    233222        } 
    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 
     227void 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 
     243void 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  
    1010 
    1111using namespace std; 
     12extern const int MAX_LEVEL_SIZE ; 
    1213 
    1314class CBasicTree 
     
    2122        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 */ 
    2223 
    23         CBasicTree();  
     24        CBasicTree() : ri(0), levelSize(MAX_LEVEL_SIZE), root(NULL), isAssignedLevel(false), okSplit(true), isActiveOkSplit(false) {}  
    2425        ~CBasicTree();  
    2526        void build(vector<Node>& nodes); 
     
    3839  void output(ostream& flux, int level) ; 
    3940 
     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   
    4052private: 
    4153        deque<NodePtr > pool; 
    42         void emptyPool(); 
    43  
     54         
     55  bool okSplit ; 
     56  
     57protected: 
     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) {}  
    4460}; 
    4561 
     
    5268class CSampleTree : public CBasicTree 
    5369{ 
    54         int keepNodes; 
    55         int assignLevel; 
     70 
    5671public: 
    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) ; 
    5975        void insertNodes(vector<Node>& nodes); 
    6076}; 
Note: See TracChangeset for help on using the changeset viewer.