Changes to AdaptiveLB strategy
[charm.git] / 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): CentralLB(opt)
28 {
29   lbname = "GreedyLB";
30   if (CkMyPe()==0)
31     CkPrintf("[%d] GreedyLB created\n",CkMyPe());
32 }
33
34 CmiBool GreedyLB::QueryBalanceNow(int _step)
35 {
36   //  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
37   return CmiTrue;
38 }
39
40 class ProcLoadGreater {
41   public:
42     bool operator()(ProcInfo p1, ProcInfo p2) {
43       return (p1.totalLoad() > p2.totalLoad());
44     }
45 };
46
47 class ObjLoadGreater {
48   public:
49     bool operator()(Vertex v1, 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   ProcArray *parr = new ProcArray(stats);
61   double bg_load = 0.0;
62
63   std::vector<ProcInfo>  procs;
64   for(pe = 0; pe < n_pes; pe++) {
65     map[pe] = -1;
66     if (stats->procs[pe].available) {
67       map[pe] = procs.size();
68       procs.push_back(ProcInfo(pe, stats->procs[pe].bg_walltime, 0.0, stats->procs[pe].pe_speed, true));
69       bg_load = stats->procs[pe].bg_walltime;
70     }
71   }
72
73   // take non migratbale object load as background load
74   for (obj = 0; obj < stats->n_objs; obj++)
75   {
76       LDObjData &oData = stats->objData[obj];
77       if (!oData.migratable)  {
78         int pe = stats->from_proc[obj];
79         pe = map[pe];
80         if (pe==-1)
81           CmiAbort("GreedyLB: nonmigratable object on an unavail processor!\n");
82         procs[pe].totalLoad() += oData.wallTime;
83       }
84   }
85   delete [] map;
86
87   // considering cpu speed
88   for (pe = 0; pe<procs.size(); pe++) {
89     procs[pe].totalLoad() +=  procs[pe].overhead();
90     procs[pe].totalLoad() *= procs[pe].pe_speed();
91   }
92
93   double max_load = 0;
94   double avg_load = 0;
95   for (pe = 0; pe<parr->procs.size(); pe++) {
96     if (parr->procs[pe].totalLoad() > max_load) {
97       max_load = parr->procs[pe].totalLoad();
98     }
99     avg_load += parr->procs[pe].totalLoad();
100   }
101   CkPrintf("Before GreedyLB max load: %lf avg load: %lf bg load: %lf\n", max_load, avg_load/procs.size(), bg_load/procs.size());
102
103   // build object array
104   std::vector<Vertex> objs;
105
106   for(int obj = 0; obj < stats->n_objs; obj++) {
107     LDObjData &oData = stats->objData[obj];
108     int pe = stats->from_proc[obj];
109     if (!oData.migratable) {
110       if (!stats->procs[pe].available) 
111         CmiAbort("GreedyLB cannot handle nonmigratable object on an unavial processor!\n");
112       continue;
113     }
114     double load = oData.wallTime * stats->procs[pe].pe_speed;
115     objs.push_back(Vertex(obj, load, stats->objData[obj].migratable, stats->from_proc[obj]));
116   }
117
118   // max heap of objects
119   sort(objs.begin(), objs.end(), ObjLoadGreater());
120   // min heap of processors
121   make_heap(procs.begin(), procs.end(), ProcLoadGreater());
122
123   if (_lb_args.debug()>1) 
124     CkPrintf("[%d] In GreedyLB strategy\n",CkMyPe());
125
126
127     // greedy algorithm
128   int nmoves = 0;
129   for (obj=0; obj < objs.size(); obj++) {
130     ProcInfo p = procs.front();
131     pop_heap(procs.begin(), procs.end(), ProcLoadGreater());
132     procs.pop_back();
133
134     // Increment the time of the least loaded processor by the cpuTime of
135     // the `heaviest' object
136     p.totalLoad() += objs[obj].getVertexLoad();
137
138     //Insert object into migration queue if necessary
139     const int dest = p.getProcId();
140     const int pe   = objs[obj].getCurrentPe();
141     const int id   = objs[obj].getVertexId();
142     if (dest != pe) {
143       stats->to_proc[id] = dest;
144       nmoves ++;
145       if (_lb_args.debug()>2) 
146         CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),objs[obj].getVertexId(),pe,dest);
147     }
148
149     //Insert the least loaded processor with load updated back into the heap
150     procs.push_back(p);
151     push_heap(procs.begin(), procs.end(), ProcLoadGreater());
152   }
153
154   if (_lb_args.debug()>0) 
155     CkPrintf("[%d] %d objects migrating.\n", CkMyPe(), nmoves);
156
157   max_load = 0;
158   avg_load = 0;
159   for (pe = 0; pe<procs.size(); pe++) {
160     if (procs[pe].totalLoad() > max_load) {
161       max_load = procs[pe].totalLoad();
162     }
163     avg_load += procs[pe].totalLoad();
164   }
165   CkPrintf("GreedyLB> After lb max load: %lf avg load: %lf\n", max_load, avg_load/procs.size());
166
167   if (_lb_args.debug()>1)  {
168     CkPrintf("CharmLB> Min obj: %f  Max obj: %f\n", objs[objs.size()-1].getVertexLoad(), objs[0].getVertexLoad());
169     CkPrintf("CharmLB> PE speed:\n");
170     for (pe = 0; pe<procs.size(); pe++)
171       CkPrintf("%f ", procs[pe].pe_speed());
172     CkPrintf("\n");
173     CkPrintf("CharmLB> PE Load:\n");
174     for (pe = 0; pe<procs.size(); pe++)
175       CkPrintf("%f (%f)  ", procs[pe].totalLoad(), procs[pe].overhead());
176     CkPrintf("\n");
177   }
178
179   stats->after_lb_max = max_load;
180   stats->after_lb_avg = avg_load/procs.size();
181   stats->is_prev_lb_refine = 0;
182
183 }
184
185 #include "GreedyLB.def.h"
186
187 /*@}*/
188
189
190
191