Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members

Rebalancer Class Reference

#include <Rebalancer.h>

Inheritance diagram for Rebalancer:

Alg7 AlgNbor AlgRecBisection RefineOnly RefineTorusLB TorusLB List of all members.

Public Member Functions

 Rebalancer (computeInfo *computeArray, patchInfo *patchArray, processorInfo *processorArray, int nComps, int nPatches, int nPes)
 ~Rebalancer ()

Protected Types

typedef pcpair pcgrid [3][3][2]

Protected Member Functions

int isAvailableOn (patchInfo *patch, processorInfo *p)
void numAvailable (computeInfo *c, processorInfo *p, int *nPatches, int *nProxies, int *isBadForCommunication)
void refine_togrid (pcgrid &grid, double thresholdLoad, processorInfo *p, computeInfo *c)
void strategy ()
void makeHeaps ()
void makeTwoHeaps ()
void assign (computeInfo *c, processorInfo *pRec)
void assign (computeInfo *c, int p)
void deAssign (computeInfo *c, processorInfo *pRec)
int refine ()
void multirefine (double overload_start=1.02)
void printSummary ()
void printResults ()
void printLoads ()
double computeAverage ()
void adjustBackgroundLoadAndComputeAverage ()
double computeMax ()
void createSpanningTree ()
void decrSTLoad ()
void incrSTLoad ()
void InitProxyUsage ()
void brickDim (int a, int b, int dim, int &min, int &max)
int withinBrick (int x, int y, int z, int xm, int xM, int dimX, int ym, int yM, int dimY, int zm, int zM, int dimZ)

Protected Attributes

int bytesPerAtom
ProxyUsage proxyUsage
const char * strategyName
computeInfocomputes
patchInfopatches
processorInfoprocessors
minHeappes
maxHeapcomputePairHeap
maxHeapcomputeSelfHeap
maxHeapcomputeBgPairHeap
maxHeapcomputeBgSelfHeap
int P
int numPatches
int numComputes
int numProxies
int numPesAvailable
double averageLoad
int firstAssignInRefine
double overLoad

Member Typedef Documentation

typedef pcpair Rebalancer::pcgrid[3][3][2] [protected]
 

Definition at line 124 of file Rebalancer.h.

Referenced by refine(), and refine_togrid().


Constructor & Destructor Documentation

Rebalancer::Rebalancer computeInfo computeArray,
patchInfo patchArray,
processorInfo processorArray,
int  nComps,
int  nPatches,
int  nPes
 

Definition at line 24 of file Rebalancer.C.

References processorInfo::available, processorInfo::backgroundLoad, bytesPerAtom, computeBgPairHeap, computeBgSelfHeap, processorInfo::computeLoad, computePairHeap, computes, computeSelfHeap, Set::find(), firstAssignInRefine, InitProxyUsage(), Set::insert(), InfoRecord::load, numComputes, numPatches, numPesAvailable, computeInfo::oldProcessor, overLoad, P, patches, processorInfo::patchSet, pes, printLoads(), computeInfo::processor, patchInfo::processor, processors, processorInfo::proxies, patchInfo::proxiesOn, and strategyName.

00026 {
00027    bytesPerAtom = 32;
00028    strategyName = "None";
00029    computes = computeArray;
00030    patches =  patchArray;
00031    processors =  processorArray;
00032    numComputes = nComps;
00033    numPatches = nPatches;
00034    P = nPes;
00035    pes = NULL;
00036    computePairHeap = NULL;
00037    computeSelfHeap = NULL;
00038    computeBgPairHeap = NULL;
00039    computeBgSelfHeap = NULL;
00040    overLoad = 0.;
00041    numPesAvailable = 0;
00042    firstAssignInRefine = 0;
00043 
00044    int i;
00045    for (i=0; i<P; i++)
00046    {
00047       // For testing only...
00048       // processors[i].backgroundLoad = 0;
00049       // End of test section
00050       processors[i].load = processors[i].backgroundLoad;
00051       processors[i].computeLoad = 0;
00052       if (processors[i].available) {
00053         numPesAvailable += 1;
00054       }
00055    }
00056 
00057    for (i=0; i<nPatches; i++)
00058    {
00059       if (!patches[i].proxiesOn.find(&(processors[patches[i].processor]))) 
00060       {
00061          patches[i].proxiesOn.insert(&(processors[patches[i].processor]));
00062          processors[patches[i].processor].proxies.insert(&(patches[i]));
00063       }
00064       processors[patches[i].processor].patchSet.insert(&patches[i]);
00065    }                      
00066 
00067    InitProxyUsage();
00068 
00069    for (i=0; i<numComputes; i++)
00070       computeArray[i].processor = -1;
00071 
00072    for (i=0; i < numComputes; i++)
00073       processors[computes[i].oldProcessor].computeLoad += computes[i].load;
00074 
00075    // Added 4-29-98: Temporarily adds the compute load to the background
00076    // load so that the correct value for the total load can be displayed.
00077    float *temploads = new float[P];
00078    for(i=0; i<P; i++)
00079    {
00080       temploads[i] = processors[i].load;
00081       processors[i].load += processors[i].computeLoad;
00082    }
00083 
00084    // iout << iINFO << "Initial load" << "\n";
00085    printLoads();
00086 
00087    for(i=0;i<P; i++)
00088    {
00089       processors[i].load = temploads[i];
00090       processors[i].computeLoad = 0;
00091    }
00092    
00093    delete [] temploads;
00094 
00095    // int count1=0, count2=0;
00096    // for (i=0; i<nPatches; i++)
00097    // {
00098    //    if (patches[i].proxiesOn.numElements() <= 1)
00099    //    count1++;
00100    //    else count2++;
00101    // }                   
00102    // iout << iINFO << "Count1 = " << count1
00103    //      << "Count2 = " << count2
00104    //      << "\n" << std::endl;
00105    // 
00106    // for (i=0; i <P; i++) 
00107    // {
00108    //    iout << iINFO << "\n proxies on proc. " << i << " are for patches:";
00109    //    processorArray[i].proxies->print();
00110    // }
00111    // 
00112    // iout << iINFO <<"\n" << endi;
00113    // strategy();
00114 
00115    // for (i=0; i<nPatches; i++)
00116    // {
00117    //    iout << "patch " << i << " on processor " << patches[i].processor << "\n" << endi;
00118    // }
00119 }

