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