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