Rebalancer::~Rebalancer  ) 
 

Definition at line 121 of file Rebalancer.C.

00122 {
00123   //for(int i=0; i<P; i++)
00124   //  delete [] processors[i].proxyUsage;
00125    delete pes;
00126    delete computePairHeap;
00127    delete computeSelfHeap;
00128    delete computeBgPairHeap;
00129    delete computeBgSelfHeap;
00130 }


Member Function Documentation

void Rebalancer::adjustBackgroundLoadAndComputeAverage  )  [protected]
 

Definition at line 899 of file Rebalancer.C.

References processorInfo::available, processorInfo::backgroundLoad, computeAverage(), iINFO(), iout, numPesAvailable, and processors.

00900 {
00901   // useful for AlgSeven when some loads start out as zero
00902 
00903    if (numPesAvailable == 0) {
00904      computeAverage();  // because otherwise someone will forget
00905      return;
00906    }
00907   
00908    int i;
00909    double bgtotal = 0.;
00910    for (i=0; i<P; i++) {
00911       if (processors[i].available) {
00912         bgtotal += processors[i].backgroundLoad;
00913       }
00914    }
00915    double bgavg = bgtotal / numPesAvailable;
00916 
00917    int nadjusted = 0;
00918    for (i=0; i<P; i++) {
00919       if (processors[i].available) {
00920         double bgload = processors[i].backgroundLoad;
00921         if ( bgload < bgavg ) {
00922           processors[i].backgroundLoad = bgavg;
00923           ++nadjusted;
00924         }
00925       }
00926    }
00927    iout << iINFO << "Adjusted background load on " << nadjusted
00928         << " nodes.\n" << endi;
00929 
00930    computeAverage();  // because otherwise someone will forget
00931 }

void Rebalancer::assign computeInfo c,
int  p
[protected]
 

Definition at line 336 of file Rebalancer.C.

References assign(), and processors.

00337 {
00338    assign(c, &(processors[processor]));
00339 }

void Rebalancer::assign computeInfo c,
processorInfo pRec
[protected]
 

Definition at line 341 of file Rebalancer.C.

References processorInfo::backgroundLoad, processorInfo::computeLoad, processorInfo::computeSet, Set::find(), InfoRecord::Id, ProxyUsage::increment(), Set::insert(), iout, InfoRecord::load, numProxies, patches, computeInfo::processor, processors, processorInfo::proxies, patchInfo::proxiesOn, and proxyUsage.

Referenced by assign(), and RefineTorusLB::newRefine().

00342 {
00343    c->processor = p->Id;
00344    p->computeSet.insert((InfoRecord *) c);
00345 #if COMPUTE_CORRECTION
00346    if(firstAssignInRefine)
00347      p->computeLoad += c->load + COMPUTE_LOAD;
00348    else
00349 #endif
00350      p->computeLoad += c->load;
00351      
00352    p->load = p->computeLoad + p->backgroundLoad;
00353    patchInfo* patch1 = (patchInfo *) &(patches[c->patch1]);
00354    patchInfo* patch2 = (patchInfo *) &(patches[c->patch2]);
00355 
00356    if (!p->proxies.find(patch1))   p->proxies.insert(patch1); 
00357    if (!patch1->proxiesOn.find(p)) {
00358      patch1->proxiesOn.insert(p); 
00359      numProxies++;
00360 #if PROXY_CORRECTION
00361      if(firstAssignInRefine) {
00362        processors[p->Id].load += PROXY_LOAD;
00363        processors[p->Id].backgroundLoad += PROXY_LOAD;
00364      }
00365 #endif
00366    }
00367 
00368    if (!p->proxies.find(patch2))   p->proxies.insert(patch2); 
00369    if (!patch2->proxiesOn.find(p)) {
00370      patch2->proxiesOn.insert(p);
00371      numProxies++;
00372 #if PROXY_CORRECTION
00373      if(firstAssignInRefine) {
00374        processors[p->Id].load += PROXY_LOAD;
00375        processors[p->Id].backgroundLoad += PROXY_LOAD;
00376      }
00377 #endif
00378    }
00379    
00380    // 4-29-98: Added the following code to keep track of how many proxies
00381    // on each processor are being used by a compute on that processor
00382    /* int n1 = */ //p->proxyUsage[c->patch1]++;
00383    proxyUsage.increment (p->Id, c->patch1);
00384    /* int n2 = */ //p->proxyUsage[c->patch2]++;
00385    proxyUsage.increment (p->Id, c->patch2);
00386 
00387    // iout << iINFO  
00388    // << "Assigning compute " << c->Id << " with work = " << c->load 
00389    // << " to processor " << p->Id << "\n"
00390    // << "\tproxyUsage[" << c->patch1 << "]: " << n1 << " --> " << n1+1 << "\n"
00391    // << "\tproxyUsage[" << c->patch2 << "]: " << n2 << " --> " << n2+1 << "\n"
00392    // << std::endl;
00393 
00394 #if 0
00395    iout << "Assign " << c->Id << " patches " << c->patch1 << " " << c->patch2
00396         << " load " << c->load << " to " << p->Id << " new load "
00397         << p->load << " background " << p->backgroundLoad
00398         << " nPatches " << nPatches << " nProxies " << nProxies;
00399    if ( nPatches + nProxies < 2 ) iout << " addProxy";
00400    if ( badForComm ) iout << " badForComm";
00401    iout << "\n" << endi;
00402 #endif
00403 }

