source: XIOS/trunk/extern/remap/src/tree.cpp @ 923

Last change on this file since 923 was 923, checked in by ymipsl, 5 years ago

Improve remapper :

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

YM

File size: 5.6 KB
Line 
1#include <cassert>
2#include "tree.hpp"
3#include "node.hpp"
4#include "elt.hpp"
5#include <iostream>
6#include "mpi.hpp"
7#include <stdlib.h>     /* srand, rand */
8#include <time.h>       /* time */
9#include <vector>
10#include <list>
11#include <set>
12
13#include "timer.hpp"
14#include "mpi_routing.hpp"
15
16namespace sphereRemap {
17
18static const int MAX_LEVEL_SIZE = 100;
19
20double cputime();
21using namespace std;
22
23/*
24CBasicTree::CBasicTree() : ri(0), levelSize(MAX_LEVEL_SIZE), root(NULL)
25{
26}
27*/
28
29void CBasicTree::routeNodes(vector<int>& route, vector<Node>& nodes, int assignLevel)
30{
31        for (int i = 0; i < nodes.size(); i++)
32        {
33                root->routeNode(&nodes[i], assignLevel);
34                route[i] = nodes[i].route;
35        }
36}
37
38void CBasicTree::routeIntersections(vector<vector<int> >& routes, vector<Node>& nodes)
39{
40        for (int i = 0; i < nodes.size(); i++)
41                root->routeIntersection(routes[i], &nodes[i]);
42}
43
44void CBasicTree::build(vector<Node>& nodes)
45{
46        newRoot(1);
47        insertNodes(nodes);
48}
49
50void CBasicTree::output(ostream& flux, int level)
51{
52        root->output(flux,level,0) ;
53}
54void CBasicTree::slim(int nbIts)
55{
56        for (int i = 0; i < nbIts; i++)
57        {
58                for (int level = root->level - 1; level > 0; level--)
59                {
60                        slim2(root, level);
61                        ri = 0;
62                        emptyPool();
63                }
64
65                for (int level = 2; level < root->level; level++)
66                {
67                        slim2(root, level);
68                        ri = 0;
69                        emptyPool();
70                }
71        }
72}
73
74
75
76void CBasicTree::insertNode(NodePtr node)
77{
78        node->tree = this;
79        increaseLevelSize(0);
80        push_back(node);
81
82        NodePtr q;
83        while (pool.size())
84        {
85                q = pool.front();
86                pool.pop_front();
87                q = insert(q, root);
88                if (ri)
89                {
90                        delete q;
91                        ri = 0;
92                }
93        }
94}
95
96void CBasicTree::emptyPool(void)
97{
98        while (pool.size())
99        {
100                NodePtr q = pool.front();
101                pool.pop_front();
102                q = insert(q, root);
103                if (ri)
104                {
105                        delete q;
106                        ri = 0;
107                }
108        }
109}
110
111void CBasicTree::push_back(NodePtr node)
112{
113#ifdef DEBUG
114        node->parent = NULL; // will be overridden later, but for mem leak check better trigger leak as soon as possible
115#endif
116        pool.push_back(node);
117}
118
119void CBasicTree::push_front(NodePtr node)
120{
121#ifdef DEBUG
122        node->parent = NULL; // will be overridden later, but for mem leak check better trigger leak as soon as possible
123#endif
124        pool.push_front(node);
125}
126
127void CBasicTree::increaseLevelSize(int level)
128{
129        levelSize[level]++;
130}
131
132void CBasicTree::decreaseLevelSize(int level)
133{
134        levelSize[level]--;
135}
136
137void CBasicTree::newRoot(int level)  // newroot <- root
138{
139        root = new Node;
140        // if (level > 1) cout << " newRoot level " << level << endl;
141        root->level = level;
142        root->parent = 0;
143        root->leafCount = 0;
144        root->centre = ORIGIN;
145        root->radius = 0.;
146        root->reinserted = false;
147        root->updateCount = 0;
148        root->tree = this;
149        levelSize[level]++;
150}
151
152CBasicTree::~CBasicTree()
153{
154        //FIXME uncomment the next line and figure out why it segfault sometimes
155        //root->free_descendants(); // recursively deletes all nodes in the tree
156        if (root) delete root;
157}
158
159void CTree::insertNodes(vector<Node>& nodes)
160{
161        int stepSlim = MAX_NODE_SZ*MAX_NODE_SZ*2;
162        const double ratio = 1.5;
163        for (int i = 0; i < nodes.size(); i++)
164        {
165                insertNode(&nodes[i]);
166
167                if (root->leafCount > stepSlim) // time for slim down
168                {
169                        slim();
170                        stepSlim = stepSlim * ratio;
171                }
172        }
173}
174
175
176void CSampleTree::insertNodes(vector<Node>& nodes)
177{
178        bool first1 = true;
179        bool first2 = true;
180        int stepSlim = MAX_NODE_SZ * MAX_NODE_SZ * keepNodes / 4;
181//      double ratio = 1 + (0.5 * (1 - (keepNodes - 1) / (1.0 * keepNodes))) ;
182        double ratio = 1.5 ;
183  int i ;
184 
185//  cout<<"CSampleTree::insertNodes  : nb node to be inserted : "<<nodes.size()<<endl ;
186  for (i = 0; i < nodes.size(); i++)
187        {
188    insertNode(&nodes[i]);
189
190                if (root->leafCount > stepSlim && levelSize[assignLevel] < keepNodes-2) // time for slim down
191                {
192                        slim();
193                        stepSlim = stepSlim * ratio;
194                }
195
196   
197    if (levelSize[assignLevel] == keepNodes-2 && first1)
198                {
199      slim();
200                        first1 = false;
201                }
202
203                if (levelSize[assignLevel] == keepNodes-1 && first2)
204                {
205      slim();
206      first2=false ;
207                }
208
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      }
220      break ;
221                }
222        }
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}
Note: See TracBrowser for help on using the repository browser.