Handling imbalance based on how well the load balancers could balance load
authorHarshitha <gplkrsh2@illinois.edu>
Sat, 31 Mar 2012 18:58:30 +0000 (13:58 -0500)
committerHarshitha <gplkrsh2@illinois.edu>
Sat, 31 Mar 2012 18:58:30 +0000 (13:58 -0500)
src/ck-ldb/AdaptiveLB.C
src/ck-ldb/CentralLB.h
src/ck-ldb/LBDatabase.C
src/ck-ldb/LBDatabase.h

index a2e43ab1274051f02aa51391af428e93c930e822..057ea838432fd4abf3f26cefffe16934bf65c24a 100644 (file)
@@ -84,40 +84,43 @@ void AdaptiveLB::work(LDStats* stats)
   CkPrintf("AdaptiveLB> Total Bytes %ld\n", totalBytes);
   CkPrintf("AdaptiveLB> Total Comm Overhead %E Total Load %E\n", commOverhead, totalLoad);
 
-  double after_lb_max;
-  double after_lb_avg;
-  int is_prev_lb_refine;
-  GetPrevLBData(is_prev_lb_refine, after_lb_max, after_lb_avg);
+  double lb_max_avg_ratio;
+  int lb_type;
+  GetPrevLBData(lb_type, lb_max_avg_ratio);
 
-  CkPrintf("AdaptiveLB> Previous LB %d\n", is_prev_lb_refine);
+  CkPrintf("AdaptiveLB> Previous LB %d\n", lb_type);
 
