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     /*
  76      * Resource proportionality between variable is kept while
  77      * varying consumption weight
  78      *
  79      * In details:
  80      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
  81      *   o consumption_weight: a1=1 ; a2=2
  82      *   o sharing_penalty:    p1=1 ; p2=2
  83      *
  84      * Expectations
  85      *   o rho1 = 2* rho2 (because rho2 has twice the penalty)
  86      *   o rho1 + 2*rho2 = C (because consumption weight of rho2 is 2)
  87      */
  88
  89     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 20);
  90     lmm::Variable* rho_1      = Sys->variable_new(nullptr, 1);
  91     lmm::Variable* rho_2      = Sys->variable_new(nullptr, 2);
  92
  93     Sys->expand(sys_cnst, rho_1, 1);
  94     Sys->expand(sys_cnst, rho_2, 2);
  95     Sys->solve();
  96
  97     double rho_1_share = 10;
  98     REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_maxmin_precision));
  99     REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_maxmin_precision));
 100   }
 101
 102   SECTION("Multiple constraints systems")
 103   {
 104
 105     /*
 106      * Multiple constraint systems can be solved with shared variables
 107      *
 108      * In details:
 109      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C1
 110      *              a3 * p1 * \rho1  +  a4 * p3 * \rho3 < C2
 111      *   o consumption_weight: a1=1 ; a2=2 ; a3=2 ; a4=1
 112      *   o sharing_penalty:    p1=1 ; p2=2 ; p3=1
 113      *   o load: load_1=C1/(p1/a1 + p2/a2)=20 ; load_2=C2/(a2/p1 + a3/p3)=30
 114      *
 115      * Expectations
 116      *   o First constraint will be solve first (because load_1 < load_2)
 117      *   o rho1 = 2* rho2 (because rho2 has twice the penalty)
 118      *   o rho1 + 2*rho2 = C1 (because consumption weight of rho2 is 2)
 119      *   o 2*rho1 + rho3 = C2 (because consumption weight of rho1 is 2)
 120      */
 121
 122     lmm::Constraint* sys_cnst_1 = Sys->constraint_new(nullptr, 20);
 123     lmm::Constraint* sys_cnst_2 = Sys->constraint_new(nullptr, 60);
 124
 125     lmm::Variable* rho_1 = Sys->variable_new(nullptr, 1, -1, 2);
 126     lmm::Variable* rho_2 = Sys->variable_new(nullptr, 2, -1, 1);
 127     lmm::Variable* rho_3 = Sys->variable_new(nullptr, 1, -1, 1);
 128
 129     // Constraint 1
 130     Sys->expand(sys_cnst_1, rho_1, 1);
 131     Sys->expand(sys_cnst_1, rho_2, 2);
 132
 133     // Constraint 2
 134     Sys->expand(sys_cnst_2, rho_1, 2);
 135     Sys->expand(sys_cnst_2, rho_3, 1);
 136     Sys->solve();
 137
 138     double rho_1_share = 10; // Start by solving the first constraint (results is the same as previous tests)
 139     REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_maxmin_precision));
 140     REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_maxmin_precision));
 141     REQUIRE(double_equals(rho_3->get_value(), 60 - 2 * rho_1_share, sg_maxmin_precision));
 142   }
 143
 144   Sys->variable_free_all();
 145   delete Sys;
 146 }
 147
 148 TEST_CASE("kernel::lmm Single constraint unshared systems", "[kernel-lmm-unshared-single-sys]")
 149 {
 150   lmm::System* Sys = lmm::make_new_maxmin_system(false);
 151
 152   SECTION("Variable penalty")
 153   {
 154
 155     /*
 156      * A variable with a penalty of two get half of the max_share
 157      *
 158      * In details:
 159      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C1
 160      *   o consumption_weight: a1=1 ; a2=1
 161      *   o sharing_penalty:    p1=1 ; p2=2
 162      *   o max_share: max(C1/(a1/p1),C1/(a2/p2))
 163      *
 164      * Expectations
 165      *   o rho1 = max_share
 166      *   o rho2 = max_share/2 (because penalty of rho2 is 2)
 167      */
 168
 169     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
 170     sys_cnst->unshare(); // FATPIPE
 171     lmm::Variable* rho_1 = Sys->variable_new(nullptr, 1);
 172     lmm::Variable* rho_2 = Sys->variable_new(nullptr, 2);
 173
 174     Sys->expand(sys_cnst, rho_1, 1);
 175     Sys->expand(sys_cnst, rho_2, 1);
 176     Sys->solve();
 177
 178     REQUIRE(double_equals(rho_1->get_value(), 10, sg_maxmin_precision));
 179     REQUIRE(double_equals(rho_2->get_value(), 10 / 2, sg_maxmin_precision));
 180   }
 181
 182   SECTION("Consumption weight")
 183   {
 184
 185     /*
 186      * In a given constraint with all variable penalty to 1,
 187      * the max_share is affected only by the maximum consumption weight
 188      *
 189      * In details:
 190      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C1
 191      *   o consumption_weight: a1=1 ; a2=1
 192      *   o sharing_penalty:    p1=1 ; p2=2
 193      *   o max_share: max(C1/(a1/p1),C1/(a2/p2))
 194      *
 195      * Expectations
 196      *   o rho1 = max_share/2 (because penalty of rho1 is 1)
 197      *   o rho2 = max_share/2 (because penalty of rho2 is 1)
 198      */
 199
 200     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
 201     sys_cnst->unshare(); // FATPIPE
 202     lmm::Variable* rho_1 = Sys->variable_new(nullptr, 1);
 203     lmm::Variable* rho_2 = Sys->variable_new(nullptr, 1);
 204
 205     Sys->expand(sys_cnst, rho_1, 1);
 206     Sys->expand(sys_cnst, rho_2, 2);
 207     Sys->solve();
 208
 209     REQUIRE(double_equals(rho_1->get_value(), 5, sg_maxmin_precision));
 210     REQUIRE(double_equals(rho_2->get_value(), 5, sg_maxmin_precision));
 211   }
 212
 213   SECTION("Consumption weight + variable penalty")
 214   {
 215
 216     /*
 217      * Resource proportionality between variable is kept but
 218      * constraint bound can be violated
 219      *
 220      * In details:
 221      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
 222      *   o consumption_weight: a1=1 ; a2=2
 223      *   o sharing_penalty:    p1=1 ; p2=2
 224      *
 225      * Expectations
 226      *   o rho1 = 2 * rho2 (because rho2 has twice the penalty)
 227      *   o rho1 + 2*rho2 can be greater than C
 228      *   o rho1 <= C and 2*rho2 <= C
 229      */
 230
 231     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
 232     sys_cnst->unshare();
 233     lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 1);
 234     lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 2);
 235
 236     Sys->expand(sys_cnst, sys_var_1, 1);
 237     Sys->expand(sys_cnst, sys_var_2, 2);
 238     Sys->solve();
 239
 240     REQUIRE(double_equals(sys_var_1->get_value(), 10, sg_maxmin_precision));
 241     REQUIRE(double_equals(sys_var_2->get_value(), 5, sg_maxmin_precision));
 242   }
 243
 244   SECTION("Multiple constraints systems")
 245   {
 246
 247     /*
 248      * Multiple constraint systems can be solved with shared variables
 249      * on unshair constraints.
 250      *
 251      * In details:
 252      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C1
 253      *              a3 * p1 * \rho1  +  a4 * p3 * \rho3 < C2
 254      *   o consumption_weight: a1=1 ; a2=2 ; a3=2 ; a4=1
 255      *   o sharing_penalty:    p1=1 ; p2=2 ; p3=1
 256      *   o load: load_1=C1/max(p1/a1,p2/a2)=20 ; load_2=C2/max(a3/p1,a4/p3)=30
 257      *
 258      * Expectations
 259      *   o First constraint will be solve first (because load_1 < load_2)
 260      *   o Second constraint load will not be updated !
 261      *   o Each constraint should satisfy max(a_i * rho_i) <= C_r
 262      */
 263
 264     lmm::Constraint* sys_cnst_1 = Sys->constraint_new(nullptr, 10);
 265     lmm::Constraint* sys_cnst_2 = Sys->constraint_new(nullptr, 60);
 266     sys_cnst_1->unshare(); // FATPIPE
 267     sys_cnst_2->unshare();
 268
 269     lmm::Variable* rho_1 = Sys->variable_new(nullptr, 1, -1, 2);
 270     lmm::Variable* rho_2 = Sys->variable_new(nullptr, 2, -1, 1);
 271     lmm::Variable* rho_3 = Sys->variable_new(nullptr, 1, -1, 1);
 272
 273     // Constraint 1
 274     Sys->expand(sys_cnst_1, rho_1, 1);
 275     Sys->expand(sys_cnst_1, rho_2, 2);
 276
 277     // Constraint 2
 278     Sys->expand(sys_cnst_2, rho_1, 2);
 279     Sys->expand(sys_cnst_2, rho_3, 1);
 280     Sys->solve();
 281
 282     double rho_1_share = 10; // Start by solving the first constraint (results is the same as previous tests)
 283     REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_maxmin_precision));
 284     REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_maxmin_precision));
 285     REQUIRE(double_equals(rho_3->get_value(), 60, sg_maxmin_precision));
 286   }
 287
 288   Sys->variable_free_all();
 289   delete Sys;
 290 }