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