void Rebalancer::brickDim int  a,
int  b,
int  dim,
int &  min,
int &  max
[inline, protected]
 

brickDim This function returns the coordinates of the inner brick between any two points on the torus. The coordinates need to be seen modulo the dimension in that direction

Definition at line 176 of file Rebalancer.h.

Referenced by RefineTorusLB::newRefine().

00176                                                                   {
00177     int x1, x2, x3, x4, temp, i;
00178     if(a < b)
00179       { x1 = a; x2 = b; } 
00180     else
00181       { x1 = b; x2 = a; }
00182 
00183     x3 = x2 - x1;
00184     x4 = dim - x3;
00185     if(x3 < x4) {
00186       min = x1; max = x2;
00187     } else {
00188       min = x2; max = x1 + dim;
00189     }
00190   }

double Rebalancer::computeAverage  )  [protected]
 

Definition at line 877 of file Rebalancer.C.

References processorInfo::available, averageLoad, processorInfo::backgroundLoad, computes, InfoRecord::load, numPesAvailable, and processors.

Referenced by adjustBackgroundLoadAndComputeAverage(), RefineTorusLB::binaryRefine(), multirefine(), printLoads(), RefineOnly::RefineOnly(), and RefineTorusLB::RefineTorusLB().

00878 {
00879    int i;
00880    double total = 0.;
00881    for (i=0; i<numComputes; i++)
00882       total += computes[i].load;
00883 
00884    for (i=0; i<P; i++) {
00885       if (processors[i].available) {
00886         total += processors[i].backgroundLoad;
00887       }
00888    }
00889   
00890    if (numPesAvailable == 0) {
00891      CmiPrintf("Warning: no processors available for load balancing!\n");
00892      averageLoad = 0.0;
00893    }
00894    else 
00895      averageLoad = total/numPesAvailable;
00896    return averageLoad;
00897 }

double Rebalancer::computeMax  )  [protected]
 

Definition at line 933 of file Rebalancer.C.

References InfoRecord::load, and processors.

Referenced by RefineTorusLB::binaryRefine(), multirefine(), and printLoads().

00934 {
00935    int i;
00936    double max = processors[0].load;
00937    for (i=1; i<P; i++)
00938    {
00939       if (processors[i].load > max) 
00940          max = processors[i].load;
00941    }
00942    return max;
00943 }

void Rebalancer::createSpanningTree  )  [protected]
 

Definition at line 1018 of file Rebalancer.C.

References ProxyMgr::buildSpanningTree0(), ProxyMgr::getPtree(), InfoRecord::Id, Iterator::id, Set::iterator(), Set::next(), PatchMap::node(), NodeIDList, PatchMap::Object(), ProxyMgr::Object(), patches, patchInfo::proxiesOn, ProxyTree::proxylist, ResizeArray< Elem >::resize(), and ProxyTree::sizes.

Referenced by RefineOnly::RefineOnly(), and RefineTorusLB::RefineTorusLB().

01018                                     {
01019   ProxyTree &pt = ProxyMgr::Object()->getPtree();
01020   Iterator nextP;
01021   processorInfo *p;
01022 #ifndef NODEAWARE_PROXY_SPANNINGTREE
01023   if(pt.sizes==NULL)
01024     pt.sizes = new int[numPatches];
01025 #endif
01026  
01027   if (pt.proxylist == NULL)
01028     pt.proxylist = new NodeIDList[numPatches];
01029   for(int i=0; i<numPatches; i++)
01030   {
01031     pt.proxylist[i].resize(patches[i].proxiesOn.numElements());
01032     nextP.id = 0;
01033     p = (processorInfo *)(patches[i].proxiesOn.iterator((Iterator *)&nextP));
01034     int j = 0;
01035     while(p) {
01036       //if (p->Id < 0)
01037       //  printf ("Inserting proxy on -ve processor %d for patch %d\n", p->Id, i);
01038 
01039       if (p->Id == (PatchMap::Object()->node(i))) {
01040         p = (processorInfo *)(patches[i].proxiesOn.next((Iterator *)&nextP));
01041         continue;
01042       }
01043 
01044       pt.proxylist[i][j] = p->Id;
01045       nextP.id++;
01046       p = (processorInfo *)(patches[i].proxiesOn.next((Iterator *)&nextP));
01047       j++;
01048     }
01049     pt.proxylist[i].resize(j);
01050   }
01051   CkPrintf("Done intialising\n");
01052 #ifdef NODEAWARE_PROXY_SPANNINGTREE
01053   ProxyMgr::Object()->buildNodeAwareSpanningTree0();
01054 #else
01055   ProxyMgr::Object()->buildSpanningTree0();
01056 #endif
01057 }

