src/ck-ldb/BaseLB.h

   1 /**
   2  \defgroup CkLdb  Charm++ Load Balancing Framework
   3 */
   4 /*@{*/
   5
   6 #ifndef BASELB_H
   7 #define BASELB_H
   8
   9 #include "LBDatabase.h"
  10
  11 #define PER_MESSAGE_SEND_OVERHEAD_DEFAULT   3.5e-5
  12 #define PER_BYTE_SEND_OVERHEAD_DEFAULT      8.5e-9
  13 #define PER_MESSAGE_RECV_OVERHEAD           0.0
  14 #define PER_BYTE_RECV_OVERHEAD              0.0
  15
  16 /// Base class for all LB strategies.
  17 /**
  18   BaseLB is the base class for all LB strategy class.
  19   it does some tracking about how many lb strategies are created.
  20   it also defines some common functions.
  21 */
  22 class BaseLB: public CBase_BaseLB
  23 {
  24 protected:
  25   int  seqno;
  26   const char *lbname;
  27   LBDatabase *theLbdb;
  28   LDBarrierReceiver receiver;
  29   int  notifier;
  30   int  startLbFnHdl;
  31 private:
  32   void initLB(const CkLBOptions &);
  33 public:
  34   struct ProcStats {            // per processor data
  35     int n_objs;                 // number of objects on the processor
  36     double pe_speed;            // processor frequency
  37 #if defined(TEMP_LDB)
  38         float pe_temp;
  39 #endif
  40
  41     /// total time (total_walltime) = idletime + overhead (bg_walltime)
  42     ///                             + object load (obj_walltime)
  43     /// walltime and cputime may be different on shared compute nodes
  44     /// it is advisable to use walltime in most cases
  45     double total_walltime;
  46     /// time for which the processor is sitting idle
  47     double idletime;
  48     /// bg_walltime called background load (overhead in ckgraph.h) is a
  49     /// derived quantity: total_walltime - idletime - object load (obj_walltime)
  50     double bg_walltime;
  51 #if CMK_LB_CPUTIMER
  52     double total_cputime;
  53     double bg_cputime;
  54 #endif
  55     // double utilization;
  56     int pe;                     // processor id
  57     bool available;
  58     ProcStats(): n_objs(0), pe_speed(1), total_walltime(0.0), idletime(0.0),
  59 #if CMK_LB_CPUTIMER
  60                  total_cputime(0.0), bg_cputime(0.0),
  61 #endif
  62                  bg_walltime(0.0), pe(-1), available(true) {}
  63     inline void clearBgLoad() {
  64       idletime = bg_walltime =
  65 #if CMK_LB_CPUTIMER
  66       bg_cputime =
  67 #endif
  68       0.0;
  69     }
  70     inline void pup(PUP::er &p) {
  71       p|total_walltime;
  72       p|idletime;
  73       p|bg_walltime;
  74 #if CMK_LB_CPUTIMER
  75       p|total_cputime;
  76       p|bg_cputime;
  77 #endif
  78       p|pe_speed;
  79       if (_lb_args.lbversion() < 1 && p.isUnpacking()) {
  80          double dummy;  p|dummy;    // for old format with utilization
  81       }
  82       p|available; p|n_objs;
  83       if (_lb_args.lbversion()>=2) p|pe;
  84     }
  85   };
  86
  87   /** Passed to the virtual functions Strategy(...) and work(...) */
  88   struct LDStats {
  89     int count;                  // number of processors in the array "procs"
  90     ProcStats *procs;           // processor statistics
  91
  92     int n_objs;                 // total number of objects in the vector "objData"
  93     int n_migrateobjs;          // total number of migratable objects
  94     CkVec<LDObjData> objData;   // LDObjData and LDCommData defined in lbdb.h
  95     CkVec<int> from_proc;       // current pe an object is on
  96     CkVec<int> to_proc;         // new pe you want the object to be on
  97
  98     int n_comm;                 // number of edges in the vector "commData"
  99     CkVec<LDCommData> commData; // communication data - edge list representation
 100                                 // of the communication between objects
 101
 102     int *objHash;               // this a map from the hash for the 4 integer
 103                                 // LDObjId to the index in the vector "objData"
 104     int  hashSize;
 105
 106     int complete_flag;          // if this ocg is complete, eg in HybridLB,
 107     // this LDStats may not be complete
 108
 109     int is_prev_lb_refine;
 110     double after_lb_max;
 111     double after_lb_avg;
 112
 113     LDStats(int c=0, int complete_flag=1);
 114     /// the functions below should be used to obtain the number of processors
 115     /// instead of accessing count directly
 116     inline int nprocs() const { return count; }
 117     inline int &nprocs() { return count; }
 118
 119     void assign(int oid, int pe) { CmiAssert(procs[pe].available); to_proc[oid] = pe; }
 120     /// build hash table
 121     void makeCommHash();
 122     void deleteCommHash();
 123     /// given an LDObjKey, returns the index in the objData vector
 124     /// this index changes every time one does load balancing even within a run
 125     int getHash(const LDObjKey &);
 126     int getHash(const LDObjid &oid, const LDOMid &mid);
 127     int getSendHash(LDCommData &cData);
 128     int getRecvHash(LDCommData &cData);
 129     void clearCommHash();
 130     void clear() {
 131       n_objs = n_migrateobjs = n_comm = 0;
 132       objData.free();
 133       commData.free();
 134       from_proc.free();
 135       to_proc.free();
 136       deleteCommHash();
 137     }
 138     void clearBgLoad() {
 139       for (int i=0; i<nprocs(); i++) procs[i].clearBgLoad();
 140     }
 141     void computeNonlocalComm(int &nmsgs, int &nbytes);
 142     double computeAverageLoad();
 143     void normalize_speed();
 144     void print();
 145     // edit functions
 146     void removeObject(int obj);
 147     void pup(PUP::er &p);
 148     int useMem();
 149   };
 150
 151   BaseLB(const CkLBOptions &opt)  { initLB(opt); }
 152   BaseLB(CkMigrateMessage *m):CBase_BaseLB(m) {
 153     theLbdb = CProxy_LBDatabase(_lbdb).ckLocalBranch();
 154   }
 155   virtual ~BaseLB();
 156
 157   void unregister();
 158   inline const char *lbName() { return lbname; }
 159   inline int step() { return theLbdb->step(); }
 160   virtual void turnOff() { CmiAbort("turnOff not implemented"); }
 161   virtual void turnOn()  { CmiAbort("turnOn not implemented"); }
 162   virtual int  useMem()  { return 0; }
 163   virtual void pup(PUP::er &p);
 164   virtual void flushStates();
 165
 166   CkGroupID getGroupID() {return thisgroup;}
 167 };
 168
 169 /// migration decision for an obj.
 170 struct MigrateInfo {
 171     int index;   // object index in objData array
 172     LDObjHandle obj;
 173     int from_pe;
 174     int to_pe;
 175     int async_arrival;      // if an object is available for immediate migrate
 176     MigrateInfo():  async_arrival(0) {
 177 #if CMK_GLOBAL_LOCATION_UPDATE
 178       obj.id.isArrayElement = 0;
 179 #endif
 180     }
 181
 182     void pup(PUP::er &p) {
 183       p | index;
 184       p | obj;
 185       p | from_pe;
 186       p | to_pe;
 187       p | async_arrival;
 188     }
 189 };
 190
 191 struct MigrateDecision {
 192   LDObjIndex dbIndex;
 193   int fromPe;
 194   int toPe;
 195
 196   MigrateDecision &operator=(const MigrateInfo &mInfo) {
 197     dbIndex = mInfo.obj.handle;
 198     fromPe = mInfo.from_pe;
 199     toPe = mInfo.to_pe;
 200
 201     return *this;
 202   }
 203
 204 };
 205
 206 class LBScatterMsg : public CMessage_LBScatterMsg {
 207 public:
 208   int numMigrates;
 209   int firstPeInSpan;
 210   int lastPeInSpan;
 211   int *numMigratesPerPe;
 212   MigrateDecision *moves;
 213
 214   LBScatterMsg(int firstPe, int lastPe) {
 215     numMigrates = 0;
 216     firstPeInSpan = firstPe;
 217     lastPeInSpan = lastPe;
 218   }
 219 };
 220
 221
 222
 223 /**
 224   message contains the migration decision from LB strategies.
 225 */
 226 class LBMigrateMsg : public CMessage_LBMigrateMsg {
 227 public:
 228   int level;                    // which level in hierarchy, used in hybridLB
 229
 230   int n_moves;                  // number of moves
 231   MigrateInfo* moves;
 232
 233   char * avail_vector;          // processor bit vector
 234   int next_lb;                  // next load balancer
 235
 236   double * expectedLoad;        // expected load for future
 237
 238 public:
 239 #if (defined(_FAULT_MLOG_) || defined(_FAULT_CAUSAL_))
 240         int step;
 241         int lbDecisionCount;
 242 #endif
 243   LBMigrateMsg(): level(0), n_moves(0), next_lb(0) {}
 244   void pup(PUP::er &p) {
 245     int i;
 246     p | level;
 247     p | n_moves;
 248     // Warning: it relies on the fact that the message has been allocated already
 249     // with the correct number of moves!
 250     p | next_lb;
 251     int numPes = CkNumPes();
 252     p | numPes;
 253     CkAssert(numPes == CkNumPes());
 254     for (i=0; i<n_moves; ++i) p | moves[i];
 255     p(avail_vector, numPes);
 256     for (i=0; i<numPes; ++i) p | expectedLoad[i];
 257   }
 258 };
 259
 260 struct VectorMigrateInfo {
 261     int from_pe;
 262     int to_pe;
 263     double load;
 264     int async_arrival;      // if an object is available for immediate migrate
 265     VectorMigrateInfo():  async_arrival(0) {}
 266 };
 267
 268 class LBVectorMigrateMsg : public CMessage_LBVectorMigrateMsg {
 269 public:
 270   int level;                    // which level in hierarchy, used in hybridLB
 271
 272   int n_moves;                  // number of moves
 273   VectorMigrateInfo* moves;
 274
 275 public:
 276   LBVectorMigrateMsg(): level(0), n_moves(0) {}
 277 };
 278
 279 // for a FooLB, the following macro defines these functions for each LB:
 280 // CreateFooLB():        create BOC and register with LBDatabase with a
 281 //                       sequence ticket,
 282 // AllocateFooLB():      allocate the class instead of a BOC
 283 // static void lbinit(): an init call for charm module registration
 284 #if CMK_LBDB_ON
 285
 286 #define CreateLBFunc_Def(x, str)                \
 287 void Create##x(void) {  \
 288   int seqno = LBDatabaseObj()->getLoadbalancerTicket(); \
 289   CProxy_##x::ckNew(CkLBOptions(seqno));        \
 290 }       \
 291 \
 292 BaseLB *Allocate##x(void) { \
 293   return new x((CkMigrateMessage*)NULL);        \
 294 }       \
 295 \
 296 static void lbinit(void) {      \
 297   LBRegisterBalancer(#x,        \
 298                      Create##x, \
 299                      Allocate##x,       \
 300                      str);      \
 301 }
 302
 303 #else           /* CMK_LBDB_ON */
 304
 305 #define CreateLBFunc_Def(x, str)        \
 306 void Create##x(void) {}         \
 307 BaseLB *Allocate##x(void) { return NULL; }      \
 308 static void lbinit(void) {}
 309
 310 #endif          /* CMK_LBDB_ON */
 311
 312 #endif
 313
 314 /*@}*/