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 beta = _lb_args.beta();
 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 * beta;
 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