AlgSeven.C

Go to the documentation of this file.

/*****************************************************************************
 * $Source: /home/cvs/namd/cvsroot/namd2/src/AlgSeven.C,v $
 * $Author: bhatele $
 * $Date: 2007/11/01 17:39:53 $
 * $Revision: 1.55 $
 *****************************************************************************/

#include "common.h"
#include "InfoStream.h"
#include "Node.h"
#include "Alg7.h"

#define TINYLOAD 0.0005

Alg7::Alg7(computeInfo *computeArray, patchInfo *patchArray, 
           processorInfo *processorArray, int nComps, 
           int nPatches, int nPes) :
  Rebalancer(computeArray, patchArray, 
             processorArray, nComps, 
             nPatches, nPes)
{
strategyName = "Alg7";
strategy();
}

extern int isPmeProcessor(int);

void Alg7::togrid(processorInfo* goodP[3][3][2], processorInfo* poorP[3][3][2],
                        processorInfo *p, computeInfo *c) {
      if(p->available == CmiFalse) return;

      int nPatches, nProxies, badForComm;
      numAvailable(c,p,&nPatches,&nProxies,&badForComm);

      if (c->load + p->load < overLoad*averageLoad) {
        processorInfo* &altp = goodP[nPatches][nProxies][badForComm];   

#if USE_TOPOMAP 
        if(!altp)
          altp = p;
        else {
          //Find processors that are patch neighbors on the BGL torus
          int neighbor = 0, neighbor_alt = 0;
          
          /*
            if((tmgr->isNeighbor(altp->Id, patches[c->patch1].processor) ||
            tmgr->isNeighbor(altp->Id, patches[c->patch2].processor)))
            neighbor_alt = 1;
            
            if(tmgr->isNeighbor(p->Id, patches[c->patch1].processor) ||
            tmgr->isNeighbor(p->Id, patches[c->patch2].processor))
            neighbor = 1;
          */
          
          if(tmgr.areNeighbors(altp->Id, patches[c->patch1].processor,
                                    patches[c->patch2].processor, 4))
            neighbor_alt = 1;
          
          if(tmgr.areNeighbors(p->Id, patches[c->patch1].processor, 
                                    patches[c->patch2].processor, 4))
            neighbor = 1;
          
          if(neighbor_alt == 1 && neighbor == 1) {
            //Both are neighbors, only replace if lighter
            if (p->load < altp->load ) {
              altp = p;
            }
          }
          else if(neighbor_alt == 0 && neighbor == 1)
            //Previous was not a neighbor, kick him out
            altp = p;
          else if(neighbor_alt == 1 && neighbor == 0)
            ;      //Give preference to good neighbors
          else {
            //Both not neighbors, choose nearby node to minimize hop bytes
            /*
              if (!altp || p->load < altp->load ) {
              altp = p;
              }
            */

            int alt_dist = 0, dist = 0;     
            int ax,ay,az, x,y,z, p1x,p1y,p1z, p2x,p2y,p2z;
            
            tmgr.rankToCoordinates(altp->Id, ax,ay,az);
            tmgr.rankToCoordinates(p->Id, x,y,z);
            tmgr.rankToCoordinates(patches[c->patch1].processor, p1x, p1y, p1z);
            tmgr.rankToCoordinates(patches[c->patch2].processor, p2x, p2y, p2z);
 
            alt_dist = abs(p1x - ax) + abs(p2x - ax) +
              abs(p1y - ay) + abs(p1z - az) +
              abs(p2y - ay) + abs(p2z - az);
            
            dist = abs(p1x - x) + abs(p2x - x) +
              abs(p1y - y) + abs(p1z - z) +
              abs(p2y - y) + abs(p2z - z);
            
            if(alt_dist > dist)
              altp = p;   
          }
        }
#else 
        if (!altp || p->load < altp->load ) {   
          altp = p;
        }
#endif    
      }

      {
        processorInfo* &altp = poorP[nPatches][nProxies][badForComm];
        if (!altp || p->load < altp->load ) {
          altp = p;
        }
      }
}

