src/kernel/lmm/maxmin_test.cpp

   1 /* Copyright (c) 2019-2022. The SimGrid Team. All rights reserved.               */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include "src/include/catch.hpp"
   7 #include "src/kernel/lmm/maxmin.hpp"
   8 #include "src/surf/surf_interface.hpp"
   9 #include "xbt/log.h"
  10
  11 namespace lmm = simgrid::kernel::lmm;
  12
  13 TEST_CASE("kernel::lmm Single constraint shared systems", "[kernel-lmm-shared-single-sys]")
  14 {
  15   lmm::System Sys(false);
  16
  17   SECTION("Variable penalty")
  18   {
  19     /*
  20      * A variable with twice the penalty gets half of the share
  21      *
  22      * In details:
  23      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
  24      *   o consumption_weight: a1=1 ; a2=1
  25      *   o sharing_penalty:    p1=1 ; p2=2
  26      *
  27      * Expectations
  28      *   o rho1 = 2* rho2 (because rho2 has twice the penalty)
  29      *   o rho1 + rho2 = C (because all weights are 1)
  30      */
  31
  32     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
  33     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
  34     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 2);
  35
  36     Sys.expand(sys_cnst, rho_1, 1);
  37     Sys.expand(sys_cnst, rho_2, 1);
  38     Sys.solve();
  39
  40     REQUIRE(double_equals(rho_1->get_value(), 2, sg_maxmin_precision));
  41     REQUIRE(double_equals(rho_2->get_value(), 1, sg_maxmin_precision));
  42   }
  43
  44   SECTION("Consumption weight")
  45   {
  46     /*
  47      * Variables of higher consumption weight consume more resource but get the same share
  48      *
  49      * In details:
  50      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
  51      *   o consumption_weight: a1=1 ; a2=2
  52      *   o sharing_penalty:    p1=1 ; p2=1
  53      *
  54      * Expectations
  55      *   o rho1 = rho2 (because all penalties are 1)
  56      *   o rho1 + 2* rho2 = C (because weight_2 is 2)
  57      *   o so, rho1 = rho2 = 1 (because C is 3)
  58      */
  59
  60     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
  61     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
  62     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 1);
  63
  64     Sys.expand(sys_cnst, rho_1, 1);
  65     Sys.expand(sys_cnst, rho_2, 2);
  66     Sys.solve();
  67
  68     REQUIRE(double_equals(rho_1->get_value(), 1, sg_maxmin_precision));
  69     REQUIRE(double_equals(rho_2->get_value(), 1, sg_maxmin_precision));
  70   }
  71
  72   SECTION("Consumption weight + variable penalty")
  73   {
  74     /*
  75      * Resource proportionality between variable is kept while
  76      * varying consumption weight
  77      *
  78      * In details:
  79      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
  80      *   o consumption_weight: a1=1 ; a2=2
  81      *   o sharing_penalty:    p1=1 ; p2=2
  82      *
  83      * Expectations
  84      *   o rho1 = 2* rho2 (because rho2 has twice the penalty)
  85      *   o rho1 + 2*rho2 = C (because consumption weight of rho2 is 2)
  86      */
  87
  88     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 20);
  89     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
  90     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 2);
  91
  92     Sys.expand(sys_cnst, rho_1, 1);
  93     Sys.expand(sys_cnst, rho_2, 2);
  94     Sys.solve();
  95
  96     double rho_1_share = 10;
  97     REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_maxmin_precision));
  98     REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_maxmin_precision));
  99   }
 100
 101   SECTION("Multiple constraints systems")
 102   {
 103     /*
 104      * Multiple constraint systems can be solved with shared variables
 105      *
 106      * In details:
 107      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C1
 108      *              a3 * p1 * \rho1  +  a4 * p3 * \rho3 < C2
 109      *   o consumption_weight: a1=1 ; a2=2 ; a3=2 ; a4=1
 110      *   o sharing_penalty:    p1=1 ; p2=2 ; p3=1
 111      *   o load: load_1=C1/(p1/a1 + p2/a2)=20 ; load_2=C2/(a2/p1 + a3/p3)=30
 112      *
 113      * Expectations
 114      *   o First constraint will be solve first (because load_1 < load_2)
 115      *   o rho1 = 2* rho2 (because rho2 has twice the penalty)
 116      *   o rho1 + 2*rho2 = C1 (because consumption weight of rho2 is 2)
 117      *   o 2*rho1 + rho3 = C2 (because consumption weight of rho1 is 2)
 118      */
 119
 120     lmm::Constraint* sys_cnst_1 = Sys.constraint_new(nullptr, 20);
 121     lmm::Constraint* sys_cnst_2 = Sys.constraint_new(nullptr, 60);
 122
 123     lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
 124     lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2, -1, 1);
 125     lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 1);
 126
 127     // Constraint 1
 128     Sys.expand(sys_cnst_1, rho_1, 1);
 129     Sys.expand(sys_cnst_1, rho_2, 2);
 130
 131     // Constraint 2
 132     Sys.expand(sys_cnst_2, rho_1, 2);
 133     Sys.expand(sys_cnst_2, rho_3, 1);
 134     Sys.solve();
 135
 136     double rho_1_share = 10; // Start by solving the first constraint (results is the same as previous tests)
 137     REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_maxmin_precision));
 138     REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_maxmin_precision));
 139     REQUIRE(double_equals(rho_3->get_value(), 60 - 2 * rho_1_share, sg_maxmin_precision));
 140   }
 141
 142   Sys.variable_free_all();
 143 }
 144
 145 TEST_CASE("kernel::lmm Single constraint unshared systems", "[kernel-lmm-unshared-single-sys]")
 146 {
 147   lmm::System Sys(false);
 148
 149   SECTION("Variable penalty")
 150   {
 151     /*
 152      * A variable with a penalty of two get half of the max_share
 153      *
 154      * In details:
 155      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C1
 156      *   o consumption_weight: a1=1 ; a2=1
 157      *   o sharing_penalty:    p1=1 ; p2=2
 158      *   o max_share: max(C1/(a1/p1),C1/(a2/p2))
 159      *
 160      * Expectations
 161      *   o rho1 = max_share
 162      *   o rho2 = max_share/2 (because penalty of rho2 is 2)
 163      */
 164
 165     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10);
 166     sys_cnst->unshare(); // FATPIPE
 167     lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
 168     lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2);
 169
 170     Sys.expand(sys_cnst, rho_1, 1);
 171     Sys.expand(sys_cnst, rho_2, 1);
 172     Sys.solve();
 173
 174     REQUIRE(double_equals(rho_1->get_value(), 10, sg_maxmin_precision));
 175     REQUIRE(double_equals(rho_2->get_value(), 10 / 2, sg_maxmin_precision));
 176   }
 177
 178   SECTION("Consumption weight")
 179   {
 180     /*
 181      * In a given constraint with all variable penalty to 1,
 182      * the max_share is affected only by the maximum consumption weight
 183      *
 184      * In details:
 185      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C1
 186      *   o consumption_weight: a1=1 ; a2=1
 187      *   o sharing_penalty:    p1=1 ; p2=2
 188      *   o max_share: max(C1/(a1/p1),C1/(a2/p2))
 189      *
 190      * Expectations
 191      *   o rho1 = max_share/2 (because penalty of rho1 is 1)
 192      *   o rho2 = max_share/2 (because penalty of rho2 is 1)
 193      */
 194
 195     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10);
 196     sys_cnst->unshare(); // FATPIPE
 197     lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
 198     lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
 199
 200     Sys.expand(sys_cnst, rho_1, 1);
 201     Sys.expand(sys_cnst, rho_2, 2);
 202     Sys.solve();
 203
 204     REQUIRE(double_equals(rho_1->get_value(), 5, sg_maxmin_precision));
 205     REQUIRE(double_equals(rho_2->get_value(), 5, sg_maxmin_precision));
 206   }
 207
 208   SECTION("Consumption weight + variable penalty")
 209   {
 210     /*
 211      * Resource proportionality between variable is kept but
 212      * constraint bound can be violated
 213      *
 214      * In details:
 215      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
 216      *   o consumption_weight: a1=1 ; a2=2
 217      *   o sharing_penalty:    p1=1 ; p2=2
 218      *
 219      * Expectations
 220      *   o rho1 = 2 * rho2 (because rho2 has twice the penalty)
 221      *   o rho1 + 2*rho2 can be greater than C
 222      *   o rho1 <= C and 2*rho2 <= C
 223      */
 224
 225     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10);
 226     sys_cnst->unshare();
 227     lmm::Variable* sys_var_1 = Sys.variable_new(nullptr, 1);
 228     lmm::Variable* sys_var_2 = Sys.variable_new(nullptr, 2);
 229
 230     Sys.expand(sys_cnst, sys_var_1, 1);
 231     Sys.expand(sys_cnst, sys_var_2, 2);
 232     Sys.solve();
 233
 234     REQUIRE(double_equals(sys_var_1->get_value(), 10, sg_maxmin_precision));
 235     REQUIRE(double_equals(sys_var_2->get_value(), 5, sg_maxmin_precision));
 236   }
 237
 238   SECTION("Multiple constraints systems")
 239   {
 240     /*
 241      * Multiple constraint systems can be solved with shared variables
 242      * on unshared constraints.
 243      *
 244      * In details:
 245      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C1
 246      *              a3 * p1 * \rho1  +  a4 * p3 * \rho3 < C2
 247      *   o consumption_weight: a1=1 ; a2=2 ; a3=2 ; a4=1
 248      *   o sharing_penalty:    p1=1 ; p2=2 ; p3=1
 249      *   o load: load_1=C1/max(p1/a1,p2/a2)=20 ; load_2=C2/max(a3/p1,a4/p3)=30
 250      *
 251      * Expectations
 252      *   o First constraint will be solve first (because load_1 < load_2)
 253      *   o Second constraint load will not be updated !
 254      *   o Each constraint should satisfy max(a_i * rho_i) <= C_r
 255      */
 256
 257     lmm::Constraint* sys_cnst_1 = Sys.constraint_new(nullptr, 10);
 258     lmm::Constraint* sys_cnst_2 = Sys.constraint_new(nullptr, 60);
 259     sys_cnst_1->unshare(); // FATPIPE
 260     sys_cnst_2->unshare();
 261
 262     lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
 263     lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2, -1, 1);
 264     lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 1);
 265
 266     // Constraint 1
 267     Sys.expand(sys_cnst_1, rho_1, 1);
 268     Sys.expand(sys_cnst_1, rho_2, 2);
 269
 270     // Constraint 2
 271     Sys.expand(sys_cnst_2, rho_1, 2);
 272     Sys.expand(sys_cnst_2, rho_3, 1);
 273     Sys.solve();
 274
 275     double rho_1_share = 10; // Start by solving the first constraint (results is the same as previous tests)
 276     REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_maxmin_precision));
 277     REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_maxmin_precision));
 278     REQUIRE(double_equals(rho_3->get_value(), 60, sg_maxmin_precision));
 279   }
 280
 281   Sys.variable_free_all();
 282 }
 283
 284 TEST_CASE("kernel::lmm dynamic constraint shared systems", "[kernel-lmm-shared-single-sys]")
 285 {
 286   auto cb = [](double bound, int flows) -> double {
 287     // decrease 10 % for each extra flow sharing this resource
 288     return bound - (flows - 1) * .10 * bound;
 289   };
 290   lmm::System Sys(false);
 291   lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10);
 292   sys_cnst->set_sharing_policy(lmm::Constraint::SharingPolicy::NONLINEAR, cb);
 293
 294   SECTION("1 activity, 100% C")
 295   {
 296     /*
 297      * A single variable gets all the share
 298      *
 299      * In details:
 300      *   o System:  a1 * p1 * \rho1 < C
 301      *   o consumption_weight: a1=1
 302      *   o sharing_penalty:    p1=1
 303      *
 304      * Expectations
 305      *   o rho1 = C (because all weights are 1)
 306      */
 307
 308     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
 309
 310     Sys.expand(sys_cnst, rho_1, 1);
 311     Sys.solve();
 312
 313     REQUIRE(double_equals(rho_1->get_value(), 10, sg_maxmin_precision));
 314   }
 315
 316   SECTION("2 activities, but ignore crosstraffic 100% C")
 317   {
 318     /*
 319      * Ignore small activities (e.g. crosstraffic)
 320      *
 321      * In details:
 322      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
 323      *   o consumption_weight: a1=1 ; a2=0.05
 324      *   o sharing_penalty:    p1=1 ; p2=1
 325      *
 326      * Expectations
 327      *   o rho1 = C/1.05
 328      *   o rho2 = C/1.05
 329      *   o rho1 = rho2 (because rho1 and rho2 has the same penalty)
 330      */
 331
 332     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
 333     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 1);
 334
 335     Sys.expand(sys_cnst, rho_1, 1);
 336     Sys.expand(sys_cnst, rho_2, 0.05);
 337     Sys.solve();
 338
 339     REQUIRE(double_equals(rho_1->get_value(), 10 / 1.05, sg_maxmin_precision));
 340     REQUIRE(double_equals(rho_1->get_value(), rho_2->get_value(), sg_maxmin_precision));
 341   }
 342
 343   SECTION("2 activities, 1 inactive 100% C")
 344   {
 345     /*
 346      * 2 activities but 1 is inactive (sharing_penalty = 0)
 347      *
 348      * In details:
 349      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
 350      *   o consumption_weight: a1=1 ; a2=1
 351      *   o sharing_penalty:    p1=1 ; p2=0
 352      *
 353      * Expectations
 354      *   o rho1 = C
 355      *   o rho2 = 0
 356      */
 357
 358     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
 359     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 0);
 360
 361     Sys.expand(sys_cnst, rho_1, 1);
 362     Sys.expand(sys_cnst, rho_2, 1);
 363     Sys.solve();
 364
 365     REQUIRE(double_equals(rho_1->get_value(), 10, sg_maxmin_precision));
 366     REQUIRE(double_equals(rho_2->get_value(), 0, sg_maxmin_precision));
 367   }
 368
 369   SECTION("2 activity, 90% C")
 370   {
 371     /*
 372      * 2 similar variables degrades performance, but get same share
 373      *
 374      * In details:
 375      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < .9C
 376      *   o consumption_weight: a1=1 ; a2=1
 377      *   o sharing_penalty:    p1=1 ; p2=1
 378      *
 379      * Expectations
 380      *   o rho1 = rho2
 381      *   o rho1 + rho2 = C (because all weights are 1)
 382      */
 383
 384     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
 385     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 1);
 386
 387     Sys.expand(sys_cnst, rho_1, 1);
 388     Sys.expand(sys_cnst, rho_2, 1);
 389     Sys.solve();
 390
 391     REQUIRE(double_equals(rho_1->get_value(), 4.5, sg_maxmin_precision));
 392     REQUIRE(double_equals(rho_1->get_value(), 4.5, sg_maxmin_precision));
 393   }
 394
 395   SECTION("3 activity, 80% C")
 396   {
 397     /*
 398      * 3 similar variables degrades performance, sharing proportional to penalty
 399      *
 400      * In details:
 401      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 + a3 * p3 * \rho3 < .8C
 402      *   o consumption_weight: a1=1 ; a2=1 ; a3=1
 403      *   o sharing_penalty:    p1=1 ; p2=3 ; p3=4
 404      *
 405      * Expectations
 406      *   o rho1 = 2*rho2 = 2*rho3
 407      *   0 rho1 = 4, rho2 = 2, rho3 = 2
 408      *   o rho1 + rho2 + rho3 = .8C (because all weights are 1)
 409      */
 410
 411     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
 412     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 2);
 413     lmm::Variable* rho_3      = Sys.variable_new(nullptr, 2);
 414
 415     Sys.expand(sys_cnst, rho_1, 1);
 416     Sys.expand(sys_cnst, rho_2, 1);
 417     Sys.expand(sys_cnst, rho_3, 1);
 418     Sys.solve();
 419
 420     REQUIRE(double_equals(rho_1->get_value(), 4, sg_maxmin_precision));
 421     REQUIRE(double_equals(rho_2->get_value(), 2, sg_maxmin_precision));
 422     REQUIRE(double_equals(rho_3->get_value(), 2, sg_maxmin_precision));
 423   }
 424
 425   Sys.variable_free_all();
 426 }