Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
* Added an "exact" alternative computation for test1 to check the lagrange results...
authoralegrand <alegrand@48e7efb5-ca39-0410-a469-dd3cf9ba447f>
Wed, 25 Jul 2007 12:45:36 +0000 (12:45 +0000)
committeralegrand <alegrand@48e7efb5-ca39-0410-a469-dd3cf9ba447f>
Wed, 25 Jul 2007 12:45:36 +0000 (12:45 +0000)
* Cosmetics (indent).

git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@3890 48e7efb5-ca39-0410-a469-dd3cf9ba447f

testsuite/surf/simeng_usage.c

index 17cc29e..f517beb 100644 (file)
 #include "surf/maxmin.h"
 #include "xbt/log.h"
 #include "xbt/module.h"
+#include <math.h>
 
 
 
-
-
-XBT_LOG_NEW_DEFAULT_CATEGORY(surf_test,"Messages specific for surf example");
+XBT_LOG_NEW_DEFAULT_CATEGORY(surf_test,
+                            "Messages specific for surf example");
 
 #define PRINT_VAR(var) DEBUG1(#var " = %g",lmm_variable_getvalue(var));
+#define SHOW_EXPR(expr) DEBUG1(#expr " = %g",expr);
 
 /*                               */
 /*        ______                 */
@@ -37,10 +38,66 @@ typedef enum {
   LAGRANGE_VEGAS,
 } method_t;
 
