Charm++: Charm Source Code Documentation

00001 
00005 
00006 #include "charm++.h"
00007 #include "BaseLB.h"
00008 #include "LBSimulation.h"
00009 
00010 #if CMK_LBDB_ON
00011 
00012 void BaseLB::initLB(const CkLBOptions &opt) {
00013   seqno = opt.getSeqNo();
00014   CkpvAccess(numLoadBalancers) ++;
00015 /*
00016   if (CkpvAccess(numLoadBalancers) - CkpvAccess(hasNullLB) > 1)
00017     CmiAbort("Error: try to create more than one load balancer strategies!");
00018 */
00019   theLbdb = CProxy_LBDatabase(_lbdb).ckLocalBranch();
00020   lbname = "Unknown";
00021   // register this load balancer to LBDatabase at the sequence number
00022   theLbdb->addLoadbalancer(this, seqno);
00023 }
00024 
00025 BaseLB::~BaseLB() {
00026   CkpvAccess(numLoadBalancers) --;
00027 }
00028 
00029 void BaseLB::unregister() {
00030   theLbdb->RemoveLocalBarrierReceiver(receiver);
00031   CkpvAccess(numLoadBalancers) --;
00032 }
00033 
00034 void BaseLB::pup(PUP::er &p) { 
00035   CBase_BaseLB::pup(p); 
00036   p|seqno;
00037   if (p.isUnpacking())
00038   {
00039     if (CkMyPe()==0) {
00040       if (seqno!=-1) {
00041         int newseq = LBDatabaseObj()->getLoadbalancerTicket();
00042         CmiAssert(newseq == seqno);
00043       }
00044     }
00045     initLB(seqno);
00046   }
00047 }
00048 
00049 void BaseLB::flushStates() {
00050   theLbdb->ClearLoads();
00051 }
00052 
00053 #else
00054 BaseLB::~BaseLB() {} 
00055 void BaseLB::initLB(const CkLBOptions &) {}
00056 void BaseLB::unregister() {}
00057 void BaseLB::pup(PUP::er &p) {}
00058 void BaseLB::flushStates() {}
00059 #endif
00060 
00061 static inline int i_abs(int c) { return c>0?c:-c; }
00062 
00063 // assume integer is 32 bits
00064 inline static int ObjKey(const LDObjid &oid, const int hashSize) {
00065   // make sure all positive
00066   return (((i_abs(oid.id[2]) & 0x7F)<<24)
00067          |((i_abs(oid.id[1]) & 0xFF)<<16)
00068          |i_abs(oid.id[0])) % hashSize;
00069 }
00070 
00071 BaseLB::LDStats::LDStats(int c, int complete)
00072         : n_objs(0), n_migrateobjs(0), n_comm(0), 
00073           objHash(NULL), complete_flag(complete)
00074 {
00075   count = c;
00076   if (count == 0) count = CkNumPes();
00077   procs = new ProcStats[count];
00078 }
00079 
00080 const static unsigned int doublingPrimes[] = {
00081 3,
00082 7,
00083 17,
00084 37,
00085 73,
00086 157,
00087 307,
00088 617,
00089 1217,
00090 2417,
00091 4817,
00092 9677,
00093 20117,
00094 40177,
00095 80177,
00096 160117,
00097 320107,
00098 640007,
00099 1280107,
00100 2560171,
00101 5120117,
00102 10000079,
00103 20000077,
00104 40000217,
00105 80000111,
00106 160000177,
00107 320000171,
00108 640000171,
00109 1280000017,
00110 2560000217u,
00111 4200000071u
00112 /* extra primes larger than an unsigned 32-bit integer:
00113 51200000077,
00114 100000000171,
00115 200000000171,
00116 400000000171,
00117 800000000117,
00118 1600000000021,
00119 3200000000051,
00120 6400000000081,
00121 12800000000003,
00122 25600000000021,
00123 51200000000077,
00124 100000000000067,
00125 200000000000027,
00126 400000000000063,
00127 800000000000017,
00128 1600000000000007,
00129 3200000000000059,
00130 6400000000000007,
00131 12800000000000009,
00132 25600000000000003,
00133 51200000000000023,
00134 100000000000000003,
00135 200000000000000003,
00136 400000000000000013,
00137 800000000000000119,
00138 1600000000000000031,
00139 3200000000000000059 //This is a 62-bit number
00140 */
00141 };
00142 
00143 //This routine returns an arbitrary prime larger than x
00144 static unsigned int primeLargerThan(unsigned int x)
00145 {
00146         int i=0;
00147         while (doublingPrimes[i]<=x) i++;
00148         return doublingPrimes[i];
00149 }
00150 
00151 void BaseLB::LDStats::makeCommHash() {
00152   // hash table is already build
00153   if (objHash) return;
00154    
00155   int i;
00156   hashSize = n_objs*2;
00157   hashSize = primeLargerThan(hashSize);
00158   objHash = new int[hashSize];
00159   for(i=0;i<hashSize;i++)
00160         objHash[i] = -1;
00161    
00162   for(i=0;i<n_objs;i++){
00163         const LDObjid &oid = objData[i].objID();
00164         int hash = ObjKey(oid, hashSize);
00165         CmiAssert(hash != -1);
00166         while(objHash[hash] != -1)
00167             hash = (hash+1)%hashSize;
00168         objHash[hash] = i;
00169   }
00170 }
00171 
00172 void BaseLB::LDStats::deleteCommHash() {
00173   if (objHash) delete [] objHash;
00174   objHash = NULL;
00175   for(int i=0; i < n_comm; i++) {
00176       commData[i].clearHash();
00177   }
00178 }
00179 
00180 int BaseLB::LDStats::getHash(const LDObjid &oid, const LDOMid &mid)
00181 {
00182 #if CMK_LBDB_ON
00183     CmiAssert(hashSize > 0);
00184     int hash = ObjKey(oid, hashSize);
00185 
00186     for(int id=0;id<hashSize;id++){
00187         int index = (id+hash)%hashSize;
00188         if (index == -1 || objHash[index] == -1) return -1;
00189         if (LDObjIDEqual(objData[objHash[index]].objID(), oid) &&
00190             LDOMidEqual(objData[objHash[index]].omID(), mid))
00191             return objHash[index];
00192     }
00193     //  CkPrintf("not found \n");
00194 #endif
00195     return -1;
00196 }
00197 
00198 int BaseLB::LDStats::getHash(const LDObjKey &objKey)
00199 {
00200   const LDObjid &oid = objKey.objID();
00201   const LDOMid  &mid = objKey.omID();
00202   return getHash(oid, mid);
00203 }
00204 
00205 int BaseLB::LDStats::getSendHash(LDCommData &cData)
00206 {
00207   if (cData.sendHash == -1) {
00208     cData.sendHash = getHash(cData.sender);
00209   }
00210   return cData.sendHash;
00211 }
00212 
00213 int BaseLB::LDStats::getRecvHash(LDCommData &cData)
00214 {
00215   if (cData.recvHash == -1) {
00216     cData.recvHash =  getHash(cData.receiver.get_destObj());
00217   }
00218   return cData.recvHash;
00219 }
00220 
00221 void BaseLB::LDStats::clearCommHash() {
00222   for(int i=0; i < n_comm; i++) {
00223       commData[i].clearHash();
00224   }
00225 }
00226 
00227 void BaseLB::LDStats::computeNonlocalComm(int &nmsgs, int &nbytes)
00228 {
00229 #if CMK_LBDB_ON
00230         nmsgs = 0;
00231         nbytes = 0;
00232 
00233         makeCommHash();
00234 
00235         int mcast_count = 0;
00236         for (int cidx=0; cidx < n_comm; cidx++) {
00237             LDCommData& cdata = commData[cidx];
00238             int senderPE, receiverPE;
00239             if (cdata.from_proc())
00240               senderPE = cdata.src_proc;
00241             else {
00242               int idx = getHash(cdata.sender);
00243               if (idx == -1) continue;    // sender has just migrated?
00244               senderPE = to_proc[idx];
00245               CmiAssert(senderPE != -1);
00246             }
00247             CmiAssert(senderPE < nprocs() && senderPE >= 0);
00248 
00249             // find receiver: point-to-point and multicast two cases
00250             int receiver_type = cdata.receiver.get_type();
00251             if (receiver_type == LD_PROC_MSG || receiver_type == LD_OBJ_MSG) {
00252               if (receiver_type == LD_PROC_MSG)
00253                 receiverPE = cdata.receiver.proc();
00254               else  {  // LD_OBJ_MSG
00255                 int idx = getHash(cdata.receiver.get_destObj());
00256                 if (idx == -1) {                // receiver outside this domain
00257                   if (complete_flag) continue;
00258                   else receiverPE = -1;
00259                 }
00260                 else {
00261                   receiverPE = to_proc[idx];
00262                   CmiAssert(receiverPE < nprocs() && receiverPE >= 0);
00263                 }
00264               }
00265               if(senderPE != receiverPE)
00266               {
00267                 nmsgs += cdata.messages;
00268                 nbytes += cdata.bytes;
00269               }
00270             }
00271             else if (receiver_type == LD_OBJLIST_MSG) {
00272               int nobjs;
00273               LDObjKey *objs = cdata.receiver.get_destObjs(nobjs);
00274               mcast_count ++;
00275               CkVec<int> pes;
00276               for (int i=0; i<nobjs; i++) {
00277                 int idx = getHash(objs[i]);
00278                 CmiAssert(idx != -1);
00279                 if (idx == -1) continue;    // receiver has just been removed?
00280                 receiverPE = to_proc[idx];
00281                 CmiAssert(receiverPE < nprocs() && receiverPE >= 0);
00282                 int exist = 0;
00283                 for (int p=0; p<pes.size(); p++) 
00284                   if (receiverPE == pes[p]) { exist=1; break; }
00285                 if (exist) continue;
00286                 pes.push_back(receiverPE);
00287                 if(senderPE != receiverPE)
00288                 {
00289                   nmsgs += cdata.messages;
00290                   nbytes += cdata.bytes;
00291                 }
00292               }
00293             }
00294         }   // end of for
00295 #endif
00296 }
00297 
00298 void BaseLB::LDStats::normalize_speed() {
00299   int pe;
00300   double maxspeed = 0.0;
00301 
00302   for(int pe=0; pe < nprocs(); pe++) {
00303     if (procs[pe].pe_speed > maxspeed) maxspeed = procs[pe].pe_speed;
00304   }
00305   for(int pe=0; pe < nprocs(); pe++)
00306     procs[pe].pe_speed /= maxspeed;
00307 }
00308 
00309 void BaseLB::LDStats::print()
00310 {
00311 #if CMK_LBDB_ON
00312   int i;
00313   CkPrintf("------------- Processor Data: %d -------------\n", nprocs());
00314   for(int pe=0; pe < nprocs(); pe++) {
00315     struct ProcStats &proc = procs[pe];
00316 
00317     CkPrintf("Proc %d (%d) Speed %d Total = %f Idle = %f Bg = %f nObjs = %d",
00318       pe, proc.pe, proc.pe_speed, proc.total_walltime, proc.idletime,
00319       proc.bg_walltime, proc.n_objs);
00320 #if CMK_LB_CPUTIMER
00321     CkPrintf(" CPU Total %f Bg %f", proc.total_cputime, proc.bg_cputime);
00322 #endif
00323     CkPrintf("\n");
00324   }
00325 
00326   CkPrintf("------------- Object Data: %d objects -------------\n", n_objs);
00327   for(i=0; i < n_objs; i++) {
00328       LDObjData &odata = objData[i];
00329       CkPrintf("Object %d\n",i);
00330       CkPrintf("     id = %d %d %d %d\n",odata.objID().id[0],odata.objID().id[1
00331 ], odata.objID().id[2], odata.objID().id[3]);
00332       CkPrintf("  OM id = %d\t",odata.omID().id);
00333       CkPrintf("   Mig. = %d\n",odata.migratable);
00334 #if CMK_LB_CPUTIMER
00335       CkPrintf("    CPU = %f\t",odata.cpuTime);
00336 #endif
00337       CkPrintf("   Wall = %f\n",odata.wallTime);
00338   }
00339 
00340   CkPrintf("------------- Comm Data: %d records -------------\n", n_comm);
00341   CkVec<LDCommData> &cdata = commData;
00342   for(i=0; i < n_comm; i++) {
00343       CkPrintf("Link %d\n",i);
00344 
00345       LDObjid &sid = cdata[i].sender.objID();
00346       if (cdata[i].from_proc())
00347         CkPrintf("    sender PE = %d\t",cdata[i].src_proc);
00348       else
00349         CkPrintf("    sender id = %d:[%d %d %d %d]\t",
00350                  cdata[i].sender.omID().id,sid.id[0], sid.id[1], sid.id[2], sid.id[3]);
00351 
00352       LDObjid &rid = cdata[i].receiver.get_destObj().objID();
00353       if (cdata[i].recv_type() == LD_PROC_MSG)
00354         CkPrintf("  receiver PE = %d\n",cdata[i].receiver.proc());
00355       else      
00356         CkPrintf("  receiver id = %d:[%d %d %d %d]\n",
00357                  cdata[i].receiver.get_destObj().omID().id,rid.id[0],rid.id[1],rid.id[2],rid.id[3]);
00358       
00359       CkPrintf("     messages = %d\t",cdata[i].messages);
00360       CkPrintf("        bytes = %d\n",cdata[i].bytes);
00361   }
00362   CkPrintf("------------- Object to PE mapping -------------\n");
00363   for (i=0; i<n_objs; i++) CkPrintf(" %d", from_proc[i]);
00364   CkPrintf("\n");
00365 #endif
00366 }
00367 
00368 double BaseLB::LDStats::computeAverageLoad()
00369 {
00370   int i, numAvail=0;
00371   double total = 0;
00372   for (i=0; i<n_objs; i++) total += objData[i].wallTime;
00373                                                                                 
00374   for (i=0; i<nprocs(); i++)
00375     if (procs[i].available == CmiTrue) {
00376         total += procs[i].bg_walltime;
00377         numAvail++;
00378     }
00379                                                                                 
00380   double averageLoad = total/numAvail;
00381   return averageLoad;
00382 }
00383 
00384 // remove the obj-th object from database
00385 void BaseLB::LDStats::removeObject(int obj)
00386 {
00387   CmiAssert(obj < objData.size());
00388   LDObjData odata = objData[obj];
00389 
00390   LDObjKey okey;                // build a key
00391   okey.omID() = odata.omID();
00392   okey.objID() = odata.objID();
00393 
00394   objData.remove(obj);
00395   from_proc.remove(obj);
00396   to_proc.remove(obj);
00397   n_objs --;
00398   if (odata.migratable) n_migrateobjs --;
00399 
00400   // search for sender, can be multiple sender
00401   int removed = 0;
00402   for (int com=0; com<n_comm; com++) {
00403     LDCommData &cdata = commData[com-removed];
00404     if(!cdata.from_proc() && cdata.sender == okey) {
00405       commData.remove(com-removed);
00406       removed++;
00407     }
00408   }
00409   n_comm -= removed;
00410 }
00411 
00412 void BaseLB::LDStats::pup(PUP::er &p)
00413 {
00414   int i;
00415   p(count);
00416   p(n_objs);
00417   p(n_migrateobjs);
00418   p(n_comm);
00419   if (p.isUnpacking()) {
00420     // user can specify simulated processors other than the real # of procs.
00421     int maxpe = nprocs() > LBSimulation::simProcs ? nprocs() : LBSimulation::simProcs;
00422     procs = new ProcStats[maxpe];
00423     objData.resize(n_objs);
00424     commData.resize(n_comm);
00425     from_proc.resize(n_objs);
00426     to_proc.resize(n_objs);
00427     objHash = NULL;
00428   }
00429   // ignore the background load when unpacking if the user change the # of procs
00430   // otherwise load everything
00431   if (p.isUnpacking() && LBSimulation::procsChanged) {
00432     ProcStats dummy;
00433     for (i=0; i<nprocs(); i++) p|dummy;
00434   }
00435   else
00436     for (i=0; i<nprocs(); i++) p|procs[i];
00437   for (i=0; i<n_objs; i++) p|objData[i]; 
00438   for (i=0; i<n_objs; i++) p|from_proc[i]; 
00439   for (i=0; i<n_objs; i++) p|to_proc[i]; 
00440   // reset to_proc when unpacking
00441   if (p.isUnpacking())
00442     for (i=0; i<n_objs; i++) to_proc[i] = from_proc[i];
00443   for (i=0; i<n_comm; i++) p|commData[i];
00444   if (p.isUnpacking())
00445     count = LBSimulation::simProcs;
00446   if (p.isUnpacking()) {
00447     objHash = NULL;
00448     if (_lb_args.lbversion() <= 1) 
00449       for (i=0; i<nprocs(); i++) procs[i].pe = i;
00450   }
00451 }
00452 
00453 int BaseLB::LDStats::useMem() { 
00454   // calculate the memory usage of this LB (superclass).
00455   return sizeof(LDStats) + sizeof(ProcStats) * nprocs() +
00456          (sizeof(LDObjData) + 2 * sizeof(int)) * n_objs +
00457          sizeof(LDCommData) * n_comm;
00458 }
00459 
00460 #include "BaseLB.def.h"
00461
ck-ldb/BaseLB.C