void Rebalancer::deAssign computeInfo c,
processorInfo pRec
[protected]
 

Definition at line 405 of file Rebalancer.C.

References processorInfo::backgroundLoad, processorInfo::computeLoad, processorInfo::computeSet, ProxyUsage::decrement(), ProxyUsage::getVal(), InfoRecord::Id, iINFO(), iout, InfoRecord::load, numProxies, computeInfo::patch1, computeInfo::patch2, patches, patchInfo::processor, computeInfo::processor, processors, processorInfo::proxies, patchInfo::proxiesOn, proxyUsage, and Set::remove().

Referenced by RefineTorusLB::newRefine().

00406 {
00407    if (!p->computeSet.remove(c))  {
00408       iout << iINFO << "ERROR: Rebalancer tried to deAssign an object that is not on the processor.\n" << endi;
00409       return;
00410    }
00411 
00412    c->processor = -1;
00413    p->computeLoad -= c->load;
00414    CmiAssert(p->computeLoad >= 0.0);
00415    p->load = p->computeLoad + p->backgroundLoad;
00416 
00417    // 4-29-98: Added the following code to keep track of how many proxies 
00418    // on each processor are being used by a compute on that processor.
00419    // If no computes are using the proxy, it should be removed if it is not
00420    // on the processor that its patch is on.
00421    /* int n1 = */ //p->proxyUsage[c->patch1]--;
00422    proxyUsage.decrement (p->Id, c->patch1);
00423    /* int n2 = */ //p->proxyUsage[c->patch2]--;
00424    proxyUsage.decrement (p->Id, c->patch2);
00425 
00426    // iout << iINFO
00427    // << "De-assigning compute " << c->Id << " from processor " << p->Id << "\n"
00428    // << "\tproxyUsage[" << c->patch1 << "]: " << n1 << " --> " << n1-1 << "\n"
00429    // << "\tproxyUsage[" << c->patch2 << "]: " << n2 << " --> " << n2-1 << "\n"
00430    // << std::endl;
00431 
00432    //if(p->proxyUsage[c->patch1] <= 0 && p->Id != patches[c->patch1].processor)
00433    if(proxyUsage.getVal(p->Id, c->patch1) <= 0 && p->Id != patches[c->patch1].processor)
00434    {
00435       // iout << iINFO 
00436       // << "REMOVING PROXY " << c->patch1 << " FROM PROCESSOR " << p->Id 
00437       // << std::endl << endl;
00438 
00439       patchInfo* patch1 = (patchInfo *) &(patches[c->patch1]);
00440       p->proxies.remove(patch1);
00441       patch1->proxiesOn.remove(p);
00442       numProxies--;
00443 #if PROXY_CORRECTION
00444       if(firstAssignInRefine) {
00445         processors[p->Id].load -= PROXY_LOAD;
00446         processors[p->Id].backgroundLoad -= PROXY_LOAD;
00447         if(processors[p->Id].backgroundLoad < 0) {
00448           processors[p->Id].backgroundLoad = 0;
00449           processors[p->Id].load += PROXY_LOAD;
00450         }
00451       }
00452 #endif
00453    }
00454    
00455    //if(p->proxyUsage[c->patch2] <= 0 && p->Id != patches[c->patch2].processor)
00456    if(proxyUsage.getVal(p->Id, c->patch2) <= 0 && p->Id != patches[c->patch2].processor)
00457    {
00458       // iout << iINFO
00459       // << "REMOVING PROXY " << c->patch1 << " FROM PROCESSOR " << p->Id 
00460       // << std::endl << endl;
00461 
00462       patchInfo* patch2 = (patchInfo *) &(patches[c->patch2]);
00463       p->proxies.remove(patch2);
00464       patch2->proxiesOn.remove(p);
00465       numProxies--;
00466 #if PROXY_CORRECTION
00467       if(firstAssignInRefine) {
00468         processors[p->Id].load -= PROXY_LOAD;
00469         processors[p->Id].backgroundLoad -= PROXY_LOAD;
00470         if(processors[p->Id].backgroundLoad < 0) {
00471           processors[p->Id].backgroundLoad = 0;
00472           processors[p->Id].load += PROXY_LOAD;
00473         }
00474       }
00475 #endif
00476    }
00477 }

void Rebalancer::decrSTLoad  )  [protected]
 

Definition at line 1059 of file Rebalancer.C.

References processorInfo::backgroundLoad, ProxyMgr::getPtree(), InfoRecord::load, ProxyMgr::Object(), processors, ProxyTree::proxylist, and ResizeArray< Elem >::size().

