src/ck-ldb/GreedyRefineLB.h

   1 /**
   2  * \addtogroup CkLdb
   3 */
   4 /*@{*/
   5
   6 /**
   7  * Author: jjgalvez@illinois.edu (Juan Galvez)
   8  * Greedy algorithm to minimize cpu max_load and object migrations.
   9  * Can find solution equal or close to regular Greedy with less (sometimes much less) migrations.
  10  * The amount of migrations that the user can tolerate is passed via the command-line
  11  * option +LBNumMoves (as percentage of chares that can be moved).
  12  *
  13  * If LBNumMoves is not passed, strategy assumes it can move all objects.
  14  * In this case, the algorithm will give preference to minimizing cpu max_load.
  15  * It will still move less than greedy, but the amount of migrations
  16  * will depend very much on the particular case (object load distribution and processor background loads),
  17  *
  18  * supports processor avail bitvector
  19  * supports nonmigratable attrib
  20  *
  21 */
  22
  23 #ifndef _GREEDY_REFINE_LB_H_
  24 #define _GREEDY_REFINE_LB_H_
  25
  26 #include "CentralLB.h"
  27 #include "GreedyRefineLB.decl.h"
  28
  29 void CreateGreedyRefineLB();
  30 BaseLB *AllocateGreedyRefineLB();
  31
  32 #define __DEBUG_GREEDY_REFINE_ 0
  33
  34 class GreedyRefineLB : public CBase_GreedyRefineLB {
  35 public:
  36   GreedyRefineLB(const CkLBOptions &);
  37   GreedyRefineLB(CkMigrateMessage *m);
  38   void work(LDStats* stats);
  39   void receiveSolutions(CkReductionMsg *msg);
  40   void receiveTotalTime(double time);
  41   void setMigrationTolerance(float tol) { migrationTolerance = tol; }
  42
  43 private:
  44   bool QueryBalanceNow(int step) { return true; }
  45
  46   class GProc {
  47   public:
  48     GProc() : available(true), load(0) {}
  49     int id;
  50     bool available;
  51     int pos;    // position in min heap
  52     double load;
  53     double bgload; // background load
  54     float speed;
  55   };
  56
  57   class GObj {
  58   public:
  59     int id;
  60     double load;
  61     int oldPE;
  62   };
  63
  64   class ObjLoadGreater {
  65   public:
  66     inline bool operator() (const GObj *o1, const GObj *o2) const {
  67       return (o1->load > o2->load);
  68     }
  69   };
  70
  71   class PHeap;
  72   class Solution;
  73
  74   double fillData(LDStats *stats,
  75                   std::vector<GObj> &objs,
  76                   std::vector<GObj*> &pobjs,
  77                   std::vector<GProc> &procs,
  78                   PHeap &procHeap);
  79
  80   double greedyLB(const std::vector<GObj*> &pobjs, PHeap &procHeap, const BaseLB::LDStats *stats) const;
  81   void sendSolution(double maxLoad, int migrations);
  82
  83   double strategyStartTime;
  84   double totalObjLoad;
  85   int availablePes;
  86   float migrationTolerance;
  87   int totalObjs;
  88
  89 #if __DEBUG_GREEDY_REFINE_
  90   void dumpObjLoads(std::vector<GObj> &objs);
  91   void dumpProcLoads(std::vector<GProc> &procs);
  92 #endif
  93 };
  94
  95 #endif
  96
  97 /*@}*/