rewrite GreedyLB to consider migratable obj flag, PE avail bitvector and PE spee
authorGengbin Zheng <gzheng@illinois.edu>
Wed, 21 Dec 2011 06:15:14 +0000 (00:15 -0600)
committerGengbin Zheng <gzheng@illinois.edu>
Wed, 21 Dec 2011 06:15:14 +0000 (00:15 -0600)
d.
change the default as that no pe speed is measured unless runtime option +LBTestPESpeed presents.

src/ck-ldb/BaseLB.C
src/ck-ldb/BaseLB.h
src/ck-ldb/CentralLB.C
src/ck-ldb/GraphBFTLB.C
src/ck-ldb/GreedyLB.C
src/ck-ldb/LBDatabase.C
src/ck-ldb/LBDatabase.h
src/ck-ldb/RecBipartLB.C
src/ck-ldb/TreeMatchLB.C
src/ck-ldb/ckgraph.C
src/ck-ldb/ckgraph.h

index 6c1f8aecdc83bdb28325ffa136a1ff44e6122708..162a9ff6f3bd0958d81bb5acc08e42330b372aa4 100644 (file)
@@ -295,6 +295,17 @@ void BaseLB::LDStats::computeNonlocalComm(int &nmsgs, int &nbytes)
 #endif
 }
 
