defines lbinit() in macro CreateLBFunc_Def to simplify code and future extensions.
[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 <charm++.h>
22
23
24 #include "cklists.h"
25 #include "GreedyLB.h"
26
27 CreateLBFunc_Def(GreedyLB, "always assign the heaviest obj onto lightest loaded processor.");
28
29 GreedyLB::GreedyLB(const CkLBOptions &opt): CentralLB(opt)
30 {
31   lbname = "GreedyLB";
32   if (CkMyPe()==0)
33     CkPrintf("[%d] GreedyLB created\n",CkMyPe());
34 }
35
36 CmiBool GreedyLB::QueryBalanceNow(int _step)
37 {
38   //  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
39   return CmiTrue;
40 }
41
42 CmiBool  GreedyLB::Compare(double x, double y, HeapCmp cmp)
43 {
44   const int test =  ((cmp == GT) ? (x > y) : (x < y));
45
46   if (test) return CmiTrue; 
47   else return CmiFalse;
48 }
49
50
51 void GreedyLB::Heapify(HeapData *heap, int node, int heapSize, HeapCmp cmp)
52 {
53   int left = 2*node+1;
54   int right = 2*node+2;
55   int xchange;
56
57   //heap[left].load > heap[node].load)
58   if (left <= heapSize &&  Compare(heap[left].load, heap[node].load, cmp))
59     xchange = left;
60   else xchange = node;
61   //heap[right].load > heap[xchange].load) 
62   if (right <= heapSize && Compare(heap[right].load, heap[xchange].load, cmp))
63     xchange = right;
64
65   if (xchange != node) {
66     HeapData obj;
67     obj = heap[node];
68     heap[node] = heap[xchange];
69     heap[xchange] = obj;
70     Heapify(heap, xchange, heapSize, cmp);
71   }    
72 }
73
74 void GreedyLB::BuildHeap(HeapData *data, int heapSize, HeapCmp cmp)
75 {
76         int i;
77         for(i=heapSize/2; i >= 0; i--)
78                 Heapify(data, i, heapSize, cmp);
79 }
80
81 void GreedyLB::HeapSort(HeapData *data, int heapSize, HeapCmp cmp)
82 {
83         int i;
84         HeapData key;
85
86         int origSize = heapSize;
87         BuildHeap(data, heapSize, cmp);
88         for (i=heapSize; i > 0; i--) {
89                key = data[0];
90                data[0] = data[i];
91                data[i] = key;
92                heapSize--;
93                Heapify(data, 0, heapSize, cmp);
94         }
95         // after HeapSort, the data are in reverse order
96         for (i=0; i<(origSize+1)/2; i++) {
97           key = data[i];
98           data[i] = data[origSize-i];
99           data[origSize-i] = key;
100         }
101 }
102
103 GreedyLB::HeapData* 
104 GreedyLB::BuildObjectArray(CentralLB::LDStats* stats, 
105                              int count, int *objCount)
106 {
107   HeapData *objData;
108   int obj;
109
110 //for (obj = 0; obj < stats[pe].n_objs; obj++)
111 //if (stats[pe].objData[obj].migratable == CmiTrue) (*objCount)++; 
112
113   objData  = new HeapData[stats->n_objs];
114   *objCount = 0; 
115   for(obj=0; obj < stats->n_objs; obj++) {
116     LDObjData &oData = stats->objData[obj];
117     int pe = stats->from_proc[obj];
118     if (!oData.migratable) {
119       if (!stats->procs[pe].available) 
120         CmiAbort("GreedyLB cannot handle nonmigratable object on an unavial processor!\n");
121       continue;
122     }
123     objData[*objCount].load = oData.wallTime * stats->procs[pe].pe_speed;
124     objData[*objCount].pe = pe;
125     objData[*objCount].id = obj;
126     (*objCount)++;
127   }
128   
129   HeapSort(objData, *objCount-1, GT);
130 /*
131 for (int i=0; i<*objCount; i++)
132   CmiPrintf("%f ", objData[i].load);
133 CmiPrintf("\n");
134 */
135   return objData;
136 }
137
138 GreedyLB::HeapData* 
139 GreedyLB::BuildCpuArray(CentralLB::LDStats* stats, 
140                           int count, int *peCount)
141 {
142   int pe;
143
144   *peCount = 0;
145   for (pe = 0; pe < count; pe++)
146     if (stats->procs[pe].available) (*peCount)++;
147   HeapData *data = new HeapData[*peCount];
148   int *map = new int[count];
149   
150   *peCount = 0;
151   for (pe=0; pe < count; pe++) {
152     CentralLB::ProcStats &peData = stats->procs[pe];
153  
154     data[*peCount].load = 0.0;
155     map[pe] = -1;
156     if (peData.available) 
157     {
158       data[*peCount].load += peData.bg_walltime;
159       data[*peCount].pe = data[*peCount].id = pe;
160       map[pe] = *peCount;
161       (*peCount)++;
162     }
163   }
164
165   // take non migratbale object load as background load
166   for (int obj = 0; obj < stats->n_objs; obj++) 
167   { 
168       LDObjData &oData = stats->objData[obj];
169       if (!oData.migratable)  {
170         int pe = stats->from_proc[obj];
171         pe = map[pe];
172         if (pe==-1) 
173           CmiAbort("GreedyLB: nonmigratable object on an unavail processor!\n");
174         data[pe].load += oData.wallTime;
175       }
176   }
177
178   // considering cpu speed
179   for (pe = 0; pe<*peCount; pe++)
180     data[pe].load *= stats->procs[data[pe].pe].pe_speed;
181
182   BuildHeap(data, *peCount-1, LT);     // minHeap
183   delete [] map;
184   return data;
185 }
186
187 void GreedyLB::work(CentralLB::LDStats* stats, int count)
188 {
189   int  obj, heapSize, objCount;
190   int *pemap = new int [count];
191   HeapData *cpuData = BuildCpuArray(stats, count, &heapSize);
192   HeapData *objData = BuildObjectArray(stats, count, &objCount);
193
194   if (_lb_args.debug()) CkPrintf("In GreedyLB strategy\n",CkMyPe());
195
196   heapSize--;
197   for (obj=0; obj < objCount; obj++) {
198     HeapData minCpu;  
199     // Operation of extracting the the least loaded processor
200     // from the heap
201     minCpu = cpuData[0];
202     cpuData[0] = cpuData[heapSize];
203     heapSize--;
204     Heapify(cpuData, 0, heapSize, LT);    
205
206     // Increment the time of the least loaded processor by the cpuTime of
207     // the `heaviest' object
208     minCpu.load += objData[obj].load;
209
210     //Insert object into migration queue if necessary
211     const int dest = minCpu.pe;
212     const int pe   = objData[obj].pe;
213     const int id   = objData[obj].id;
214     if (dest != pe) {
215       stats->to_proc[id] = dest;
216       if (_lb_args.debug()>1) 
217         CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),obj,pe,dest);
218     }
219
220     //Insert the least loaded processor with load updated back into the heap
221     heapSize++;
222     int location = heapSize;
223     while (location>0 && cpuData[(location-1)/2].load > minCpu.load) {
224       cpuData[location] = cpuData[(location-1)/2];
225       location = (location-1)/2;
226     }
227     cpuData[location] = minCpu;
228   }
229
230   delete [] cpuData;
231   delete [] objData;
232 }
233
234 #include "GreedyLB.def.h"
235
236 /*@}*/
237
238
239
240