Removed all STL template code from load balancer. Too bad STL doesn't work
[charm.git] / src / ck-ldb / RefineLB.C
1 #include <charm++.h>
2
3 #if CMK_LBDB_ON
4
5 #include "CkLists.h"
6
7 #include "RefineLB.h"
8 #include "RefineLB.def.h"
9
10 void CreateRefineLB()
11 {
12   loadbalancer = CProxy_RefineLB::ckNew();
13   CkPrintf("[%d] created RefineLB %d\n",CkMyPe(),loadbalancer);
14 }
15
16 RefineLB::RefineLB()
17 {
18   CkPrintf("[%d] RefineLB created\n",CkMyPe());
19 }
20
21 CmiBool RefineLB::QueryBalanceNow(int _step)
22 {
23   return CmiTrue;
24 }
25
26 void RefineLB::create(CentralLB::LDStats* stats, int count)
27 {
28   int i,j;
29
30   P = count;
31
32   numComputes = 0;
33   for(j=0; j < P; j++) numComputes+= stats[j].n_objs;
34   computes = new computeInfo[numComputes];
35
36   processors = new processorInfo[count];
37
38   int index = 0;
39   for(j=0; j < count; j++) {
40     processors[j].Id = j;
41     processors[j].backgroundLoad = 0;
42     processors[j].load = processors[j].backgroundLoad;
43     processors[j].computeLoad = 0;
44     processors[j].computeSet = new Set();
45
46     LDObjData *odata = stats[j].objData;
47     const int osz = stats[j].n_objs;  
48     for(i=0; i < osz; i++) {
49 //      computes[index].omID = odata[i].omID;
50 //      computes[index].id = odata[i].id;
51       computes[index].id = odata[i].id;
52       computes[index].handle = odata[i].handle;
53       computes[index].load = odata[i].cpuTime;
54       computes[index].processor = -1;
55       computes[index].oldProcessor = j;
56       index ++;
57     }
58   }
59
60 //  for (i=0; i < numComputes; i++)
61 //      processors[computes[i].oldProcessor].computeLoad += computes[i].load;
62 }
63
64 void RefineLB::assign(computeInfo *c, int processor)
65 {
66    assign(c, &(processors[processor]));
67 }
68
69 void RefineLB::assign(computeInfo *c, processorInfo *p)
70 {
71    c->processor = p->Id;
72    p->computeSet->insert((InfoRecord *) c);
73    p->computeLoad += c->load;
74    p->load = p->computeLoad + p->backgroundLoad;
75 }
76
77 void  RefineLB::deAssign(computeInfo *c, processorInfo *p)
78 {
79    c->processor = -1;
80    p->computeSet->remove(c);
81    p->computeLoad -= c->load;
82    p->load = p->computeLoad + p->backgroundLoad;
83 }
84
85 void RefineLB::computeAverage()
86 {
87    int i;
88    double total = 0;
89    for (i=0; i<numComputes; i++)
90       total += computes[i].load;
91
92    for (i=0; i<P; i++)
93       total += processors[i].backgroundLoad;
94
95    averageLoad = total/P;
96 }
97
98 double RefineLB::computeMax()
99 {
100    int i;
101    double max = processors[0].load;
102    for (i=1; i<P; i++)
103    {
104       if (processors[i].load > max)
105          max = processors[i].load;
106    }
107    return max;
108 }
109
110 int RefineLB::refine()
111 {
112    int finish = 1;
113    maxHeap *heavyProcessors = new maxHeap(P);
114
115    Set *lightProcessors = new Set();
116    int i;
117    for (i=0; i<P; i++)
118    {
119       if (processors[i].load > overLoad*averageLoad)
120       {
121 //CkPrintf("Processor %d is HEAVY: load:%f averageLoad:%f!\n", i, processors[i].load, averageLoad);
122          heavyProcessors->insert((InfoRecord *) &(processors[i]));
123       }
124       else if (processors[i].load < averageLoad)
125       {
126 //CkPrintf("Processor %d is LIGHT: load:%f averageLoad:%f!\n", i, processors[i].load, averageLoad);
127               lightProcessors->insert((InfoRecord *) &(processors[i]));
128       }
129    }
130    int done = 0;
131
132    while (!done)
133    {
134       double bestSize;
135       computeInfo *bestCompute;
136       processorInfo *bestP;
137     
138       processorInfo *donor = (processorInfo *) heavyProcessors->deleteMax();
139       if (!donor) break;
140
141       //find the best pair (c,receiver)
142       Iterator nextProcessor;
143       processorInfo *p = (processorInfo *) 
144              lightProcessors->iterator((Iterator *) &nextProcessor);
145       bestSize = 0;
146       bestP = 0;
147       bestCompute = 0;
148
149       while (p)
150       {
151          Iterator nextCompute;
152          nextCompute.id = 0;
153          computeInfo *c = (computeInfo *) 
154             donor->computeSet->iterator((Iterator *)&nextCompute);
155          // iout << iINFO << "Considering Procsessor : " << p->Id << "\n" << endi;
156          while (c)
157          {
158 //CkPrintf("c->load: %f p->load:%f overLoad*averageLoad:%f \n", c->load, p->load, overLoad*averageLoad);
159             if ( c->load + p->load < overLoad*averageLoad) 
160             {
161                // iout << iINFO << "Considering Compute : " << c->Id << " with load " 
162                //      << c->load << "\n" << endi;
163                if(c->load > bestSize) 
164                {
165                   bestSize = c->load;
166                   bestCompute = c;
167                   bestP = p;
168                }
169             }
170             nextCompute.id++;
171             c = (computeInfo *) donor->computeSet->next((Iterator *)&nextCompute);
172          }
173          p = (processorInfo *) 
174          lightProcessors->next((Iterator *) &nextProcessor);
175       }
176
177       if (bestCompute)
178       {
179 //CkPrintf("Assign: [%d] with load: %f from %d to %d \n", bestCompute->id.id[0], bestCompute->load, donor->Id, bestP->Id);
180         deAssign(bestCompute, donor);      
181         assign(bestCompute, bestP);
182       }
183       else {
184         finish = 0;
185         break;
186       }
187
188       if (bestP->load > averageLoad)
189          lightProcessors->remove(bestP);
190     
191       if (donor->load > overLoad*averageLoad)
192          heavyProcessors->insert((InfoRecord *) donor);
193       else if (donor->load < averageLoad)
194          lightProcessors->insert((InfoRecord *) donor);
195    }  
196    return finish;
197 }
198
199 CLBMigrateMsg* RefineLB::Strategy(CentralLB::LDStats* stats, int count)
200 {
201   CkPrintf("[%d] RefineLB strategy\n",CkMyPe());
202
203   create(stats, count);
204
205   int i;
206   for (i=0; i<numComputes; i++)
207     assign((computeInfo *) &(computes[i]),
208            (processorInfo *) &(processors[computes[i].oldProcessor]));
209
210   computeAverage();
211   overLoad = 1.02;
212
213   refine();
214
215   CkVector migrateInfo;
216
217   for (int pe=0; pe < P; pe++) {
218     Iterator nextCompute;
219     nextCompute.id = 0;
220     computeInfo *c = (computeInfo *)
221          processors[pe].computeSet->iterator((Iterator *)&nextCompute);
222     while(c) {
223       if (c->oldProcessor != c->processor)  {
224         CkPrintf("Migrate: from %d to %d\n",c->oldProcessor, c->processor);
225         MigrateInfo* migrateMe = new MigrateInfo;
226         migrateMe->obj = c->handle;
227         migrateMe->from_pe = c->oldProcessor;
228         migrateMe->to_pe = c->processor;
229         migrateInfo.push_back((void*)migrateMe);
230       }
231       nextCompute.id++;
232       c = (computeInfo *) processors[pe].computeSet->
233                      next((Iterator *)&nextCompute);
234     }
235   }
236
237   int migrate_count=migrateInfo.size();
238   CLBMigrateMsg* msg = new(&migrate_count,1) CLBMigrateMsg;
239   msg->n_moves = migrate_count;
240   for(i=0; i < migrate_count; i++) {
241     MigrateInfo* item = (MigrateInfo*)migrateInfo[i];
242     msg->moves[i] = *item;
243     delete item;
244     migrateInfo[i] = 0;
245   }
246
247   return msg;
248 };
249
250 #endif