doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / LBAgent.C
1 /***********************************
2 *       Author : Amit Sharma
3 *       Date : 12/04/2004
4 ************************************/
5
6
7 #include <math.h>
8 #include <string.h>
9
10 #include "LBAgent.h"
11
12 #define PREF_RET_SIZE 5
13
14 TopologyAgent::TopologyAgent(CentralLB::LDStats* lbDB,int p): stats(lbDB), Agent(p){
15         int i;
16
17         LBtopoFn topofn;
18         topofn = LBTopoLookup(_lbtopo);
19   if (topofn == NULL) {
20         char str[1024];
21         CmiPrintf("LBAgent> Fatal error: Unknown topology: %s. Choose from:\n", _lbtopo);
22         printoutTopo();
23         sprintf(str, "LBAgent> Fatal error: Unknown topology: %s", _lbtopo);
24         CmiAbort(str);
25   }
26         topo = topofn(p);
27
28         stats->makeCommHash();
29         preferred_list = new Elem[p];
30         commObjs = new int*[stats->n_objs];
31         for(i=0;i<stats->n_objs;i++){
32                 commObjs[i] = new int[stats->n_objs];
33                 for(int j=0;j<stats->n_objs;j++)
34                         commObjs[i][j] = 0;
35         }
36
37         hopCount = new int*[npes];
38         for(i=0;i<npes;i++){
39                 hopCount[i] = new int[npes];
40                 for(int j=0;j<npes;j++)
41                         hopCount[i][j] = 0;
42         }
43         //commObjs = comm;
44
45         for(i=0;i<stats->n_comm;i++){
46                 //DO I consider other comm too....i.e. to or from a processor
47                 //CkPrintf("in loop..\n");
48                 LDCommData &cdata = stats->commData[i];
49                 if(cdata.from_proc() || cdata.receiver.get_type() != LD_OBJ_MSG)
50                 continue;
51         int senderID = stats->getHash(cdata.sender);
52                 CmiAssert(senderID < stats->n_objs);
53         int recverID = stats->getHash(cdata.receiver.get_destObj());
54         CmiAssert(recverID < stats->n_objs);
55         
56                 //Check with Gengbin if 2 different commData have the same pair of processors as role reversed
57                 //for(int j=0;j<num_comm;j++)
58                         
59                 commObjs[senderID][recverID] += cdata.bytes;
60                 commObjs[recverID][senderID] += cdata.bytes;
61         }
62 }
63
64 int TopologyAgent :: compare(const void *p,const void *q){
65         return (int)(((Elem*)p)->Cost - ((Elem*)q)->Cost);
66 }
67                 
68
69 Agent::Elem* TopologyAgent :: my_preferred_procs(int *existing_map,int object,int *trialpes,int metric) {
70
71         int tp;   // tmp var
72         int *procs_list;
73         
74         //int *preferred_list;
75         //CkPrintf("npes:%d\n",npes);
76         for(int i=0;i<npes;i++){
77                 preferred_list[i].pe = -1;
78                 preferred_list[i].Cost = 0;
79         }
80
81         int preflistSize=0;
82         
83         if(metric==1){ //First metric
84                 //CkPrintf("in first metric\n");
85                 if(trialpes == NULL) {
86                         procs_list = &tp;
87                         *procs_list = -1;
88                 }
89                 else
90                         procs_list = trialpes;
91
92                 //Before everything...construct a list of comm of this object with all the other objects
93                 int proc=0;
94                 int index=0;
95                 int cost=0;
96
97                 if(procs_list[0]!=-1)
98                         proc = procs_list[index];
99         
100                 while(1){
101                         cost=0;
102                         if(!stats->procs[proc].available){
103                                 if(procs_list[0]==-1){
104                                         proc++;
105                                         if(proc == npes)
106                                                 break;
107                                 }
108                                 else {
109                                         index++;
110                                         if(procs_list[index] == -1)
111                                                 break;
112                                         proc = procs_list[index];
113                                 }
114                                 continue;
115                         }
116                 
117                         //First metric --- hops*bytes
118                         for(int i=0;i<stats->n_objs;i++){
119                                 if(existing_map[i]!=-1 && commObjs[object][i]!=0){
120                                         //CkPrintf("before calling get hop count..proc:%d,existing map:%d\n",proc,existing_map[comm[i].obj]);
121                                         if(hopCount[proc][existing_map[i]])
122                                                 cost += hopCount[proc][existing_map[i]]*commObjs[object][i];
123                                         else{
124                                                 hopCount[proc][existing_map[i]]=topo->get_hop_count(proc,existing_map[i]);
125                                                 hopCount[existing_map[i]][proc]=hopCount[proc][existing_map[i]];
126                                                 cost += hopCount[proc][existing_map[i]]*commObjs[object][i];
127                                         }
128                                 }
129                         }
130                         preferred_list[preflistSize].pe = proc;
131                         preferred_list[preflistSize].Cost = cost;
132                         preflistSize++;
133                 
134                         if(procs_list[0]==-1){
135                                 proc++;
136                                 if(proc == npes)
137                                         break;
138                         }
139                         else {
140                                 index++;
141                                 if(procs_list[index] == -1)
142                                         break;
143                                 proc = procs_list[index];
144                         }
145                 }
146         }
147         
148         if(metric==2){
149                 //Second metric --- place the object closer to maximum comm. processor
150                 int i=0;
151                 int max_neighbors = topo->max_neighbors();
152                 int *comProcs = new int[npes];
153                 for(i=0;i<npes;i++)
154                         comProcs[i]=0;
155                 int max_comm=0;
156                 int max_proc=-1;
157                 int *neigh;
158                 for(i=0;i<stats->n_objs;i++){
159                         if(existing_map[i]!=-1 && commObjs[object][i]!=0){
160                                 comProcs[existing_map[i]] += commObjs[object][i];
161                                 if(comProcs[existing_map[i]] > max_comm){
162                                         max_comm = comProcs[existing_map[i]];
163                                         max_proc = existing_map[i];
164                                 }
165                         }
166                 }
167                 int num_neigh=0;
168                 int done=0,j=0;
169                 if(max_proc!=-1){
170                         i=0;
171                         while(trialpes[i]!=-1){
172                                 if(max_proc==trialpes[i]){
173                                         preferred_list[0].pe = max_proc;
174                                         preferred_list[0].Cost = max_comm;
175                                         preflistSize++;
176                                         done = 1;
177                                 }
178                         }
179                         if(!done){
180                                 neigh = new int[max_neighbors];
181                                 topo->neighbors(max_proc,neigh,num_neigh);
182                                 while(trialpes[i]!=-1){
183                                         for(j=0;j<num_neigh;j++)
184                                                 if(trialpes[i]==neigh[j]){
185                                                         preferred_list[preflistSize].pe = neigh[j];
186                                                         preferred_list[preflistSize].Cost = comProcs[neigh[j]];
187                                                         preflistSize++;
188                                                         done=1;
189                                                 }
190                                 }
191                         }
192                         if(!done){
193                                 int *secondneigh = new int[max_neighbors];
194                                 int k=0;
195                                 i=0;
196                                 int num=num_neigh;
197                                 for(k=0;k<num;k++){
198                                         topo->neighbors(neigh[k],secondneigh,num_neigh);
199                                         while(trialpes[i]!=-1){
200                                                 for(j=0;j<num_neigh;j++)
201                                                         if(trialpes[i]==secondneigh[j]){
202                                                                 preferred_list[preflistSize].pe = secondneigh[j];
203                                                                 preferred_list[preflistSize].Cost = comProcs[secondneigh[j]];
204                                                                 preflistSize++;
205                                                                 done=1;
206                                                         }
207                                         }
208                                 }
209                         }
210
211                 }
212         }
213                 /***************************************************************************/
214
215         //Third metric -- as sugggested by Sanjay
216
217         //Sort all the elements of the preferred list in increasing order
218         Agent::Elem *prefreturnList = new Elem[PREF_RET_SIZE+1];
219         int *taken_proc = new int[preflistSize];
220         double min_cost=preferred_list[0].Cost;
221         int min_cost_index=0;
222
223         //prefreturnList[0].pe=preferred_list[min_cost_index].pe;
224         //prefreturnList[0].Cost=preferred_list[min_cost_index].Cost;
225         
226         int s=0;
227         int flag=0;
228         int u=0;
229         
230         for(s=0;s<preflistSize;s++)
231                 taken_proc[s]=0;
232         for(s=0;s<PREF_RET_SIZE;s++){
233                 for(u=0;u<preflistSize;u++)
234                         if(!taken_proc[u]){
235                                 min_cost=preferred_list[u].Cost;
236                                 min_cost_index=u;
237                                 break;
238                         }
239                 if(u==preflistSize)
240                         break;
241                 for(int t=u;t<preflistSize;t++){
242                         if(preferred_list[t].Cost <= min_cost && !taken_proc[t]){
243                                 min_cost = preferred_list[t].Cost;
244                                 min_cost_index=t;
245                                 flag=1;
246                         }
247                 }
248                 if(flag){
249                         taken_proc[min_cost_index]=1;
250                         prefreturnList[s].pe=preferred_list[min_cost_index].pe;
251                         prefreturnList[s].Cost=preferred_list[min_cost_index].Cost;
252                         flag=0;
253                 }
254         }
255         prefreturnList[s].pe=-1;
256         prefreturnList[s].Cost=-1;
257         //qsort(preferred_list,preflistSize,sizeof(Elem),&compare);
258         //for(int k=0;k<preflistSize;k++)
259                 //CkPrintf("pe:%d cost:%d\n",preferred_list[k].pe,preferred_list[k].Cost);
260         
261         return prefreturnList;
262         //return preferred_list;
263 }
264
265 /*****************************************************************************
266                 Multicast Agent 
267 *****************************************************************************/
268
269 MulticastAgent::MulticastAgent(BaseLB::LDStats* stats, int p): Agent(p)
270 {
271   stats->makeCommHash();
272   // build multicast knowledge
273   nobj = stats->n_objs;
274   objmap = new CkVec<int> [nobj];
275   for (int com = 0; com < stats->n_comm;com++) {
276     LDCommData &commData = stats->commData[com];
277     if (commData.recv_type()!=LD_OBJLIST_MSG) continue;
278       // create a multicast instance
279     mcastList.push_back(MInfo(commData.bytes, commData.messages));
280     int mID = mcastList.size()-1;
281     MInfo &minfo = mcastList[mID];
282     int sender = stats->getHash(commData.sender);
283       // stores all multicast that this object (sender) participated
284     objmap[sender].push_back(mID);
285       // stores all objects that belong to this multicast
286     minfo.objs.push_back(sender);
287     int nobjs;
288     LDObjKey *objs = commData.receiver.get_destObjs(nobjs);
289     for (int i=0; i<nobjs; i++) {
290        int receiver = stats->getHash(objs[i]);
291        if((sender == -1)||(receiver == -1)) {
292          if (_lb_args.migObjOnly()) continue;
293          else CkAbort("Error in search\n");
294        }
295        objmap[receiver].push_back(mID);
296        minfo.objs.push_back(receiver);
297     }
298   }
299 }
300
301 Agent::Elem* MulticastAgent::my_preferred_procs(int *existing_map,int object,int *trialpes,int metric){ 
302   int i;
303   // check all multicast this object participated
304   CmiAssert(object < nobj);
305
306   double * comcosts = new double [npes];
307   memset(comcosts, 0, sizeof(double)*npes);
308   double alpha = _lb_args.alpha();
309   double beeta = _lb_args.beeta();
310
311     // all multicast this object belongs to
312   CkVec<int> &mlist = objmap[object];
313   // traverse all multicast participated
314   // find out which processor it communicates the most
315   for (i=0; i<mlist.size(); i++) {
316      MInfo &minfo = mcastList[mlist[i]];
317      for (int obj=0; obj<minfo.objs.size(); obj++) {
318        int pe = existing_map[obj];
319        if (pe == -1) continue;          // not assigned yet
320        comcosts[pe] += minfo.messages * alpha + minfo.nbytes * beeta;
321      }
322   }
323   // find number of processors with non-0 cost
324   int count = 0;
325   for (i=0; i<npes; i++) {
326     if (comcosts[i] != 0.0) count++;
327   }
328   Elem *prefered = new Elem[count+1];
329   for (i=0; i<count; i++) {
330     // find the maximum
331     Elem maxp;    // cost default -1
332     for (int j=0; j<npes; j++)
333       if (comcosts[j] != 0.0 && comcosts[j] > maxp.Cost) {
334         maxp.pe = j;
335         maxp.Cost = comcosts[j];
336       }
337     CmiAssert(maxp.pe!=-1);
338     prefered[i] = maxp;
339     comcosts[maxp.pe] = 0.0;
340   }
341
342   delete [] comcosts;
343   return prefered;
344 }
345
346
347
348