make +LBPrintSummary work again.
[charm.git] / src / ck-ldb / HybridBaseLB.h
1 /**
2  * \addtogroup CkLdb
3 */
4 /*@{*/
5
6 #ifndef HYBRIDBASELB_H
7 #define HYBRIDBASELB_H
8
9 #include <map>
10
11 #include "charm++.h"
12 #include "BaseLB.h"
13 #include "CentralLB.h"
14 #include "HybridBaseLB.decl.h"
15
16 #include "topology.h"
17
18 void CreateHybridBaseLB();
19
20 /// for backward compatibility
21 typedef LBMigrateMsg NLBMigrateMsg;
22
23 inline int mymin(int x, int y) { return x<y?x:y; }
24
25 // base class
26 class MyHierarchyTree {
27 protected:
28   int *span;
29   int nLevels;
30   const char *myname;
31 public:
32   MyHierarchyTree(): span(NULL), myname(NULL) {}
33   virtual ~MyHierarchyTree() {}
34   const char* name() const { return myname; }
35   virtual const int numLevels() const { return nLevels; }
36   virtual int parent(int mype, int level) = 0;
37   virtual int isroot(int mype, int level) = 0;
38   virtual int numChildren(int mype, int level) = 0;
39   virtual void getChildren(int mype, int level, int *children, int &count) = 0;
40   virtual int numNodes(int level) {
41     CmiAssert(level>=0 && level<nLevels);
42     int count=1;
43     for (int i=0; i<level; i++) count *= span[i];
44     CmiAssert(CkNumPes()%count ==0);
45     return CkNumPes()/count;
46   }
47 };
48
49 // a simple 2 layer tree, fat at level 1
50 //        0
51 //     ---+---
52 //     0  1  2
53 class TwoLevelTree: public MyHierarchyTree {
54 private:
55   int toproot;
56 public:
57   TwoLevelTree() {
58     myname = "TwoLevelTree";
59     span = new int[1];
60     nLevels = 2;
61     span[0] = CkNumPes();
62     toproot = 0;
63   }
64   virtual ~TwoLevelTree() { delete [] span; }
65   virtual int parent(int mype, int level) {
66     if (level == 0) return toproot;
67     if (level == 1) return -1;
68     CmiAssert(0);
69     return -1;
70   }
71   virtual int isroot(int mype, int level) {
72     if (level == 0) return 0;
73     if (level == 1 && mype == toproot) return 1;
74     return 0;
75   }
76   virtual int numChildren(int mype, int level) {
77     if (level == 0) return 0;
78     if (level == 1) return CkNumPes();
79     CmiAssert(0);
80     return 0;
81   }
82   virtual void getChildren(int mype, int level, int *children, int &count) {
83     CmiAssert(isroot(mype, level));
84     count = numChildren(mype, level);
85     if (count == 0) { return; }
86     if (level == 1) {
87       for (int i=0; i<count; i++) 
88         children[i] = i;
89     }
90   }
91 };
92
93 // a simple 3 layer tree, fat at level 1
94 //        1
95 //     ---+---
96 //     0  4  8
97 //  ---+--
98 //  0 1 2 3
99 class ThreeLevelTree: public MyHierarchyTree {
100 private:
101   int toproot;
102 public:
103   ThreeLevelTree(int groupsize=512) {
104     myname = "ThreeLevelTree";
105     span = new int[2];
106     nLevels = 3;
107     while (groupsize && CkNumPes() / groupsize < 2) {
108       groupsize /= 2;
109     }
110     while ( CkNumPes() % groupsize ) --groupsize;
111     if ( groupsize == 1 ) {
112       ++groupsize;
113       while ( CkNumPes() % groupsize ) ++groupsize;
114     }
115     span[0] = groupsize;
116     CmiAssert(span[0]>1);
117     span[1] = (CkNumPes()+span[0]-1)/span[0];
118     if (CmiNumPhysicalNodes() > 1)
119       toproot = CmiGetFirstPeOnPhysicalNode(1);
120     else
121       toproot = 1;
122   }
123   virtual ~ThreeLevelTree() { delete [] span; }
124   virtual int parent(int mype, int level) {
125     if (level == 0) return mype/span[0]*span[0];
126     if (level == 1) return toproot;
127     if (level == 2) return -1;
128     CmiAssert(0);
129     return -1;
130   }
131   virtual int isroot(int mype, int level) {
132     if (level == 0) return 0;
133     if (level == 1 && mype % span[0] == 0) return 1;
134     if (level == 2 && mype == toproot) return 1;
135     return 0;
136   }
137   virtual int numChildren(int mype, int level) {
138     if (level == 0) return 0;
139     if (level == 1) return mymin(CkNumPes(), mype+span[0]) - mype;
140     if (level == 2) return span[1];
141     CmiAssert(0);
142     return 0;
143   }
144   virtual void getChildren(int mype, int level, int *children, int &count) {
145     CmiAssert(isroot(mype, level));
146     count = numChildren(mype, level);
147     if (count == 0) { return; }
148     if (level == 1) {
149       for (int i=0; i<count; i++) 
150         children[i] = mype + i;
151     }
152     if (level == 2) {
153       for (int i=0; i<count; i++) 
154         children[i] = i*span[0];
155     }
156   }
157 };
158
159 // a simple 4 layer tree, fat at level 1
160 //        1
161 //     ---+---
162 //     0  4  8
163 //  ---+--
164 //  0 
165 // -+-
166 // 0 1 2 3
167 class FourLevelTree: public MyHierarchyTree {
168 private:
169   int toproot;
170 public:
171   FourLevelTree() {
172     myname = "FourLevelTree";
173     span = new int[3];
174     nLevels = 4;
175 #if 1
176     span[0] = 64;
177     span[1] = 32;
178     span[2] = 32;
179 #else
180     span[0] = 4;
181     span[1] = 2;
182     span[2] = 2;
183 #endif
184     CmiAssert(CkNumPes() == span[0]*span[1]*span[2]);
185     toproot = 2;
186   }
187   virtual ~FourLevelTree() { delete [] span; }
188   virtual int parent(int mype, int level) {
189     if (level == 0) return mype/span[0]*span[0];
190     if (level == 1) return mype/span[0]/span[1]*span[0]*span[1]+1;
191     if (level == 2) return toproot;
192     if (level == 3) return -1;
193     CmiAssert(0);
194     return -1;
195   }
196   virtual int isroot(int mype, int level) {
197     if (level == 0) return 0;
198     if (level == 1 && (mype % span[0]) == 0) return 1;
199     if (level == 2 && ((mype-1)%(span[0]*span[1])) == 0) return 1;
200     if (level == 3 && mype == toproot) return 1;
201     return 0;
202   }
203   virtual int numChildren(int mype, int level) {
204     if (level == 0) return 0;
205     if (level == 1) return span[0];
206     if (level == 2) return span[1];
207     if (level == 3) return span[2];
208     CmiAssert(0);
209     return 0;
210   }
211   virtual void getChildren(int mype, int level, int *children, int &count) {
212     CmiAssert(isroot(mype, level));
213     count = numChildren(mype, level);
214     if (count == 0) { return; }
215     if (level == 1) {
216       for (int i=0; i<count; i++) 
217         children[i] = mype + i;
218     }
219     if (level == 2) {
220       for (int i=0; i<count; i++) 
221         children[i] = mype-1+i*span[0];
222     }
223     if (level == 3) {
224       for (int i=0; i<count; i++) 
225         children[i] = i*span[0]*span[1]+1;
226     }
227   }
228 };
229
230 // a tree with same G branching factor at all levels
231 class KLevelTree: public MyHierarchyTree {
232 private:
233   int toproot;
234   int G;
235 public:
236   KLevelTree(int k) {
237     myname = "KLevelTree";
238     nLevels = k;
239     span = new int[nLevels-1];
240     int P=CkNumPes();
241     G = (int)(exp(log(P*1.0)/(nLevels-1))+0.5);
242     if (pow(G*1.0, nLevels-1) != P) {
243       CkPrintf("KLevelTree failed: P=%d Level=%d G=%d\n", P, nLevels, G);
244       CmiAbort("KLevelTree failed");
245     }
246     for (int i=0; i<nLevels-1; i++) span[i] = G;
247     if (CmiNumPhysicalNodes() > 1)
248       toproot = CmiGetFirstPeOnPhysicalNode(1);
249     else
250       toproot = 1;
251     if (CkMyPe()==0) CmiPrintf("KLevelTree: %d (toproot:%d).\n", G, toproot);
252   }
253   virtual ~KLevelTree() { delete [] span; }
254   virtual int parent(int mype, int level) {
255     if (level == nLevels-2) return toproot;
256     if (level == nLevels-1) return -1;
257     int S = 1;
258     for (int i=0; i<=level; i++) S*=span[i];
259     return mype/S*S+level;
260   }
261   virtual int isroot(int mype, int level) {
262     if (level == 0) return 0;
263     if (level == nLevels-1) return mype == toproot;
264     int S = 1;
265     for (int i=0; i<level; i++) S*=span[i];
266     if ((mype - (level-1)) % S == 0) return 1;
267     return 0;
268   }
269   virtual int numChildren(int mype, int level) {
270     if (level == 0) return 0;
271     return span[level-1];
272   }
273   virtual void getChildren(int mype, int level, int *children, int &count) {
274     CmiAssert(isroot(mype, level));
275     count = numChildren(mype, level);
276     if (count == 0) { return; }
277     int S = 1;
278     for (int i=0; i<level-1; i++) S*=span[i];
279
280     if (level == nLevels-1) {
281       for (int i=0; i<count; i++)
282         children[i] = i*S+(level-2);
283     }
284     else if (level == 1) {
285       for (int i=0; i<count; i++)
286         children[i] = mype+i*S;
287     }
288     else {
289       for (int i=0; i<count; i++)
290         children[i] = mype-1+i*S;
291     }
292   }
293 };
294
295 class HybridBaseLB : public BaseLB
296 {
297 public:
298   HybridBaseLB(const CkLBOptions &);
299   HybridBaseLB(CkMigrateMessage *m):BaseLB(m) {}
300   ~HybridBaseLB();
301
302   static void staticAtSync(void*);
303   void AtSync(void); // Everything is at the PE barrier
304   void ProcessAtSync(void);
305
306   void ReceiveStats(CkMarshalledCLBStatsMessage &m, int fromlevel); 
307   void ResumeClients(CkReductionMsg *msg);
308   void ResumeClients(int balancing);
309   void ReceiveMigration(LBMigrateMsg *);        // Receive migration data
310   void ReceiveVectorMigration(LBVectorMigrateMsg *); // Receive migration data
311   void TotalObjMigrated(int count, int level);
312
313   // Migrated-element callback
314   static void staticMigrated(void* me, LDObjHandle h, int waitBarrier);
315   void Migrated(LDObjHandle h, int waitBarrier);
316
317   void ObjMigrated(LDObjData data, LDCommData *cdata, int n, int level);
318   void ObjsMigrated(LDObjData *data, int m, LDCommData *cdata, int n, int level);
319   void VectorDone(int atlevel);
320   void MigrationDone(int balancing);  // Call when migration is complete
321   void StatsDone(int level);  // Call when LDStats migration is complete
322   void NotifyObjectMigrationDone(int level);    
323   virtual void Loadbalancing(int level);        // start load balancing
324   void StartCollectInfo(DummyMsg *m);
325   void CollectInfo(Location *loc, int n, int fromlevel);
326   void PropagateInfo(Location *loc, int n, int fromlevel);
327
328   void reportLBQulity(double mload, double mCpuLoad, double totalload, int nmsgs, double bytesentry );
329   void reportLBMem(double);
330
331   struct MigrationRecord {
332     LDObjHandle handle;
333     int      fromPe;            // real from pe
334     int      toPe;
335     MigrationRecord(): fromPe(-1), toPe(-1) {}
336     MigrationRecord(LDObjHandle &k, int f, int t): handle(k), fromPe(f), toPe(t) {}
337     void pup(PUP::er &p) { p|handle; p|fromPe; p|toPe; }
338   };
339
340 private:
341   CProxy_HybridBaseLB  thisProxy;
342   int              foundNeighbors;
343   CmiGroup            group1;              // level 1 multicast group
344   int                 group1_created;
345
346 protected:
347   virtual CmiBool QueryBalanceNow(int) { return CmiTrue; };  
348   virtual CmiBool QueryMigrateStep(int) { return CmiTrue; };  
349   virtual LBMigrateMsg* Strategy(LDStats* stats);
350   virtual void work(LDStats* stats);
351   virtual LBMigrateMsg * createMigrateMsg(LDStats* stats);
352   // helper function
353   LBMigrateMsg * createMigrateMsg(CkVec<MigrateInfo *> &migrateInfo, int count);
354   virtual LBVectorMigrateMsg* VectorStrategy(LDStats* stats);
355   void    printSummary(LDStats *stats, int count);
356   void    initTree();
357
358   // Not to be used -- maintained for legacy applications
359   virtual LBMigrateMsg* Strategy(LDStats* stats, int nprocs) {
360     return Strategy(stats);
361   }
362
363   virtual int     useMem();
364   int NeighborIndex(int pe, int atlevel);   // return the neighbor array index
365
366   MyHierarchyTree  *tree;
367   int shrinklevel;
368
369   class LevelData {
370   public:
371     int parent;
372     int*  children;
373     int nChildren;
374     CLBStatsMsg **statsMsgsList;
375     int stats_msg_count;
376     LDStats *statsData;
377     int obj_expected, obj_completed;
378     int migrates_expected, migrates_completed;
379     int mig_reported;           // for NotifyObjectMigrationDone
380     int info_recved;            // for CollectInfo()
381     int vector_expected, vector_completed;
382     int resumeAfterMigration;
383     CkVec<MigrationRecord> outObjs;
384     //CkVec<Location> unmatchedObjs;
385     std::map< LDObjKey, int >  unmatchedObjs;
386     CkVec<Location> matchedObjs;         // don't need to be sent up
387   public:
388     LevelData(): parent(-1), children(NULL), nChildren(0), 
389                  statsMsgsList(NULL), stats_msg_count(0),
390                  statsData(NULL), obj_expected(-1), obj_completed(0),
391                  migrates_expected(-1), migrates_completed(0),
392                  mig_reported(0), info_recved(0), 
393                  vector_expected(-1), vector_completed(0),
394                  resumeAfterMigration(0)
395                  {}
396     ~LevelData() {
397       if (children) delete [] children;
398       if (statsMsgsList) delete [] statsMsgsList;
399       if (statsData) delete statsData;
400     }
401     int migrationDone() {
402 //CkPrintf("[%d] checking migrates_expected: %d migrates_completed: %d obj_completed: %d\n", CkMyPe(), migrates_expected, migrates_completed, obj_completed);
403       return migrates_expected == 0 || migrates_completed + obj_completed == migrates_expected;
404     }
405     int vectorReceived() {
406       return vector_expected==0 || vector_expected == vector_completed;
407     }
408     void clear() {
409       obj_expected = -1;
410       obj_completed = 0;
411       migrates_expected = -1;
412       migrates_completed = 0;
413       mig_reported = 0;
414       info_recved = 0;
415       vector_expected = -1;
416       vector_completed = 0;
417       resumeAfterMigration = 0;
418       if (statsData) statsData->clear();
419       outObjs.free();
420       matchedObjs.free();
421       unmatchedObjs.clear();
422     }
423     int useMem() {
424       int memused = sizeof(LevelData);
425       if (statsData) memused += statsData->useMem();
426       memused += outObjs.size() * sizeof(MigrationRecord);
427       memused += (unmatchedObjs.size()+matchedObjs.size()) * sizeof(Location);
428       return memused;
429     }
430   };
431
432   CkVec<LevelData *>  levelData;
433
434   int currentLevel;
435
436   enum StatsStrategy { FULL, SHRINK, SHRINK_NULL} ;
437   StatsStrategy statsStrategy;
438
439 private:
440   void FindNeighbors();
441   CLBStatsMsg* AssembleStats();
442   void buildStats(int level);
443   CLBStatsMsg * buildCombinedLBStatsMessage(int atlevel);
444   void depositLBStatsMessage(CLBStatsMsg *msg, int atlevel);
445   void collectCommData(int objIdx, CkVec<LDCommData> &comm, int atlevel);
446
447   int future_migrates_expected;
448   LBMigrateMsg** mig_msgs;
449   int mig_msgs_received;
450   int cur_ld_balancer;
451   double start_lb_time;
452
453   double maxLoad;                   // on level = 1
454   double maxCpuLoad;                // on level = 1
455   double maxCommBytes;      // on level = 1
456   int    maxCommCount;      // on level = 1
457   double totalLoad;
458   double maxMem;                    // on level = max - 1
459
460   CkVec<Location> newObjs;
461
462   int vector_n_moves;
463 };
464
465
466 #endif /* NBORBASELB_H */
467
468 /*@}*/