Rebalancer Class Reference

#include <Rebalancer.h>

Inheritance diagram for Rebalancer:

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
computeInfo *	computes
patchInfo *	patches
processorInfo *	processors
minHeap *	pes
maxHeap *	computePairHeap
maxHeap *	computeSelfHeap
maxHeap *	computeBgPairHeap
maxHeap *	computeBgSelfHeap
int	P
int	numPatches
int	numComputes
int	numProxies
int	numPesAvailable
double	averageLoad
double	origMaxLoad
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 26 of file Rebalancer.C. References processorInfo::available, processorInfo::backgroundLoad, bytesPerAtom, computeBgPairHeap, computeBgSelfHeap, processorInfo::computeLoad, computeMax(), computePairHeap, computes, computeSelfHeap, IRSet::find(), firstAssignInRefine, InfoRecord::Id, INGROUP, InitProxyUsage(), InfoRecord::load, numComputes, numPatches, numPesAvailable, computeInfo::oldProcessor, origMaxLoad, overLoad, P, patches, processorInfo::patchSet, pes, printLoads(), computeInfo::processor, patchInfo::processor, processors, processorInfo::proxies, patchInfo::proxiesOn, strategyName, and IRSet::unchecked_insert(). { bytesPerAtom = 32; strategyName = "None"; computes = computeArray; patches = patchArray; processors = processorArray; numComputes = nComps; numPatches = nPatches; P = nPes; pes = NULL; computePairHeap = NULL; computeSelfHeap = NULL; computeBgPairHeap = NULL; computeBgSelfHeap = NULL; overLoad = 0.; numPesAvailable = 0; firstAssignInRefine = 0; const int beginGroup = processors[0].Id; const int endGroup = beginGroup + P; #define INGROUP(PROC) ((PROC) >= beginGroup && (PROC) < endGroup) int i; int index; for (i=0; i<P; i++) { // For testing only... // processors[i].backgroundLoad = 0; // End of test section processors[i].load = processors[i].backgroundLoad; processors[i].computeLoad = 0; if (processors[i].available) { numPesAvailable += 1; } } for (i=0; i<nPatches; i++) { // Only for those patches which are in my group (hierarchical case) if INGROUP(patches[i].processor) { index = patches[i].processor - beginGroup; if (!patches[i].proxiesOn.find(&(processors[index]))) { patches[i].proxiesOn.unchecked_insert(&(processors[index])); processors[index].proxies.unchecked_insert(&(patches[i])); } processors[index].patchSet.unchecked_insert(&patches[i]); } } InitProxyUsage(); for (i=0; i<numComputes; i++) computeArray[i].processor = -1; for (i=0; i < numComputes; i++) { // Only for those computes which are in my group (hierarchical case) if INGROUP(computes[i].oldProcessor) { index = computes[i].oldProcessor - beginGroup; processors[index].computeLoad += computes[i].load; } } // Added 4-29-98: Temporarily adds the compute load to the background // load so that the correct value for the total load can be displayed. float *temploads = new float[P]; for(i=0; i<P; i++) { temploads[i] = processors[i].load; processors[i].load += processors[i].computeLoad; } origMaxLoad = computeMax(); // iout << iINFO << "Initial load" << "\n"; printLoads(); for(i=0;i<P; i++) { processors[i].load = temploads[i]; processors[i].computeLoad = 0; } delete [] temploads; // int count1=0, count2=0; // for (i=0; i<nPatches; i++) // { // if (patches[i].proxiesOn.numElements() <= 1) // count1++; // else count2++; // } // iout << iINFO << "Count1 = " << count1 // << "Count2 = " << count2 // << "\n" << std::endl; // // for (i=0; i <P; i++) // { // iout << iINFO << "\n proxies on proc. " << i << " are for patches:"; // processorArray[i].proxies->print(); // } // // iout << iINFO <<"\n" << endi; // strategy(); // for (i=0; i<nPatches; i++) // { // iout << "patch " << i << " on processor " << patches[i].processor << "\n" << endi; // } }

Rebalancer::~Rebalancer (   )

Definition at line 137 of file Rebalancer.C. References computeMax(), computes, InfoRecord::Id, INGROUP, iout, computeInfo::oldProcessor, P, computeInfo::processor, and processors. { if ( computeMax() > origMaxLoad ) { iout << "LDB:"; if ( P != CkNumPes() ) { int w = 1; int maxinw = 10; while ( maxinw < CkNumPes() ) { ++w; maxinw = 10*maxinw; } iout << " PES " << std::setw(w) << std::right << processors[0].Id << "-" << std::setw(w) << std::left << processors[P-1].Id << std::right; } iout << " Reverting to original mapping\n" << endi; fflush(stdout); const int beginGroup = processors[0].Id; const int endGroup = beginGroup + P; for (int i=0; i < numComputes; i++) { // Only for those computes which are in my group (hierarchical case) if INGROUP(computes[i].oldProcessor) { computes[i].processor = computes[i].oldProcessor; } } } //for(int i=0; i<P; i++) // delete [] processors[i].proxyUsage; delete pes; delete computePairHeap; delete computeSelfHeap; delete computeBgPairHeap; delete computeBgSelfHeap; }

---

Member Function Documentation

void Rebalancer::adjustBackgroundLoadAndComputeAverage (   )  [protected]

Definition at line 959 of file Rebalancer.C. References processorInfo::available, processorInfo::backgroundLoad, computeAverage(), numPesAvailable, and processors. { // useful for AlgSeven when some loads start out as zero if (numPesAvailable == 0) { computeAverage(); // because otherwise someone will forget return; } int i; double bgtotal = 0.; for (i=0; i<P; i++) { if (processors[i].available) { bgtotal += processors[i].backgroundLoad; } } double bgavg = bgtotal / numPesAvailable; int nadjusted = 0; for (i=0; i<P; i++) { if (processors[i].available) { double bgload = processors[i].backgroundLoad; if ( bgload < bgavg ) { processors[i].backgroundLoad = bgavg; ++nadjusted; } } } // iout << iINFO << "Adjusted background load on " << nadjusted // << " nodes.\n" << endi; computeAverage(); // because otherwise someone will forget }

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

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

Definition at line 384 of file Rebalancer.C. References processorInfo::backgroundLoad, processorInfo::computeLoad, processorInfo::computeSet, IRSet::find(), InfoRecord::Id, ProxyUsage::increment(), iout, InfoRecord::load, numProxies, patches, computeInfo::processor, processors, processorInfo::proxies, patchInfo::proxiesOn, proxyUsage, and IRSet::unchecked_insert(). Referenced by RefineTorusLB::newRefine(). { c->processor = p->Id; p->computeSet.unchecked_insert((InfoRecord *) c); #if COMPUTE_CORRECTION if(firstAssignInRefine) p->computeLoad += c->load + COMPUTE_LOAD; else #endif p->computeLoad += c->load; p->load = p->computeLoad + p->backgroundLoad; patchInfo* patch1 = (patchInfo *) &(patches[c->patch1]); patchInfo* patch2 = (patchInfo *) &(patches[c->patch2]); if (!patch1->proxiesOn.find(p)) { p->proxies.unchecked_insert(patch1); patch1->proxiesOn.unchecked_insert(p); numProxies++; #if PROXY_CORRECTION if(firstAssignInRefine) { processors[p->Id].load += PROXY_LOAD; processors[p->Id].backgroundLoad += PROXY_LOAD; } #endif } if (!patch2->proxiesOn.find(p)) { p->proxies.unchecked_insert(patch2); patch2->proxiesOn.unchecked_insert(p); numProxies++; #if PROXY_CORRECTION if(firstAssignInRefine) { processors[p->Id].load += PROXY_LOAD; processors[p->Id].backgroundLoad += PROXY_LOAD; } #endif } // 4-29-98: Added the following code to keep track of how many proxies // on each processor are being used by a compute on that processor /* int n1 = */ //p->proxyUsage[c->patch1]++; proxyUsage.increment (p->Id, c->patch1); /* int n2 = */ //p->proxyUsage[c->patch2]++; proxyUsage.increment (p->Id, c->patch2); // iout << iINFO // << "Assigning compute " << c->Id << " with work = " << c->load // << " to processor " << p->Id << "\n" // << "\tproxyUsage[" << c->patch1 << "]: " << n1 << " --> " << n1+1 << "\n" // << "\tproxyUsage[" << c->patch2 << "]: " << n2 << " --> " << n2+1 << "\n" // << std::endl; #if 0 iout << "Assign " << c->Id << " patches " << c->patch1 << " " << c->patch2 << " load " << c->load << " to " << p->Id << " new load " << p->load << " background " << p->backgroundLoad << " nPatches " << nPatches << " nProxies " << nProxies; if ( nPatches + nProxies < 2 ) iout << " addProxy"; if ( badForComm ) iout << " badForComm"; iout << "\n" << endi; #endif }

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 177 of file Rebalancer.h. Referenced by RefineTorusLB::newRefine(). { int x1, x2, x3, x4, temp, i; if(a < b) { x1 = a; x2 = b; } else { x1 = b; x2 = a; } x3 = x2 - x1; x4 = dim - x3; if(x3 < x4) { min = x1; max = x2; } else { min = x2; max = x1 + dim; } }

double Rebalancer::computeAverage (   )  [protected]

Definition at line 937 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(). { int i; double total = 0.; for (i=0; i<numComputes; i++) total += computes[i].load; for (i=0; i<P; i++) { if (processors[i].available) { total += processors[i].backgroundLoad; } } if (numPesAvailable == 0) { CmiPrintf("Warning: no processors available for load balancing!\n"); averageLoad = 0.0; } else averageLoad = total/numPesAvailable; return averageLoad; }

double Rebalancer::computeMax (   )  [protected]

Definition at line 993 of file Rebalancer.C. References InfoRecord::load, and processors. Referenced by RefineTorusLB::binaryRefine(), multirefine(), printLoads(), Rebalancer(), and ~Rebalancer(). { int i; double max = processors[0].load; for (i=1; i<P; i++) { if (processors[i].load > max) max = processors[i].load; } return max; }

void Rebalancer::createSpanningTree (   )  [protected]

Definition at line 1090 of file Rebalancer.C. References ProxyMgr::buildSpanningTree0(), ProxyMgr::getPtree(), InfoRecord::Id, Iterator::id, IRSet::iterator(), j, IRSet::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(). { ProxyTree &pt = ProxyMgr::Object()->getPtree(); Iterator nextP; processorInfo *p; #ifndef NODEAWARE_PROXY_SPANNINGTREE if(pt.sizes==NULL) pt.sizes = new int[numPatches]; #endif if (pt.proxylist == NULL) pt.proxylist = new NodeIDList[numPatches]; for(int i=0; i<numPatches; i++) { pt.proxylist[i].resize(patches[i].proxiesOn.numElements()); nextP.id = 0; p = (processorInfo *)(patches[i].proxiesOn.iterator((Iterator *)&nextP)); int j = 0; while(p) { //if (p->Id < 0) // printf ("Inserting proxy on -ve processor %d for patch %d\n", p->Id, i); if (p->Id == (PatchMap::Object()->node(i))) { p = (processorInfo *)(patches[i].proxiesOn.next((Iterator *)&nextP)); continue; } pt.proxylist[i][j] = p->Id; nextP.id++; p = (processorInfo *)(patches[i].proxiesOn.next((Iterator *)&nextP)); j++; } pt.proxylist[i].resize(j); } CkPrintf("Done intialising\n"); #ifdef NODEAWARE_PROXY_SPANNINGTREE ProxyMgr::Object()->buildNodeAwareSpanningTree0(); #else ProxyMgr::Object()->buildSpanningTree0(); #endif }

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

Definition at line 448 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 IRSet::remove(). Referenced by RefineTorusLB::newRefine(). { if (!p->computeSet.remove(c)) { iout << iINFO << "ERROR: Rebalancer tried to deAssign an object that is not on the processor.\n" << endi; return; } double temp_load = 0.0; c->processor = -1; p->computeLoad -= c->load; CmiAssert(p->computeLoad >= 0.0); temp_load = p->load - c->load; p->load = p->computeLoad + p->backgroundLoad; CmiAssert( fabs(temp_load - p->load) < 0.001 ); // 4-29-98: Added the following code to keep track of how many proxies // on each processor are being used by a compute on that processor. // If no computes are using the proxy, it should be removed if it is not // on the processor that its patch is on. /* int n1 = */ //p->proxyUsage[c->patch1]--; proxyUsage.decrement (p->Id, c->patch1); /* int n2 = */ //p->proxyUsage[c->patch2]--; proxyUsage.decrement (p->Id, c->patch2); // iout << iINFO // << "De-assigning compute " << c->Id << " from processor " << p->Id << "\n" // << "\tproxyUsage[" << c->patch1 << "]: " << n1 << " --> " << n1-1 << "\n" // << "\tproxyUsage[" << c->patch2 << "]: " << n2 << " --> " << n2-1 << "\n" // << std::endl; //if(p->proxyUsage[c->patch1] <= 0 && p->Id != patches[c->patch1].processor) if(proxyUsage.getVal(p->Id, c->patch1) <= 0 && p->Id != patches[c->patch1].processor) { // iout << iINFO // << "REMOVING PROXY " << c->patch1 << " FROM PROCESSOR " << p->Id // << std::endl << endl; patchInfo* patch1 = (patchInfo *) &(patches[c->patch1]); p->proxies.remove(patch1); patch1->proxiesOn.remove(p); numProxies--; #if PROXY_CORRECTION if(firstAssignInRefine) { processors[p->Id].load -= PROXY_LOAD; processors[p->Id].backgroundLoad -= PROXY_LOAD; if(processors[p->Id].backgroundLoad < 0.0) { processors[p->Id].backgroundLoad = 0.0; processors[p->Id].load += PROXY_LOAD; } } #endif } //if(p->proxyUsage[c->patch2] <= 0 && p->Id != patches[c->patch2].processor) if(proxyUsage.getVal(p->Id, c->patch2) <= 0 && p->Id != patches[c->patch2].processor) { // iout << iINFO // << "REMOVING PROXY " << c->patch1 << " FROM PROCESSOR " << p->Id // << std::endl << endl; patchInfo* patch2 = (patchInfo *) &(patches[c->patch2]); p->proxies.remove(patch2); patch2->proxiesOn.remove(p); numProxies--; #if PROXY_CORRECTION if(firstAssignInRefine) { processors[p->Id].load -= PROXY_LOAD; processors[p->Id].backgroundLoad -= PROXY_LOAD; if(processors[p->Id].backgroundLoad < 0.0) { processors[p->Id].backgroundLoad = 0.0; processors[p->Id].load += PROXY_LOAD; } } #endif } }

void Rebalancer::decrSTLoad (   )  [protected]

Definition at line 1131 of file Rebalancer.C. References processorInfo::backgroundLoad, ProxyMgr::getPtree(), j, InfoRecord::load, ProxyMgr::Object(), processors, ProxyTree::proxylist, and ResizeArray< Elem >::size(). Referenced by RefineOnly::RefineOnly(), and RefineTorusLB::RefineTorusLB(). { int pe; ProxyTree &pt = ProxyMgr::Object()->getPtree(); for(int i=0; i<numPatches; i++) for(int j=1; j<pt.proxylist[i].size() && j<proxySpanDim; j++) { pe = pt.proxylist[i][j]; processors[pe].load -= ST_NODE_LOAD; processors[pe].backgroundLoad -= ST_NODE_LOAD; if(processors[pe].load < 0.0) processors[pe].load = 0.0; if(processors[pe].backgroundLoad < 0.0) processors[pe].backgroundLoad = 0.0; } }

void Rebalancer::incrSTLoad (   )  [protected]

Definition at line 1146 of file Rebalancer.C. References processorInfo::backgroundLoad, ProxyMgr::getPtree(), j, InfoRecord::load, ProxyMgr::Object(), processors, ProxyTree::proxylist, and ResizeArray< Elem >::size(). Referenced by RefineOnly::RefineOnly(), and RefineTorusLB::RefineTorusLB(). { int pe; ProxyTree &pt = ProxyMgr::Object()->getPtree(); for(int i=0; i<numPatches; i++) for(int j=1; j<pt.proxylist[i].size() && j<proxySpanDim; j++) { pe = pt.proxylist[i][j]; processors[pe].load += ST_NODE_LOAD; processors[pe].backgroundLoad += ST_NODE_LOAD; } }

void Rebalancer::InitProxyUsage (   )  [protected]

Definition at line 177 of file Rebalancer.C. References processorInfo::computeSet, InfoRecord::Id, Iterator::id, ProxyUsage::increment(), IRSet::iterator(), IRSet::next(), IRSet::numElements(), numProxies, computeInfo::patch1, computeInfo::patch2, patches, processors, patchInfo::proxiesOn, and proxyUsage. Referenced by Rebalancer(), RefineOnly::RefineOnly(), and RefineTorusLB::RefineTorusLB(). { int i; numProxies = 0; for(i=0; i<P; i++) { //processors[i].proxyUsage = new unsigned char [numPatches]; //for(int j=0; j<numPatches; j++) //{ // processors[i].proxyUsage[j] = 0; //} Iterator nextCompute; nextCompute.id = 0; computeInfo *c = (computeInfo *) processors[i].computeSet.iterator((Iterator *)&nextCompute); while(c) { /* int n1 = */ //processors[i].proxyUsage[c->patch1]++; proxyUsage.increment (i, c->patch1); /* int n2 = */ //processors[i].proxyUsage[c->patch2]++; proxyUsage.increment (i, c->patch2); // iout << iINFO // << "Assigning compute " << c->Id << " with work = " << c->load // << " to processor " << processors[i].Id << "\n" // << "\tproxyUsage[" << c->patch1 << "]: " << n1 << " --> " << n1+1 << "\n"; // << "\tproxyUsage[" << c->patch2 << "]: " << n2 << " --> " << n2+1 << "\n"; // << std::endl; nextCompute.id++; c = (computeInfo *) processors[i].computeSet.next((Iterator *)&nextCompute); } } for (i=0; i<numPatches; i++) { numProxies += ( patches[i].proxiesOn.numElements() - 1 ); Iterator nextProc; processorInfo *p = (processorInfo *)patches[i].proxiesOn.iterator((Iterator *)&nextProc); while (p) { //p->proxyUsage[i] += 1; proxyUsage.increment (p->Id, i); p = (processorInfo *)patches[i].proxiesOn.next((Iterator*)&nextProc); } } }

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

Definition at line 1005 of file Rebalancer.C. References IRSet::find(), and patchInfo::proxiesOn. { return patch->proxiesOn.find(p); }

void Rebalancer::makeHeaps (   )  [protected]

Definition at line 234 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. { int i, j; delete pes; pes = new minHeap(P+2); for (i=0; i<P; i++) pes->insert((InfoRecord *) &(processors[i])); delete computePairHeap; delete computeSelfHeap; delete computeBgPairHeap; delete computeBgSelfHeap; double bgLoadLimit = 0.5 * averageLoad; /* iout << iINFO << "Background load limit = " << bgLoadLimit << "\n"; for (i=0; i<P; i++) if ( processors[i].backgroundLoad > bgLoadLimit ) iout << iINFO << "Processor " << i << " background load = " << processors[i].backgroundLoad << "\n"; iout << endi; */ int numSelfComputes, numPairComputes, numBgSelfComputes, numBgPairComputes; while ( 1 ) { numSelfComputes = 0; numPairComputes = 0; numBgSelfComputes = 0; numBgPairComputes = 0; for (i=0; i<numComputes; i++) { int pa1 = computes[i].patch1; int pa2 = computes[i].patch2; if ( pa1 == pa2 ) { if ( processors[patches[pa1].processor].backgroundLoad > bgLoadLimit) { ++numBgSelfComputes; } else { ++numSelfComputes; } } else { if ( processors[patches[pa1].processor].backgroundLoad > bgLoadLimit || processors[patches[pa2].processor].backgroundLoad > bgLoadLimit) { ++numBgPairComputes; } else { ++numPairComputes; } } } int numBgComputes = numBgPairComputes + numBgSelfComputes; /*if ( numBgComputes ) { iout << iINFO << numBgComputes << " of " << numComputes << " computes have background load > " << bgLoadLimit << "\n" << endi; }*/ if ( numBgComputes < 0.3 * numComputes ) break; else bgLoadLimit += 0.1 * averageLoad; } computePairHeap = new maxHeap(numPairComputes+2); computeSelfHeap = new maxHeap(numSelfComputes+2); computeBgPairHeap = new maxHeap(numBgPairComputes+2); computeBgSelfHeap = new maxHeap(numBgSelfComputes+2); for (i=0; i<numComputes; i++) { int pa1 = computes[i].patch1; int pa2 = computes[i].patch2; if ( pa1 == pa2 ) { if ( processors[patches[pa1].processor].backgroundLoad > bgLoadLimit) { computeBgSelfHeap->insert( (InfoRecord *) &(computes[i])); } else { computeSelfHeap->insert( (InfoRecord *) &(computes[i])); } } else { if ( processors[patches[pa1].processor].backgroundLoad > bgLoadLimit || processors[patches[pa2].processor].backgroundLoad > bgLoadLimit) { computeBgPairHeap->insert( (InfoRecord *) &(computes[i])); } else { computePairHeap->insert( (InfoRecord *) &(computes[i])); } } } /* delete computePairHeap; delete computeSelfHeap; int numSelfComputes = 0; for (i=0; i<numComputes; i++) if ( computes[i].patch1 == computes[i].patch2 ) ++numSelfComputes; computeSelfHeap = new maxHeap(numSelfComputes+2); computePairHeap = new maxHeap(numComputes-numSelfComputes+2); for (i=0; i<numComputes; i++) if ( computes[i].patch1 == computes[i].patch2 ) computeSelfHeap->insert( (InfoRecord *) &(computes[i])); else computePairHeap->insert( (InfoRecord *) &(computes[i])); */ }

void Rebalancer::makeTwoHeaps (   )  [protected]

Definition at line 338 of file Rebalancer.C. References computePairHeap, computes, computeSelfHeap, maxHeap::insert(), minHeap::insert(), P, computeInfo::patch1, computeInfo::patch2, pes, and processors. { int i, j; delete pes; pes = new minHeap(P+2); for (i=0; i<P; i++) pes->insert((InfoRecord *) &(processors[i])); delete computePairHeap; delete computeSelfHeap; delete computeBgPairHeap; delete computeBgSelfHeap; int numSelfComputes, numPairComputes; numSelfComputes = 0; numPairComputes = 0; for (i=0; i<numComputes; i++) { int pa1 = computes[i].patch1; int pa2 = computes[i].patch2; if (pa1 == pa2) ++numSelfComputes; else ++numPairComputes; } computePairHeap = new maxHeap(numPairComputes+2); computeSelfHeap = new maxHeap(numSelfComputes+2); for (i=0; i<numComputes; i++) { int pa1 = computes[i].patch1; int pa2 = computes[i].patch2; if ( pa1 == pa2 ) computeSelfHeap->insert( (InfoRecord *) &(computes[i])); else computePairHeap->insert( (InfoRecord *) &(computes[i])); } }

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

Definition at line 766 of file Rebalancer.C. References processorInfo::backgroundLoad, computeAverage(), processorInfo::computeLoad, computeMax(), processorInfo::computeSet, iINFO(), iout, iWARN(), InfoRecord::load, IRSet::numElements(), overLoad, processors, and refine(). Referenced by RefineOnly::RefineOnly(). { // The New refinement procedure. This is identical to the code in // RefineOnly.C, and probably should be merged with that code to form // a binary-search function double avg = computeAverage(); double max = computeMax(); #if LDB_DEBUG iout << "******** Processors with background load > average load ********" << "\n"; #endif int numOverloaded = 0; for (int ip=0; ip<P; ip++) { if ( processors[ip].backgroundLoad > averageLoad ) { ++numOverloaded; #if LDB_DEBUG 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"; #endif } } if ( numOverloaded ) { iout << iWARN << numOverloaded << " processors are overloaded due to high background load.\n" << endi; } #if LDB_DEBUG iout << "******** Processor List Ends ********" << "\n\n"; #endif const double overloadStep = 0.01; const double overloadStart = overload_start; //1.05; double dCurOverload = max / avg; int minOverload = 0; //Min overload should be 1.05 ? int maxOverload = (int)((dCurOverload - overloadStart)/overloadStep + 1); double dMinOverload = minOverload * overloadStep + overloadStart; double dMaxOverload = maxOverload * overloadStep + overloadStart; #if LDB_DEBUG iout << iINFO << "Balancing from " << minOverload << " = " << dMinOverload << " to " << maxOverload << "=" << dMaxOverload << " dCurOverload=" << dCurOverload << " max=" << max << " avg=" << avg << "\n" << endi; #endif int curOverload; int refineDone = 0; overLoad = dMinOverload; if (refine()) refineDone = 1; else { overLoad = dMaxOverload; if (!refine()) { iout << iINFO << "ERROR: Could not refine at max overload\n" << endi; refineDone = 1; } } // Scan up, until we find a refine that works while (!refineDone) { if (maxOverload - minOverload <= 1) refineDone = 1; else { curOverload = (maxOverload + minOverload ) / 2; overLoad = curOverload * overloadStep + overloadStart; #if LDB_DEBUG iout << iINFO << "Testing curOverload " << curOverload << "=" << overLoad << " [min,max]=" << minOverload << ", " << maxOverload << "\n" << endi; #endif if (refine()) maxOverload = curOverload; else minOverload = curOverload; } } }

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

Definition at line 1010 of file Rebalancer.C. References processorInfo::backgroundLoad, IRSet::find(), InfoRecord::Id, INGROUP, IRSet::numElements(), numPatches, numPesAvailable, numProxies, computeInfo::patch1, computeInfo::patch2, patches, patchInfo::processor, processors, processorInfo::proxies, and patchInfo::proxiesOn. Referenced by refine_togrid(). { // return the number of proxy/home patches available on p for c (0, 1, 2) int realPe, index; int patch_count = 0; int proxy_count = 0; const int beginGroup = processors[0].Id; const int endGroup = beginGroup + P; patchInfo &pa1 = patches[c->patch1]; patchInfo &pa2 = patches[c->patch2]; int pa1_avail = 1; int pa2_avail = 1; if (pa1.processor == p->Id) { patch_count++; } else if ( pa1.proxiesOn.find(p) ) { proxy_count++; } else { pa1_avail = 0; } // self computes get one patch for free here if (c->patch1 == c->patch2 || pa2.processor == p->Id) { patch_count++; } else if ( pa2.proxiesOn.find(p) ) { proxy_count++; } else { pa2_avail = 0; } *nPatches = patch_count; *nProxies = proxy_count; if ( isBadForCommunication ) { // skip work if pointer is null int bad = 0; if ( patch_count + proxy_count < 2 ) { double bgLoadLimit = 1.2 * averageLoad; if ( p->backgroundLoad > bgLoadLimit ) bad = 1; else { int proxiesPerPeLimit = numProxies / numPesAvailable + 3; if ( proxiesPerPeLimit < 6 ) proxiesPerPeLimit = 6; if ( p->proxies.numElements() > proxiesPerPeLimit ) bad = 1; int proxiesPerPatchLimit = numProxies / numPatches + 3; if ( proxiesPerPatchLimit < 6 ) proxiesPerPatchLimit = 6; if ( ! bad && ! pa1_avail ) { // HYBRID check for range in local group realPe = pa1.processor; if INGROUP(realPe) { index = realPe - beginGroup; //BACKUP if ( processors[pa1.processor].backgroundLoad > bgLoadLimit) bad = 1; if (processors[index].backgroundLoad > bgLoadLimit) bad = 1; else if ( pa1.proxiesOn.numElements() > proxiesPerPatchLimit ) bad = 1; } else bad = 1; // patch has proxies we don't know about } if ( ! bad && ! pa2_avail ) { // HYBRID check for range in local group realPe = pa2.processor; if INGROUP(realPe) { index = realPe - beginGroup; // BACKUP if ( processors[pa2.processor].backgroundLoad > bgLoadLimit) bad = 1; if ( processors[index].backgroundLoad > bgLoadLimit) bad = 1; else if ( pa2.proxiesOn.numElements() > proxiesPerPatchLimit ) bad = 1; } else bad = 1; // patch has proxies we don't know about } } } *isBadForCommunication = bad; } }

void Rebalancer::printLoads (   )  [protected]

Definition at line 856 of file Rebalancer.C. References averageLoad, processorInfo::backgroundLoad, computeAverage(), computeMax(), InfoRecord::Id, iout, IRSet::iterator(), memusage_MB(), IRSet::next(), patchInfo::numAtoms, IRSet::numElements(), processorInfo::patchSet, processors, processorInfo::proxies, patchInfo::proxiesOn, and strategyName. Referenced by Rebalancer(), RefineOnly::RefineOnly(), and RefineTorusLB::RefineTorusLB(). { int i, total = 0, numBytes = 0; double max; int maxproxies = 0; int maxpatchproxies = 0; double avgBgLoad =0.0; for (i=0; i<P; i++) { int nproxies = processors[i].proxies.numElements() - processors[i].patchSet.numElements(); total += nproxies; if ( nproxies > maxproxies ) maxproxies = nproxies; avgBgLoad += processors[i].backgroundLoad; Iterator p; int count = 0; patchInfo *patch = (patchInfo *) processors[i].patchSet.iterator(&p); while (patch) { int myProxies; myProxies = patch->proxiesOn.numElements()-1; if ( myProxies > maxpatchproxies ) maxpatchproxies = myProxies; numBytes += myProxies *patch->numAtoms*bytesPerAtom; count += myProxies; patch = (patchInfo *)processors[i].patchSet.next(&p); } } avgBgLoad /= P; computeAverage(); max = computeMax(); iout << "LDB:"; if ( P != CkNumPes() ) { int w = 1; int maxinw = 10; while ( maxinw < CkNumPes() ) { ++w; maxinw = 10*maxinw; } iout << " PES " << std::setw(w) << std::right << processors[0].Id << "-" << std::setw(w) << std::left << processors[P-1].Id << std::right; } iout << " TIME " << CmiWallTimer() << " LOAD: AVG " << averageLoad << " MAX " << max << " PROXIES: TOTAL " << total << " MAXPE " << maxproxies << " MAXPATCH " << maxpatchproxies << " " << strategyName << " MEM: " << memusage_MB() << " MB\n" << endi; fflush(stdout); }

void Rebalancer::printResults (   )  [protected]

Definition at line 850 of file Rebalancer.C. References iINFO(), and iout. { iout << iINFO << "ready to print result \n" << "\n"; }

void Rebalancer::printSummary (   )  [protected]

Definition at line 911 of file Rebalancer.C. References processorInfo::backgroundLoad, processorInfo::computeLoad, processorInfo::computeSet, iINFO(), iout, InfoRecord::load, IRSet::numElements(), processors, and processorInfo::proxies. Referenced by RefineTorusLB::newRefine(), and refine(). { int i; // After refining, compute min, max and avg processor load double total = processors[0].load; double min = processors[0].load; int min_proc = 0; double max = processors[0].load; int max_proc = 0; for (i=1; i<P; i++) { total += processors[i].load; if (processors[i].load < min) { min = processors[i].load; min_proc = i; } if (processors[i].load > max) { max = processors[i].load; max_proc = i; } } iout << iINFO << " min = " << min << " processor " << min_proc << "\n"; iout << iINFO << " max = " << max << " processor " << max_proc << "\n"; iout << iINFO << " total = " << total << " average = " << total/P << "\n"; iout << iINFO << "Info about most overloaded processor " << max_proc << ": Load: " << processors[max_proc].load << " Bg Load: " << processors[max_proc].backgroundLoad << " Compute Load: " << processors[max_proc].computeLoad << " No of computes: " << processors[max_proc].computeSet.numElements() << " No. of proxies: " << processors[max_proc].proxies.numElements() << "\n" << endi; }

int Rebalancer::refine (   )  [protected]

Definition at line 559 of file Rebalancer.C. References processorInfo::computeSet, maxHeap::deleteMax(), IRSet::hasElements(), InfoRecord::Id, Iterator::id, iINFO(), IRSet::insert(), maxHeap::insert(), iout, IRSet::iterator(), InfoRecord::load, IRSet::next(), next(), overLoad, P, computeInfo::patch1, computeInfo::patch2, patches, pcgrid, printSummary(), computeInfo::processor, patchInfo::processor, processors, REASSIGN, refine_togrid(), and IRSet::remove(). Referenced by multirefine(). { int finish = 1; int no_new_proxies = 0; // set to true if new proxies are futile maxHeap *heavyProcessors = new maxHeap(P); IRSet *lightProcessors = new IRSet(); int i; double thresholdLoad = overLoad * averageLoad; for (i=0; i<P; i++) { // iout << iINFO << "\n Computes on processor " << i << " "; // processors[i].computeSet->print(); // iout << iINFO << "\n" << endi; if (processors[i].load > thresholdLoad) heavyProcessors->insert((InfoRecord *) &(processors[i])); else lightProcessors->insert((InfoRecord *) &(processors[i])); } #if LDB_DEBUG iout << "\nBefore Refinement Summary" << "\n"; printSummary(); #endif int done = 0; while (!done) { // processorInfo *donor = (processorInfo *) heavyProcessors->deleteMax(); /* Keep selecting new donors, until we find one with some compute to * migrate */ /* computeInfo* c=0; while (donor && !c) { Iterator nextCompute; nextCompute.id = 0; c = (computeInfo *) donor-> computeSet.iterator((Iterator *)&nextCompute); if (!c) { iout << iINFO << "Ignoring donor " << donor->Id << " because no computes\n" << endi; donor = (processorInfo*)heavyProcessors->deleteMax(); } }; */ processorInfo *donor; while (donor = (processorInfo*)heavyProcessors->deleteMax()) { if (donor->computeSet.hasElements()) break; if ( ! no_new_proxies ) { /* iout << iINFO << "Most-loaded processor " << donor->Id << " (" << donor->patchSet.numElements() << " patches, " << donor->proxies.numElements() << " proxies)" << " has no migratable work.\n" << endi; */ no_new_proxies = 1; // New proxies would not improve load balance. } } if (!donor) break; // No donors found at all! Give up pcgrid grid; #define REASSIGN(GRID) if (GRID.c) { \ deAssign(GRID.c, donor); \ assign(GRID.c, GRID.p); \ bestP = GRID.p; \ } // try for at least one proxy { Iterator nextCompute; nextCompute.id = 0; computeInfo *c = (computeInfo *) donor->computeSet.iterator((Iterator *)&nextCompute); while (c) { Iterator nextProc; processorInfo *p; p = &processors[patches[c->patch1].processor]; refine_togrid(grid, thresholdLoad, p, c); if (c->patch1 != c->patch2) { p = &processors[patches[c->patch2].processor]; refine_togrid(grid, thresholdLoad, p, c); } p = (processorInfo *)patches[c->patch1]. proxiesOn.iterator((Iterator *)&nextProc); while (p) { refine_togrid(grid, thresholdLoad, p, c); p = (processorInfo *)patches[c->patch1]. proxiesOn.next((Iterator*)&nextProc); } if (c->patch1 != c->patch2) { p = (processorInfo *)patches[c->patch2]. proxiesOn.iterator((Iterator *)&nextProc); while (p) { refine_togrid(grid, thresholdLoad, p, c); p = (processorInfo *)patches[c->patch2]. proxiesOn.next((Iterator*)&nextProc); } } nextCompute.id++; c = (computeInfo *) donor->computeSet. next((Iterator *)&nextCompute); } processorInfo* bestP = 0; // prefer proxies to home patches REASSIGN(grid[0][2][0]) else REASSIGN(grid[1][1][0]) else REASSIGN(grid[2][0][0]) else if ( no_new_proxies ) { finish = 0; break; } else REASSIGN(grid[0][1][0]) else REASSIGN(grid[1][0][0]) else REASSIGN(grid[0][0][0]) // else REASSIGN(grid[0][1][1]) // else REASSIGN(grid[1][0][1]) // else REASSIGN(grid[0][0][1]) if (bestP) { if (bestP->load > averageLoad) lightProcessors->remove(bestP); if (donor->load > thresholdLoad) heavyProcessors->insert((InfoRecord *) donor); else lightProcessors->insert((InfoRecord *) donor); continue; } } if ( no_new_proxies ) iout << iINFO << "ERROR: Rebalancer::refine() algorithm is broken.\n" << endi; // no luck, do it the long way //find the best pair (c,receiver) Iterator nextProcessor; processorInfo *p = (processorInfo *) lightProcessors->iterator((Iterator *) &nextProcessor); while (p) { Iterator nextCompute; nextCompute.id = 0; computeInfo *c = (computeInfo *) donor->computeSet.iterator((Iterator *)&nextCompute); while (c) { #if USE_TOPOMAP int flag = tmgr.areNeighbors(p->Id, patches[c->patch1].processor, patches[c->patch2].processor, 8); if(flag) #endif { refine_togrid(grid, thresholdLoad, p, c); } nextCompute.id++; c = (computeInfo *) donor->computeSet. next((Iterator *)&nextCompute); } p = (processorInfo *) lightProcessors->next((Iterator *) &nextProcessor); } //we have narrowed the choice to 6 candidates. // prefer proxies to home patches { processorInfo* bestP = 0; REASSIGN(grid[0][2][0]) else REASSIGN(grid[1][1][0]) else REASSIGN(grid[2][0][0]) else REASSIGN(grid[0][1][0]) else REASSIGN(grid[1][0][0]) else REASSIGN(grid[0][0][0]) // else REASSIGN(grid[0][1][1]) // else REASSIGN(grid[1][0][1]) // else REASSIGN(grid[0][0][1]) else { finish = 0; break; } if (bestP->load > averageLoad) lightProcessors->remove(bestP); if (donor->load > thresholdLoad) heavyProcessors->insert((InfoRecord *) donor); else lightProcessors->insert((InfoRecord *) donor); } } #if LDB_DEBUG iout << "After Refinement Summary" << "\n"; printSummary(); if (!finish) { iout << iINFO << "Refine: No solution found for overLoad = " << overLoad << "\n" << endi; } #endif delete heavyProcessors; delete lightProcessors; return finish; }

void Rebalancer::refine_togrid (  pcgrid &  grid, double  thresholdLoad, processorInfo *  p, computeInfo *  c )  [protected]

Definition at line 526 of file Rebalancer.C. References processorInfo::available, Rebalancer::pcpair::c, InfoRecord::load, numAvailable(), Rebalancer::pcpair::p, and pcgrid. Referenced by refine(). { if(p->available == CmiFalse) return; if ( c->load + p->load < thresholdLoad) { int nPatches, nProxies, badForComm; numAvailable(c,p,&nPatches,&nProxies,&badForComm); // if ( badForComm ) return; pcpair *pair = &grid[nPatches][nProxies][badForComm]; if (! pair->c) { pair->c = c; pair->p = p; } else { double newval = p->load - c->load; if ( c->load + p->load < averageLoad ) { newval -= averageLoad; } double oldval = pair->p->load - pair->c->load; if ( pair->c->load + pair->p->load < averageLoad ) { oldval -= averageLoad; } if (newval < oldval) { pair->c = c; pair->p = p; } } } }

void Rebalancer::strategy (   )  [protected]

Definition at line 229 of file Rebalancer.C. References iINFO(), and iout. Referenced by Alg7::Alg7(), AlgNbor::AlgNbor(), AlgRecBisection::AlgRecBisection(), RefineOnly::RefineOnly(), RefineTorusLB::RefineTorusLB(), and TorusLB::TorusLB(). { iout << iINFO << "Strategy not implemented for the base class.\n" << "\n"; }

int Rebalancer::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 )  [inline, protected]

withinBrick This function returns whether a particular coordinate is within the region defined by xm, xM, ym, yM, zm, zM Definition at line 197 of file Rebalancer.h. { int wbX, wbY, wbZ; if( ((x >= xm) && (x <= xM)) || ((x < xm) && (x+dimX <= xM)) ) wbX = 1; else return 0; if( ((y >= ym) && (y <= yM)) || ((y < ym) && (y+dimY <= yM)) ) wbY = 1; else return 0; if( ((z >= zm) && (z <= zM)) || ((z < zm) && (z+dimZ <= zM)) ) wbZ = 1; else return 0; //if( wbX && wbY && wbZ) return 1; }

---

Member Data Documentation

double Rebalancer::averageLoad [protected]

Definition at line 140 of file Rebalancer.h. Referenced by computeAverage(), and printLoads().

int Rebalancer::bytesPerAtom [protected]

Definition at line 123 of file Rebalancer.h. Referenced by Rebalancer().

maxHeap* Rebalancer::computeBgPairHeap [protected]

Definition at line 133 of file Rebalancer.h. Referenced by makeHeaps(), and Rebalancer().

maxHeap* Rebalancer::computeBgSelfHeap [protected]

Definition at line 134 of file Rebalancer.h. Referenced by makeHeaps(), and Rebalancer().

maxHeap* Rebalancer::computePairHeap [protected]

Definition at line 131 of file Rebalancer.h. Referenced by makeHeaps(), makeTwoHeaps(), and Rebalancer().

computeInfo* Rebalancer::computes [protected]

Definition at line 127 of file Rebalancer.h. Referenced by computeAverage(), makeHeaps(), makeTwoHeaps(), Rebalancer(), and ~Rebalancer().

maxHeap* Rebalancer::computeSelfHeap [protected]

Definition at line 132 of file Rebalancer.h. Referenced by makeHeaps(), makeTwoHeaps(), and Rebalancer().

int Rebalancer::firstAssignInRefine [protected]

Definition at line 142 of file Rebalancer.h. Referenced by Rebalancer().

int Rebalancer::numComputes [protected]

Definition at line 137 of file Rebalancer.h. Referenced by Rebalancer().

int Rebalancer::numPatches [protected]

Definition at line 136 of file Rebalancer.h. Referenced by numAvailable(), and Rebalancer().

int Rebalancer::numPesAvailable [protected]

Definition at line 139 of file Rebalancer.h. Referenced by adjustBackgroundLoadAndComputeAverage(), computeAverage(), numAvailable(), and Rebalancer().

int Rebalancer::numProxies [protected]

Definition at line 138 of file Rebalancer.h. Referenced by assign(), deAssign(), InitProxyUsage(), and numAvailable().

double Rebalancer::origMaxLoad [protected]

Definition at line 141 of file Rebalancer.h. Referenced by Rebalancer().

double Rebalancer::overLoad [protected]

Definition at line 166 of file Rebalancer.h. Referenced by multirefine(), Rebalancer(), and refine().

int Rebalancer::P [protected]

Definition at line 135 of file Rebalancer.h. Referenced by makeHeaps(), makeTwoHeaps(), Rebalancer(), refine(), and ~Rebalancer().

patchInfo* Rebalancer::patches [protected]

Definition at line 128 of file Rebalancer.h. Referenced by assign(), createSpanningTree(), deAssign(), InitProxyUsage(), makeHeaps(), numAvailable(), Rebalancer(), and refine().

minHeap* Rebalancer::pes [protected]

Definition at line 130 of file Rebalancer.h. Referenced by makeHeaps(), makeTwoHeaps(), and Rebalancer().

processorInfo* Rebalancer::processors [protected]

Definition at line 129 of file Rebalancer.h. Referenced by adjustBackgroundLoadAndComputeAverage(), assign(), computeAverage(), computeMax(), deAssign(), decrSTLoad(), incrSTLoad(), InitProxyUsage(), makeHeaps(), makeTwoHeaps(), multirefine(), numAvailable(), printLoads(), printSummary(), Rebalancer(), refine(), and ~Rebalancer().

ProxyUsage Rebalancer::proxyUsage [protected]

Definition at line 125 of file Rebalancer.h. Referenced by assign(), deAssign(), and InitProxyUsage().

const char* Rebalancer::strategyName [protected]

Definition at line 126 of file Rebalancer.h. Referenced by printLoads(), and Rebalancer().

---

The documentation for this class was generated from the following files:

• Rebalancer.h
• Rebalancer.C

---