-  refineLB->work(stats);
+  metisLB->work(stats);
   return;
   // Choose the right LB
   //
   // If communication overhead is 10% computation, then choose Scotch LB
   if (isComm || (commOverhead > (totalLoad * percent_overhead / 100))) {
     metisLB->work(stats);
+    lb_type = 2;
     CkPrintf("---METIS LB\n");
   } else {
-    if (is_prev_lb_refine == 1) {
-      if (after_lb_max/after_lb_avg < 1.01) {
+    if (lb_type == 1) {
+      if (lb_max_avg_ratio < 1.01) {
+        lb_type = 1;
         refineLB->work(stats);
         CkPrintf("---REFINE LB\n");
       } else {
+        lb_type = 0;
         greedyLB->work(stats);
         CkPrintf("---GREEDY LB\n");
       }
-    } else if (is_prev_lb_refine == -1) {
+    } else if (lb_type == -1) {
+      lb_type = 0;
       greedyLB->work(stats);
       CkPrintf("---GREEDY LB\n");
     } else {
+      lb_type = 1;
       refineLB->work(stats);
       CkPrintf("---REFINE LB\n");
     }
   }
-  UpdateLBDBWithData(stats->is_prev_lb_refine, stats->after_lb_max,
-      stats->after_lb_avg);
+  UpdateLBDBWithData(lb_type, stats->after_lb_max, stats->after_lb_avg);
 
   delete parr;
   delete ogr;
index b0dbd5f3a2f6fe3b44b8d4c1e4eae7390da34732..e7884fba25d7857dcd3793c87f3131633f145857 100644 (file)
@@ -244,9 +244,8 @@ protected:
     theLbdb->UpdateAfterLBData(is_prev_lb_refine, lb_max, lb_avg);
   }
 
-  virtual void GetPrevLBData(int& is_prev_lb_refine, double& lb_max,
-      double& lb_avg) {
-    theLbdb->GetPrevLBData(is_prev_lb_refine, lb_max, lb_avg);
+  virtual void GetPrevLBData(int& is_prev_lb_refine, double& lb_max_avg_ratio) {
+    theLbdb->GetPrevLBData(is_prev_lb_refine, lb_max_avg_ratio);
   }
 
 
index df77d591424852294f8387a463be43a998057d34..4baba5c398322c49241502631cbc91047433fe41 100644 (file)
@@ -18,6 +18,7 @@
 #include "NullLB.h"
 
 #define VEC_SIZE 500
+#define IMB_TOLERANCE 1.1
 
 struct AdaptiveData {
   int iteration;
@@ -31,6 +32,10 @@ struct AdaptiveLBDatabase {
   std::vector<AdaptiveData> history_data;
 } adaptive_lbdb;
 
+struct AdaptiveLBInfo {
+  double max_avg_ratio;
+};
+
 struct AdaptiveLBStructure {
   int lb_ideal_period;
   int lb_calculated_period;
@@ -41,10 +46,14 @@ struct AdaptiveLBStructure {
   double lb_strategy_cost;
   double lb_migration_cost;
   bool lb_period_informed;
-  bool isCommLB;
+  bool doCommStrategy;
   int lb_msg_send_no;
   int lb_msg_recv_no;
   int total_syncs_called;
+  int last_lb_type;
+  AdaptiveLBInfo greedy_info;
+  AdaptiveLBInfo refine_info;
+  AdaptiveLBInfo metis_info;
 } adaptive_struct;
 
 
@@ -430,6 +439,7 @@ void LBDatabase::init(void)
   adaptive_struct.lb_msg_send_no = 0;
   adaptive_struct.lb_msg_recv_no = 0;
   adaptive_struct.total_syncs_called = 0;
+  adaptive_struct.last_lb_type = -1;
 
   is_prev_lb_refine = -1;
 }
@@ -663,7 +673,12 @@ void LBDatabase::ReceiveMinStats(CkReductionMsg *msg) {
   // If the max/avg ratio is greater than the threshold and also this is not the
   // step immediately after load balancing, carry out load balancing
   //if (max/avg >= 1.1 && adaptive_lbdb.history_data.size() > 4) {
-  if ((max_idle_load_ratio >= 0.1 || max/avg >= 1.5) && adaptive_lbdb.history_data.size() > 4) {
+  int tmp1;
+  double tmp2;
+  GetPrevLBData(tmp1, tmp2);
+  double tolerate_imb = IMB_TOLERANCE * tmp2;
+
+  if ((max_idle_load_ratio >= 0.1 || max/avg >= tolerate_imb) && adaptive_lbdb.history_data.size() > 4) {
     CkPrintf("Carry out load balancing step at iter max/avg(%lf) and max_idle_load_ratio ratio (%lf)\n", max/avg, max_idle_load_ratio);
 //    if (!adaptive_struct.lb_period_informed) {
 //      // Just for testing
@@ -674,13 +689,14 @@ void LBDatabase::ReceiveMinStats(CkReductionMsg *msg) {
 //    }
 
 
+
     // If the new lb period is less than current set lb period
     if (adaptive_struct.lb_calculated_period > iteration_n + 1) {
-      if (max/avg < 1.5) {
-        adaptive_struct.isCommLB = true;
+      if (max/avg < tolerate_imb) {
+        adaptive_struct.doCommStrategy = true;
         CkPrintf("No load imbalance but idle time\n");
       } else {
-        adaptive_struct.isCommLB = false;
+        adaptive_struct.doCommStrategy = false;
         CkPrintf("load imbalance \n");
       }
       adaptive_struct.lb_calculated_period = iteration_n + 1;
@@ -700,7 +716,7 @@ void LBDatabase::ReceiveMinStats(CkReductionMsg *msg) {
 
     // If the new lb period is less than current set lb period
     if (adaptive_struct.lb_calculated_period > period) {
-      adaptive_struct.isCommLB = false;
+      adaptive_struct.doCommStrategy = false;
       adaptive_struct.lb_calculated_period = period;
       adaptive_struct.in_progress = true;
       adaptive_struct.lb_period_informed = true;
@@ -742,9 +758,13 @@ bool LBDatabase::generatePlan(int& period) {
   // If we can attain perfect balance, then the new load is close to the
   // average. Hence we pass 1, else pass in some other value which would be the
   // new max_load after load balancing.
+  int tmp1;
+  double tmp2;
+  GetPrevLBData(tmp1, tmp2);
+  
+  double tolerate_imb = IMB_TOLERANCE * tmp2;
 
-
-  return getPeriodForStrategy(1, 1, period);
+  return getPeriodForStrategy(tolerate_imb, 1, period);
 
 //  int refine_period, scratch_period;
 //  bool obtained_refine, obtained_scratch;
@@ -866,6 +886,10 @@ bool LBDatabase::getLineEq(double new_load_percent, double& aslope, double& ac,
   mslope = 2 * (m2 - m1) / iterations;
   ac = adaptive_lbdb.history_data[0].avg_load * new_load_percent;
   mc = adaptive_lbdb.history_data[0].max_load;
+
+  //ac = (adaptive_lbdb.history_data[1].avg_load * new_load_percent - aslope);
+  //mc = (adaptive_lbdb.history_data[1].max_load - mslope);
+
   return true;
 }
 
@@ -934,7 +958,7 @@ int LBDatabase::getPredictedLBPeriod() {
 }
 
 bool LBDatabase::isStrategyComm() {
-  return adaptive_struct.isCommLB;
+  return adaptive_struct.doCommStrategy;
 }
 
 void LBDatabase::SetMigrationCost(double lb_migration_cost) {
@@ -945,6 +969,25 @@ void LBDatabase::SetStrategyCost(double lb_strategy_cost) {
   adaptive_struct.lb_strategy_cost = lb_strategy_cost;
 }
 
+void LBDatabase::UpdateAfterLBData(int lb, double lb_max, double lb_avg) {
+  adaptive_struct.last_lb_type = lb;
+  if (lb == 0) {
+    adaptive_struct.greedy_info.max_avg_ratio = lb_max/lb_avg;
+  } else if (lb == 1) {
+    adaptive_struct.refine_info.max_avg_ratio = lb_max/lb_avg;
+  }
+}
+
+void GetPrevLBData(int& lb_type, double& lb_max_avg_ratio) {
+  lb_type = adaptive_struct.last_lb_type;
+  lb_max_avg_ratio = 1;
+  if (lb_type == 0) {
+    lb_max_avg_ratio = adaptive_struct.greedy_info.max_avg_ratio;
+  } else if (lb_type == 1) {
+    lb_max_avg_ratio = adaptive_struct.refine_info.max_avg_ratio;
+  }
+}
+
 /*
   callable from user's code
 */
index 7f0ec235e9be0457edf880eaaa6c304aba8dd5a9..23fc35ed42442649d0199caebdb888cbc6c9dd61 100644 (file)
@@ -369,17 +369,9 @@ public:
   int getPredictedLBPeriod();
 
   bool isStrategyComm();
-  void UpdateAfterLBData(int is_lb_refine, double lb_max, double lb_avg) {
-    is_prev_lb_refine = is_lb_refine;
-    after_lb_avg = lb_avg;
-    after_lb_max = lb_max;
-  }
 
-  void GetPrevLBData(int& is_lb_refine, double& lb_max, double& lb_avg) {
-    is_lb_refine = is_prev_lb_refine;
-    lb_max = after_lb_max;
-    lb_avg = after_lb_avg;
-  }
+  void UpdateAfterLBData(int is_lb_refine, double lb_max, double lb_avg);
+  void GetPrevLBData(int& lb_type, double& lb_max_avg_ratio);
 
   void SetMigrationCost(double lb_migration_cost);
   void SetStrategyCost(double lb_strategy_cost);