doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / GreedyAgentLB.C
1 /**
2  * \addtogroup CkLdb
3 */
4 /*@{*/
5
6 /*
7  status:
8   * support processor avail bitvector
9   * support nonmigratable attrib
10 */
11
12 #include <LBSimulation.h>
13 #include "GreedyAgentLB.h"
14
15 #define LOAD_OFFSET 0.05
16
17 CreateLBFunc_Def(GreedyAgentLB,"always assign the heaviest obj onto lightest loaded processor taking into account the topology")
18
19 /*static void lbinit(void) {
20   LBRegisterBalancer("GreedyAgentLB", 
21                      CreateGreedyAgentLB, 
22                      AllocateGreedyAgentLB, 
23                      "always assign the heaviest obj onto lightest loaded processor.");
24 }
25 */
26 #include "GreedyAgentLB.def.h"
27
28 GreedyAgentLB::GreedyAgentLB(const CkLBOptions &opt): CentralLB(opt)
29 {
30   lbname = "GreedyAgentLB";
31   if (CkMyPe()==0)
32     CkPrintf("[%d] GreedyAgentLB created\n",CkMyPe());
33 }
34
35 CmiBool GreedyAgentLB::QueryBalanceNow(int _step)
36 {
37   //  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
38   return CmiTrue;
39 }
40
41 CmiBool  GreedyAgentLB::Compare(double x, double y, HeapCmp cmp)
42 {
43   const int test =  ((cmp == GT) ? (x > y) : (x < y));
44
45   if (test) return CmiTrue; 
46   else return CmiFalse;
47 }
48
49
50 void GreedyAgentLB::Heapify(HeapData *heap, int node, int heapSize, HeapCmp cmp)
51 {
52   int left = 2*node+1;
53   int right = 2*node+2;
54   int xchange;
55
56   //heap[left].load > heap[node].load)
57   if (left <= heapSize &&  Compare(heap[left].load, heap[node].load, cmp))
58     xchange = left;
59   else xchange = node;
60   //heap[right].load > heap[xchange].load) 
61   if (right <= heapSize && Compare(heap[right].load, heap[xchange].load, cmp))
62     xchange = right;
63
64   if (xchange != node) {
65     HeapData obj;
66     obj = heap[node];
67     heap[node] = heap[xchange];
68     heap[xchange] = obj;
69     Heapify(heap, xchange, heapSize, cmp);
70   }    
71 }
72
73 void GreedyAgentLB::BuildHeap(HeapData *data, int heapSize, HeapCmp cmp)
74 {
75         int i;
76         for(i=heapSize/2; i >= 0; i--)
77                 Heapify(data, i, heapSize, cmp);
78 }
79
80 void GreedyAgentLB::HeapSort(HeapData *data, int heapSize, HeapCmp cmp)
81 {
82         int i;
83         HeapData key;
84
85         int origSize = heapSize;
86         BuildHeap(data, heapSize, cmp);
87         for (i=heapSize; i > 0; i--) {
88                key = data[0];
89                data[0] = data[i];
90                data[i] = key;
91                heapSize--;
92                Heapify(data, 0, heapSize, cmp);
93         }
94         // after HeapSort, the data are in reverse order
95         for (i=0; i<(origSize+1)/2; i++) {
96           key = data[i];
97           data[i] = data[origSize-i];
98           data[origSize-i] = key;
99         }
100 }
101
102 GreedyAgentLB::HeapData* 
103 GreedyAgentLB::BuildObjectArray(CentralLB::LDStats* stats, 
104                              int count, int *objCount)
105 {
106   HeapData *objData;
107   int obj;
108
109 //for (obj = 0; obj < stats[pe].n_objs; obj++)
110 //if (stats[pe].objData[obj].migratable == CmiTrue) (*objCount)++; 
111
112   objData  = new HeapData[stats->n_objs];
113   *objCount = 0; 
114   for(obj=0; obj < stats->n_objs; obj++) {
115     LDObjData &oData = stats->objData[obj];
116     int pe = stats->from_proc[obj];
117     if (!oData.migratable) {
118       if (!stats->procs[pe].available) 
119         CmiAbort("GreedyAgentLB cannot handle nonmigratable object on an unavial processor!\n");
120       continue;
121     }
122     objData[*objCount].load = oData.wallTime * stats->procs[pe].pe_speed;
123     objData[*objCount].pe = pe;
124     objData[*objCount].id = obj;
125     (*objCount)++;
126   }
127   
128   HeapSort(objData, *objCount-1, GT);
129 /*
130 for (int i=0; i<*objCount; i++)
131   CmiPrintf("%f ", objData[i].load);
132 CmiPrintf("\n");
133 */
134   return objData;
135 }
136
137 GreedyAgentLB::HeapData* 
138 GreedyAgentLB::BuildCpuArray(CentralLB::LDStats* stats, 
139                           int count, int *peCount)
140 {
141   int pe;
142
143   *peCount = 0;
144   for (pe = 0; pe < count; pe++)
145     if (stats->procs[pe].available) (*peCount)++;
146   HeapData *data = new HeapData[*peCount];
147   int *map = new int[count];
148   
149   *peCount = 0;
150   for (pe=0; pe < count; pe++) {
151     CentralLB::ProcStats &peData = stats->procs[pe];
152  
153     data[*peCount].load = 0.0;
154     map[pe] = -1;
155     if (peData.available) 
156     {
157       data[*peCount].load += peData.bg_walltime;
158       data[*peCount].pe = data[*peCount].id = pe;
159       map[pe] = *peCount;
160       (*peCount)++;
161     }
162   }
163
164   // take non migratbale object load as background load
165   for (int obj = 0; obj < stats->n_objs; obj++) 
166   { 
167       LDObjData &oData = stats->objData[obj];
168       if (!oData.migratable)  {
169         int pe = stats->from_proc[obj];
170         pe = map[pe];
171         if (pe==-1) 
172           CmiAbort("GreedyAgentLB: nonmigratable object on an unavail processor!\n");
173         data[pe].load += oData.wallTime;
174       }
175   }
176
177   // considering cpu speed
178   for (pe = 0; pe<*peCount; pe++)
179     data[pe].load *= stats->procs[data[pe].pe].pe_speed;
180
181   BuildHeap(data, *peCount-1, LT);     // minHeap
182   delete [] map;
183   return data;
184 }
185
186 void GreedyAgentLB::work(LDStats* stats)
187 {
188   int  i, obj, heapSize, objCount;
189   int n_pes = stats->nprocs();
190
191   int *pemap = new int [n_pes];
192   HeapData *cpuData = BuildCpuArray(stats, n_pes, &heapSize);
193   HeapData *objData = BuildObjectArray(stats, n_pes, &objCount);
194         
195         int max_neighbors=0;
196  
197         //int simprocs = LBSimulation::simProcs;
198         //CkPrintf("\nnum of procs:%d\n",simprocs);
199         
200
201         CkPrintf("num procs in stats:%d\n", n_pes);
202         topologyAgent = new TopologyAgent(stats, n_pes);
203
204         max_neighbors = topologyAgent->topo->max_neighbors();
205         
206   if (_lb_args.debug()) CkPrintf("In GreedyAgentLB strategy\n",CkMyPe());
207
208   heapSize--;
209         
210         HeapData *minCpu = new HeapData[n_pes];
211         double minLoad = 0.0;
212         double loadThreshold = 0.0;
213         int *trialpes = new int[n_pes + 1];
214         int *trialmap = new int[n_pes];
215         int *existing_map = new int[objCount];
216         Agent::Elem *preferList;
217         
218         for(i=0;i<objCount;i++)
219                 existing_map[i]=-1;
220
221         int extractIndex=0;
222
223         //stats->makeCommHash();
224
225         CkPrintf("before assigning objects...objcount:%d\n",objCount);
226   for (obj=0; obj < objCount; obj++) {
227     //HeapData minCpu;  
228     // Operation of extracting the the least loaded processor
229     // from the heap
230     //int extractIndex=0;
231                 
232                         CkPrintf("obj count:%d\n",obj);
233                 for(i = 0; i <= n_pes; i++)
234                         trialpes[i]=-1;
235
236                 if(extractIndex==0)
237                         minLoad = cpuData[0].load;
238                 else
239                         minLoad = minCpu[0].load;
240
241                                 //if(minLoad < 0.0)
242                 //      loadThreshold = minLoad*(1-LOAD_OFFSET);
243                 //else
244                 loadThreshold = minLoad*(1+LOAD_OFFSET);
245                 
246                 //CkPrintf("minload :%lf , threshold:%lf , heapSize:%d\n",minLoad,loadThreshold,heapSize);
247                 //We can do better by extracting from the heap only the incremental load nodes
248                 //after we have assigned the preferred node in the previous step
249                 //....as the others are still with us..
250         
251                 //CkPrintf("heapsize before :%d\n",heapSize);
252                 /*CkPrintf("heap stats...\n");
253                 for(int t=0;t<=heapSize;t++)
254                         CkPrintf("..pe:%d,load:%f..",cpuData[t].pe,cpuData[t].load);
255                 */
256                 while(1){
257                         if(cpuData[0].load > loadThreshold)
258                                 break;
259                         minCpu[extractIndex]=cpuData[0];
260                         extractIndex++;
261         cpuData[0]=cpuData[heapSize];
262         heapSize--;
263                         if(heapSize==-1)
264                                 break;
265         Heapify(cpuData, 0, heapSize, LT);    
266                 }
267                 //CkPrintf("after extracting loop....extractindex:%d,heapsize:%d\n",extractIndex,heapSize);
268                 //CkPrintf("trialpes...\n");
269                 int trialLen = 0;
270                 if(obj!=0){
271                         trialLen = max_neighbors*max_neighbors;
272                         if(trialLen > extractIndex)
273                                 trialLen = extractIndex;
274                 }
275                 else
276                         trialLen = extractIndex;
277                         
278                 for(i=0;i<trialLen;i++){
279                         trialpes[i]=minCpu[i].pe;
280                         trialmap[minCpu[i].pe]=i;
281                 }
282                 preferList = topologyAgent->my_preferred_procs(existing_map,objData[obj].id,trialpes,1);
283     // Increment the time of the least loaded processor by the cpuTime of
284     // the `heaviest' object
285                 // Assign the object to first processor in the preferList...we may change this
286                 // and assign by comparing the object load with topology comm cost
287                 int minIndex = trialmap[preferList[0].pe];
288                 /*int s=0;
289                 for(s=0;s<trialLen;s++)
290                         if(minCpu[s].pe == preferList[0].pe){
291                                 minIndex = s;
292                                 break;
293                         }
294                 */
295                 //CkPrintf("first element of prefer list...%d,%d...\n",minIndex,minCpu[minIndex].pe);
296                 
297                 //if(s==extractIndex)
298                         //CmiAbort("Seems as if Agent has returned corrupt value");
299
300                 const int dest = minCpu[minIndex].pe;
301                 const int id   = objData[obj].id;
302
303                 //CkPrintf("chk before load updation\n");
304     minCpu[minIndex].load += objData[obj].load;
305                 //CkPrintf("chk within updation.\n");
306                 existing_map[id]=minCpu[minIndex].pe;
307                 
308     //Insert object into migration queue if necessary
309     //const int dest = minCpu[minIndex].pe;
310     const int pe   = objData[obj].pe;
311     //const int id   = objData[obj].id;
312     if (dest != pe) {
313       stats->to_proc[id] = dest;
314       if (_lb_args.debug()>1) 
315         CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),obj,pe,dest);
316     }
317
318     //Insert all the extracted processors (one with load updated) back into the heap
319     /*int cnt=0;
320                 while(cnt<extractIndex){
321                         heapSize++;
322         int location = heapSize;
323         while (location>0 && cpuData[(location-1)/2].load > minCpu[cnt].load) {
324         cpuData[location] = cpuData[(location-1)/2];
325         location = (location-1)/2;
326         }
327         cpuData[location] = minCpu[cnt];
328                         cnt++;
329                 }*/
330                 
331                 heapSize++;
332     extractIndex--;
333                 int location = heapSize;
334     while (location>0 && cpuData[(location-1)/2].load > minCpu[minIndex].load) {
335         cpuData[location] = cpuData[(location-1)/2];
336         location = (location-1)/2;
337     }
338     cpuData[location] = minCpu[minIndex];
339
340                 for(int r=minIndex;r<extractIndex;r++)
341                         minCpu[r] = minCpu[r+1];
342         }
343
344   delete [] cpuData;
345   delete [] objData;
346         delete [] minCpu;
347 }
348
349
350
351 /*@}*/
352
353
354
355