Handling imbalance based on how well the load balancers could balance load
[charm.git] / src / ck-ldb / AdaptiveLB.C
1 /**
2  * \addtogroup CkLdb
3 */
4 /*@{*/
5
6 #include "AdaptiveLB.h"
7 #include "ckgraph.h"
8
9 #define alpha 4.0e-6
10 #define beta 2.67e-9
11 #define percent_overhead 10
12
13 extern LBAllocFn getLBAllocFn(char *lbname);
14
15 CreateLBFunc_Def(AdaptiveLB, "Allow multiple strategies to work serially")
16
17 AdaptiveLB::AdaptiveLB(const CkLBOptions &opt): CentralLB(opt)
18 {
19   lbname = "AdaptiveLB";
20   const char *lbs = theLbdb->loadbalancer(opt.getSeqNo());
21   if (CkMyPe() == 0)
22     CkPrintf("[%d] AdaptiveLB created with %s\n",CkMyPe(), lbs);
23
24   char *lbcopy = strdup(lbs);
25   char *greedyLBString = "GreedyLB";
26   char *refineLBString = "RefineLB";
27   char *metisLBString = "MetisLB";
28
29   LBAllocFn fn = getLBAllocFn(greedyLBString);
30   if (fn == NULL) {
31     CkPrintf("LB> Invalid load balancer: %s.\n", greedyLBString);
32     CmiAbort("");
33   }
34   BaseLB *glb = fn();
35   greedyLB = (CentralLB*)glb;
36
37   fn = getLBAllocFn(refineLBString);
38   if (fn == NULL) {
39     CkPrintf("LB> Invalid load balancer: %s.\n", refineLBString);
40     CmiAbort("");
41   }
42   BaseLB *rlb = fn();
43   refineLB = (CentralLB*)rlb;
44
45   fn = getLBAllocFn(metisLBString);
46   if (fn == NULL) {
47     CkPrintf("LB> Invalid load balancer: %s.\n", metisLBString);
48     CmiAbort("");
49   }
50   BaseLB *slb = fn();
51   metisLB = (CentralLB*)slb;
52 }
53
54 void AdaptiveLB::work(LDStats* stats)
55 {
56
57   ProcArray *parr = new ProcArray(stats);
58   ObjGraph *ogr = new ObjGraph(stats);
59   CkPrintf("Adaptive work\n");
60
61   bool isComm = theLbdb->isStrategyComm();
62
63   // Calculate the load and total messages
64   double totalLoad = 0.0;
65   long totalMsgs = 0;
66   long long totalBytes = 0;
67   int vertnbr = ogr->vertices.size();
68
69   /** the object load is normalized to an integer between 0 and 256 */
70   for(int i = 0; i < vertnbr; i++) {
71     totalLoad += ogr->vertices[i].getVertexLoad();
72   }
73
74   for(int i = 0; i < vertnbr; i++) {
75     for(int j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
76       totalMsgs += ogr->vertices[i].sendToList[j].getNumMsgs();
77       totalBytes += ogr->vertices[i].sendToList[j].getNumBytes();
78     }
79   }
80   double commOverhead = (totalMsgs * alpha) + (totalBytes * beta);
81
82   CkPrintf("AdaptiveLB> Total load %E\n", totalLoad);
83   CkPrintf("AdaptiveLB> Total Msgs %d\n", totalMsgs);
84   CkPrintf("AdaptiveLB> Total Bytes %ld\n", totalBytes);
85   CkPrintf("AdaptiveLB> Total Comm Overhead %E Total Load %E\n", commOverhead, totalLoad);
86
87   double lb_max_avg_ratio;
88   int lb_type;
89   GetPrevLBData(lb_type, lb_max_avg_ratio);
90
91   CkPrintf("AdaptiveLB> Previous LB %d\n", lb_type);
92
93   metisLB->work(stats);
94   return;
95   // Choose the right LB
96   //
97   // If communication overhead is 10% computation, then choose Scotch LB
98   if (isComm || (commOverhead > (totalLoad * percent_overhead / 100))) {
99     metisLB->work(stats);
100     lb_type = 2;
101     CkPrintf("---METIS LB\n");
102   } else {
103     if (lb_type == 1) {
104       if (lb_max_avg_ratio < 1.01) {
105         lb_type = 1;
106         refineLB->work(stats);
107         CkPrintf("---REFINE LB\n");
108       } else {
109         lb_type = 0;
110         greedyLB->work(stats);
111         CkPrintf("---GREEDY LB\n");
112       }
113     } else if (lb_type == -1) {
114       lb_type = 0;
115       greedyLB->work(stats);
116       CkPrintf("---GREEDY LB\n");
117     } else {
118       lb_type = 1;
119       refineLB->work(stats);
120       CkPrintf("---REFINE LB\n");
121     }
122   }
123   UpdateLBDBWithData(lb_type, stats->after_lb_max, stats->after_lb_avg);
124
125   delete parr;
126   delete ogr;
127
128 }
129
130 #include "AdaptiveLB.def.h"
131
132
133 /*@}*/