AlgNbor.C

Go to the documentation of this file.
00001 
00007 #include "common.h"
00008 #include "InfoStream.h"
00009 #include "AlgNbor.h"
00010 
00011 #define TINYLOAD 0.0005
00012 
00013 AlgNbor::AlgNbor(int pe, computeInfo *computeArray, patchInfo *patchArray, 
00014            processorInfo *processorArray, int nComps, 
00015            int nPatches, int nPes, int nNbs) :
00016   Rebalancer(computeArray, patchArray, 
00017              processorArray, nComps, 
00018              nPatches, nPes)
00019 {
00020 strategyName = "AlgNbor";
00021 mype = pe;
00022 nNbors = nNbs;
00023 strategy();
00024 }
00025 
00026 void AlgNbor::strategy()
00027 {
00028   int i, j;
00029   double startTime = CmiWallTimer();
00030   // CmiPrintf("strategy started on %d\n", CmiMyPe());
00031 
00032   // make initial assignment as it is now
00033   for (i=0; i<numComputes; i++) {
00034         assign((computeInfo *) &(computes[i]),
00035                  (processorInfo *) &(processors[computes[i].oldProcessor]));
00036   }
00037 
00038   // black-red mode balancing
00039   if (processors[mype].available == false) return;
00040 
00041   // calculate avarage load for neighbors
00042   double myload = processors[mype].load;
00043   double avgload = 0.0;
00044   for (i=0; i<P; i++) {
00045     if (processors[i].Id >= 0) {
00046 //CmiPrintf("[%d] %d:%f\n", CmiMyPe(), i, processors[i].load);
00047       avgload += processors[i].load;
00048     }
00049   }
00050   avgload /= (nNbors+1);
00051 
00052   if (myload <= avgload) return;
00053 
00054   CmiPrintf("[%d]:Myload: %f, avrage load: %f. \n", mype, myload, avgload);
00055 
00056   IRSet *lightProcessors = new IRSet();
00057   for (i=0; i<P; i++) {
00058     if (processors[i].Id >= 0 &&  i != mype)
00059       if (processors[i].load < processors[mype].load)
00060         lightProcessors->insert((InfoRecord *) &(processors[i]));
00061   }
00062 
00063   int done = 0;
00064   while (processors[mype].load > avgload)
00065   {
00066     processorInfo* goodP[3][3];
00067     computeInfo* goodCompute[3][3];
00068     double goodSize[3][3];
00069     processorInfo* bestP;
00070 
00071     Iterator nextProcessor;
00072     if (lightProcessors->hasElements() == 0) break;
00073     processorInfo *p = (processorInfo *)lightProcessors->iterator((Iterator *) &nextProcessor);
00074     for(i=0; i < 3; i++)
00075         for(j=0; j<3; j++) {
00076           goodP[i][j] = 0;
00077           goodCompute[i][j] = 0;
00078           goodSize[i][j] = 0.;
00079         }
00080     while (p) 
00081     {
00082       Iterator nextCompute;
00083       nextCompute.id = 0;
00084       if (processors[mype].computeSet.hasElements() == 0) break;
00085       computeInfo *c = (computeInfo *)
00086                 processors[mype].computeSet.iterator((Iterator *)&nextCompute);
00087       while (c) {
00088       
00089         if (c->load + p->load < processors[mype].load - c->load) {
00090           int nPatches, nProxies, badForComm;
00091           numAvailable(c,p,&nPatches,&nProxies,&badForComm);
00092 
00093           if ( c->load > goodSize[nPatches][nProxies] ) {
00094             goodSize[nPatches][nProxies] = c->load;
00095             goodCompute[nPatches][nProxies] = c;
00096             goodP[nPatches][nProxies] = p;
00097           }
00098         }
00099 
00100         nextCompute.id++;
00101         c = (computeInfo *) processors[mype].computeSet.
00102           next((Iterator *)&nextCompute);
00103       }
00104       p = (processorInfo *)
00105          lightProcessors->next((Iterator *) &nextProcessor);
00106     }
00107     if (goodCompute[2][0]) {
00108          deAssign(goodCompute[2][0], &processors[mype]);
00109          assign(goodCompute[2][0], goodP[2][0]);
00110          bestP = goodP[2][0];
00111     } else if (goodCompute[1][1]) {
00112          deAssign(goodCompute[1][1], &processors[mype]);
00113          assign(goodCompute[1][1], goodP[1][1]);
00114          bestP = goodP[1][1];
00115     } else if (goodCompute[0][2]) {
00116          deAssign(goodCompute[0][2], &processors[mype]);
00117          assign(goodCompute[0][2], goodP[0][2]);
00118          bestP = goodP[0][2];
00119     } else if (goodCompute[1][0]) {
00120          deAssign(goodCompute[1][0], &processors[mype]);
00121          assign(goodCompute[1][0], goodP[1][0]);
00122          bestP = goodP[1][0];
00123     } else if (goodCompute[0][1]) {
00124          deAssign(goodCompute[0][1], &processors[mype]);
00125          assign(goodCompute[0][1], goodP[0][1]);
00126          bestP = goodP[0][1];
00127     } else if (goodCompute[0][0]) {
00128          deAssign(goodCompute[0][0], &processors[mype]);
00129          assign(goodCompute[0][0], goodP[0][0]);
00130          bestP = goodP[0][0];
00131     } else {
00132          iout << iINFO << "AlgNbor: No receiver found" << "\n" << endi;
00133          break;
00134     }
00135     if (bestP->load > processors[mype].load) 
00136       lightProcessors->remove(bestP);
00137   }
00138 
00139 /*
00140   do {
00141     processorInfo *p;
00142     computeInfo *c;
00143 
00144     p = (processorInfo *)procs.deleteMin();
00145     if (p == NULL) break;
00146     bool objfound = false;
00147     do {
00148       c = (computeInfo *)objs.deleteMax();
00149       if (c == NULL) break;
00150 
00151       double new_p_load = p->load + c->load;
00152       double my_new_load = myload - c->load;
00153 //CmiPrintf("new load: new_p_load:%e my_new_load:%e c:%e\n", new_p_load, my_new_load, c->load);
00154       if (new_p_load < my_new_load) {
00155         objfound = true;
00156       } 
00157     } while (!objfound);
00158     if (!objfound) break;
00159     deAssign(c, &processors[mype]);
00160     assign(c, p);
00161     myload -= c->load;
00162     procs.insert(p);
00163   } while (myload > avgload);
00164   */
00165 /*
00166   // double bestSize0, bestSize1, bestSize2;
00167   computeInfo *c;
00168   int numAssigned;
00169   processorInfo* goodP[3][3];  // goodP[# of real patches][# of proxies]
00170   processorInfo* poorP[3][3];  // fallback option
00171 
00172 
00173   //   iout << iINFO  << "calling makeHeaps. \n";
00174   computeAverage();
00175   makeHeaps();
00176   //   iout << iINFO
00177   //    << "Before assignment\n" << endi;
00178   //   printLoads();
00179               
00180   numAssigned = 0;
00181 
00182   //   for (int i=0; i<numPatches; i++)
00183   //     { std::cout << "(" << patches[i].Id << "," << patches[i].processor ;}
00184   overLoad = 1.2;
00185   for (int ic=0; ic<numComputes; ic++) {
00186     c = (computeInfo *) computesHeap->deleteMax();
00187     if ( ! c ) NAMD_bug("AlgNbor: computesHeap empty!");
00188     if (c->processor != -1) continue; // skip to the next compute;
00189     heapIterator nextProcessor;
00190     processorInfo *p = (processorInfo *) 
00191       pes->iterator((heapIterator *) &nextProcessor);
00192     int i,j;
00193     for(i=0;i<3;i++)
00194       for(j=0;j<3;j++) {
00195         goodP[i][j]=0;
00196         poorP[i][j]=0;
00197       }
00198     while (p) {
00199       int nPatches = numPatchesAvail(c,p);
00200       int nProxies = numProxiesAvail(c,p);
00201       if (nPatches < 0 || nPatches > 2)
00202         iout << iERROR << "Too many patches: " << nPatches << "\n" << endi;
00203       if (nProxies < 0 || nProxies > 2)
00204         iout << iERROR << "Too many proxies: " << nProxies << "\n" << endi;
00205 
00206       if (!goodP[nPatches][nProxies] ||
00207             (p->load < goodP[nPatches][nProxies]->load)) {
00208         if (c->load + p->load < overLoad*averageLoad) {
00209           goodP[nPatches][nProxies] = p;
00210         }
00211       }
00212       if (!poorP[nPatches][nProxies] ||
00213             (p->load < poorP[nPatches][nProxies]->load)) {
00214         poorP[nPatches][nProxies] = p;   // fallback
00215       }
00216       p = (processorInfo *) pes->next(&nextProcessor);
00217     }
00218 
00219     //    if (numAssigned >= 0) {  Else is commented out below
00220 
00221     p = 0;
00222     if ((p = goodP[2][0])    // Two home, no proxies
00223      || (p = goodP[1][1])    // One home, one proxy
00224      || (p = goodP[0][2])    // No home, two proxies
00225      || (p = goodP[1][0])    // One home, no proxies
00226      || (p = goodP[0][1])    // No home, one proxy
00227      || (p = goodP[0][0])    // No home, no proxies
00228      || (p = poorP[2][0])    // Two home, no proxies, overload
00229      || (p = poorP[1][1])    // One home, one proxy, overload
00230      || (p = poorP[0][2])    // No home, two proxies, overload
00231      || (p = poorP[1][0])    // One home, no proxies, overload
00232      || (p = poorP[0][1])    // No home, one proxy, overload
00233      || (p = poorP[0][0])    // No home, no proxies, overload
00234        ) {
00235       assign(c,p); numAssigned++;
00236     } else {
00237       NAMD_bug("*** Alg 7 No receiver found 1 ***");
00238       break;
00239     }
00240 
00241   }
00242 
00243 
00244   // binary-search refinement procedure
00245   multirefine();
00246 */
00247 
00248   CmiPrintf("AlgNbor finish time: %f.\n", CmiWallTimer()-startTime);
00249 }
00250 
00251 
00252 
00253 
00254 
00255 
00256 
00257 
00258 
00259 
00260 
00261 
00262 
00263 
00264 

Generated on Tue Sep 26 01:17:11 2017 for NAMD by  doxygen 1.4.7