doc: Add serial to list of ci file reserved words
[charm.git] / 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   CBase_BaseLB::pup(p); 
36   p|seqno;
37   if (p.isUnpacking())
38   {
39     if (CkMyPe()==0) {
40       if (seqno!=-1) {
41         int newseq = LBDatabaseObj()->getLoadbalancerTicket();
42         CmiAssert(newseq == seqno);
43       }
44     }
45     initLB(seqno);
46   }
47 }
48
49 void BaseLB::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 == CmiTrue) {
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 /*@}*/