src/ck-ldb/GreedyLB.C

   1 /**
   2  * \addtogroup CkLdb
   3 */
   4 /*@{*/
   5
   6 /*
   7  status:
   8   * support processor avail bitvector
   9   * support nonmigratable attrib
  10       nonmigratable object load is added to its processor's background load
  11       and the nonmigratable object is not taken in the objData array
  12 */
  13
  14 #include <algorithm>
  15
  16 #include "charm++.h"
  17
  18
  19 #include "ckgraph.h"
  20 #include "cklists.h"
  21 #include "GreedyLB.h"
  22
  23 using namespace std;
  24
  25 CreateLBFunc_Def(GreedyLB, "always assign the heaviest obj onto lightest loaded processor.")
  26
  27 GreedyLB::GreedyLB(const CkLBOptions &opt): CBase_GreedyLB(opt)
  28 {
  29   lbname = "GreedyLB";
  30   if (CkMyPe()==0)
  31     CkPrintf("[%d] GreedyLB created\n",CkMyPe());
  32 }
  33
  34 bool GreedyLB::QueryBalanceNow(int _step)
  35 {
  36   //  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
  37   return true;
  38 }
  39
  40 class ProcLoadGreater {
  41   public:
  42     bool operator()(const ProcInfo &p1, const ProcInfo &p2) {
  43       return (p1.getTotalLoad() > p2.getTotalLoad());
  44     }
  45 };
  46
  47 class ObjLoadGreater {
  48   public:
  49     bool operator()(const Vertex &v1, const Vertex &v2) {
  50       return (v1.getVertexLoad() > v2.getVertexLoad());
  51     }
  52 };
  53
  54 void GreedyLB::work(LDStats* stats)
  55 {
  56   int  obj, objCount, pe;
  57   int n_pes = stats->nprocs();
  58   int *map = new int[n_pes];
  59
  60   std::vector<ProcInfo>  procs;
  61   for(pe = 0; pe < n_pes; pe++) {
  62     map[pe] = -1;
  63     if (stats->procs[pe].available) {
  64       map[pe] = procs.size();
  65       procs.push_back(ProcInfo(pe, stats->procs[pe].bg_walltime, 0.0, stats->procs[pe].pe_speed, true));
  66     }
  67   }
  68
  69   // take non migratbale object load as background load
  70   for (obj = 0; obj < stats->n_objs; obj++)
  71   {
  72       LDObjData &oData = stats->objData[obj];
  73       if (!oData.migratable)  {
  74         int pe = stats->from_proc[obj];
  75         pe = map[pe];
  76         if (pe==-1)
  77           CmiAbort("GreedyLB: nonmigratable object on an unavail processor!\n");
  78         procs[pe].totalLoad() += oData.wallTime;
  79       }
  80   }
  81   delete [] map;
  82
  83   // Add the overhead to the total load
  84   for (pe = 0; pe<procs.size(); pe++) {
  85     procs[pe].totalLoad() +=  procs[pe].overhead();
  86   }
  87
  88   // build object array
  89   std::vector<Vertex> objs;
  90
  91   for(int obj = 0; obj < stats->n_objs; obj++) {
  92     LDObjData &oData = stats->objData[obj];
  93     int pe = stats->from_proc[obj];
  94     if (!oData.migratable) {
  95       if (!stats->procs[pe].available)
  96         CmiAbort("GreedyLB cannot handle nonmigratable object on an unavial processor!\n");
  97       continue;
  98     }
  99     double load = oData.wallTime * stats->procs[pe].pe_speed;
 100     objs.push_back(Vertex(obj, load, stats->objData[obj].migratable, stats->from_proc[obj]));
 101   }
 102
 103   // max heap of objects
 104   sort(objs.begin(), objs.end(), ObjLoadGreater());
 105   // min heap of processors
 106   make_heap(procs.begin(), procs.end(), ProcLoadGreater());
 107
 108   if (_lb_args.debug()>1)
 109     CkPrintf("[%d] In GreedyLB strategy\n",CkMyPe());
 110
 111
 112     // greedy algorithm
 113   int nmoves = 0;
 114   for (obj=0; obj < objs.size(); obj++) {
 115     ProcInfo p = procs.front();
 116     pop_heap(procs.begin(), procs.end(), ProcLoadGreater());
 117     procs.pop_back();
 118
 119     // Increment the time of the least loaded processor by the cpuTime of
 120     // the `heaviest' object
 121     p.totalLoad() += objs[obj].getVertexLoad() / p.pe_speed();
 122
 123     //Insert object into migration queue if necessary
 124     const int dest = p.getProcId();
 125     const int pe   = objs[obj].getCurrentPe();
 126     const int id   = objs[obj].getVertexId();
 127     if (dest != pe) {
 128       stats->to_proc[id] = dest;
 129       nmoves ++;
 130       if (_lb_args.debug()>2)
 131         CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),objs[obj].getVertexId(),pe,dest);
 132     }
 133
 134     //Insert the least loaded processor with load updated back into the heap
 135     procs.push_back(p);
 136     push_heap(procs.begin(), procs.end(), ProcLoadGreater());
 137   }
 138
 139   if (_lb_args.debug()>0)
 140     CkPrintf("[%d] %d objects migrating.\n", CkMyPe(), nmoves);
 141
 142   if (_lb_args.debug()>1)  {
 143     CkPrintf("CharmLB> Min obj: %f  Max obj: %f\n", objs[objs.size()-1].getVertexLoad(), objs[0].getVertexLoad());
 144     CkPrintf("CharmLB> PE speed:\n");
 145     for (pe = 0; pe<procs.size(); pe++)
 146       CkPrintf("%f ", procs[pe].pe_speed());
 147     CkPrintf("\n");
 148     CkPrintf("CharmLB> PE Load:\n");
 149     for (pe = 0; pe<procs.size(); pe++)
 150       CkPrintf("%f (%f)  ", procs[pe].totalLoad(), procs[pe].overhead());
 151     CkPrintf("\n");
 152   }
 153
 154   if (_lb_args.metaLbOn()) {
 155     double max_load = 0;
 156     double avg_load = 0;
 157     for (pe = 0; pe<procs.size(); pe++) {
 158       if (procs[pe].totalLoad() > max_load) {
 159         max_load = procs[pe].totalLoad();
 160       }
 161       avg_load += procs[pe].totalLoad();
 162     }
 163
 164     stats->after_lb_max = max_load;
 165     stats->after_lb_avg = avg_load/procs.size();
 166     stats->is_prev_lb_refine = 0;
 167     if (_lb_args.debug() > 0)
 168       CkPrintf("GreedyLB> After lb max load: %lf avg load: %lf\n", max_load, avg_load/procs.size());
 169   }
 170 }
 171
 172 #include "GreedyLB.def.h"
 173
 174 /*@}*/
 175
 176
 177
 178