ck-ldb: the API for the virtual work function changed
[charm.git] / src / ck-ldb / CommLB.C
1 /**
2  * \addtogroup CkLdb
3 */
4 /*@{*/
5
6 /*
7   status:
8   * knows nonmigratable attribe
9   * doesnot support processor avail bitvector
10
11   rewritten by Gengbin Zheng to use the new load balancer database and comm hash table;
12   modified to recognize the nonmigratable attrib of an object 
13   by Gengbin Zheng, 7/28/2003
14
15 */
16
17 #include <charm++.h>
18 #include <stdio.h>
19
20 #include "cklists.h"
21
22 #include "CommLB.h"
23
24 #define alpha 35e-6
25 #define beeta 8.5e-9
26
27 #define LOWER_FACTOR 0.33
28 #define UPPER_FACTOR 0.67
29 #define MAX_WEIGHT 5.0
30
31 CreateLBFunc_Def(CommLB, "another variation of CommLB")
32
33 CommLB::CommLB(const CkLBOptions &opt): CentralLB(opt)
34 {
35   if (CkMyPe() == 0)
36     CkPrintf("[%d] CommLB created\n",CkMyPe());
37   lbname = "CommLB";
38 }
39
40 CmiBool CommLB::QueryBalanceNow(int _step)
41 {
42   //  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
43   return CmiTrue;
44 }
45
46 void CommLB::alloc(int pe , int id, double load, int nmsg, int nbyte){
47   alloc_array[npe][id].load = 1.0;
48   alloc_array[pe][id].load = load;
49   alloc_array[pe][id].nmsg = nmsg;
50   alloc_array[pe][id].nbyte = nbyte;
51   alloc_array[pe][nobj].load += load;
52   alloc_array[pe][nobj].nmsg += nmsg;
53   alloc_array[pe][nobj].nbyte += nbyte;
54 }
55
56 double CommLB::compute_cost(int id, int pe, int n_alloc, int &com_msg, int &com_data){
57   int j;
58   double total_cost, com_cost, weight=0.0;
59   graph * ptr;
60   double bound1,bound2;
61
62   bound1 = LOWER_FACTOR * nobj;
63   bound2 = UPPER_FACTOR * nobj;
64
65   if(n_alloc <= (int)bound1)
66     weight = MAX_WEIGHT;
67   else if((n_alloc > (int)bound1)&&(n_alloc < (int)bound2))
68     weight = (bound2 - n_alloc)/(bound2 - bound1) * (MAX_WEIGHT - 1) + 1;
69   else if(n_alloc >= (int)bound2)
70     weight = 1.0;
71
72 //  weight = MAX_WEIGHT;
73   ptr = object_graph[id].next;
74
75   com_msg = 0;
76   com_data = 0;
77   for(j=0;(j<2*nobj)&&(ptr != NULL);j++,ptr=ptr->next){
78     if(alloc_array[npe][ptr->id].load == 0.0)
79       continue;
80     if(alloc_array[pe][ptr->id].load > 0.0)
81       continue;
82     com_data += ptr->data;
83     com_msg += ptr->nmsg;
84   }
85   com_cost = weight * (alpha*(com_msg + alloc_array[pe][nobj].nmsg) + beeta*(com_data + alloc_array[pe][nobj].nbyte));
86 //  CkPrintf("%d, %d \n",com_data,com_msg);
87   total_cost = alloc_array[pe][nobj].load + com_cost;
88   return total_cost;
89 }
90
91 void CommLB::add_graph(int x, int y, int data, int nmsg){
92   graph * ptr, *temp;
93
94 //  CkPrintf("Add graph : %d,%d", data, nmsg);
95   ptr = &(object_graph[x]);  
96   for(;ptr->next != NULL; ptr = ptr->next);
97   
98   temp = new graph;
99   
100   temp->id = y;
101   temp->data = data;
102   temp->nmsg = nmsg;
103   temp->next = NULL;
104
105   ptr->next = temp;
106
107   ptr = &(object_graph[y]);  
108   for(;ptr->next != NULL; ptr = ptr->next);
109   
110   temp = new graph;
111   
112   temp->id = x;
113   temp->data = data;
114   temp->nmsg = nmsg;
115   temp->next = NULL;
116
117   ptr->next = temp;
118 }
119   
120  
121 void init(alloc_struct **a, graph * object_graph, int l, int b){
122   int i,j;
123
124   for(i=0;i<l+1;i++)
125     for(j=0;j<b+1;j++){
126       a[i][j].load = 0.0;
127       a[i][j].nbyte = 0;
128       a[i][j].nmsg = 0;
129     }
130       
131   for(j=0;j<b;j++){
132     object_graph[j].data = 0;
133     object_graph[j].nmsg = 0;
134     object_graph[j].next = NULL;
135   }
136 }
137
138 void CommLB::work(LDStats* stats)
139 {
140   int pe,obj,com;
141   double mean_load =0.0;
142   ObjectRecord *x;
143
144   //  CkPrintf("[%d] CommLB strategy\n",CkMyPe());
145
146   nobj = stats->n_objs;
147   npe = stats->count;
148
149   stats->makeCommHash();
150
151   alloc_array = new alloc_struct *[npe + 1];
152
153   object_graph = new graph[nobj];
154   
155   for(pe = 0; pe <= npe; pe++)
156     alloc_array[pe] = new alloc_struct[nobj +1];
157
158   init(alloc_array,object_graph,npe,nobj);
159
160   ObjectHeap maxh(nobj+1);
161   for(obj=0; obj < nobj; obj++) {
162       LDObjData &objData = stats->objData[obj];
163       int onpe = stats->from_proc[obj];
164       x = new ObjectRecord;
165       x->id = obj;
166       x->pos = obj;
167       x->val = objData.wallTime;
168       x->pe = onpe;
169       maxh.insert(x);
170       mean_load += objData.wallTime;
171   }
172   mean_load /= npe;
173
174   int xcoord=0,ycoord=0;
175
176   for(com =0; com< stats->n_comm;com++) {
177       LDCommData &commData = stats->commData[com];
178       if((!commData.from_proc())&&(commData.recv_type()==LD_OBJ_MSG)){
179         xcoord = stats->getHash(commData.sender); 
180         ycoord = stats->getHash(commData.receiver.get_destObj());
181         if((xcoord == -1)||(ycoord == -1))
182           if (_lb_args.ignoreBgLoad()) continue;
183           else CkAbort("Error in search\n");
184         add_graph(xcoord,ycoord,commData.bytes, commData.messages);     
185       }
186   }
187   
188   int id,maxid,spe=0,minpe=0,mpos;
189   double temp_cost,min_cost;
190
191   pe = 0;
192   x  = maxh.deleteMax();
193   maxid = x->id;
194   spe = x->pe;
195   mpos = x->pos;
196   
197   alloc(pe,maxid,stats->objData[mpos].wallTime,0,0);
198   if(pe != spe){
199     //      CkPrintf("**Moving from %d to %d\n",spe,pe);
200     CmiAssert(stats->from_proc[mpos] == spe);
201     stats->to_proc[mpos] = pe;
202   }
203
204   int out_msg,out_byte,min_msg,min_byte;
205
206   for(id = 1;id<nobj;id++){
207     x  = maxh.deleteMax();   
208
209     maxid = x->id;
210     spe = x->pe;
211     mpos = x->pos;
212     LDObjData &objData = stats->objData[mpos];
213
214     if (!objData.migratable) {
215       if (!stats->procs[spe].available) {
216           CmiAbort("Load balancer is not be able to move a nonmigratable object out of an unavailable processor.\n");
217       }
218       temp_cost = compute_cost(maxid,spe,id,out_msg,out_byte);
219       alloc(spe, maxid, x->val, out_msg, out_byte);
220       continue;
221     }
222
223     for(pe =0; pe < npe; pe++)
224       if((alloc_array[pe][nobj].load <= mean_load)||(id >= UPPER_FACTOR*nobj))
225         break;
226     CmiAssert(pe < npe);
227
228     temp_cost = compute_cost(maxid,pe,id,out_msg,out_byte);
229     min_cost = temp_cost;
230     minpe = pe;
231     min_msg = out_msg;
232     min_byte = out_byte;
233     pe++;
234     for(; pe < npe; pe++) {
235       if((alloc_array[pe][nobj].load > mean_load) && (id < UPPER_FACTOR*nobj))
236         continue;
237       temp_cost = compute_cost(maxid,pe,id,out_msg,out_byte);
238       if(min_cost > temp_cost){
239         minpe = pe;
240         min_cost = temp_cost;
241         min_msg = out_msg;
242         min_byte = out_byte;
243       }
244     }
245     CmiAssert(minpe < npe);
246
247     alloc(minpe, maxid, x->val, min_msg, min_byte);
248
249     if(minpe != spe){
250       //      CkPrintf("**Moving from %d to %d\n",spe,minpe);
251       CmiAssert(stats->from_proc[mpos] == spe);
252       stats->to_proc[mpos] = minpe;
253     }
254   }
255 }
256
257 #include "CommLB.def.h"
258
259 /*@}*/
260
261