+void BaseLB::LDStats::normalize_speed() {
+  int pe;
+  double maxspeed = 0.0;
+
+  for(int pe=0; pe < nprocs(); pe++) {
+    if (procs[pe].pe_speed > maxspeed) maxspeed = procs[pe].pe_speed;
+  }
+  for(int pe=0; pe < nprocs(); pe++)
+    procs[pe].pe_speed /= maxspeed;
+}
+
 void BaseLB::LDStats::print()
 {
 #if CMK_LBDB_ON
index 0ddcce18a57f4541f5337d08ddde9e9b52e67f49..36456dc750116c7dac1e95bdac18fcbd482d990a 100644 (file)
@@ -33,7 +33,7 @@ private:
 public:
   struct ProcStats {           // per processor data
     int n_objs;                        // number of objects on the processor
-    int pe_speed;              // processor frequency
+    double pe_speed;           // processor frequency
     /// total time (total_walltime) = idletime + overhead (bg_walltime)
     ///                             + object load (obj_walltime)
     /// walltime and cputime may be different on shared compute nodes
@@ -132,6 +132,7 @@ public:
     }
     void computeNonlocalComm(int &nmsgs, int &nbytes);
     double computeAverageLoad();
+    void normalize_speed();
     void print();
     // edit functions
     void removeObject(int obj);
index 1257ea7efcc06b66428244108a44fc414c2f5bb5..a7c96b706f490c282b3bba4e3badf98f8fd77fdf 100644 (file)
@@ -551,6 +551,8 @@ void CentralLB::LoadBalance()
   for (proc = 0; proc < clients; proc++) statsMsgsList[proc] = NULL;
 #endif
 
+  if (!_lb_args.samePeSpeed()) statsData->normalize_speed();
+
   if (_lb_args.debug()) 
       CmiPrintf("\nCharmLB> %s: PE [%d] step %d starting at %f Memory: %f MB\n",
                  lbname, cur_ld_balancer, step(), start_lb_time,
@@ -1042,7 +1044,7 @@ LBMigrateMsg* CentralLB::Strategy(LDStats* stats)
 
   work(stats);
 
-  if (_lb_args.debug()>1)  {
+  if (_lb_args.debug()>2)  {
     CkPrintf("CharmLB> Obj Map:\n");
     for (int i=0; i<stats->n_objs; i++) CkPrintf("%d ", stats->to_proc[i]);
     CkPrintf("\n");
index 824212b7138a7035dd134a7382bac1807b225270..5de362c0fcbe2692f37cc90555b4007b7bbc1297 100644 (file)
@@ -52,7 +52,7 @@ void GraphBFTLB::work(LDStats *stats) {
   }
   ogr->vertices[start].setNewPe(nextPe);
   // CkPrintf("[%d] %d %d %g %g %g\n", start, ogr->vertices[start].getCurrentPe(), ogr->vertices[start].getNewPe(), parr->procs[nextPe].getTotalLoad(), ogr->vertices[start].getVertexLoad(), parr->procs[nextPe].getTotalLoad() + ogr->vertices[start].getVertexLoad());
-  parr->procs[nextPe].setTotalLoad(parr->procs[nextPe].getTotalLoad() + ogr->vertices[start].getVertexLoad());
+  parr->procs[nextPe].totalLoad() += ogr->vertices[start].getVertexLoad();
 
   int i, nbr;
   // breadth first traversal
@@ -73,7 +73,7 @@ void GraphBFTLB::work(LDStats *stats) {
        }
        ogr->vertices[nbr].setNewPe(nextPe);
        // CkPrintf("[%d] %d %d %g %g %g\n", nbr, ogr->vertices[nbr].getCurrentPe(), ogr->vertices[nbr].getNewPe(), parr->procs[nextPe].getTotalLoad(), ogr->vertices[start].getVertexLoad(), parr->procs[nextPe].getTotalLoad() + ogr->vertices[start].getVertexLoad());
-       parr->procs[nextPe].setTotalLoad(parr->procs[nextPe].getTotalLoad() + ogr->vertices[nbr].getVertexLoad());
+       parr->procs[nextPe].totalLoad() += ogr->vertices[nbr].getVertexLoad();
       }
     } // end of for loop
   } // end of while loop
index a562f03a3551859796de8e6d687817768508d5f4..8e6a80298391d1279a3ecedfcfeff47a9b164390 100644 (file)
@@ -1,22 +1,32 @@
-/** \file GreedyLB.C
- *
- *  Written by Gengbin Zheng
- *  Updated by Abhinav Bhatele, 2010-12-09 to use ckgraph
- *
- *  Status:
- *    -- Does not support pe_speed's currently
- *    -- Does not support nonmigratable attribute
- */
+/*****************************************************************************
+ * $Source$
+ * $Author$
+ * $Date$
+ * $Revision$
+ *****************************************************************************/
 
 /**
  * \addtogroup CkLdb
 */
 /*@{*/
 
-#include "GreedyLB.h"
-#include "ckgraph.h"
+/*
+ status:
+  * support processor avail bitvector
+  * support nonmigratable attrib
+      nonmigratable object load is added to its processor's background load
+      and the nonmigratable object is not taken in the objData array
+*/
+
 #include <algorithm>
 
+#include "charm++.h"
+
+
+#include "ckgraph.h"
+#include "cklists.h"
+#include "GreedyLB.h"
+
 CreateLBFunc_Def(GreedyLB, "always assign the heaviest obj onto lightest loaded processor.")
 
 GreedyLB::GreedyLB(const CkLBOptions &opt): CentralLB(opt)
@@ -35,7 +45,7 @@ CmiBool GreedyLB::QueryBalanceNow(int _step)
 class ProcLoadGreater {
   public:
     bool operator()(ProcInfo p1, ProcInfo p2) {
-      return (p1.getTotalLoad() > p2.getTotalLoad());
+      return (p1.totalLoad() > p2.totalLoad());
     }
 };
 
@@ -48,44 +58,111 @@ class ObjLoadGreater {
 
 void GreedyLB::work(LDStats* stats)
 {
-  /** ========================== INITIALIZATION ============================= */
-  ProcArray *parr = new ProcArray(stats);       // Processor Array
-  ObjGraph *ogr = new ObjGraph(stats);          // Object Graph
+  int  obj, objCount, pe;
+  int n_pes = stats->nprocs();
+  int *map = new int[n_pes];
+
+  std::vector<ProcInfo>  procs;
+  for(pe = 0; pe < n_pes; pe++) {
+    map[pe] = -1;
+    if (stats->procs[pe].available) {
+      map[pe] = procs.size();
+      procs.push_back(ProcInfo(pe, stats->procs[pe].bg_walltime, 0.0, stats->procs[pe].pe_speed, true));
+    }
+  }
 
-  /** ============================= STRATEGY ================================ */
-  parr->resetTotalLoad();
+  // take non migratbale object load as background load
+  for (obj = 0; obj < stats->n_objs; obj++)
+  {
+      LDObjData &oData = stats->objData[obj];
+      if (!oData.migratable)  {
+        int pe = stats->from_proc[obj];
+        pe = map[pe];
+        if (pe==-1)
+          CmiAbort("GreedyLB: nonmigratable object on an unavail processor!\n");
+        procs[pe].totalLoad() += oData.wallTime;
+      }
+  }
+  delete [] map;
 
-  if (_lb_args.debug()>1) 
-    CkPrintf("[%d] In GreedyLB strategy\n",CkMyPe());
+  // considering cpu speed
+  for (pe = 0; pe<procs.size(); pe++) {
+    procs[pe].totalLoad() +=  procs[pe].overhead();
+    procs[pe].totalLoad() *= procs[pe].pe_speed();
+  }
 
-  int vert;
+  // build object array
+  std::vector<Vertex> objs;
+
+  for(int obj = 0; obj < stats->n_objs; obj++) {
+    LDObjData &oData = stats->objData[obj];
+    int pe = stats->from_proc[obj];
+    if (!oData.migratable) {
+      if (!stats->procs[pe].available) 
+        CmiAbort("GreedyLB cannot handle nonmigratable object on an unavial processor!\n");
+      continue;
+    }
+    double load = oData.wallTime * stats->procs[pe].pe_speed;
+    objs.push_back(Vertex(obj, load, stats->objData[obj].migratable, stats->from_proc[obj]));
+  }
 
   // max heap of objects
-  std::sort(ogr->vertices.begin(), ogr->vertices.end(), ObjLoadGreater());
+  sort(objs.begin(), objs.end(), ObjLoadGreater());
   // min heap of processors
-  std::make_heap(parr->procs.begin(), parr->procs.end(), ProcLoadGreater());
-
-  for(vert = 0; vert < ogr->vertices.size(); vert++) {
-    // Pop the least loaded processor
-    ProcInfo p = parr->procs.front();
-    std::pop_heap(parr->procs.begin(), parr->procs.end(), ProcLoadGreater());
-    parr->procs.pop_back();
-
-    // Increment the load of the least loaded processor by the load of the
-    // 'heaviest' unmapped object
-    p.setTotalLoad(p.getTotalLoad() + ogr->vertices[vert].getVertexLoad());
-    ogr->vertices[vert].setNewPe(p.getProcId());
-
-    // Insert the least loaded processor with load updated back into the heap
-    parr->procs.push_back(p);
-    std::push_heap(parr->procs.begin(), parr->procs.end(), ProcLoadGreater());
+  make_heap(procs.begin(), procs.end(), ProcLoadGreater());
+
+  if (_lb_args.debug()>1) 
+    CkPrintf("[%d] In GreedyLB strategy\n",CkMyPe());
+
+
+    // greedy algorithm
+  int nmoves = 0;
+  for (obj=0; obj < objs.size(); obj++) {
+    ProcInfo p = procs.front();
+    pop_heap(procs.begin(), procs.end(), ProcLoadGreater());
+    procs.pop_back();
+
+    // Increment the time of the least loaded processor by the cpuTime of
+    // the `heaviest' object
+    p.totalLoad() += objs[obj].getVertexLoad();
+
+    //Insert object into migration queue if necessary
+    const int dest = p.getProcId();
+    const int pe   = objs[obj].getCurrentPe();
+    const int id   = objs[obj].getVertexId();
+    if (dest != pe) {
+      stats->to_proc[id] = dest;
+      nmoves ++;
+      if (_lb_args.debug()>2) 
+        CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),objs[obj].getVertexId(),pe,dest);
+    }
+
+    //Insert the least loaded processor with load updated back into the heap
+    procs.push_back(p);
+    push_heap(procs.begin(), procs.end(), ProcLoadGreater());
+  }
+
+  if (_lb_args.debug()>0) 
+    CkPrintf("[%d] %d objects migrating.\n", CkMyPe(), nmoves);
+
+  if (_lb_args.debug()>1)  {
+    CkPrintf("CharmLB> Min obj: %f  Max obj: %f\n", objs[objs.size()-1].getVertexLoad(), objs[0].getVertexLoad());
+    CkPrintf("CharmLB> PE speed:\n");
+    for (pe = 0; pe<procs.size(); pe++)
+      CkPrintf("%f ", procs[pe].pe_speed());
+    CkPrintf("\n");
+    CkPrintf("CharmLB> PE Load:\n");
+    for (pe = 0; pe<procs.size(); pe++)
+      CkPrintf("%f (%f)  ", procs[pe].totalLoad(), procs[pe].overhead());
+    CkPrintf("\n");
   }
 
-  /** ============================== CLEANUP ================================ */
-  ogr->convertDecisions(stats);         // Send decisions back to LDStats
 }
 
 #include "GreedyLB.def.h"
 
 /*@}*/
 
+
+
+
index 4cdf67685a69a00cf6a3def6aec20116a6a0332e..5ff8559ef4b3d5d2316d2892af57c87e3f6ebab1 100644 (file)
@@ -257,8 +257,11 @@ void _loadbalancerInit()
   if (_lb_args.migObjOnly()) _lb_args.ignoreBgLoad() = 1;
 
   // assume all CPUs are identical
+  _lb_args.testPeSpeed() = CmiGetArgFlagDesc(argv, "+LBTestPESpeed", 
+                      "Load balancer test all CPUs speed.");
   _lb_args.samePeSpeed() = CmiGetArgFlagDesc(argv, "+LBSameCpus", 
                       "Load balancer assumes all CPUs are of same speed.");
+  if (!_lb_args.testPeSpeed()) _lb_args.samePeSpeed() = 1;
 
   _lb_args.useCpuTime() = CmiGetArgFlagDesc(argv, "+LBUseCpuTime", 
                       "Load balancer uses CPU time instead of wallclock time.");
index a110dbda3bee41d937309b7dfc59b3b8ad7f4c0f..9b02f0d67c03076ad8e0db0d97f2de2ec3228b7e 100644 (file)
@@ -28,6 +28,7 @@ private:
   int _lb_migObjOnly;          // only consider migratable objs
   int _lb_syncResume;
   int _lb_samePeSpeed;         // ignore cpu speed
+  int _lb_testPeSpeed;         // test cpu speed
   int _lb_useCpuTime;           // use cpu instead of wallclock time
   int _lb_statson;             // stats collection
   int _lb_traceComm;           // stats collection for comm
@@ -47,7 +48,7 @@ public:
     _lb_percentMovesAllowed=100;
     _lb_loop = 0;
     _lb_central_pe = 0;
-       _lb_teamSize = 1;
+    _lb_teamSize = 1;
   }
   inline double & lbperiod() { return _autoLbPeriod; }
   inline int & debug() { return _lb_debug; }
