src/ck-ldb/BaseLB.C

   1 /**
   2  * \addtogroup CkLdb
   3 */
   4 /*@{*/
   5
   6 #include "charm++.h"
   7 #include "BaseLB.h"
   8 #include "LBSimulation.h"
   9
  10 #if CMK_LBDB_ON
  11
  12 void BaseLB::initLB(const CkLBOptions &opt) {
  13   seqno = opt.getSeqNo();
  14   CkpvAccess(numLoadBalancers) ++;
  15 /*
  16   if (CkpvAccess(numLoadBalancers) - CkpvAccess(hasNullLB) > 1)
  17     CmiAbort("Error: try to create more than one load balancer strategies!");
  18 */
  19   theLbdb = CProxy_LBDatabase(_lbdb).ckLocalBranch();
  20   lbname = "Unknown";
  21   // register this load balancer to LBDatabase at the sequence number
  22   theLbdb->addLoadbalancer(this, seqno);
  23 }
  24
  25 BaseLB::~BaseLB() {
  26   CkpvAccess(numLoadBalancers) --;
  27 }
  28
  29 void BaseLB::unregister() {
  30   theLbdb->RemoveLocalBarrierReceiver(receiver);
  31   CkpvAccess(numLoadBalancers) --;
  32 }
  33
  34 void BaseLB::pup(PUP::er &p) {
  35   p|seqno;
  36   if (p.isUnpacking())
  37   {
  38     if (CkMyPe()==0) {
  39       if (seqno!=-1) {
  40         int newseq = LBDatabaseObj()->getLoadbalancerTicket();
  41         CmiAssert(newseq == seqno);
  42       }
  43     }
  44     initLB(seqno);
  45   }
  46 }
  47
  48 void BaseLB::flushStates() {
  49   Group::flushStates();
  50   theLbdb->ClearLoads();
  51 }
  52
  53 #else
  54 BaseLB::~BaseLB() {}
  55 void BaseLB::initLB(const CkLBOptions &) {}
  56 void BaseLB::unregister() {}
  57 void BaseLB::pup(PUP::er &p) {}
  58 void BaseLB::flushStates() {}
  59 #endif
  60
  61 static inline int i_abs(int c) { return c>0?c:-c; }
  62
  63 // assume integer is 32 bits
  64 inline static int ObjKey(const LDObjid &oid, const int hashSize) {
  65   // make sure all positive
  66   return (((i_abs(oid.id[2]) & 0x7F)<<24)
  67          |((i_abs(oid.id[1]) & 0xFF)<<16)
  68          |i_abs(oid.id[0])) % hashSize;
  69 }
  70
  71 BaseLB::LDStats::LDStats(int c, int complete)
  72         : n_objs(0), n_migrateobjs(0), n_comm(0),
  73           objHash(NULL), complete_flag(complete)
  74 {
  75   count = c;
  76   if (count == 0) count = CkNumPes();
  77   procs = new ProcStats[count];
  78 }
  79
  80 const static unsigned int doublingPrimes[] = {
  81 3,
  82 7,
  83 17,
  84 37,
  85 73,
  86 157,
  87 307,
  88 617,
  89 1217,
  90 2417,
  91 4817,
  92 9677,
  93 20117,
  94 40177,
  95 80177,
  96 160117,
  97 320107,
  98 640007,
  99 1280107,
 100 2560171,
 101 5120117,
 102 10000079,
 103 20000077,
 104 40000217,
 105 80000111,
 106 160000177,
 107 320000171,
 108 640000171,
 109 1280000017,
 110 2560000217u,
 111 4200000071u
 112 /* extra primes larger than an unsigned 32-bit integer:
 113 51200000077,
 114 100000000171,
 115 200000000171,
 116 400000000171,
 117 800000000117,
 118 1600000000021,
 119 3200000000051,
 120 6400000000081,
 121 12800000000003,
 122 25600000000021,
 123 51200000000077,
 124 100000000000067,
 125 200000000000027,
 126 400000000000063,
 127 800000000000017,
 128 1600000000000007,
 129 3200000000000059,
 130 6400000000000007,
 131 12800000000000009,
 132 25600000000000003,
 133 51200000000000023,
 134 100000000000000003,
 135 200000000000000003,
 136 400000000000000013,
 137 800000000000000119,
 138 1600000000000000031,
 139 3200000000000000059 //This is a 62-bit number
 140 */
 141 };
 142
 143 //This routine returns an arbitrary prime larger than x
 144 static unsigned int primeLargerThan(unsigned int x)
 145 {
 146         int i=0;
 147         while (doublingPrimes[i]<=x) i++;
 148         return doublingPrimes[i];
 149 }
 150
 151 void BaseLB::LDStats::makeCommHash() {
 152   // hash table is already build
 153   if (objHash) return;
 154
 155   int i;
 156   hashSize = n_objs*2;
 157   hashSize = primeLargerThan(hashSize);
 158   objHash = new int[hashSize];
 159   for(i=0;i<hashSize;i++)
 160         objHash[i] = -1;
 161
 162   for(i=0;i<n_objs;i++){
 163         const LDObjid &oid = objData[i].objID();
 164         int hash = ObjKey(oid, hashSize);
 165         CmiAssert(hash != -1);
 166         while(objHash[hash] != -1)
 167             hash = (hash+1)%hashSize;
 168         objHash[hash] = i;
 169   }
 170 }
 171
 172 void BaseLB::LDStats::deleteCommHash() {
 173   if (objHash) delete [] objHash;
 174   objHash = NULL;
 175   for(int i=0; i < n_comm; i++) {
 176       commData[i].clearHash();
 177   }
 178 }
 179
 180 int BaseLB::LDStats::getHash(const LDObjid &oid, const LDOMid &mid)
 181 {
 182 #if CMK_LBDB_ON
 183     CmiAssert(hashSize > 0);
 184     int hash = ObjKey(oid, hashSize);
 185
 186     for(int id=0;id<hashSize;id++){
 187         int index = (id+hash)%hashSize;
 188         if (index == -1 || objHash[index] == -1) return -1;
 189         if (LDObjIDEqual(objData[objHash[index]].objID(), oid) &&
 190             LDOMidEqual(objData[objHash[index]].omID(), mid))
 191             return objHash[index];
 192     }
 193     //  CkPrintf("not found \n");
 194 #endif
 195     return -1;
 196 }
 197
 198 int BaseLB::LDStats::getHash(const LDObjKey &objKey)
 199 {
 200   const LDObjid &oid = objKey.objID();
 201   const LDOMid  &mid = objKey.omID();
 202   return getHash(oid, mid);
 203 }
 204
 205 int BaseLB::LDStats::getSendHash(LDCommData &cData)
 206 {
 207   if (cData.sendHash == -1) {
 208     cData.sendHash = getHash(cData.sender);
 209   }
 210   return cData.sendHash;
 211 }
 212
 213 int BaseLB::LDStats::getRecvHash(LDCommData &cData)
 214 {
 215   if (cData.recvHash == -1) {
 216     cData.recvHash =  getHash(cData.receiver.get_destObj());
 217   }
 218   return cData.recvHash;
 219 }
 220
 221 void BaseLB::LDStats::clearCommHash() {
 222   for(int i=0; i < n_comm; i++) {
 223       commData[i].clearHash();
 224   }
 225 }
 226
 227 void BaseLB::LDStats::computeNonlocalComm(int &nmsgs, int &nbytes)
 228 {
 229 #if CMK_LBDB_ON
 230         nmsgs = 0;
 231         nbytes = 0;
 232
 233         makeCommHash();
 234
 235         int mcast_count = 0;
 236         for (int cidx=0; cidx < n_comm; cidx++) {
 237             LDCommData& cdata = commData[cidx];
 238             int senderPE, receiverPE;
 239             if (cdata.from_proc())
 240               senderPE = cdata.src_proc;
 241             else {
 242               int idx = getHash(cdata.sender);
 243               if (idx == -1) continue;    // sender has just migrated?
 244               senderPE = to_proc[idx];
 245               CmiAssert(senderPE != -1);
 246             }
 247             CmiAssert(senderPE < nprocs() && senderPE >= 0);
 248
 249             // find receiver: point-to-point and multicast two cases
 250             int receiver_type = cdata.receiver.get_type();
 251             if (receiver_type == LD_PROC_MSG || receiver_type == LD_OBJ_MSG) {
 252               if (receiver_type == LD_PROC_MSG)
 253                 receiverPE = cdata.receiver.proc();
 254               else  {  // LD_OBJ_MSG
 255                 int idx = getHash(cdata.receiver.get_destObj());
 256                 if (idx == -1) {                // receiver outside this domain
 257                   if (complete_flag) continue;
 258                   else receiverPE = -1;
 259                 }
 260                 else {
 261                   receiverPE = to_proc[idx];
 262                   CmiAssert(receiverPE < nprocs() && receiverPE >= 0);
 263                 }
 264               }
 265               if(senderPE != receiverPE)
 266               {
 267                 nmsgs += cdata.messages;
 268                 nbytes += cdata.bytes;
 269               }
 270             }
 271             else if (receiver_type == LD_OBJLIST_MSG) {
 272               int nobjs;
 273               LDObjKey *objs = cdata.receiver.get_destObjs(nobjs);
 274               mcast_count ++;
 275               CkVec<int> pes;
 276               for (int i=0; i<nobjs; i++) {
 277                 int idx = getHash(objs[i]);
 278                 CmiAssert(idx != -1);
 279                 if (idx == -1) continue;    // receiver has just been removed?
 280                 receiverPE = to_proc[idx];
 281                 CmiAssert(receiverPE < nprocs() && receiverPE >= 0);
 282                 int exist = 0;
 283                 for (int p=0; p<pes.size(); p++)
 284                   if (receiverPE == pes[p]) { exist=1; break; }
 285                 if (exist) continue;
 286                 pes.push_back(receiverPE);
 287                 if(senderPE != receiverPE)
 288                 {
 289                   nmsgs += cdata.messages;
 290                   nbytes += cdata.bytes;
 291                 }
 292               }
 293             }
 294         }   // end of for
 295 #endif
 296 }
 297
 298 void BaseLB::LDStats::normalize_speed() {
 299   int pe;
 300   double maxspeed = 0.0;
 301
 302   for(int pe=0; pe < nprocs(); pe++) {
 303     if (procs[pe].pe_speed > maxspeed) maxspeed = procs[pe].pe_speed;
 304   }
 305   for(int pe=0; pe < nprocs(); pe++)
 306     procs[pe].pe_speed /= maxspeed;
 307 }
 308
 309 void BaseLB::LDStats::print()
 310 {
 311 #if CMK_LBDB_ON
 312   int i;
 313   CkPrintf("------------- Processor Data: %d -------------\n", nprocs());
 314   for(int pe=0; pe < nprocs(); pe++) {
 315     struct ProcStats &proc = procs[pe];
 316
 317     CkPrintf("Proc %d (%d) Speed %d Total = %f Idle = %f Bg = %f nObjs = %d",
 318       pe, proc.pe, proc.pe_speed, proc.total_walltime, proc.idletime,
 319       proc.bg_walltime, proc.n_objs);
 320 #if CMK_LB_CPUTIMER
 321     CkPrintf(" CPU Total %f Bg %f", proc.total_cputime, proc.bg_cputime);
 322 #endif
 323     CkPrintf("\n");
 324   }
 325
 326   CkPrintf("------------- Object Data: %d objects -------------\n", n_objs);
 327   for(i=0; i < n_objs; i++) {
 328       LDObjData &odata = objData[i];
 329       CkPrintf("Object %d\n",i);
 330       CkPrintf("     id = %d %d %d %d\n",odata.objID().id[0],odata.objID().id[1
 331 ], odata.objID().id[2], odata.objID().id[3]);
 332       CkPrintf("  OM id = %d\t",odata.omID().id);
 333       CkPrintf("   Mig. = %d\n",odata.migratable);
 334 #if CMK_LB_CPUTIMER
 335       CkPrintf("    CPU = %f\t",odata.cpuTime);
 336 #endif
 337       CkPrintf("   Wall = %f\n",odata.wallTime);
 338   }
 339
 340   CkPrintf("------------- Comm Data: %d records -------------\n", n_comm);
 341   CkVec<LDCommData> &cdata = commData;
 342   for(i=0; i < n_comm; i++) {
 343       CkPrintf("Link %d\n",i);
 344
 345       LDObjid &sid = cdata[i].sender.objID();
 346       if (cdata[i].from_proc())
 347         CkPrintf("    sender PE = %d\t",cdata[i].src_proc);
 348       else
 349         CkPrintf("    sender id = %d:[%d %d %d %d]\t",
 350                  cdata[i].sender.omID().id,sid.id[0], sid.id[1], sid.id[2], sid.id[3]);
 351
 352       LDObjid &rid = cdata[i].receiver.get_destObj().objID();
 353       if (cdata[i].recv_type() == LD_PROC_MSG)
 354         CkPrintf("  receiver PE = %d\n",cdata[i].receiver.proc());
 355       else
 356         CkPrintf("  receiver id = %d:[%d %d %d %d]\n",
 357                  cdata[i].receiver.get_destObj().omID().id,rid.id[0],rid.id[1],rid.id[2],rid.id[3]);
 358
 359       CkPrintf("     messages = %d\t",cdata[i].messages);
 360       CkPrintf("        bytes = %d\n",cdata[i].bytes);
 361   }
 362   CkPrintf("------------- Object to PE mapping -------------\n");
 363   for (i=0; i<n_objs; i++) CkPrintf(" %d", from_proc[i]);
 364   CkPrintf("\n");
 365 #endif
 366 }
 367
 368 double BaseLB::LDStats::computeAverageLoad()
 369 {
 370   int i, numAvail=0;
 371   double total = 0;
 372   for (i=0; i<n_objs; i++) total += objData[i].wallTime;
 373
 374   for (i=0; i<nprocs(); i++)
 375     if (procs[i].available == true) {
 376         total += procs[i].bg_walltime;
 377         numAvail++;
 378     }
 379
 380   double averageLoad = total/numAvail;
 381   return averageLoad;
 382 }
 383
 384 // remove the obj-th object from database
 385 void BaseLB::LDStats::removeObject(int obj)
 386 {
 387   CmiAssert(obj < objData.size());
 388   LDObjData odata = objData[obj];
 389
 390   LDObjKey okey;                // build a key
 391   okey.omID() = odata.omID();
 392   okey.objID() = odata.objID();
 393
 394   objData.remove(obj);
 395   from_proc.remove(obj);
 396   to_proc.remove(obj);
 397   n_objs --;
 398   if (odata.migratable) n_migrateobjs --;
 399
 400   // search for sender, can be multiple sender
 401   int removed = 0;
 402   for (int com=0; com<n_comm; com++) {
 403     LDCommData &cdata = commData[com-removed];
 404     if(!cdata.from_proc() && cdata.sender == okey) {
 405       commData.remove(com-removed);
 406       removed++;
 407     }
 408   }
 409   n_comm -= removed;
 410 }
 411
 412 void BaseLB::LDStats::pup(PUP::er &p)
 413 {
 414   int i;
 415   p(count);
 416   p(n_objs);
 417   p(n_migrateobjs);
 418   p(n_comm);
 419   if (p.isUnpacking()) {
 420     // user can specify simulated processors other than the real # of procs.
 421     int maxpe = nprocs() > LBSimulation::simProcs ? nprocs() : LBSimulation::simProcs;
 422     procs = new ProcStats[maxpe];
 423     objData.resize(n_objs);
 424     commData.resize(n_comm);
 425     from_proc.resize(n_objs);
 426     to_proc.resize(n_objs);
 427     objHash = NULL;
 428   }
 429   // ignore the background load when unpacking if the user change the # of procs
 430   // otherwise load everything
 431   if (p.isUnpacking() && LBSimulation::procsChanged) {
 432     ProcStats dummy;
 433     for (i=0; i<nprocs(); i++) p|dummy;
 434   }
 435   else
 436     for (i=0; i<nprocs(); i++) p|procs[i];
 437   for (i=0; i<n_objs; i++) p|objData[i];
 438   for (i=0; i<n_objs; i++) p|from_proc[i];
 439   for (i=0; i<n_objs; i++) p|to_proc[i];
 440   // reset to_proc when unpacking
 441   if (p.isUnpacking())
 442     for (i=0; i<n_objs; i++) to_proc[i] = from_proc[i];
 443   for (i=0; i<n_comm; i++) p|commData[i];
 444   if (p.isUnpacking())
 445     count = LBSimulation::simProcs;
 446   if (p.isUnpacking()) {
 447     objHash = NULL;
 448     if (_lb_args.lbversion() <= 1)
 449       for (i=0; i<nprocs(); i++) procs[i].pe = i;
 450   }
 451 }
 452
 453 int BaseLB::LDStats::useMem() {
 454   // calculate the memory usage of this LB (superclass).
 455   return sizeof(LDStats) + sizeof(ProcStats) * nprocs() +
 456          (sizeof(LDObjData) + 2 * sizeof(int)) * n_objs +
 457          sizeof(LDCommData) * n_comm;
 458 }
 459
 460 #include "BaseLB.def.h"
 461
 462 /*@}*/