Referenced by RefineOnly::RefineOnly(), and RefineTorusLB::RefineTorusLB().

01059                             {
01060   int pe;
01061   ProxyTree &pt = ProxyMgr::Object()->getPtree();
01062   for(int i=0; i<numPatches; i++)
01063     for(int j=1; j<pt.proxylist[i].size() && j<proxySpanDim; j++) {
01064       pe = pt.proxylist[i][j];
01065       processors[pe].load -= ST_NODE_LOAD;
01066       processors[pe].backgroundLoad -= ST_NODE_LOAD;
01067       if(processors[pe].load < 0.0)
01068         processors[pe].load = 0.0;
01069       if(processors[pe].backgroundLoad < 0.0)
01070         processors[pe].backgroundLoad = 0.0;
01071     }
01072 }

void Rebalancer::incrSTLoad  )  [protected]
 

Definition at line 1074 of file Rebalancer.C.

References processorInfo::backgroundLoad, ProxyMgr::getPtree(), InfoRecord::load, ProxyMgr::Object(), processors, ProxyTree::proxylist, and ResizeArray< Elem >::size().

Referenced by RefineOnly::RefineOnly(), and RefineTorusLB::RefineTorusLB().

01074                             {
01075   int pe;
01076   ProxyTree &pt = ProxyMgr::Object()->getPtree();
01077   for(int i=0; i<numPatches; i++)
01078     for(int j=1; j<pt.proxylist[i].size() && j<proxySpanDim; j++) {
01079       pe = pt.proxylist[i][j];
01080       processors[pe].load += ST_NODE_LOAD;
01081       processors[pe].backgroundLoad += ST_NODE_LOAD;
01082     }
01083 }

void Rebalancer::InitProxyUsage  )  [protected]
 

Definition at line 135 of file Rebalancer.C.

References processorInfo::computeSet, InfoRecord::Id, Iterator::id, ProxyUsage::increment(), Set::iterator(), Set::next(), Set::numElements(), numProxies, computeInfo::patch1, computeInfo::patch2, patches, processors, patchInfo::proxiesOn, and proxyUsage.

Referenced by Rebalancer(), RefineOnly::RefineOnly(), and RefineTorusLB::RefineTorusLB().

00136 {
00137    int i;
00138    numProxies = 0;
00139 
00140    for(i=0; i<P; i++) {
00141      //processors[i].proxyUsage = new unsigned char [numPatches];
00142      //for(int j=0; j<numPatches; j++)
00143      //{
00144      //  processors[i].proxyUsage[j] = 0;
00145      //}
00146 
00147       Iterator nextCompute;
00148       nextCompute.id = 0;
00149 
00150       computeInfo *c = (computeInfo *)
00151          processors[i].computeSet.iterator((Iterator *)&nextCompute);
00152 
00153       while(c)
00154       {
00155         /* int n1 = */ //processors[i].proxyUsage[c->patch1]++;
00156         proxyUsage.increment (i, c->patch1); 
00157         /* int n2 = */ //processors[i].proxyUsage[c->patch2]++;
00158         proxyUsage.increment (i, c->patch2); 
00159 
00160          // iout << iINFO  
00161          // << "Assigning compute " << c->Id << " with work = " << c->load 
00162          // << " to processor " << processors[i].Id << "\n"
00163          // << "\tproxyUsage[" << c->patch1 << "]: " << n1 << " --> " << n1+1 << "\n";
00164          // << "\tproxyUsage[" << c->patch2 << "]: " << n2 << " --> " << n2+1 << "\n";
00165          // << std::endl;
00166 
00167          nextCompute.id++;
00168          c = (computeInfo *) processors[i].computeSet.next((Iterator *)&nextCompute);
00169       }
00170    }
00171 
00172   for (i=0; i<numPatches; i++)
00173   {
00174       numProxies += ( patches[i].proxiesOn.numElements() - 1 );
00175       Iterator nextProc;
00176       processorInfo *p = (processorInfo *)patches[i].proxiesOn.iterator((Iterator *)&nextProc);
00177       while (p) {
00178           //p->proxyUsage[i] += 1;
00179           proxyUsage.increment (p->Id, i);
00180           p = (processorInfo *)patches[i].proxiesOn.next((Iterator*)&nextProc);
00181       }
00182   }
00183 
00184 }

int Rebalancer::isAvailableOn patchInfo patch,
processorInfo p
[protected]
 

Definition at line 945 of file Rebalancer.C.

References Set::find(), and processorInfo::proxies.

00946 {
00947    return  p->proxies.find(patch);
00948 }

void Rebalancer::makeHeaps  )  [protected]
 

Definition at line 192 of file Rebalancer.C.

References processorInfo::backgroundLoad, computeBgPairHeap, computeBgSelfHeap, computePairHeap, computes, computeSelfHeap, maxHeap::insert(), minHeap::insert(), P, computeInfo::patch1, computeInfo::patch2, patches, pes, patchInfo::processor, and processors.

