src/kernel/lmm/maxmin_test.cpp

   1 /* Copyright (c) 2019-2020. 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 }