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