add missing namespace std.
[charm.git] / src / ck-ldb / GreedyLB.C
1 /*****************************************************************************
2  * $Source$
3  * $Author$
4  * $Date$
5  * $Revision$
6  *****************************************************************************/
7
8 /**
9  * \addtogroup CkLdb
10 */
11 /*@{*/
12
13 /*
14  status:
15   * support processor avail bitvector
16   * support nonmigratable attrib
17       nonmigratable object load is added to its processor's background load
18       and the nonmigratable object is not taken in the objData array
19 */
20
21 #include <algorithm>
22
23 #include "charm++.h"
24
25
26 #include "ckgraph.h"
27 #include "cklists.h"
28 #include "GreedyLB.h"
29
30 using namespace std;
31
32 CreateLBFunc_Def(GreedyLB, "always assign the heaviest obj onto lightest loaded processor.")
33
34 GreedyLB::GreedyLB(const CkLBOptions &opt): CentralLB(opt)
35 {
36   lbname = "GreedyLB";
37   if (CkMyPe()==0)
38     CkPrintf("[%d] GreedyLB created\n",CkMyPe());
39 }
40
41 CmiBool GreedyLB::QueryBalanceNow(int _step)
42 {
43   //  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
44   return CmiTrue;
45 }
46
47 class ProcLoadGreater {
48   public:
49     bool operator()(ProcInfo p1, ProcInfo p2) {
50       return (p1.totalLoad() > p2.totalLoad());
51     }
52 };
53
54 class ObjLoadGreater {
55   public:
56     bool operator()(Vertex v1, Vertex v2) {
57       return (v1.getVertexLoad() > v2.getVertexLoad());
58     }
59 };
60
61 void GreedyLB::work(LDStats* stats)
62 {
63   int  obj, objCount, pe;
64   int n_pes = stats->nprocs();
65   int *map = new int[n_pes];
66
67   std::vector<ProcInfo>  procs;
68   for(pe = 0; pe < n_pes; pe++) {
69     map[pe] = -1;
70     if (stats->procs[pe].available) {
71       map[pe] = procs.size();
72       procs.push_back(ProcInfo(pe, stats->procs[pe].bg_walltime, 0.0, stats->procs[pe].pe_speed, true));
73     }
74   }
75
76   // take non migratbale object load as background load
77   for (obj = 0; obj < stats->n_objs; obj++)
78   {
79       LDObjData &oData = stats->objData[obj];
80       if (!oData.migratable)  {
81         int pe = stats->from_proc[obj];
82         pe = map[pe];
83         if (pe==-1)
84           CmiAbort("GreedyLB: nonmigratable object on an unavail processor!\n");
85         procs[pe].totalLoad() += oData.wallTime;
86       }
87   }
88   delete [] map;
89
90   // considering cpu speed
91   for (pe = 0; pe<procs.size(); pe++) {
92     procs[pe].totalLoad() +=  procs[pe].overhead();
93     procs[pe].totalLoad() *= procs[pe].pe_speed();
94   }
95
96   // build object array
97   std::vector<Vertex> objs;
98
99   for(int obj = 0; obj < stats->n_objs; obj++) {
100     LDObjData &oData = stats->objData[obj];
101     int pe = stats->from_proc[obj];
102     if (!oData.migratable) {
103       if (!stats->procs[pe].available) 
104         CmiAbort("GreedyLB cannot handle nonmigratable object on an unavial processor!\n");
105       continue;
106     }
107     double load = oData.wallTime * stats->procs[pe].pe_speed;
108     objs.push_back(Vertex(obj, load, stats->objData[obj].migratable, stats->from_proc[obj]));
109   }
110
111   // max heap of objects
112   sort(objs.begin(), objs.end(), ObjLoadGreater());
113   // min heap of processors
114   make_heap(procs.begin(), procs.end(), ProcLoadGreater());
115
116   if (_lb_args.debug()>1) 
117     CkPrintf("[%d] In GreedyLB strategy\n",CkMyPe());
118
119
120     // greedy algorithm
121   int nmoves = 0;
122   for (obj=0; obj < objs.size(); obj++) {
123     ProcInfo p = procs.front();
124     pop_heap(procs.begin(), procs.end(), ProcLoadGreater());
125     procs.pop_back();
126
127     // Increment the time of the least loaded processor by the cpuTime of
128     // the `heaviest' object
129     p.totalLoad() += objs[obj].getVertexLoad();
130
131     //Insert object into migration queue if necessary
132     const int dest = p.getProcId();
133     const int pe   = objs[obj].getCurrentPe();
134     const int id   = objs[obj].getVertexId();
135     if (dest != pe) {
136       stats->to_proc[id] = dest;
137       nmoves ++;
138       if (_lb_args.debug()>2) 
139         CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),objs[obj].getVertexId(),pe,dest);
140     }
141
142     //Insert the least loaded processor with load updated back into the heap
143     procs.push_back(p);
144     push_heap(procs.begin(), procs.end(), ProcLoadGreater());
145   }
146
147   if (_lb_args.debug()>0) 
148     CkPrintf("[%d] %d objects migrating.\n", CkMyPe(), nmoves);
149
150   if (_lb_args.debug()>1)  {
151     CkPrintf("CharmLB> Min obj: %f  Max obj: %f\n", objs[objs.size()-1].getVertexLoad(), objs[0].getVertexLoad());
152     CkPrintf("CharmLB> PE speed:\n");
153     for (pe = 0; pe<procs.size(); pe++)
154       CkPrintf("%f ", procs[pe].pe_speed());
155     CkPrintf("\n");
156     CkPrintf("CharmLB> PE Load:\n");
157     for (pe = 0; pe<procs.size(); pe++)
158       CkPrintf("%f (%f)  ", procs[pe].totalLoad(), procs[pe].overhead());
159     CkPrintf("\n");
160   }
161
162 }
163
164 #include "GreedyLB.def.h"
165
166 /*@}*/
167
168
169
170