16b45675dc337d6d3bc2ef4bf5c9764158f7c4b4
[charm.git] / src / ck-ldb / Comm1LB.C
1 /*****************************************************************************
2  * $Source$
3  * $Author$
4  * $Date$
5  * $Revision$
6  *****************************************************************************/
7
8 /**
9  * \addtogroup CkLdb
10 */
11 /*@{*/
12
13 #include <charm++.h>
14 #include <stdio.h>
15
16 #if CMK_LBDB_ON
17
18 #include "cklists.h"
19
20 #include "Comm1LB.h"
21
22 #define alpha 35e-6
23 #define beeta 8.5e-9
24
25 #define LOWER_FACTOR 0.33
26 #define UPPER_FACTOR 0.67
27 #define MAX_WEIGHT 5.0
28
29 void CreateComm1LB()
30 {
31   loadbalancer = CProxy_Comm1LB::ckNew();
32 }
33
34 static void lbinit(void) {
35 //        LBSetDefaultCreate(CreateComm1LB);        
36   LBRegisterBalancer("Comm1LB", CreateComm1LB, "another variation of CommLB");
37 }
38
39 #include "Comm1LB.def.h"
40
41 Comm1LB::Comm1LB()
42 {
43   if (CkMyPe() == 0)
44     CkPrintf("[%d] Comm1LB created\n",CkMyPe());
45   lbname = "Comm1LB";
46 }
47
48 CmiBool Comm1LB::QueryBalanceNow(int _step)
49 {
50   //  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
51   return CmiTrue;
52 }
53
54 int Comm1LB::search(LDObjid oid, LDOMid mid){
55   int id,hash;
56   
57   hash = (oid.id[0] | oid.id[1]) % nobj;
58
59   for(id=0;id<nobj;id++){
60     if((translate[htable[(id+hash)%nobj]].oid.id[0] == oid.id[0])&&(translate[htable[(id+hash)%nobj]].oid.id[1] == oid.id[1])&&(translate[htable[(id+hash)%nobj]].oid.id[2] == oid.id[2])&&(translate[htable[(id+hash)%nobj]].oid.id[3] == oid.id[3])&&(translate[htable[(id+hash)%nobj]].mid.id == mid.id))
61       return htable[(id + hash)%nobj];
62   }
63   //  CkPrintf("not found \n");
64   return -1;
65 }
66
67 void Comm1LB::alloc(int pe , int id, double load, int nmsg, int nbyte){
68   alloc_array[npe][id].load = 1.0;
69   alloc_array[pe][id].load = load;
70   alloc_array[pe][id].nmsg = nmsg;
71   alloc_array[pe][id].nbyte = nbyte;
72   alloc_array[pe][nobj].load += load;
73   alloc_array[pe][nobj].nmsg += nmsg;
74   alloc_array[pe][nobj].nbyte += nbyte;
75 }
76
77 double Comm1LB::compute_cost(int id, int pe, int n_alloc, int &com_msg, int &com_data){
78   int j;
79   double total_cost, com_cost, weight=0.0;
80   graph * ptr;
81   double bound1,bound2;
82
83   bound1 = LOWER_FACTOR * nobj;
84   bound2 = UPPER_FACTOR * nobj;
85
86   if(n_alloc <= (int)bound1)
87     weight = MAX_WEIGHT;
88   else if((n_alloc > (int)bound1)&&(n_alloc < (int)bound2))
89     weight = (bound2 - n_alloc)/(bound2 - bound1) * (MAX_WEIGHT - 1) + 1;
90   else if(n_alloc >= (int)bound2)
91     weight = 1.0;
92
93 //  weight = MAX_WEIGHT;
94   ptr = object_graph[id].next;
95
96   com_msg = 0;
97   com_data = 0;
98   for(j=0;(j<2*nobj)&&(ptr != NULL);j++,ptr=ptr->next){
99     if(alloc_array[npe][ptr->id].load == 0.0)
100       continue;
101     if(alloc_array[pe][ptr->id].load > 0.0)
102       continue;
103     com_data += ptr->data;
104     com_msg += ptr->nmsg;
105   }
106   com_cost = weight * (alpha*(com_msg + alloc_array[pe][nobj].nmsg) + beeta*(com_data + alloc_array[pe][nobj].nbyte));
107 //  CkPrintf("%d, %d \n",com_data,com_msg);
108   total_cost = alloc_array[pe][nobj].load + com_cost;
109   return total_cost;
110 }
111
112 void Comm1LB::add_graph(int x, int y, int data, int nmsg){
113   graph * ptr, *temp;
114
115 //  CkPrintf("Add graph : %d,%d", data, nmsg);
116   ptr = &(object_graph[x]);  
117   for(;ptr->next != NULL; ptr = ptr->next);
118   
119   temp = new graph;
120   
121   temp->id = y;
122   temp->data = data;
123   temp->nmsg = nmsg;
124   temp->next = NULL;
125
126   ptr->next = temp;
127
128   ptr = &(object_graph[y]);  
129   for(;ptr->next != NULL; ptr = ptr->next);
130   
131   temp = new graph;
132   
133   temp->id = x;
134   temp->data = data;
135   temp->nmsg = nmsg;
136   temp->next = NULL;
137
138   ptr->next = temp;
139 }
140   
141 void Comm1LB::make_hash(){
142   int i, hash;
143   LDObjid oid;
144   
145   htable = new int[nobj];
146   for(i=0;i<nobj;i++)
147     htable[i] = -1;
148   
149   for(i=0;i<nobj;i++){
150     oid = translate[i].oid;
151     hash = ((oid.id[0])|(oid.id[1])) % nobj;
152     while(htable[hash] != -1)
153       hash = (hash+1)%nobj;
154     
155     htable[hash] = i;
156   }
157
158 }
159     
160 void init(alloc_struct **a, graph * object_graph, int l, int b){
161   int i,j;
162
163   for(i=0;i<l+1;i++)
164     for(j=0;j<b+1;j++){
165       a[i][j].load = 0.0;
166       a[i][j].nbyte = 0;
167       a[i][j].nmsg = 0;
168     }
169       
170   for(j=0;j<b;j++){
171     object_graph[j].data = 0;
172     object_graph[j].nmsg = 0;
173     object_graph[j].next = NULL;
174   }
175 }
176
177 LBMigrateMsg* Comm1LB::Strategy(CentralLB::LDStats* stats, int count)
178 {
179   int pe,obj,com;
180   double load_pe=0.0,mean_load =0.0;
181   ObjectRecord *x;
182
183   //  CkPrintf("[%d] Comm1LB strategy\n",CkMyPe());
184
185   CkVec<MigrateInfo*> migrateInfo;
186
187   alloc_array = new alloc_struct *[count+1];
188
189   nobj = stats->n_objs;
190   //  CkPrintf("OBJ: Before \n");
191
192   ObjectHeap maxh(nobj+1);
193   for(obj=0; obj < nobj; obj++) {
194       x = new ObjectRecord;
195       x->id = obj;
196       x->pos = obj;
197       x->load = stats->objData[obj].wallTime;
198       x->pe = stats->from_proc[obj];
199       maxh.insert(x);
200   }
201   for(pe=0; pe < count; pe++) {
202      mean_load += stats->procs[pe].total_walltime;
203   }
204   mean_load /= count;
205 /*
206   for(pe=0; pe < count; pe++) {
207     load_pe = 0.0;
208     for(obj=0; obj < stats[pe].n_objs; obj++) {
209       load_pe += stats->objData[obj].data.wallTime;
210       nobj++;
211       x = new ObjectRecord;
212       x->id = nobj -1;
213       x->pos = obj;
214       x->load = stats->objData[obj].data.wallTime;
215       x->pe = pe;
216       maxh.insert(x);
217     }
218     mean_load += load_pe/count;
219 //    CkPrintf("LOAD on %d = %5.3lf\n",pe,load_pe);
220   }
221 */
222
223   npe = count;
224   translate = new obj_id[nobj];
225   int objno=0;
226
227   for(obj=0; obj < stats->n_objs; obj++){ 
228       LDObjData &oData = stats->objData[obj];
229       translate[objno].mid.id = oData.omID().id;
230       translate[objno].oid.id[0] = oData.id().id[0];
231       translate[objno].oid.id[1] = oData.id().id[1];
232       translate[objno].oid.id[2] = oData.id().id[2];
233       translate[objno].oid.id[3] = oData.id().id[3];
234       objno++;
235   }
236
237   make_hash();
238
239   object_graph = new graph[nobj];
240   
241   for(pe=0;pe <= count;pe++)
242     alloc_array[pe] = new alloc_struct[nobj +1];
243
244   init(alloc_array,object_graph,npe,nobj);
245
246   int xcoord=0,ycoord=0;
247
248   for(com =0; com< stats->n_comm;com++) {
249       LDCommData &commData = stats->commData[com];
250       if((!commData.from_proc())&&(!commData.to_proc())){
251         xcoord = search(commData.sender, commData.senderOM); 
252         ycoord = search(commData.receiver, commData.receiverOM);
253         if((xcoord == -1)||(ycoord == -1))
254           if (lb_ignoreBgLoad) continue;
255           else CkAbort("Error in search\n");
256         add_graph(xcoord,ycoord,commData.bytes, commData.messages);     
257       }
258   }
259   
260   int id,maxid,spe=0,minpe=0,mpos;
261   double temp_cost,min_cost;
262
263   pe = 0;
264   x  = maxh.deleteMax();
265   maxid = x->id;
266   spe = x->pe;
267   mpos = x->pos;
268   
269   alloc(pe,maxid,stats->objData[mpos].wallTime,0,0);
270   if(pe != spe){
271     //      CkPrintf("**Moving from %d to %d\n",spe,pe);
272     MigrateInfo* migrateMe = new MigrateInfo;
273     migrateMe->obj = stats->objData[mpos].handle;
274     migrateMe->from_pe = spe;
275     migrateMe->to_pe = pe;
276     migrateInfo.insertAtEnd(migrateMe);
277   }
278
279   int out_msg,out_byte,min_msg,min_byte;
280
281   for(id = 1;id<nobj;id++){
282     x  = maxh.deleteMax();   
283
284     maxid = x->id;
285     spe = x->pe;
286     mpos = x->pos;
287
288     for(pe =0; pe < count; pe++)
289       if((alloc_array[pe][nobj].load <= mean_load)||(id >= UPPER_FACTOR*nobj))
290         break;
291
292     temp_cost = compute_cost(maxid,pe,id,out_msg,out_byte);
293     min_cost = temp_cost;
294     minpe = pe;
295     min_msg = out_msg;
296     min_byte = out_byte;
297     pe++;
298     for(; pe < count;pe++){
299       if((alloc_array[pe][nobj].load > mean_load) && (id < UPPER_FACTOR*nobj))
300         continue;
301       temp_cost = compute_cost(maxid,pe,id,out_msg,out_byte);
302       if(min_cost > temp_cost){
303         minpe = pe;
304         min_cost = temp_cost;
305         min_msg = out_msg;
306         min_byte = out_byte;
307       }
308     }
309
310     alloc(minpe,maxid,x->load,min_msg,min_byte);
311
312     if(minpe != spe){
313       //      CkPrintf("**Moving from %d to %d\n",spe,minpe);
314       MigrateInfo *migrateMe = new MigrateInfo;
315       migrateMe->obj = stats->objData[mpos].handle;
316       migrateMe->from_pe = spe;
317       migrateMe->to_pe = minpe;
318       migrateInfo.insertAtEnd(migrateMe);
319     }
320   }
321
322   int migrate_count = migrateInfo.length();
323   LBMigrateMsg* msg = new(&migrate_count,1) LBMigrateMsg;
324   msg->n_moves = migrate_count;
325   for(int i=0; i < migrate_count; i++) {
326     MigrateInfo* item = (MigrateInfo*)migrateInfo[i];
327     msg->moves[i] = *item;
328     delete item;
329     migrateInfo[i] = 0;
330   }
331
332   return msg;
333 }
334
335
336 #endif
337
338 /*@}*/
339
340