src/kernel/lmm/maxmin_test.cpp

   1 /* Copyright (c) 2019. 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 = lmm::make_new_maxmin_system(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   delete Sys;
 144 }
 145
 146 TEST_CASE("kernel::lmm Single constraint unshared systems", "[kernel-lmm-unshared-single-sys]")
 147 {
 148   lmm::System* Sys = lmm::make_new_maxmin_system(false);
 149
 150   SECTION("Variable penalty")
 151   {
 152     /*
 153      * A variable with a penalty of two get half of the max_share
 154      *
 155      * In details:
 156      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C1
 157      *   o consumption_weight: a1=1 ; a2=1
 158      *   o sharing_penalty:    p1=1 ; p2=2
 159      *   o max_share: max(C1/(a1/p1),C1/(a2/p2))
 160      *
 161      * Expectations
 162      *   o rho1 = max_share
 163      *   o rho2 = max_share/2 (because penalty of rho2 is 2)
 164      */
 165
 166     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
 167     sys_cnst->unshare(); // FATPIPE
 168     lmm::Variable* rho_1 = Sys->variable_new(nullptr, 1);
 169     lmm::Variable* rho_2 = Sys->variable_new(nullptr, 2);
 170
 171     Sys->expand(sys_cnst, rho_1, 1);
 172     Sys->expand(sys_cnst, rho_2, 1);
 173     Sys->solve();
 174
 175     REQUIRE(double_equals(rho_1->get_value(), 10, sg_maxmin_precision));
 176     REQUIRE(double_equals(rho_2->get_value(), 10 / 2, sg_maxmin_precision));
 177   }
 178
 179   SECTION("Consumption weight")
 180   {
 181     /*
 182      * In a given constraint with all variable penalty to 1,
 183      * the max_share is affected only by the maximum consumption weight
 184      *
 185      * In details:
 186      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C1
 187      *   o consumption_weight: a1=1 ; a2=1
 188      *   o sharing_penalty:    p1=1 ; p2=2
 189      *   o max_share: max(C1/(a1/p1),C1/(a2/p2))
 190      *
 191      * Expectations
 192      *   o rho1 = max_share/2 (because penalty of rho1 is 1)
 193      *   o rho2 = max_share/2 (because penalty of rho2 is 1)
 194      */
 195
 196     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
 197     sys_cnst->unshare(); // FATPIPE
 198     lmm::Variable* rho_1 = Sys->variable_new(nullptr, 1);
 199     lmm::Variable* rho_2 = Sys->variable_new(nullptr, 1);
 200
 201     Sys->expand(sys_cnst, rho_1, 1);
 202     Sys->expand(sys_cnst, rho_2, 2);
 203     Sys->solve();
 204
 205     REQUIRE(double_equals(rho_1->get_value(), 5, sg_maxmin_precision));
 206     REQUIRE(double_equals(rho_2->get_value(), 5, sg_maxmin_precision));
 207   }
 208
 209   SECTION("Consumption weight + variable penalty")
 210   {
 211     /*
 212      * Resource proportionality between variable is kept but
 213      * constraint bound can be violated
 214      *
 215      * In details:
 216      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
 217      *   o consumption_weight: a1=1 ; a2=2
 218      *   o sharing_penalty:    p1=1 ; p2=2
 219      *
 220      * Expectations
 221      *   o rho1 = 2 * rho2 (because rho2 has twice the penalty)
 222      *   o rho1 + 2*rho2 can be greater than C
 223      *   o rho1 <= C and 2*rho2 <= C
 224      */
 225
 226     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
 227     sys_cnst->unshare();
 228     lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 1);
 229     lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 2);
 230
 231     Sys->expand(sys_cnst, sys_var_1, 1);
 232     Sys->expand(sys_cnst, sys_var_2, 2);
 233     Sys->solve();
 234
 235     REQUIRE(double_equals(sys_var_1->get_value(), 10, sg_maxmin_precision));
 236     REQUIRE(double_equals(sys_var_2->get_value(), 5, sg_maxmin_precision));
 237   }
 238
 239   SECTION("Multiple constraints systems")
 240   {
 241     /*
 242      * Multiple constraint systems can be solved with shared variables
 243      * on unshared constraints.
 244      *
 245      * In details:
 246      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C1
 247      *              a3 * p1 * \rho1  +  a4 * p3 * \rho3 < C2
 248      *   o consumption_weight: a1=1 ; a2=2 ; a3=2 ; a4=1
 249      *   o sharing_penalty:    p1=1 ; p2=2 ; p3=1
 250      *   o load: load_1=C1/max(p1/a1,p2/a2)=20 ; load_2=C2/max(a3/p1,a4/p3)=30
 251      *
 252      * Expectations
 253      *   o First constraint will be solve first (because load_1 < load_2)
 254      *   o Second constraint load will not be updated !
 255      *   o Each constraint should satisfy max(a_i * rho_i) <= C_r
 256      */
 257
 258     lmm::Constraint* sys_cnst_1 = Sys->constraint_new(nullptr, 10);
 259     lmm::Constraint* sys_cnst_2 = Sys->constraint_new(nullptr, 60);
 260     sys_cnst_1->unshare(); // FATPIPE
 261     sys_cnst_2->unshare();
 262
 263     lmm::Variable* rho_1 = Sys->variable_new(nullptr, 1, -1, 2);
 264     lmm::Variable* rho_2 = Sys->variable_new(nullptr, 2, -1, 1);
 265     lmm::Variable* rho_3 = Sys->variable_new(nullptr, 1, -1, 1);
 266
 267     // Constraint 1
 268     Sys->expand(sys_cnst_1, rho_1, 1);
 269     Sys->expand(sys_cnst_1, rho_2, 2);
 270
 271     // Constraint 2
 272     Sys->expand(sys_cnst_2, rho_1, 2);
 273     Sys->expand(sys_cnst_2, rho_3, 1);
 274     Sys->solve();
 275
 276     double rho_1_share = 10; // Start by solving the first constraint (results is the same as previous tests)
 277     REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_maxmin_precision));
 278     REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_maxmin_precision));
 279     REQUIRE(double_equals(rho_3->get_value(), 60, sg_maxmin_precision));
 280   }
 281
 282   Sys->variable_free_all();
 283   delete Sys;
 284 }