00193 {
00194    int i, j;
00195 
00196    delete pes;
00197    pes = new minHeap(P+2);
00198    for (i=0; i<P; i++)
00199       pes->insert((InfoRecord *) &(processors[i]));
00200 
00201    delete computePairHeap;
00202    delete computeSelfHeap;
00203    delete computeBgPairHeap;
00204    delete computeBgSelfHeap;
00205 
00206    double bgLoadLimit = 0.5 * averageLoad;
00207    /*
00208    iout << iINFO << "Background load limit = " << bgLoadLimit << "\n";
00209    for (i=0; i<P; i++)
00210      if ( processors[i].backgroundLoad > bgLoadLimit )
00211        iout << iINFO << "Processor " << i << " background load = "
00212             << processors[i].backgroundLoad << "\n";
00213    iout << endi;
00214    */
00215 
00216    int numSelfComputes, numPairComputes, numBgSelfComputes, numBgPairComputes;
00217 
00218    while ( 1 ) {
00219     numSelfComputes = 0;
00220     numPairComputes = 0;
00221     numBgSelfComputes = 0;
00222     numBgPairComputes = 0;
00223     for (i=0; i<numComputes; i++) {
00224      int pa1 = computes[i].patch1;
00225      int pa2 = computes[i].patch2;
00226      if ( pa1 == pa2 ) {
00227         if ( processors[patches[pa1].processor].backgroundLoad > bgLoadLimit) {
00228           ++numBgSelfComputes;
00229         } else {
00230           ++numSelfComputes;
00231         }
00232      } else {
00233         if ( processors[patches[pa1].processor].backgroundLoad > bgLoadLimit
00234           || processors[patches[pa2].processor].backgroundLoad > bgLoadLimit) {
00235           ++numBgPairComputes;
00236         } else {
00237           ++numPairComputes;
00238         }
00239      }
00240     }
00241 
00242     int numBgComputes = numBgPairComputes + numBgSelfComputes;
00243 
00244     /*if ( numBgComputes ) {
00245         iout << iINFO << numBgComputes << " of " << numComputes
00246         << " computes have background load > " << bgLoadLimit << "\n" << endi;
00247     }*/
00248 
00249     if ( numBgComputes < 0.3 * numComputes ) break;
00250     else bgLoadLimit += 0.1 * averageLoad;
00251    }
00252 
00253    computePairHeap = new maxHeap(numPairComputes+2);
00254    computeSelfHeap = new maxHeap(numSelfComputes+2);
00255    computeBgPairHeap = new maxHeap(numBgPairComputes+2);
00256    computeBgSelfHeap = new maxHeap(numBgSelfComputes+2);
00257 
00258    for (i=0; i<numComputes; i++) {
00259      int pa1 = computes[i].patch1;
00260      int pa2 = computes[i].patch2;
00261      if ( pa1 == pa2 ) {
00262         if ( processors[patches[pa1].processor].backgroundLoad > bgLoadLimit) {
00263           computeBgSelfHeap->insert( (InfoRecord *) &(computes[i]));
00264         } else {
00265           computeSelfHeap->insert( (InfoRecord *) &(computes[i]));
00266         }
00267      } else {
00268         if ( processors[patches[pa1].processor].backgroundLoad > bgLoadLimit
00269           || processors[patches[pa2].processor].backgroundLoad > bgLoadLimit) {
00270           computeBgPairHeap->insert( (InfoRecord *) &(computes[i]));
00271         } else {
00272           computePairHeap->insert( (InfoRecord *) &(computes[i]));
00273         }
00274      }
00275    }
00276 
00277 /*
00278    delete computePairHeap;
00279    delete computeSelfHeap;
00280 
00281    int numSelfComputes = 0;
00282    for (i=0; i<numComputes; i++)
00283       if ( computes[i].patch1 == computes[i].patch2 ) ++numSelfComputes;
00284 
00285    computeSelfHeap = new maxHeap(numSelfComputes+2);
00286    computePairHeap = new maxHeap(numComputes-numSelfComputes+2);
00287 
00288    for (i=0; i<numComputes; i++)
00289       if ( computes[i].patch1 == computes[i].patch2 )
00290          computeSelfHeap->insert( (InfoRecord *) &(computes[i]));
00291       else
00292          computePairHeap->insert( (InfoRecord *) &(computes[i]));
00293 */
00294 }

void Rebalancer::makeTwoHeaps  )  [protected]
 

Definition at line 296 of file Rebalancer.C.

References computePairHeap, computes, computeSelfHeap, maxHeap::insert(), minHeap::insert(), P, computeInfo::patch1, computeInfo::patch2, pes, and processors.

00297 {
00298    int i, j;
00299 
00300    delete pes;
00301    pes = new minHeap(P+2);
00302    for (i=0; i<P; i++)
00303       pes->insert((InfoRecord *) &(processors[i]));
00304 
00305    delete computePairHeap;
00306    delete computeSelfHeap;
00307    delete computeBgPairHeap;
00308    delete computeBgSelfHeap;
00309 
00310    int numSelfComputes, numPairComputes;
00311 
00312    numSelfComputes = 0;
00313    numPairComputes = 0;
00314    for (i=0; i<numComputes; i++) {
00315      int pa1 = computes[i].patch1;
00316      int pa2 = computes[i].patch2;
00317      if (pa1 == pa2)
00318        ++numSelfComputes;
00319      else
00320        ++numPairComputes;
00321    }
00322 
00323    computePairHeap = new maxHeap(numPairComputes+2);
00324    computeSelfHeap = new maxHeap(numSelfComputes+2);
00325 
00326    for (i=0; i<numComputes; i++) {
00327      int pa1 = computes[i].patch1;
00328      int pa2 = computes[i].patch2;
00329      if ( pa1 == pa2 )
00330        computeSelfHeap->insert( (InfoRecord *) &(computes[i]));
00331      else
00332        computePairHeap->insert( (InfoRecord *) &(computes[i]));
00333    }
00334 }

