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