src/kernel/lmm/maxmin_test.cpp

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