@@ -59,6 +60,7 @@ public:
   inline int & migObjOnly() { return _lb_migObjOnly; }
   inline int & syncResume() { return _lb_syncResume; }
   inline int & samePeSpeed() { return _lb_samePeSpeed; }
+  inline int & testPeSpeed() { return _lb_testPeSpeed; }
   inline int & useCpuTime() { return _lb_useCpuTime; }
   inline int & statsOn() { return _lb_statson; }
   inline int & traceComm() { return _lb_traceComm; }
index 99b8d3f15a35e67aefeeb5f9dc51c3fb742b5474..d4c9873c598285ab400eee9e9927cb99d9d50334 100644 (file)
@@ -200,11 +200,11 @@ void RecursiveBiPart(ObjGraph *ogr, vector<Vertex *> &pvertices, int parent, int
   //if the number of processors that this call has to deal with is 1, dont recurse any further
   if(nump==1)
   {
-    parray->procs[peno].setTotalLoad(0);
+    parray->procs[peno].totalLoad() = 0.0;
     for(int i=0;i<pvertices.size();i++)
     {
       pvertices[i]->setNewPe(peno);
-      parray->procs[peno].setTotalLoad(parray->procs[peno].getTotalLoad() + pvertices[i]->getVertexLoad());
+      parray->procs[peno].totalLoad() += pvertices[i]->getVertexLoad();
     }
     peno++;
 
index b5fb05c7517bd165e678a1727a43249833d71a7d..a7389f862d7399fe0b8da662f46f5047d4e23e85 100644 (file)
@@ -62,7 +62,7 @@ tm_topology_t *build_abe_topology(int nb_procs){
 class ProcLoadGreater {
   public:
     bool operator()(ProcInfo p1, ProcInfo p2) {
-      return (p1.getTotalLoad() > p2.getTotalLoad());
+      return (p1.totalLoad() > p2.totalLoad());
     }
 };
 
@@ -102,7 +102,7 @@ void TreeMatchLB::work(BaseLB::LDStats* stats)
 
     // Increment the load of the least loaded processor by the load of the
     // 'heaviest' unmapped object
-    p.setTotalLoad(p.getTotalLoad() + ogr->vertices[vert].getVertexLoad());
+    p.totalLoad() += ogr->vertices[vert].getVertexLoad();
     ogr->vertices[vert].setNewPe(p.getProcId());
 
     // Insert the least loaded processor with load updated back into the heap
index 95b5a8b59cd5aa499a47585dc31eef00efafa61c..895d97ab982c1f09ad7f75c8546cf74db26653ff 100644 (file)
@@ -24,17 +24,17 @@ ProcArray::ProcArray(BaseLB::LDStats *stats) {
   avgLoad = 0.0;
   for(int pe = 0; pe < numPes; pe++) {
     procs[pe].id        = stats->procs[pe].pe;
-    procs[pe].overhead  = stats->procs[pe].bg_walltime;
-    procs[pe].totalLoad = stats->procs[pe].total_walltime - stats->procs[pe].idletime;
+    procs[pe].overhead()  = stats->procs[pe].bg_walltime;
+    procs[pe].totalLoad() = stats->procs[pe].total_walltime - stats->procs[pe].idletime;
     procs[pe].available = stats->procs[pe].available;
-    avgLoad += procs[pe].totalLoad;
+    avgLoad += procs[pe].totalLoad();
   }
   avgLoad /= numPes;
 }
 
 void ProcArray::resetTotalLoad() {
   for(int pe = 0; pe < procs.size(); pe++)
-    procs[pe].totalLoad = procs[pe].overhead;
+    procs[pe].totalLoad() = procs[pe].overhead();
 }
 
 ObjGraph::ObjGraph(BaseLB::LDStats *stats) {
index 403945d0deed5739256750906d1ab2ee88bf78f2..c343c50343deb6bb0597119f2eb2e9cbbbcff9bb 100644 (file)
@@ -21,16 +21,24 @@ class ProcInfo {
   friend class ProcArray;
 
   public:
+    ProcInfo() {}
+    ProcInfo(int i, double ov, double tl, double sp, bool avail): id(i), _overhead(ov), _totalLoad(tl), _pe_speed(sp), available(avail) {}
     inline int getProcId() { return id; }
-    inline double getTotalLoad() { return totalLoad; }
-    inline double getOverhead() { return overhead; }
-    inline void setTotalLoad(double _tload) { totalLoad = _tload; }
+    inline void setProcId(int _id) { id = _id; }
+    inline double getTotalLoad() { return _totalLoad; }
+//    inline void setTotalLoad(double load) { totalLoad = load; }
+//    inline double getOverhead() { return overhead; }
+//    inline void setOverhead(double oh) { overhead = oh; }
+    inline double &overhead() { return _overhead; }
+    inline double &totalLoad() { return _totalLoad; }
+    inline double &pe_speed() { return _pe_speed; }
     inline bool isAvailable() { return available; }
 
   private:
     int id;            // CkMyPe of the processor
-    double overhead;   // previously called background load (bg_walltime)
-    double totalLoad;  // includes object_load + overhead
+    double _overhead;  // previously called background load (bg_walltime)
+    double _totalLoad; // includes object_load + overhead
+    double _pe_speed;  // CPU speed
     bool available;    // if the processor is available
 };
 
@@ -117,6 +125,8 @@ class Vertex {
   friend class ObjGraph;
 
   public:
+    Vertex() {}
+    Vertex(int i, double cl, bool mig, int curpe, int newpe=-1): id(i), compLoad(cl), migratable(mig), currPe(curpe), newPe(newpe)  {}
     inline int getVertexId() { return id; }
     inline double getVertexLoad() { return compLoad; }
     inline int getCurrentPe() { return currPe; }