void Rebalancer::multirefine double  overload_start = 1.02  )  [protected]
 

Definition at line 719 of file Rebalancer.C.

References processorInfo::backgroundLoad, computeAverage(), processorInfo::computeLoad, computeMax(), processorInfo::computeSet, iINFO(), iout, iWARN(), InfoRecord::load, Set::numElements(), overLoad, processors, and refine().

Referenced by RefineOnly::RefineOnly().

00720 {
00721   // The New refinement procedure.  This is identical to the code in
00722   // RefineOnly.C, and probably should be merged with that code to form
00723   // a binary-search function
00724 
00725   double avg = computeAverage();
00726   double max = computeMax();
00727 
00728 #if LDB_DEBUG
00729   iout << "******** Processors with background load > average load ********" << "\n";
00730 #endif
00731 
00732   int numOverloaded = 0;
00733   for (int ip=0; ip<P; ip++) {
00734     if ( processors[ip].backgroundLoad > averageLoad ) {
00735       ++numOverloaded;
00736 #if LDB_DEBUG
00737       iout << iINFO << "Info about proc " << ip << ": Load: " << processors[ip].load << " Bg Load: " << processors[ip].backgroundLoad << " Compute Load: " << processors[ip].computeLoad << " No of computes: " << processors[ip].computeSet.numElements() << "\n";
00738 #endif
00739     }
00740   }
00741   if ( numOverloaded ) {
00742     iout << iWARN << numOverloaded
00743       << " processors are overloaded due to high background load.\n" << endi;
00744   }
00745 #if LDB_DEBUG
00746   iout << "******** Processor List Ends ********" << "\n\n";
00747 #endif
00748 
00749   const double overloadStep = 0.01;
00750   const double overloadStart = overload_start;       //1.05;
00751   double dCurOverload = max / avg;
00752   
00753   int minOverload = 0;   //Min overload should be 1.05 ?
00754   int maxOverload = (int)((dCurOverload - overloadStart)/overloadStep + 1);
00755   double dMinOverload = minOverload * overloadStep + overloadStart;
00756   double dMaxOverload = maxOverload * overloadStep + overloadStart;
00757 
00758 #if LDB_DEBUG 
00759   iout << iINFO
00760        << "Balancing from " << minOverload << " = " << dMinOverload 
00761        << " to " << maxOverload << "=" << dMaxOverload 
00762        << " dCurOverload=" << dCurOverload << " max=" << max << " avg=" << avg
00763        << "\n" << endi;
00764 #endif
00765 
00766   int curOverload;
00767   int refineDone = 0;
00768 
00769   overLoad = dMinOverload;
00770   if (refine())
00771     refineDone = 1;
00772   else {
00773     overLoad = dMaxOverload;
00774     if (!refine()) {
00775       iout << iINFO << "ERROR: Could not refine at max overload\n" << endi;
00776       refineDone = 1;
00777     }
00778   }
00779 
00780   // Scan up, until we find a refine that works
00781   while (!refineDone) {
00782     if (maxOverload - minOverload <= 1)
00783       refineDone = 1;
00784     else {
00785       curOverload = (maxOverload + minOverload ) / 2;
00786 
00787       overLoad = curOverload * overloadStep + overloadStart;
00788 #if LDB_DEBUG 
00789       iout << iINFO << "Testing curOverload " << curOverload 
00790            << "=" << overLoad << " [min,max]=" 
00791            << minOverload << ", " << maxOverload
00792            << "\n" << endi;
00793 #endif     
00794       if (refine())
00795         maxOverload = curOverload;
00796       else
00797         minOverload = curOverload;
00798     }
00799   }
00800 
00801 }

void Rebalancer::numAvailable computeInfo c,
processorInfo p,
int *  nPatches,
int *  nProxies,
int *  isBadForCommunication
[protected]
 

Definition at line 950 of file Rebalancer.C.

References processorInfo::backgroundLoad, Set::find(), InfoRecord::Id, Set::numElements(), numPatches, numPesAvailable, numProxies, computeInfo::patch1, computeInfo::patch2, patches, patchInfo::processor, processors, processorInfo::proxies, and patchInfo::proxiesOn.

Referenced by refine_togrid().