void Alg7::strategy()
{
  // double bestSize0, bestSize1, bestSize2;
  computeInfo *c;
  int numAssigned;
  processorInfo* goodP[3][3][2];  // goodP[# of real patches][# of proxies]
  processorInfo* poorP[3][3][2];  // fallback option

  double startTime = CmiWallTimer();

  //   iout << iINFO  << "calling makeHeaps. \n";
  adjustBackgroundLoadAndComputeAverage();
  makeHeaps();
  //   iout << iINFO
  //    << "Before assignment\n" << endi;
  //   printLoads();

  /*
  int numOverloaded = 0;
  for (int ip=0; ip<P; ip++) {
    if ( processors[ip].backgroundLoad > averageLoad ) ++numOverloaded;
  }
  if ( numOverloaded ) {
    iout << iWARN << numOverloaded
      << " processors are overloaded due to background load.\n" << endi;
  }
  */
              
  numAssigned = 0;

  //   for (int i=0; i<numPatches; i++)
  //     { std::cout << "(" << patches[i].Id << "," << patches[i].processor ;}
  overLoad = 1.2;
  for (int ic=0; ic<numComputes; ic++) {

    // place computes w/ patches on heavily background loaded nodes first
    // place pair before self, because self is more flexible
    c = (computeInfo *) computeBgPairHeap->deleteMax();
    if ( ! c ) c = (computeInfo *) computeBgSelfHeap->deleteMax();
    if ( ! c ) c = (computeInfo *) computePairHeap->deleteMax();
    if ( ! c ) c = (computeInfo *) computeSelfHeap->deleteMax();

    if (c->processor != -1) continue; // skip to the next compute;

    if ( ! c ) NAMD_bug("Alg7: computesHeap empty!");
    int i,j,k;
    for(i=0;i<3;i++)
      for(j=0;j<3;j++) {
        for(k=0;k<2;k++) {
          goodP[i][j][k]=0;
          poorP[i][j][k]=0;
        }
      }

    // first try for at least one proxy
    {
      Iterator nextProc;
      processorInfo *p;

      p = &processors[patches[c->patch1].processor];
      togrid(goodP, poorP, p, c);

      p = &processors[patches[c->patch2].processor];
      togrid(goodP, poorP, p, c);

      p = (processorInfo *)patches[c->patch1].
                            proxiesOn.iterator((Iterator *)&nextProc);
      while (p) {
        togrid(goodP, poorP, p, c);
        p = (processorInfo *)patches[c->patch1].
                            proxiesOn.next((Iterator*)&nextProc);
      }

      p = (processorInfo *)patches[c->patch2].
                            proxiesOn.iterator((Iterator *)&nextProc);
      while (p) {
        togrid(goodP, poorP, p, c);
        p = (processorInfo *)patches[c->patch2].
                            proxiesOn.next((Iterator*)&nextProc);
      }
      p = 0;
      // prefer to place compute with existing proxies over home patches
      if ((p = goodP[0][2][0])    // No home, two proxies
       || (p = goodP[1][1][0])    // One home, one proxy
       || (p = goodP[2][0][0])    // Two home, no proxies
       || (p = goodP[0][1][0])    // No home, one proxy
       || (p = goodP[1][0][0])    // One home, no proxies
       || (p = goodP[0][0][0])    // No home, no proxies
       || (p = goodP[0][1][1])    // No home, one proxy
       || (p = goodP[1][0][1])    // One home, no proxies
       || (p = goodP[0][0][1])    // No home, no proxies
         ) {
        assign(c,p); numAssigned++;
        continue;
      }
    }

    // no luck, do it the long way

    heapIterator nextProcessor;
    processorInfo *p = (processorInfo *) 
      pes->iterator((heapIterator *) &nextProcessor);
    while (p) {
      togrid(goodP, poorP, p, c);
      p = (processorInfo *) pes->next(&nextProcessor);
    }

    //    if (numAssigned >= 0) {  Else is commented out below

    p = 0;
      // prefer to place compute with existing proxies over home patches
      if ((p = goodP[0][2][0])    // No home, two proxies
       || (p = goodP[1][1][0])    // One home, one proxy
       || (p = goodP[2][0][0])    // Two home, no proxies
       || (p = goodP[0][1][0])    // No home, one proxy
       || (p = goodP[1][0][0])    // One home, no proxies
       || (p = goodP[0][0][0])    // No home, no proxies
       || (p = goodP[0][1][1])    // No home, one proxy
       || (p = goodP[1][0][1])    // One home, no proxies
       || (p = goodP[0][0][1])    // No home, no proxies
       ) {
      assign(c,p); numAssigned++;
   } else if (   // overloaded processors
          (p = poorP[0][2][0])    // No home, two proxies
       || (p = poorP[1][1][0])    // One home, one proxy
       || (p = poorP[2][0][0])    // Two home, no proxies
       || (p = poorP[0][1][0])    // No home, one proxy
       || (p = poorP[1][0][0])    // One home, no proxies
       || (p = poorP[0][0][0])    // No home, no proxies
       || (p = poorP[0][1][1])    // No home, one proxy
       || (p = poorP[1][0][1])    // One home, no proxies
       || (p = poorP[0][0][1])    // No home, no proxies
       ) {
      //iout << iWARN << "overload assign to " << p->Id << "\n" << endi;
      assign(c,p); numAssigned++;
    } else {
      NAMD_bug("*** Alg 7 No receiver found 1 ***");
      break;
    }
  }

  printLoads();

  // binary-search refinement procedure
  multirefine(1.05);
  printLoads();

}

---