+static double dichotomy(double func(double), double min, double max,
+                       double min_error)
+{
+  double middle;
+  double min_func, max_func, middle_func;
+
+  double overall_error = 2 * min_error;
+
+  min_func = func(min);
+  max_func = func(max);
+
+  if ((min_func > 0 && max_func > 0))
+    return min - 1.0;
+  if ((min_func < 0 && max_func < 0))
+    return max + 1.0;
+  if ((min_func > 0 && max_func < 0))
+    abort();
+
+  while (overall_error > min_error) {
+    if ((min_func > 0 && max_func > 0) ||
+       (min_func < 0 && max_func < 0) || (min_func > 0 && max_func < 0)) {
+      abort();
+    }
+
+    middle = (max + min) / 2.0;
+    if ((min == middle) || (max == middle)) {
+      break;
+    }
+    middle_func = func(middle);
+
+    if (middle_func < 0) {
+      min = middle;
+      min_func = middle_func;
+      overall_error = max - middle_func;
+    } else if (middle_func > 0) {
+      max = middle;
+      max_func = middle_func;
+      overall_error = max - middle_func;
+    } else {
+      overall_error = 0;
+    }
+  }
+  return ((min + max) / 2.0);
+}
+
+double a_test_1 = 0;
+double b_test_1 = 0;
+static double diff_lagrange_test_1(double x)
+{
+  return -(3 / (1 + 3 * x * x / 2) -
+          3 / (2 * (3 * (a_test_1 - x) * (a_test_1 - x) / 2 + 1)) +
+          3 / (2 *
+               (3 * (b_test_1 - a_test_1 + x) *
+                (b_test_1 - a_test_1 + x) / 2 + 1)));
+}
+
 void test1(method_t method);
 void test1(method_t method)
 {
-  lmm_system_t Sys = NULL ;
+  lmm_system_t Sys = NULL;
   lmm_constraint_t L1 = NULL;
   lmm_constraint_t L2 = NULL;
   lmm_constraint_t L3 = NULL;
@@ -50,29 +107,31 @@ void test1(method_t method)
   lmm_variable_t R_2 = NULL;
   lmm_variable_t R_3 = NULL;
 
-  if(method==LAGRANGE_VEGAS){
+  double a = 1.0, b = 10.0;
+
+  if (method == LAGRANGE_VEGAS) {
     //set default functions for TCP Vegas
     lmm_set_default_protocol_function(func_vegas_fpi);
-  }else if(method==LAGRANGE_RENO){
+  } else if (method == LAGRANGE_RENO) {
     //set default functions for TCP Reno
     lmm_set_default_protocol_function(func_reno_fpi);
   }
 
 
   Sys = lmm_system_new();
-  L1 = lmm_constraint_new(Sys, (void *) "L1", 1.0);
-  L2 = lmm_constraint_new(Sys, (void *) "L2", 10.0);
-  L3 = lmm_constraint_new(Sys, (void *) "L3", 1.0);
+  L1 = lmm_constraint_new(Sys, (void *) "L1", a);
+  L2 = lmm_constraint_new(Sys, (void *) "L2", b);
+  L3 = lmm_constraint_new(Sys, (void *) "L3", a);
 
-  R_1_2_3 = lmm_variable_new(Sys, (void *) "R 1->2->3", 1.0 , -1.0 , 3);
-  R_1 = lmm_variable_new(Sys, (void *) "R 1", 1.0 , -1.0 , 1);
-  R_2 = lmm_variable_new(Sys, (void *) "R 2", 1.0 , -1.0 , 1);
-  R_3 = lmm_variable_new(Sys, (void *) "R 3", 1.0 , -1.0 , 1);
+  R_1_2_3 = lmm_variable_new(Sys, (void *) "R 1->2->3", 1.0, -1.0, 3);
+  R_1 = lmm_variable_new(Sys, (void *) "R 1", 1.0, -1.0, 1);
+  R_2 = lmm_variable_new(Sys, (void *) "R 2", 1.0, -1.0, 1);
+  R_3 = lmm_variable_new(Sys, (void *) "R 3", 1.0, -1.0, 1);
 
   lmm_update_variable_latency(Sys, R_1_2_3, 1.0);
-  lmm_update_variable_latency(Sys,R_1, 1.0);
-  lmm_update_variable_latency(Sys,R_2, 1.0); 
-  lmm_update_variable_latency(Sys,R_3, 1.0);
+  lmm_update_variable_latency(Sys, R_1, 1.0);
+  lmm_update_variable_latency(Sys, R_2, 1.0);
+  lmm_update_variable_latency(Sys, R_3, 1.0);
 
   lmm_expand(Sys, L1, R_1_2_3, 1.0);
   lmm_expand(Sys, L2, R_1_2_3, 1.0);
@@ -85,20 +144,84 @@ void test1(method_t method)
   lmm_expand(Sys, L3, R_3, 1.0);
 
 
-  if(method==MAXMIN){
+  if (method == MAXMIN) {
     lmm_solve(Sys);
 #ifdef HAVE_SDP
-  }else if(method==SDP){
-    sdp_solve(Sys);    
+  } else if (method == SDP) {
+    sdp_solve(Sys);
 #endif
-  }else if(method==LAGRANGE_VEGAS){
-    //set default functions for TCP Vegas
-    lagrange_solve(Sys);  
-  }else if(method==LAGRANGE_RENO){
-    //set default functions for TCP Reno
-    lagrange_solve(Sys);  
-  }else{ 
-    xbt_assert0(0,"Invalid method");
+  } else if (method == LAGRANGE_VEGAS) {
+    double x = 3 * a / 4 - 3 * b / 8 + 
+      sqrt(9 * b * b + 4 * a * a - 4 * a * b) / 8;
+    /* Computed with mupad and D_f=1.0 */
+    double max_deviation = 0.0;
+    if (x > a) {
+      x = a;
+    }
+    if (x < 0) {
+      x = 0;
+    }
+
+    lagrange_solve(Sys);
+
+    max_deviation =
+       MAX(max_deviation, fabs(lmm_variable_getvalue(R_1) - x));
+    max_deviation =
+       MAX(max_deviation, fabs(lmm_variable_getvalue(R_3) - x));
+    max_deviation =
+       MAX(max_deviation, fabs(lmm_variable_getvalue(R_2) - (b - a + x)));
+    max_deviation =
+       MAX(max_deviation, fabs(lmm_variable_getvalue(R_1_2_3) - (a - x)));
+
+    if (max_deviation > 1e-8) {
+      DEBUG1("Max Deviation from optimal solution : %g", max_deviation);
+      DEBUG1("Found x = %1.20f", x);
+      DEBUG1("Deviation from optimal solution (R_1): %1.20f",
+            lmm_variable_getvalue(R_1) - x);
+      DEBUG1("Deviation from optimal solution (R_2): %1.20f",
+            lmm_variable_getvalue(R_2) - (b - a + x));
+      DEBUG1("Deviation from optimal solution (R_3): %1.20f",
+            lmm_variable_getvalue(R_3) - x);
+      DEBUG1("Deviation from optimal solution (R_1_2_3): %1.20f",
+            lmm_variable_getvalue(R_1_2_3) - (a - x));
+    }
+  } else if (method == LAGRANGE_RENO) {
+    double x;
+    double max_deviation = 0.0;
+
+    a_test_1 = a;
+    b_test_1 = b;
+    x = dichotomy(diff_lagrange_test_1, 0, a, 1e-8);
+
+    if (x < 0)
+      x = 0;
+    if (x > a)
+      x = a;
+    lagrange_solve(Sys);
+
+    max_deviation =
+       MAX(max_deviation, fabs(lmm_variable_getvalue(R_1) - x));
+    max_deviation =
+       MAX(max_deviation, fabs(lmm_variable_getvalue(R_3) - x));
+    max_deviation =
+       MAX(max_deviation, fabs(lmm_variable_getvalue(R_2) - (b - a + x)));
+    max_deviation =
+       MAX(max_deviation, fabs(lmm_variable_getvalue(R_1_2_3) - (a - x)));
+
+    if (max_deviation > 1e-8) {
+      DEBUG1("Max Deviation from optimal solution : %g", max_deviation);
+      DEBUG1("Found x = %1.20f", x);
+      DEBUG1("Deviation from optimal solution (R_1): %1.20f",
+            lmm_variable_getvalue(R_1) - x);
+      DEBUG1("Deviation from optimal solution (R_2): %1.20f",
+            lmm_variable_getvalue(R_2) - (b - a + x));
+      DEBUG1("Deviation from optimal solution (R_3): %1.20f",
+            lmm_variable_getvalue(R_3) - x);
+      DEBUG1("Deviation from optimal solution (R_1_2_3): %1.20f",
+            lmm_variable_getvalue(R_1_2_3) - (a - x));
+    }
+  } else {
+    xbt_assert0(0, "Invalid method");
   }
 
   PRINT_VAR(R_1_2_3);
@@ -107,12 +230,12 @@ void test1(method_t method)
   PRINT_VAR(R_3);
 
   lmm_system_free(Sys);
-} 
+}
 
 void test2(method_t method);
 void test2(method_t method)
 {
-  lmm_system_t Sys = NULL ;
+  lmm_system_t Sys = NULL;
   lmm_constraint_t CPU1 = NULL;
   lmm_constraint_t CPU2 = NULL;
 
@@ -120,10 +243,10 @@ void test2(method_t method)
   lmm_variable_t T2 = NULL;
 
 
-  if(method==LAGRANGE_VEGAS){
+  if (method == LAGRANGE_VEGAS) {
     //set default functions for TCP Vegas
     lmm_set_default_protocol_function(func_vegas_fpi);
-  }else if(method==LAGRANGE_RENO){
+  } else if (method == LAGRANGE_RENO) {
     //set default functions for TCP Reno
     lmm_set_default_protocol_function(func_reno_fpi);
   }
@@ -132,8 +255,8 @@ void test2(method_t method)
   CPU1 = lmm_constraint_new(Sys, (void *) "CPU1", 200.0);
   CPU2 = lmm_constraint_new(Sys, (void *) "CPU2", 100.0);
 
-  T1 = lmm_variable_new(Sys, (void *) "T1", 1.0 , -1.0 , 1);
-  T2 = lmm_variable_new(Sys, (void *) "T2", 1.0 , -1.0 , 1);
+  T1 = lmm_variable_new(Sys, (void *) "T1", 1.0, -1.0, 1);
+  T2 = lmm_variable_new(Sys, (void *) "T2", 1.0, -1.0, 1);
 
   lmm_update_variable_latency(Sys, T1, 1.0);
   lmm_update_variable_latency(Sys, T2, 1.0);
@@ -144,20 +267,18 @@ void test2(method_t method)
 
 
 
-  if(method==MAXMIN){
+  if (method == MAXMIN) {
     lmm_solve(Sys);
 #ifdef HAVE_SDP
-  }else if(method==SDP){
-    sdp_solve(Sys);    
+  } else if (method == SDP) {
+    sdp_solve(Sys);
 #endif
-  }else if(method==LAGRANGE_VEGAS){
-    //set default functions for TCP Vegas
-    lagrange_solve(Sys);  
-  }else if(method==LAGRANGE_RENO){
-    //set default functions for TCP Reno
-    lagrange_solve(Sys);  
-  }else{ 
-    xbt_assert0(0,"Invalid method");
+  } else if (method == LAGRANGE_VEGAS) {
+    lagrange_solve(Sys);
+  } else if (method == LAGRANGE_RENO) {
+    lagrange_solve(Sys);
+  } else {
+    xbt_assert0(0, "Invalid method");
   }
 
   PRINT_VAR(T1);
@@ -171,43 +292,43 @@ void test2(method_t method)
 void test3(method_t method);
 void test3(method_t method)
 {
-  int flows=11;  //flows and conexions are synonnims ?
-  int links=10;  //topology info
-  
-  //just to be carefull
+  int flows = 11;
+  int links = 10;
+
   int i = 0;
   int j = 0;
 
   double **A;
 
-  lmm_system_t Sys = NULL ;
+  lmm_system_t Sys = NULL;
   lmm_constraint_t *tmp_cnst = NULL;
-  lmm_variable_t   *tmp_var  = NULL;
+  lmm_variable_t *tmp_var = NULL;
   char **tmp_name;
 
 
   /*array to add the the constraints of fictiv variables */
-  double B[15] = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
+  double B[15] = { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
+
+    1, 1, 1, 1, 1
+  };
 
-               1, 1, 1, 1, 1};
+  A = (double **) calloc(links + 5, sizeof(double));
 
-  A = (double **)calloc(links+5, sizeof(double));
-  for(i=0 ; i< links+5; i++){
-    A[i] = (double *)calloc(flows+5, sizeof(double));
+  for (i = 0; i < links + 5; i++) {
+    A[i] = (double *) calloc(flows + 5, sizeof(double));
 
-    for(j=0 ; j< flows+5; j++){
+    for (j = 0; j < flows + 5; j++) {
       A[i][j] = 0.0;
 
-      if(i >= links || j >= flows){
-         A[i][j] = 0.0;
+      if (i >= links || j >= flows) {
+       A[i][j] = 0.0;
       }
     }
   }
 
-  /*matrix that store the constraints/topollogy*/
+  /*matrix that store the constraints/topollogy */
   /*double A[15][16]=
-    {{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0,    0, 0, 0, 0, 0},
+     {{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0,    0, 0, 0, 0, 0},
      {0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0,    0, 0, 0, 0, 0},
      {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0,    0, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,    0, 0, 0, 0, 0},
@@ -217,7 +338,7 @@ void test3(method_t method)
      {0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1,    0, 0, 0, 0, 0},
      {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1,    0, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0,    0, 0, 0, 0, 0},
-     
+
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    1, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 1, 0, 0, 0},
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 1, 0, 0},
@@ -225,49 +346,49 @@ void test3(method_t method)
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 1}
      }; */
 
-  A[0][1]  = 1.0;
-  A[0][7]  = 1.0;
-  
-  A[1][1]  = 1.0;
-  A[1][7]  = 1.0;
-  A[1][8]  = 1.0;
+  A[0][1] = 1.0;
+  A[0][7] = 1.0;
+
+  A[1][1] = 1.0;
+  A[1][7] = 1.0;
+  A[1][8] = 1.0;
 
-  A[2][1]  = 1.0;
-  A[2][8]  = 1.0;
+  A[2][1] = 1.0;
+  A[2][8] = 1.0;
 
-  A[2][1]  = 1.0;
-  A[2][8]  = 1.0;
+  A[2][1] = 1.0;
+  A[2][8] = 1.0;
 
-  A[3][8]  = 1.0;
+  A[3][8] = 1.0;
 
-  A[4][0]  = 1.0;
-  A[4][3]  = 1.0;
-  A[4][9]  = 1.0;
+  A[4][0] = 1.0;
+  A[4][3] = 1.0;
+  A[4][9] = 1.0;
 
-  A[5][0]  = 1.0;
-  A[5][3]  = 1.0;
-  A[5][4]  = 1.0;
-  A[5][9]  = 1.0;
+  A[5][0] = 1.0;
+  A[5][3] = 1.0;
+  A[5][4] = 1.0;
+  A[5][9] = 1.0;
 
-  A[6][0]  = 1.0;
-  A[6][4]  = 1.0;
-  A[6][9]  = 1.0;
+  A[6][0] = 1.0;
+  A[6][4] = 1.0;
+  A[6][9] = 1.0;
   A[6][10] = 1.0;
 
-  A[7][2]  = 1.0;
-  A[7][4]  = 1.0;
-  A[7][6]  = 1.0;
-  A[7][9]  = 1.0;
+  A[7][2] = 1.0;
+  A[7][4] = 1.0;
+  A[7][6] = 1.0;
+  A[7][9] = 1.0;
   A[7][10] = 1.0;
 
-  A[8][2]  = 1.0;
+  A[8][2] = 1.0;
   A[8][10] = 1.0;
 
-  A[9][5]  = 1.0;
-  A[9][6]  = 1.0;
-  A[9][9]  = 1.0;
+  A[9][5] = 1.0;
+  A[9][6] = 1.0;
+  A[9][9] = 1.0;
+
 
-  
   A[10][11] = 1.0;
   A[11][12] = 1.0;
   A[12][13] = 1.0;
@@ -275,29 +396,27 @@ void test3(method_t method)
   A[14][15] = 1.0;
 
 
-  if(method==LAGRANGE_VEGAS){
-    //set default functions for TCP Vegas
+  if (method == LAGRANGE_VEGAS) {
     lmm_set_default_protocol_function(func_vegas_fpi);
-  }else if(method==LAGRANGE_RENO){
-    //set default functions for TCP Reno
+  } else if (method == LAGRANGE_RENO) {
     lmm_set_default_protocol_function(func_reno_fpi);
   }
 
   Sys = lmm_system_new();
-  
+
 
 
   tmp_name = (char **) calloc(31, sizeof(char *));
-  for(i=0; i<31; i++){
+  for (i = 0; i < 31; i++) {
     tmp_name[i] = (char *) calloc(10, sizeof(char));
   }
-  
+
   /*
    * Creates the constraints
    */
   tmp_cnst = calloc(15, sizeof(lmm_constraint_t));
-  for(i=0; i<15; i++){
-    sprintf(tmp_name[i], "C_%03d", i); 
+  for (i = 0; i < 15; i++) {
+    sprintf(tmp_name[i], "C_%03d", i);
     tmp_cnst[i] = lmm_constraint_new(Sys, (void *) tmp_name[i], B[i]);
   }
 
@@ -306,42 +425,41 @@ void test3(method_t method)
    * Creates the variables
    */
   tmp_var = calloc(16, sizeof(lmm_variable_t));
-  for(j=0; j<16; j++){
-    sprintf(tmp_name[i+j], "X_%03d", j); 
-    tmp_var[j] = lmm_variable_new(Sys, (void *) tmp_name[i+j], 1.0, -1.0 , 15);
+  for (j = 0; j < 16; j++) {
+    sprintf(tmp_name[i + j], "X_%03d", j);
+    tmp_var[j] =
+       lmm_variable_new(Sys, (void *) tmp_name[i + j], 1.0, -1.0, 15);
     lmm_update_variable_latency(Sys, tmp_var[j], 1.0);
   }
 
   /*
    * Link constraints and variables
    */
-  for(i=0;i<15;i++) { 
-    for(j=0; j<16; j++){
-      if(A[i][j]){
-       lmm_expand(Sys, tmp_cnst[i], tmp_var[j], 1.0); 
+  for (i = 0; i < 15; i++) {
+    for (j = 0; j < 16; j++) {
+      if (A[i][j]) {
+       lmm_expand(Sys, tmp_cnst[i], tmp_var[j], 1.0);
       }
     }
   }
 
 
 
-  if(method==MAXMIN){
+  if (method == MAXMIN) {
     lmm_solve(Sys);
 #ifdef HAVE_SDP
-  }else if(method==SDP){
-    sdp_solve(Sys);    
+  } else if (method == SDP) {
+    sdp_solve(Sys);
 #endif
-  }else if(method==LAGRANGE_VEGAS){
-    //set default functions for TCP Vegas
-    lagrange_solve(Sys);  
-  }else if(method==LAGRANGE_RENO){
-    //set default functions for TCP Reno
-    lagrange_solve(Sys);  
-  }else{ 
-    xbt_assert0(0,"Invalid method");
+  } else if (method == LAGRANGE_VEGAS) {
+    lagrange_solve(Sys);
+  } else if (method == LAGRANGE_RENO) {
+    lagrange_solve(Sys);
+  } else {
+    xbt_assert0(0, "Invalid method");
   }
 
-  for(j=0; j<16; j++){
+  for (j = 0; j < 16; j++) {
     PRINT_VAR(tmp_var[j]);
   }
 
@@ -357,7 +475,7 @@ void test3(method_t method)
 
 int main(int argc, char **argv)
 {
-  xbt_init(&argc,argv);
+  xbt_init(&argc, argv);
 
 
   DEBUG0("**************************** ");