00952 {
00953    //return the number of proxy/home patches available on p for c (0,1,2)
00954 
00955    int patch_count = 0;
00956    int proxy_count = 0;
00957 
00958    patchInfo &pa1 = patches[c->patch1];
00959    patchInfo &pa2 = patches[c->patch2];
00960 
00961    int pa1_avail = 1;
00962    int pa2_avail = 1;
00963 
00964    if (pa1.processor == p->Id) {
00965      patch_count++;
00966    } else if ( p->proxies.find(&pa1) ) {
00967      proxy_count++;
00968    } else {
00969      pa1_avail = 0;
00970    }
00971 
00972    // self computes get one patch for free here
00973    if (c->patch1 == c->patch2 || pa2.processor == p->Id) {
00974      patch_count++;
00975    } else if ( p->proxies.find(&pa2) ) {
00976      proxy_count++;
00977    } else {
00978      pa2_avail = 0;
00979    }
00980 
00981    *nPatches = patch_count;
00982    *nProxies = proxy_count;
00983 
00984    int bad = 0;
00985 
00986    if ( patch_count + proxy_count < 2 ) {
00987 
00988      double bgLoadLimit = 1.2 * averageLoad;
00989 
00990      if ( p->backgroundLoad > bgLoadLimit ) bad = 1;
00991 #if 1
00992      else {
00993 
00994       int proxiesPerPeLimit = numProxies / numPesAvailable + 3;
00995       if ( proxiesPerPeLimit < 6 ) proxiesPerPeLimit = 6;
00996 
00997       if ( p->proxies.numElements() > proxiesPerPeLimit ) bad = 1;
00998 
00999       int proxiesPerPatchLimit = numProxies / numPatches + 3;
01000       if ( proxiesPerPatchLimit < 6 ) proxiesPerPatchLimit = 6;
01001 
01002       if ( ! bad && ! pa1_avail ) {
01003         if ( processors[pa1.processor].backgroundLoad > bgLoadLimit) bad = 1;
01004         else if ( pa1.proxiesOn.numElements() > proxiesPerPatchLimit ) bad = 1;
01005       }
01006       if ( ! bad && ! pa2_avail ) {
01007         if ( processors[pa2.processor].backgroundLoad > bgLoadLimit) bad = 1;
01008         else if ( pa2.proxiesOn.numElements() > proxiesPerPatchLimit ) bad = 1;
01009       }
01010 
01011      }
01012 #endif
01013    }
01014 
01015    *isBadForCommunication = bad;
01016 }

void Rebalancer::printLoads  )  [protected]
 

Definition at line 809 of file Rebalancer.C.

References averageLoad, processorInfo::backgroundLoad, computeAverage(), computeMax(), iout, Set::iterator(), Set::next(), patchInfo::numAtoms, Set::numElements(), processorInfo::patchSet, processors, processorInfo::proxies, patchInfo::proxiesOn, and strategyName.

Referenced by Rebalancer(), RefineOnly::RefineOnly(), RefineTorusLB::RefineTorusLB(), and TorusLB::TorusLB().

00810 {
00811 
00812    int i, total = 0, numBytes = 0;
00813    double max;
00814    int maxproxies = 0;
00815    int maxpatchproxies = 0;
00816    double avgBgLoad =0.0;
00817 
00818    for (i=0; i<P; i++) {
00819       int nproxies = processors[i].proxies.numElements() - 
00820                         processors[i].patchSet.numElements();
00821       if ( nproxies > maxproxies ) maxproxies = nproxies;
00822       avgBgLoad += processors[i].backgroundLoad;
00823       Iterator p;
00824       int count = 0;
00825     
00826       patchInfo *patch = (patchInfo *) processors[i].patchSet.iterator(&p);
00827       while (patch)
00828       {
00829          int myProxies;
00830          myProxies = patch->proxiesOn.numElements()-1;
00831          if ( myProxies > maxpatchproxies ) maxpatchproxies = myProxies;
00832          numBytes += myProxies *patch->numAtoms*bytesPerAtom;
00833          count += myProxies;
00834          patch = (patchInfo *)processors[i].patchSet.next(&p);
00835       }
00836       total += count;
00837    }
00838 
00839    avgBgLoad /= P;
00840    computeAverage();
00841    max = computeMax();
00842 
00843    iout << "LDB: TIME " << CmiWallTimer() << " LOAD: AVG " << averageLoad 
00844      << " MAX " << max << "  PROXIES: TOTAL " << total << " MAXPE " << 
00845      maxproxies << " MAXPATCH " << maxpatchproxies << " " << strategyName 
00846      << " " << avgBgLoad << "\n" << endi;
00847    fflush(stdout);
00848 
00849 }

void Rebalancer::printResults  )  [protected]
 

Definition at line 803 of file Rebalancer.C.

References iINFO(), and iout.

00804 {
00805   iout << iINFO << "ready to print result \n" << "\n";
00806 }

void Rebalancer::printSummary  )  [protected]
 

Definition at line 851 of file Rebalancer.C.

References processorInfo::backgroundLoad, processorInfo::computeLoad, processorInfo::computeSet, iINFO(), iout, InfoRecord::load, Set::numElements(), and processors.

Referenced by refine().

00852 {
00853    int i;
00854    // After refining, compute min, max and avg processor load
00855    double total = processors[0].load;
00856    double min = processors[0].load;
00857    int min_proc = 0;
00858    double max = processors[0].load;
00859    int max_proc = 0;
00860    for (i=1; i<P; i++) {
00861      total += processors[i].load;
00862      if (processors[i].load < min) {
00863        min = processors[i].load;
00864        min_proc = i;
00865      }
00866      if (processors[i].load > max) {
00867        max = processors[i].load;
00868        max_proc = i;
00869      }
00870    }
00871    iout << iINFO << "  min = " << min << " processor " << min_proc << "\n";
00872    iout << iINFO << "  max = " << max << " processor " << max_proc << "\n";
00873    iout << iINFO << "  total = " << total << " average = " << total/P << "\n";
00874    iout <<