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