testsuite/surf/lmm_usage.c

   1 /*      $Id$     */
   2
   3 /* A few tests for the maxmin library                                       */
   4
   5 /* Copyright (c) 2004 Arnaud Legrand. All rights reserved.                  */
   6
   7 /* This program is free software; you can redistribute it and/or modify it
   8  * under the terms of the license (GNU LGPL) which comes with this package. */
   9
  10 #ifdef __BORLANDC__
  11 #pragma hdrstop
  12 #endif
  13
  14 #include "xbt/sysdep.h"
  15 #include "surf/maxmin.h"
  16 #include "xbt/log.h"
  17 #include "xbt/module.h"
  18 #include <math.h>
  19
  20 XBT_LOG_NEW_DEFAULT_CATEGORY(surf_test,
  21                              "Messages specific for surf example");
  22
  23 #define PRINT_VAR(var) DEBUG1(#var " = %g",lmm_variable_getvalue(var));
  24 #define SHOW_EXPR(expr) DEBUG1(#expr " = %g",expr);
  25
  26 /*                               */
  27 /*        ______                 */
  28 /*  ==l1==  L2  ==L3==           */
  29 /*        ------                 */
  30 /*                               */
  31
  32 typedef enum {
  33   MAXMIN,
  34   SDP,
  35   LAGRANGE_RENO,
  36   LAGRANGE_VEGAS,
  37 } method_t;
  38
  39 static double dichotomy(double func(double), double min, double max,
  40                         double min_error)
  41 {
  42   double middle;
  43   double min_func, max_func, middle_func;
  44
  45   double overall_error = 2 * min_error;
  46
  47   min_func = func(min);
  48   max_func = func(max);
  49
  50   if ((min_func > 0 && max_func > 0))
  51     return min - 1.0;
  52   if ((min_func < 0 && max_func < 0))
  53     return max + 1.0;
  54   if ((min_func > 0 && max_func < 0))
  55     abort();
  56
  57   while (overall_error > min_error) {
  58     if ((min_func > 0 && max_func > 0) ||
  59         (min_func < 0 && max_func < 0) || (min_func > 0 && max_func < 0)) {
  60       abort();
  61     }
  62
  63     middle = (max + min) / 2.0;
  64     if ((min == middle) || (max == middle)) {
  65       break;
  66     }
  67     middle_func = func(middle);
  68
  69     if (middle_func < 0) {
  70       min = middle;
  71       min_func = middle_func;
  72       overall_error = max - middle_func;
  73     } else if (middle_func > 0) {
  74       max = middle;
  75       max_func = middle_func;
  76       overall_error = max - middle_func;
  77     } else {
  78       overall_error = 0;
  79     }
  80   }
  81   return ((min + max) / 2.0);
  82 }
  83
  84 double a_test_1 = 0;
  85 double b_test_1 = 0;
  86 static double diff_lagrange_test_1(double x)
  87 {
  88   return -(3 / (1 + 3 * x * x / 2) -
  89            3 / (2 * (3 * (a_test_1 - x) * (a_test_1 - x) / 2 + 1)) +
  90            3 / (2 *
  91                 (3 * (b_test_1 - a_test_1 + x) *
  92                  (b_test_1 - a_test_1 + x) / 2 + 1)));
  93 }
  94
  95 void test1(method_t method);
  96 void test1(method_t method)
  97 {
  98   lmm_system_t Sys = NULL;
  99   lmm_constraint_t L1 = NULL;
 100   lmm_constraint_t L2 = NULL;
 101   lmm_constraint_t L3 = NULL;
 102
 103   lmm_variable_t R_1_2_3 = NULL;
 104   lmm_variable_t R_1 = NULL;
 105   lmm_variable_t R_2 = NULL;
 106   lmm_variable_t R_3 = NULL;
 107
 108   double a = 1.0, b = 10.0;
 109
 110   if (method == LAGRANGE_VEGAS)
 111     lmm_set_default_protocol_function(func_vegas_f, func_vegas_fp,
 112                                       func_vegas_fpi);
 113   else if (method == LAGRANGE_RENO)
 114     lmm_set_default_protocol_function(func_reno_f, func_reno_fpi,
 115                                       func_reno_fpi);
 116
 117   Sys = lmm_system_new();
 118   L1 = lmm_constraint_new(Sys, (void *) "L1", a);
 119   L2 = lmm_constraint_new(Sys, (void *) "L2", b);
 120   L3 = lmm_constraint_new(Sys, (void *) "L3", a);
 121
 122   R_1_2_3 = lmm_variable_new(Sys, (void *) "R 1->2->3", 1.0, -1.0, 3);
 123   R_1 = lmm_variable_new(Sys, (void *) "R 1", 1.0, -1.0, 1);
 124   R_2 = lmm_variable_new(Sys, (void *) "R 2", 1.0, -1.0, 1);
 125   R_3 = lmm_variable_new(Sys, (void *) "R 3", 1.0, -1.0, 1);
 126
 127   lmm_update_variable_latency(Sys, R_1_2_3, 1.0);
 128   lmm_update_variable_latency(Sys, R_1, 1.0);
 129   lmm_update_variable_latency(Sys, R_2, 1.0);
 130   lmm_update_variable_latency(Sys, R_3, 1.0);
 131
 132   lmm_expand(Sys, L1, R_1_2_3, 1.0);
 133   lmm_expand(Sys, L2, R_1_2_3, 1.0);
 134   lmm_expand(Sys, L3, R_1_2_3, 1.0);
 135
 136   lmm_expand(Sys, L1, R_1, 1.0);
 137
 138   lmm_expand(Sys, L2, R_2, 1.0);
 139
 140   lmm_expand(Sys, L3, R_3, 1.0);
 141
 142
 143   if (method == MAXMIN) {
 144     lmm_solve(Sys);
 145 #ifdef HAVE_SDP
 146   } else if (method == SDP) {
 147     sdp_solve(Sys);
 148 #endif
 149   } else if (method == LAGRANGE_VEGAS) {
 150     double x = 3 * a / 4 - 3 * b / 8 +
 151         sqrt(9 * b * b + 4 * a * a - 4 * a * b) / 8;
 152     /* Computed with mupad and D_f=1.0 */
 153     double max_deviation = 0.0;
 154     if (x > a) {
 155       x = a;
 156     }
 157     if (x < 0) {
 158       x = 0;
 159     }
 160
 161     lagrange_solve(Sys);
 162
 163     max_deviation =
 164         MAX(max_deviation, fabs(lmm_variable_getvalue(R_1) - x));
 165     max_deviation =
 166         MAX(max_deviation, fabs(lmm_variable_getvalue(R_3) - x));
 167     max_deviation =
 168         MAX(max_deviation, fabs(lmm_variable_getvalue(R_2) - (b - a + x)));
 169     max_deviation =
 170         MAX(max_deviation, fabs(lmm_variable_getvalue(R_1_2_3) - (a - x)));
 171
 172     if (max_deviation > MAXMIN_PRECISION) {
 173       WARN1("Max Deviation from optimal solution : %g", max_deviation);
 174       WARN1("Found x = %1.20f", x);
 175       WARN2("Deviation from optimal solution (R_1 = %g): %1.20f", x,
 176             lmm_variable_getvalue(R_1) - x);
 177       WARN2("Deviation from optimal solution (R_2 = %g): %1.20f",
 178             b - a + x, lmm_variable_getvalue(R_2) - (b - a + x));
 179       WARN2("Deviation from optimal solution (R_3 = %g): %1.20f", x,
 180             lmm_variable_getvalue(R_3) - x);
 181       WARN2("Deviation from optimal solution (R_1_2_3 = %g): %1.20f",
 182             a - x, lmm_variable_getvalue(R_1_2_3) - (a - x));
 183     }
 184   } else if (method == LAGRANGE_RENO) {
 185     double x;
 186     double max_deviation = 0.0;
 187
 188     a_test_1 = a;
 189     b_test_1 = b;
 190     x = dichotomy(diff_lagrange_test_1, 0, a, 1e-8);
 191
 192     if (x < 0)
 193       x = 0;
 194     if (x > a)
 195       x = a;
 196     lagrange_solve(Sys);
 197
 198     max_deviation =
 199         MAX(max_deviation, fabs(lmm_variable_getvalue(R_1) - x));
 200     max_deviation =
 201         MAX(max_deviation, fabs(lmm_variable_getvalue(R_3) - x));
 202     max_deviation =
 203         MAX(max_deviation, fabs(lmm_variable_getvalue(R_2) - (b - a + x)));
 204     max_deviation =
 205         MAX(max_deviation, fabs(lmm_variable_getvalue(R_1_2_3) - (a - x)));
 206
 207     if (max_deviation > MAXMIN_PRECISION) {
 208       WARN1("Max Deviation from optimal solution : %g", max_deviation);
 209       WARN1("Found x = %1.20f", x);
 210       WARN2("Deviation from optimal solution (R_1 = %g): %1.20f", x,
 211             lmm_variable_getvalue(R_1) - x);
 212       WARN2("Deviation from optimal solution (R_2 = %g): %1.20f",
 213             b - a + x, lmm_variable_getvalue(R_2) - (b - a + x));
 214       WARN2("Deviation from optimal solution (R_3 = %g): %1.20f", x,
 215             lmm_variable_getvalue(R_3) - x);
 216       WARN2("Deviation from optimal solution (R_1_2_3 = %g): %1.20f",
 217             a - x, lmm_variable_getvalue(R_1_2_3) - (a - x));
 218     }
 219   } else {
 220     xbt_assert0(0, "Invalid method");
 221   }
 222
 223   PRINT_VAR(R_1_2_3);
 224   PRINT_VAR(R_1);
 225   PRINT_VAR(R_2);
 226   PRINT_VAR(R_3);
 227
 228   lmm_system_free(Sys);
 229 }
 230
 231 void test2(method_t method);
 232 void test2(method_t method)
 233 {
 234   lmm_system_t Sys = NULL;
 235   lmm_constraint_t CPU1 = NULL;
 236   lmm_constraint_t CPU2 = NULL;
 237
 238   lmm_variable_t T1 = NULL;
 239   lmm_variable_t T2 = NULL;
 240
 241
 242   if (method == LAGRANGE_VEGAS)
 243     lmm_set_default_protocol_function(func_vegas_f, func_vegas_fp,
 244                                       func_vegas_fpi);
 245   else if (method == LAGRANGE_RENO)
 246     lmm_set_default_protocol_function(func_reno_f, func_reno_fp,
 247                                       func_reno_fpi);
 248
 249   Sys = lmm_system_new();
 250   CPU1 = lmm_constraint_new(Sys, (void *) "CPU1", 200.0);
 251   CPU2 = lmm_constraint_new(Sys, (void *) "CPU2", 100.0);
 252
 253   T1 = lmm_variable_new(Sys, (void *) "T1", 1.0, -1.0, 1);
 254   T2 = lmm_variable_new(Sys, (void *) "T2", 1.0, -1.0, 1);
 255
 256   lmm_update_variable_latency(Sys, T1, 1.0);
 257   lmm_update_variable_latency(Sys, T2, 1.0);
 258
 259
 260   lmm_expand(Sys, CPU1, T1, 1.0);
 261   lmm_expand(Sys, CPU2, T2, 1.0);
 262
 263
 264
 265   if (method == MAXMIN) {
 266     lmm_solve(Sys);
 267 #ifdef HAVE_SDP
 268   } else if (method == SDP) {
 269     sdp_solve(Sys);
 270 #endif
 271   } else if (method == LAGRANGE_VEGAS) {
 272     lagrange_solve(Sys);
 273   } else if (method == LAGRANGE_RENO) {
 274     lagrange_solve(Sys);
 275   } else {
 276     xbt_assert0(0, "Invalid method");
 277   }
 278
 279   PRINT_VAR(T1);
 280   PRINT_VAR(T2);
 281
 282   lmm_system_free(Sys);
 283 }
 284
 285
 286
 287 void test3(method_t method);
 288 void test3(method_t method)
 289 {
 290   int flows = 11;
 291   int links = 10;
 292
 293   int i = 0;
 294   int j = 0;
 295
 296   double **A;
 297
 298   lmm_system_t Sys = NULL;
 299   lmm_constraint_t *tmp_cnst = NULL;
 300   lmm_variable_t *tmp_var = NULL;
 301   char **tmp_name;
 302
 303
 304   /*array to add the the constraints of fictiv variables */
 305   double B[15] = { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
 306
 307     1, 1, 1, 1, 1
 308   };
 309
 310   /*A = xbt_new0(double*, links + 5);*/
 311   A = xbt_new0(double*, links + 5);
 312
 313   for (i = 0; i < links + 5; i++) {
 314     A[i] = xbt_new0(double, flows + 5);
 315     for (j = 0; j < flows + 5; j++) {
 316       A[i][j] = 0.0;
 317
 318       if (i >= links || j >= flows) {
 319         A[i][j] = 0.0;
 320       }
 321     }
 322   }
 323
 324   /*matrix that store the constraints/topollogy */
 325   /*double A[15][16]=
 326      {{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0,    0, 0, 0, 0, 0},
 327      {0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0,    0, 0, 0, 0, 0},
 328      {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0,    0, 0, 0, 0, 0},
 329      {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,    0, 0, 0, 0, 0},
 330      {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0,    0, 0, 0, 0, 0},
 331      {1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0,    0, 0, 0, 0, 0},
 332      {1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1,    0, 0, 0, 0, 0},
 333      {0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1,    0, 0, 0, 0, 0},
 334      {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1,    0, 0, 0, 0, 0},
 335      {0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0,    0, 0, 0, 0, 0},
 336
 337      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    1, 0, 0, 0, 0},
 338      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 1, 0, 0, 0},
 339      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 1, 0, 0},
 340      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 1, 0},
 341      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 1}
 342      }; */
 343
 344   A[0][1] = 1.0;
 345   A[0][7] = 1.0;
 346
 347   A[1][1] = 1.0;
 348   A[1][7] = 1.0;
 349   A[1][8] = 1.0;
 350
 351   A[2][1] = 1.0;
 352   A[2][8] = 1.0;
 353
 354   A[2][1] = 1.0;
 355   A[2][8] = 1.0;
 356
 357   A[3][8] = 1.0;
 358
 359   A[4][0] = 1.0;
 360   A[4][3] = 1.0;
 361   A[4][9] = 1.0;
 362
 363   A[5][0] = 1.0;
 364   A[5][3] = 1.0;
 365   A[5][4] = 1.0;
 366   A[5][9] = 1.0;
 367
 368   A[6][0] = 1.0;
 369   A[6][4] = 1.0;
 370   A[6][9] = 1.0;
 371   A[6][10] = 1.0;
 372
 373   A[7][2] = 1.0;
 374   A[7][4] = 1.0;
 375   A[7][6] = 1.0;
 376   A[7][9] = 1.0;
 377   A[7][10] = 1.0;
 378
 379   A[8][2] = 1.0;
 380   A[8][10] = 1.0;
 381
 382   A[9][5] = 1.0;
 383   A[9][6] = 1.0;
 384   A[9][9] = 1.0;
 385
 386
 387   A[10][11] = 1.0;
 388   A[11][12] = 1.0;
 389   A[12][13] = 1.0;
 390   A[13][14] = 1.0;
 391   A[14][15] = 1.0;
 392
 393
 394   if (method == LAGRANGE_VEGAS)
 395     lmm_set_default_protocol_function(func_vegas_f, func_vegas_fp,
 396                                       func_vegas_fpi);
 397   else if (method == LAGRANGE_RENO)
 398     lmm_set_default_protocol_function(func_reno_f, func_reno_fp,
 399                                       func_reno_fpi);
 400
 401   Sys = lmm_system_new();
 402
 403
 404
 405   tmp_name = xbt_new0(char *,31);
 406
 407   /*
 408    * Creates the constraints
 409    */
 410   tmp_cnst = xbt_new0(lmm_constraint_t,15);
 411   for (i = 0; i < 15; i++) {
 412     tmp_name[i] = bprintf("C_%03d", i);
 413     tmp_cnst[i] = lmm_constraint_new(Sys, (void *) tmp_name[i], B[i]);
 414   }
 415
 416
 417   /*
 418    * Creates the variables
 419    */
 420   tmp_var = xbt_new0(lmm_variable_t,16);
 421   for (j = 0; j < 16; j++) {
 422     tmp_name[i + j] = bprintf("X_%03d", j);
 423     tmp_var[j] =
 424         lmm_variable_new(Sys, (void *) tmp_name[i + j], 1.0, -1.0, 15);
 425     lmm_update_variable_latency(Sys, tmp_var[j], 1.0);
 426   }
 427
 428   /*
 429    * Link constraints and variables
 430    */
 431   for (i = 0; i < 15; i++) {
 432     for (j = 0; j < 16; j++) {
 433       if (A[i][j]) {
 434         lmm_expand(Sys, tmp_cnst[i], tmp_var[j], 1.0);
 435       }
 436     }
 437   }
 438
 439
 440
 441   if (method == MAXMIN) {
 442     lmm_solve(Sys);
 443 #ifdef HAVE_SDP
 444   } else if (method == SDP) {
 445     sdp_solve(Sys);
 446 #endif
 447   } else if (method == LAGRANGE_VEGAS) {
 448     lagrange_solve(Sys);
 449   } else if (method == LAGRANGE_RENO) {
 450     lagrange_solve(Sys);
 451   } else {
 452     xbt_assert0(0, "Invalid method");
 453   }
 454
 455   for (j = 0; j < 16; j++) {
 456     PRINT_VAR(tmp_var[j]);
 457   }
 458
 459   free(tmp_var);
 460   free(tmp_cnst);
 461   free(tmp_name);
 462   lmm_system_free(Sys);
 463 }
 464
 465 #ifdef __BORLANDC__
 466 #pragma argsused
 467 #endif
 468
 469 int main(int argc, char **argv)
 470 {
 471   xbt_init(&argc, argv);
 472
 473   INFO0("***** Test 1 (Max-Min)");
 474   test1(MAXMIN);
 475 #ifdef HAVE_SDP
 476   INFO0("***** Test 1 (SDP)");
 477   test1(SDP);
 478 #endif
 479   INFO0("***** Test 1 (Lagrange - Vegas)");
 480   test1(LAGRANGE_VEGAS);
 481   INFO0("***** Test 1 (Lagrange - Reno)");
 482   test1(LAGRANGE_RENO);
 483
 484
 485
 486   INFO0("***** Test 2 (Max-Min)");
 487   test2(MAXMIN);
 488 #ifdef HAVE_SDP
 489   INFO0("***** Test 2 (SDP)");
 490   test2(SDP);
 491 #endif
 492   INFO0("***** Test 2 (Lagrange - Vegas)");
 493   test2(LAGRANGE_VEGAS);
 494   INFO0("***** Test 2 (Lagrange - Reno)");
 495   test2(LAGRANGE_RENO);
 496
 497
 498   INFO0("***** Test 3 (Max-Min)");
 499   test3(MAXMIN);
 500 #ifdef HAVE_SDP
 501   INFO0("***** Test 3 (SDP)");
 502   test3(SDP);
 503 #endif
 504   INFO0("***** Test 3 (Lagrange - Vegas)");
 505   test3(LAGRANGE_VEGAS);
 506   INFO0("***** Test 3 (Lagrange - Reno)");
 507   test3(LAGRANGE_RENO);
 508
 509   return 0;
 510 }