NAMD
AlgNbor.C
Go to the documentation of this file.
1 
8 #include "common.h"
9 #include "InfoStream.h"
10 #include "AlgNbor.h"
11 
12 #define TINYLOAD 0.0005
13 
14 AlgNbor::AlgNbor(int pe, computeInfo *computeArray, patchInfo *patchArray,
15  processorInfo *processorArray, int nComps,
16  int nPatches, int nPes, int nNbs) :
17  Rebalancer(computeArray, patchArray,
18  processorArray, nComps,
19  nPatches, nPes)
20 {
21 strategyName = "AlgNbor";
22 mype = pe;
23 nNbors = nNbs;
24 strategy();
25 }
26 
27 void AlgNbor::strategy()
28 {
29  int i, j;
30  double startTime = CmiWallTimer();
31  // CmiPrintf("strategy started on %d\n", CmiMyPe());
32 
33  // make initial assignment as it is now
34  for (i=0; i<numComputes; i++) {
35  assign((computeInfo *) &(computes[i]),
36  (processorInfo *) &(processors[computes[i].oldProcessor]));
37  }
38 
39  // black-red mode balancing
40  if (processors[mype].available == false) return;
41 
42  // calculate avarage load for neighbors
43  double myload = processors[mype].load;
44  double avgload = 0.0;
45  for (i=0; i<P; i++) {
46  if (processors[i].Id >= 0) {
47 //CmiPrintf("[%d] %d:%f\n", CmiMyPe(), i, processors[i].load);
48  avgload += processors[i].load;
49  }
50  }
51  avgload /= (nNbors+1);
52 
53  if (myload <= avgload) return;
54 
55  CmiPrintf("[%d]:Myload: %f, avrage load: %f. \n", mype, myload, avgload);
56 
57  IRSet *lightProcessors = new IRSet();
58  for (i=0; i<P; i++) {
59  if (processors[i].Id >= 0 && i != mype)
60  if (processors[i].load < processors[mype].load)
61  lightProcessors->insert((InfoRecord *) &(processors[i]));
62  }
63 
64  int done = 0;
65  while (processors[mype].load > avgload)
66  {
67  processorInfo* goodP[3][3];
68  computeInfo* goodCompute[3][3];
69  double goodSize[3][3];
70  processorInfo* bestP;
71 
72  Iterator nextProcessor;
73  if (lightProcessors->hasElements() == 0) break;
74  processorInfo *p = (processorInfo *)lightProcessors->iterator((Iterator *) &nextProcessor);
75  for(i=0; i < 3; i++)
76  for(j=0; j<3; j++) {
77  goodP[i][j] = 0;
78  goodCompute[i][j] = 0;
79  goodSize[i][j] = 0.;
80  }
81  while (p)
82  {
83  Iterator nextCompute;
84  nextCompute.id = 0;
85  if (processors[mype].computeSet.hasElements() == 0) break;
86  computeInfo *c = (computeInfo *)
87  processors[mype].computeSet.iterator((Iterator *)&nextCompute);
88  while (c) {
89 
90  if (c->load + p->load < processors[mype].load - c->load) {
91  int nPatches, nProxies, badForComm;
92  numAvailable(c,p,&nPatches,&nProxies,&badForComm);
93 
94  if ( c->load > goodSize[nPatches][nProxies] ) {
95  goodSize[nPatches][nProxies] = c->load;
96  goodCompute[nPatches][nProxies] = c;
97  goodP[nPatches][nProxies] = p;
98  }
99  }
100 
101  nextCompute.id++;
102  c = (computeInfo *) processors[mype].computeSet.
103  next((Iterator *)&nextCompute);
104  }
105  p = (processorInfo *)
106  lightProcessors->next((Iterator *) &nextProcessor);
107  }
108  if (goodCompute[2][0]) {
109  deAssign(goodCompute[2][0], &processors[mype]);
110  assign(goodCompute[2][0], goodP[2][0]);
111  bestP = goodP[2][0];
112  } else if (goodCompute[1][1]) {
113  deAssign(goodCompute[1][1], &processors[mype]);
114  assign(goodCompute[1][1], goodP[1][1]);
115  bestP = goodP[1][1];
116  } else if (goodCompute[0][2]) {
117  deAssign(goodCompute[0][2], &processors[mype]);
118  assign(goodCompute[0][2], goodP[0][2]);
119  bestP = goodP[0][2];
120  } else if (goodCompute[1][0]) {
121  deAssign(goodCompute[1][0], &processors[mype]);
122  assign(goodCompute[1][0], goodP[1][0]);
123  bestP = goodP[1][0];
124  } else if (goodCompute[0][1]) {
125  deAssign(goodCompute[0][1], &processors[mype]);
126  assign(goodCompute[0][1], goodP[0][1]);
127  bestP = goodP[0][1];
128  } else if (goodCompute[0][0]) {
129  deAssign(goodCompute[0][0], &processors[mype]);
130  assign(goodCompute[0][0], goodP[0][0]);
131  bestP = goodP[0][0];
132  } else {
133  iout << iINFO << "AlgNbor: No receiver found" << "\n" << endi;
134  break;
135  }
136  if (bestP->load > processors[mype].load)
137  lightProcessors->remove(bestP);
138  }
139 
140 /*
141  do {
142  processorInfo *p;
143  computeInfo *c;
144 
145  p = (processorInfo *)procs.deleteMin();
146  if (p == NULL) break;
147  bool objfound = false;
148  do {
149  c = (computeInfo *)objs.deleteMax();
150  if (c == NULL) break;
151 
152  double new_p_load = p->load + c->load;
153  double my_new_load = myload - c->load;
154 //CmiPrintf("new load: new_p_load:%e my_new_load:%e c:%e\n", new_p_load, my_new_load, c->load);
155  if (new_p_load < my_new_load) {
156  objfound = true;
157  }
158  } while (!objfound);
159  if (!objfound) break;
160  deAssign(c, &processors[mype]);
161  assign(c, p);
162  myload -= c->load;
163  procs.insert(p);
164  } while (myload > avgload);
165  */
166 /*
167  // double bestSize0, bestSize1, bestSize2;
168  computeInfo *c;
169  int numAssigned;
170  processorInfo* goodP[3][3]; // goodP[# of real patches][# of proxies]
171  processorInfo* poorP[3][3]; // fallback option
172 
173 
174  // iout << iINFO << "calling makeHeaps. \n";
175  computeAverage();
176  makeHeaps();
177  // iout << iINFO
178  // << "Before assignment\n" << endi;
179  // printLoads();
180 
181  numAssigned = 0;
182 
183  // for (int i=0; i<numPatches; i++)
184  // { std::cout << "(" << patches[i].Id << "," << patches[i].processor ;}
185  overLoad = 1.2;
186  for (int ic=0; ic<numComputes; ic++) {
187  c = (computeInfo *) computesHeap->deleteMax();
188  if ( ! c ) NAMD_bug("AlgNbor: computesHeap empty!");
189  if (c->processor != -1) continue; // skip to the next compute;
190  heapIterator nextProcessor;
191  processorInfo *p = (processorInfo *)
192  pes->iterator((heapIterator *) &nextProcessor);
193  int i,j;
194  for(i=0;i<3;i++)
195  for(j=0;j<3;j++) {
196  goodP[i][j]=0;
197  poorP[i][j]=0;
198  }
199  while (p) {
200  int nPatches = numPatchesAvail(c,p);
201  int nProxies = numProxiesAvail(c,p);
202  if (nPatches < 0 || nPatches > 2)
203  iout << iERROR << "Too many patches: " << nPatches << "\n" << endi;
204  if (nProxies < 0 || nProxies > 2)
205  iout << iERROR << "Too many proxies: " << nProxies << "\n" << endi;
206 
207  if (!goodP[nPatches][nProxies] ||
208  (p->load < goodP[nPatches][nProxies]->load)) {
209  if (c->load + p->load < overLoad*averageLoad) {
210  goodP[nPatches][nProxies] = p;
211  }
212  }
213  if (!poorP[nPatches][nProxies] ||
214  (p->load < poorP[nPatches][nProxies]->load)) {
215  poorP[nPatches][nProxies] = p; // fallback
216  }
217  p = (processorInfo *) pes->next(&nextProcessor);
218  }
219 
220  // if (numAssigned >= 0) { Else is commented out below
221 
222  p = 0;
223  if ((p = goodP[2][0]) // Two home, no proxies
224  || (p = goodP[1][1]) // One home, one proxy
225  || (p = goodP[0][2]) // No home, two proxies
226  || (p = goodP[1][0]) // One home, no proxies
227  || (p = goodP[0][1]) // No home, one proxy
228  || (p = goodP[0][0]) // No home, no proxies
229  || (p = poorP[2][0]) // Two home, no proxies, overload
230  || (p = poorP[1][1]) // One home, one proxy, overload
231  || (p = poorP[0][2]) // No home, two proxies, overload
232  || (p = poorP[1][0]) // One home, no proxies, overload
233  || (p = poorP[0][1]) // No home, one proxy, overload
234  || (p = poorP[0][0]) // No home, no proxies, overload
235  ) {
236  assign(c,p); numAssigned++;
237  } else {
238  NAMD_bug("*** Alg 7 No receiver found 1 ***");
239  break;
240  }
241 
242  }
243 
244 
245  // binary-search refinement procedure
246  multirefine();
247 */
248 
249  CmiPrintf("AlgNbor finish time: %f.\n", CmiWallTimer()-startTime);
250 }
251 
252 
253 
254 
255 
256 
257 
258 
259 
260 
261 
262 
263 
264 
265 
BlockLoad::TempStorage load
int numComputes
Definition: Rebalancer.h:138
std::ostream & iINFO(std::ostream &s)
Definition: InfoStream.C:107
int remove(InfoRecord *)
Definition: Set.C:75
computeInfo * computes
Definition: Rebalancer.h:128
AlgNbor(int pe, computeInfo *computeArray, patchInfo *patchArray, processorInfo *processorArray, int nComps, int nPatches, int nPes, int nNbs)
Definition: AlgNbor.C:14
void assign(computeInfo *c, processorInfo *pRec)
Definition: Rebalancer.C:402
#define iout
Definition: InfoStream.h:87
void insert(InfoRecord *)
Definition: Set.C:49
processorInfo * processors
Definition: Rebalancer.h:130
void numAvailable(computeInfo *c, processorInfo *p, int *nPatches, int *nProxies, int *isBadForCommunication)
Definition: Rebalancer.C:1074
static Units next(Units u)
Definition: ParseOptions.C:48
void deAssign(computeInfo *c, processorInfo *pRec)
Definition: Rebalancer.C:466
InfoRecord * next(Iterator *)
Definition: Set.C:131
Definition: Set.h:25
int hasElements()
Definition: Set.C:149
double load
Definition: elements.h:15
Definition: Set.h:19
infostream & endi(infostream &s)
Definition: InfoStream.C:38
InfoRecord * iterator(Iterator *)
Definition: Set.C:122
const char * strategyName
Definition: Rebalancer.h:127
int id
Definition: Set.h:21