AlgRecBisection.C

Go to the documentation of this file.
00001 
00007 #include "common.h"
00008 #include "InfoStream.h"
00009 #include "AlgRecBisection.h"
00010 
00011 //#define DEBUG
00012 
00013 //
00014 //   load balancing computes using recursion of bisection algorithm
00015 //
00016 //
00017 AlgRecBisection::AlgRecBisection(computeInfo *computeArray, patchInfo *patchArray, 
00018            processorInfo *processorArray, int nComps, 
00019            int nPatches, int nPes) :
00020   Rebalancer(computeArray, patchArray, 
00021              processorArray, nComps, 
00022              nPatches, nPes)
00023 {
00024 strategyName = "Rob";
00025 strategy();
00026 }
00027 
00028 
00029 void AlgRecBisection::rec_divide(int n, Partition &p)
00030 {
00031   int i;
00032   int midpos;
00033   int n1, n2;
00034   double load1, currentload;
00035   int maxdir, count;
00036   Partition p1, p2;
00037 
00038 #ifdef DEBUG
00039   CmiPrintf("rec_divide: partition n:%d count:%d load:%f (%d %d %d, %d %d %d)\n", n, p.count, p.load, p.origin[0], p.origin[1], p.origin[2], p.corner[0], p.corner[1], p.corner[2]);
00040 #endif
00041 
00042   if (n==1) {
00043     partitions[currentp++] = p;
00044     return;
00045   }
00046 /*
00047   if (p.origin.x==p.corner.x && p.origin.y==p.corner.y && p.origin.z==p.corner.z) 
00048      NAMD_die("AlgRecBisection failed in recursion.\n"); 
00049 */
00050 
00051   n2 = n/2;
00052   n1 = n-n2;
00053 
00054   load1 = (1.0*n1/n) * p.load;
00055 
00056   p1 = p;
00057   p1.refno = ++refno;
00058   p2 = p;
00059   p2.refno = ++refno;
00060 
00061   // determine the best division direction
00062   int maxSpan=-1;
00063   maxdir = XDIR;
00064   for (i=XDIR; i<=ZDIR; i++) {
00065     int myspan = p.corner[i] - p.origin[i];
00066     if (myspan > maxSpan) {
00067       maxdir = i;
00068       maxSpan = myspan;
00069     }
00070   }
00071 
00072   // other two dimensions
00073   int dir2 = (maxdir+1)%3;
00074   int dir3 = (maxdir+2)%3;
00075 
00076   currentload = 0.0;
00077   count = 0;
00078   midpos = p.origin[maxdir];
00079   for (i=0; i<numComputes; i++) {
00080     // not belong to this partition
00081     if (computeLoad[vArray[maxdir][i].id].refno != p.refno) continue;
00082     if (vArray[maxdir][i].v<p.origin[maxdir]) continue;
00083     if (vArray[maxdir][i].v>p.corner[maxdir]) break;
00084 
00085     int cid = vArray[maxdir][i].id;     // this compute ID
00086     // check if this compute is within the partition
00087     if ( computeLoad[cid].v[dir2] >= p.origin[dir2] &&
00088          computeLoad[cid].v[dir2] <= p.corner[dir2] &&
00089          computeLoad[cid].v[dir3] >= p.origin[dir3] &&
00090          computeLoad[cid].v[dir3] <= p.corner[dir3]  ) {
00091       // this compute is set to the first partition
00092       if (currentload <= load1) {
00093         computeLoad[cid].refno = p1.refno;
00094         currentload += computeLoad[cid].load;
00095         count ++;
00096         midpos = computeLoad[cid].v[maxdir];
00097       }
00098       else {    // or the next partition
00099 /*
00100         double c = currentload + computeLoad[cid].load;
00101         if (c - load1 < load1 - currentload) {
00102           computeLoad[cid].refno = p1.refno;
00103           currentload = c;
00104           count ++;
00105           midpos = computeLoad[cid].v[maxdir];
00106         }
00107         else
00108 */
00109         computeLoad[cid].refno = p2.refno;
00110       }
00111     }
00112   }
00113 //  CmiPrintf("X:cur:%d, prev:%d load:%f %f\n", cur, prev, currentload, prevload);
00114 #ifdef DEBUG
00115   CmiPrintf("DIR:%d %d load:%f\n", maxdir, midpos, currentload);
00116 #endif
00117 
00118 
00119   p1.corner[maxdir] = midpos;
00120   p2.origin[maxdir] = midpos;
00121 
00122   p1.load = currentload;
00123   p1.count = count;
00124   p2.load = p.load - p1.load;
00125   p2.count = p.count - p1.count;
00126 #ifdef DEBUG
00127   CmiPrintf("p1: n:%d count:%d load:%f\n", n1, p1.count, p1.load);
00128   CmiPrintf("p2: n:%d count:%d load:%f\n", n2, p2.count, p2.load);
00129 #endif
00130   CmiAssert(! (p1 == p2));
00131   rec_divide(n1, p1);
00132   rec_divide(n2, p2);
00133 }
00134 
00135 void AlgRecBisection::setVal(int x, int y, int z)
00136 {
00137   int i;
00138   for (i=0; i<numComputes; i++) {
00139     computeLoad[i].tv = 1000000*computeLoad[i].v[x]+
00140                         1000*computeLoad[i].v[y]+
00141                         computeLoad[i].v[z];
00142   }
00143 #if 0
00144   CmiPrintf("original:%d\n", x);
00145   for (i=0; i<numComputes; i++) 
00146     CmiPrintf("%d ", computeLoad[i].tv);
00147   CmiPrintf("\n");
00148 #endif
00149 }
00150 
00151 int AlgRecBisection::sort_partition(int x, int p, int r)
00152 {
00153   int mid = computeLoad[vArray[x][p].id].tv;
00154   int i= p;
00155   int j= r;
00156   while (1) {
00157     while (computeLoad[vArray[x][j].id].tv > mid && j>i) j--;
00158     while (computeLoad[vArray[x][i].id].tv < mid && i<j) i++;
00159     if (i<j) {
00160       if (computeLoad[vArray[x][i].id].tv == computeLoad[vArray[x][j].id].tv)
00161       {
00162         if (computeLoad[vArray[x][i].id].tv != mid) NAMD_die("my god!\n");
00163         if (i-p < r-j) i++;
00164         else j--;
00165         continue;
00166       }
00167       VecArray tmp = vArray[x][i];
00168       vArray[x][i] = vArray[x][j];
00169       vArray[x][j] = tmp;
00170     }
00171     else
00172       return j;
00173   }
00174 }
00175 
00176 void AlgRecBisection::qsort(int x, int p, int r)
00177 {
00178   if (p<r) {
00179     int q = sort_partition(x, p, r);
00180 //CmiPrintf("midpoint: %d %d %d\n", p,q,r);
00181     qsort(x, p, q-1);
00182     qsort(x, q+1, r);
00183   }
00184 }
00185 
00186 void AlgRecBisection::quicksort(int x)
00187 {
00188   int y = (x+1)%3;
00189   int z = (x+2)%3;
00190   setVal(x, y, z);
00191   qsort(x, 0, numComputes-1);
00192 
00193 #if 0
00194   CmiPrintf("result:%d\n", x);
00195   for (int i=0; i<numComputes; i++) 
00196     CmiPrintf("%d ", computeLoad[vArray[x][i].id].tv);
00197   CmiPrintf("\n");
00198 #endif
00199 }
00200 
00201 void AlgRecBisection::mapPartitionsToNodes()
00202 {
00203   int i,j,k;
00204 #if 0
00205   for (i=0; i<P; i++) partitions[i].node = i;
00206 #else
00207   PatchMap *patchMap = PatchMap::Object();
00208 
00209   int **pool = new int *[P];
00210   for (i=0; i<P; i++) pool[i] = new int[P];
00211   for (i=0; i<P; i++) for (j=0; j<P; j++) pool[i][j] = 0;
00212 
00213   // sum up the number of nodes that patches of computes are on
00214   for (i=0; i<numComputes; i++)
00215   {
00216     for (j=0; j<P; j++)
00217       if (computeLoad[i].refno == partitions[j].refno) 
00218       {
00219         //int node1 = patchMap->node(computes[i].patch1);
00220         //int node2 = patchMap->node(computes[i].patch2);
00221         int node1 = patches[computes[i].patch1].processor;
00222         int node2 = patches[computes[i].patch2].processor;
00223         pool[j][node1]++;
00224         pool[j][node2]++;
00225       }
00226   }
00227 #ifdef DEBUG
00228   for (i=0; i<P; i++) {
00229     for (j=0; j<P; j++) CmiPrintf("%d ", pool[i][j]);
00230     CmiPrintf("\n");
00231   }
00232 #endif
00233   while (1)
00234   {
00235     int index=-1, node=0, eager=-1;
00236     for (j=0; j<P; j++) {
00237       if (partitions[j].node != -1) continue;
00238       int wantmost=-1, maxnodes=-1;
00239       for (k=0; k<P; k++) if (pool[j][k] > maxnodes && !partitions[k].mapped) {wantmost=k; maxnodes = pool[j][k];}
00240       if (maxnodes > eager) {
00241         index = j; node = wantmost; eager = maxnodes;
00242       }
00243     }
00244     if (eager == -1) break;
00245     partitions[index].node = node;
00246     partitions[node].mapped = 1;
00247   }
00248 
00249   for (i=0; i<P; i++) delete [] pool[i];
00250   delete [] pool;
00251 #endif
00252 
00253   CmiPrintf("partitions to nodes mapping: ");
00254   for (i=0; i<P; i++) CmiPrintf("%d ", partitions[i].node);
00255   CmiPrintf("\n");
00256 }
00257 
00258 void AlgRecBisection::strategy()
00259 {
00260   int i,j;
00261 
00262   PatchMap *patchMap = PatchMap::Object();
00263 
00264   // create computeLoad and calculate tentative computes coordinates
00265   computeLoad = new ComputeLoad[numComputes];
00266   for (i=XDIR; i<=ZDIR; i++) vArray[i] = new VecArray[numComputes];
00267 
00268   CmiPrintf("AlgRecBisection: numComputes:%d\n", numComputes);
00269 
00270   int size_x = patchMap->gridsize_a();
00271   int size_y = patchMap->gridsize_b();
00272   int size_z = patchMap->gridsize_c();
00273 
00274   // v[0] = XDIR  v[1] = YDIR v[2] = ZDIR
00275   // vArray[XDIR] is an array holding the x vector for all computes
00276   for (i=0; i<numComputes; i++) {
00277     int pid1 = computes[i].patch1;
00278     int pid2 = computes[i].patch2;
00279     computeLoad[i].id = i;
00280     int a1 = patchMap->index_a(pid1);
00281     int b1 = patchMap->index_b(pid1);
00282     int c1 = patchMap->index_c(pid1);
00283     int a2 = patchMap->index_a(pid2);
00284     int b2 = patchMap->index_b(pid2);
00285     int c2 = patchMap->index_c(pid1);
00286     computeLoad[i].v[0] = a1 + a2;
00287     computeLoad[i].v[1] = b1 + b2;
00288     computeLoad[i].v[2] = c1 + c2;
00289 //    CmiPrintf("(%d %d %d)", computeLoad[i].x, computeLoad[i].y, computeLoad[i].z);
00290     computeLoad[i].load = computes[i].load;
00291     computeLoad[i].refno = 0;
00292 
00293     for (j=XDIR; j<=ZDIR; j++) {
00294       vArray[j][i].id = i;
00295       vArray[j][i].v = computeLoad[i].v[j];
00296     }
00297   }
00298 //  CmiPrintf("\n");
00299 
00300   double t = CmiWallTimer();
00301 
00302   quicksort(XDIR);
00303   quicksort(YDIR);
00304   quicksort(ZDIR);
00305   CmiPrintf("qsort time: %f\n", CmiWallTimer() - t);
00306 
00307   npartition = P;
00308   partitions = new Partition[npartition];
00309 
00310   top_partition.origin[XDIR] = 0;
00311   top_partition.origin[YDIR] = 0;
00312   top_partition.origin[ZDIR] = 0;
00313   top_partition.corner[XDIR] = 2*(size_x-1);
00314   top_partition.corner[YDIR] = 2*(size_y-1);
00315   top_partition.corner[ZDIR] = 2*(size_z-1);
00316 
00317   top_partition.refno = 0;
00318   top_partition.load = 0.0;
00319   top_partition.count = numComputes;
00320   for (i=0; i<numComputes; i++) top_partition.load += computes[i].load;
00321 
00322   currentp = 0;
00323   refno = 0;
00324 
00325   // recursively divide
00326   rec_divide(npartition, top_partition);
00327 
00328   CmiPrintf("After partitioning: \n");
00329   for (i=0; i<P; i++) {
00330     CmiPrintf("[%d] (%d,%d,%d) (%d,%d,%d) load:%f count:%d\n", i, partitions[i].origin[0], partitions[i].origin[1], partitions[i].origin[2], partitions[i].corner[0], partitions[i].corner[1], partitions[i].corner[2], partitions[i].load, partitions[i].count);
00331   }
00332 
00333   for (i=0; i<numComputes; i++) computes[i].processor=-1;
00334 
00335   // mapping partitions to nodes
00336   mapPartitionsToNodes();
00337 
00338   // this is for debugging
00339   int *num = new int[P];
00340   for (i=0; i<P; i++) num[i] = 0;
00341 
00342   for (i=0; i<numComputes; i++)
00343   {
00344     for (j=0; j<P; j++)
00345       if (computeLoad[i].refno == partitions[j].refno) 
00346         { computes[computeLoad[i].id].processor = partitions[j].node; num[j]++; break; }
00347   }
00348 
00349   for (i=0; i<P; i++)
00350     if (num[i] != partitions[i].count) 
00351       NAMD_die("AlgRecBisection: Compute counts don't agree!\n");
00352 
00353   delete [] num;
00354 
00355   for (i=0; i<numComputes; i++) {
00356     if (computes[i].processor == -1) NAMD_bug("AlgRecBisection failure!\n");
00357   }
00358 
00359 
00360   delete [] computeLoad;
00361   for (i=0; i<3; i++) delete [] vArray[i];
00362   delete [] partitions;
00363 
00364   // use refinement
00365   for (i=0; i<numComputes; i++)
00366     assign((computeInfo *) &(computes[i]),
00367            (processorInfo *) &(processors[computes[i].processor]));
00368          
00369   printLoads();
00370 
00371 #if 1
00372   multirefine();
00373 #else
00374   printSummary();
00375 #endif
00376 
00377   printLoads();
00378 
00379   CmiPrintf("AlgRecBisection finished time: %f\n", CmiWallTimer() - t);
00380 
00381 }
00382 
00383 

Generated on Sat Sep 23 01:17:11 2017 for NAMD by  doxygen 1.4.7