teshsuite/surf/lmm_usage/lmm_solve.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 weight")
  73   {
  74     /*
  75      * Strange system under consideration:
  76      * 56\times\rho_1^{74} + 21\times\rho_2^{6} + 2\times\rho_3^{2} \le 123
  77      * Expectations:
  78      *  - This test combine variable weight and consumption weight
  79      *  - Thus, we expect that \rho_j=\frac{\frac{10}{\sum{\frac{a_i}{w_i}}}}{w_j}
  80      */
  81
  82     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 123);
  83     lmm::Variable* sys_var_1  = Sys->variable_new(nullptr, 56);
  84     lmm::Variable* sys_var_2  = Sys->variable_new(nullptr, 21);
  85     lmm::Variable* sys_var_3  = Sys->variable_new(nullptr, 3);
  86
  87     Sys->expand(sys_cnst, sys_var_1, 74);
  88     Sys->expand(sys_cnst, sys_var_2, 6);
  89     Sys->expand(sys_cnst, sys_var_3, 2);
  90     Sys->solve();
  91
  92     REQUIRE(double_equals(sys_var_1->get_value(), 0.9659686, sg_maxmin_precision));
  93     REQUIRE(double_equals(sys_var_2->get_value(), 2.575916, sg_maxmin_precision));
  94     REQUIRE(double_equals(sys_var_3->get_value(), 18.03141, sg_maxmin_precision));
  95   }
  96
  97   Sys->variable_free_all();
  98   delete Sys;
  99 }
 100
 101 TEST_CASE("kernel::lmm Multiple constraint shared systems", "[kernel-lmm-shared-multiple-sys]")
 102 {
 103   lmm::System* Sys = lmm::make_new_maxmin_system(false);
 104
 105   SECTION("3 Constraints system")
 106   {
 107
 108     /*
 109      * System under consideration:
 110      * 4\times\rho_1^{5.1} + 2.6\times\rho_2^{7} + 1.2\times\rho_3^{8.5} \le 14.6 \\
 111      * 5\times\rho_4^{6.2} + 2\times\rho_2^{7}   + 4.1\times\rho_3^{8.5} \le 40.7 \\
 112      * 6\times\rho_5^1                                                   \le 7
 113      * Expectation:
 114      *  - Order of inequation solving: 3, 1 and 2
 115      *  - Variable values are fixed using: \rho_j=\frac{\frac{C_r}{\sum{\frac{a_{r,i}}{w_i}}}}{w_j}
 116      */
 117
 118     lmm::Constraint* sys_cnst_1 = Sys->constraint_new(nullptr, 14.6);
 119     lmm::Constraint* sys_cnst_2 = Sys->constraint_new(nullptr, 10.7);
 120     lmm::Constraint* sys_cnst_3 = Sys->constraint_new(nullptr, 7);
 121
 122     lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 5.1, 0.0, 1);
 123     lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 7, 0.0, 2);
 124     lmm::Variable* sys_var_3 = Sys->variable_new(nullptr, 8.5, 0.0, 2);
 125     lmm::Variable* sys_var_4 = Sys->variable_new(nullptr, 6.2, 0.0, 1);
 126     lmm::Variable* sys_var_5 = Sys->variable_new(nullptr, 1, 0.0, 1);
 127
 128     // Constraint 1
 129     Sys->expand(sys_cnst_1, sys_var_1, 4);
 130     Sys->expand(sys_cnst_1, sys_var_2, 2.6);
 131     Sys->expand(sys_cnst_1, sys_var_3, 1.2);
 132     // Constraint 2
 133     Sys->expand(sys_cnst_2, sys_var_4, 5);
 134     Sys->expand(sys_cnst_2, sys_var_2, 2);
 135     Sys->expand(sys_cnst_2, sys_var_3, 4.1);
 136     // Constraint 3
 137     Sys->expand(sys_cnst_3, sys_var_5, 6);
 138     Sys->solve();
 139
 140     REQUIRE(double_equals(sys_var_1->get_value(), 2.779119, sg_maxmin_precision));
 141     REQUIRE(double_equals(sys_var_2->get_value(), 0.9708181, sg_maxmin_precision));
 142     REQUIRE(double_equals(sys_var_3->get_value(), 0.7994973, sg_maxmin_precision));
 143     REQUIRE(double_equals(sys_var_4->get_value(), 1.096085, sg_maxmin_precision));
 144     REQUIRE(double_equals(sys_var_5->get_value(), 1.166667, sg_maxmin_precision));
 145   }
 146
 147   Sys->variable_free_all();
 148   delete Sys;
 149 }
 150
 151 TEST_CASE("kernel::lmm Single constraint unshared systems", "[kernel-lmm-unshared-single-sys]")
 152 {
 153   lmm::System* Sys = lmm::make_new_maxmin_system(false);
 154
 155   SECTION("Variable weight")
 156   {
 157     /*
 158      * System under consideration:
 159      * 1\times\rho_1^{1} + 1\times\rho_2^{2} + 1\times\rho_3^{3} \le 10
 160      * Expectation:
 161      *  - Variables are fixed using: \rho_j=\frac{\frac{10}{\frac{1}{1}}}{w_j}
 162      */
 163
 164     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
 165     sys_cnst->unshare(); // FATPIPE
 166     lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 1, 0.0, 1);
 167     lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 2, 0.0, 1);
 168     lmm::Variable* sys_var_3 = Sys->variable_new(nullptr, 3, 0.0, 1);
 169
 170     Sys->expand(sys_cnst, sys_var_1, 1);
 171     Sys->expand(sys_cnst, sys_var_2, 1);
 172     Sys->expand(sys_cnst, sys_var_3, 1);
 173     Sys->solve();
 174
 175     REQUIRE(double_equals(sys_var_1->get_value(), 10, sg_maxmin_precision));
 176     REQUIRE(double_equals(sys_var_2->get_value(), 5, sg_maxmin_precision));
 177     REQUIRE(double_equals(sys_var_3->get_value(), 3.333333, sg_maxmin_precision));
 178   }
 179
 180   SECTION("Consumption weight")
 181   {
 182     /*
 183      * System under consideration:
 184      * 1\times\rho_1^{1} + 2\times\rho_2^{1} + 3\times\rho_3^{1} \le 10
 185      * Expectations:
 186      *  - Variables are fixed using: \rho_j=\frac{\frac{10}{\frac{3}{1}}}{w_j}
 187      */
 188
 189     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
 190     sys_cnst->unshare();
 191     lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 1, 0.0, 1);
 192     lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 1, 0.0, 1);
 193     lmm::Variable* sys_var_3 = Sys->variable_new(nullptr, 1, 0.0, 1);
 194
 195     Sys->expand(sys_cnst, sys_var_1, 1);
 196     Sys->expand(sys_cnst, sys_var_2, 2);
 197     Sys->expand(sys_cnst, sys_var_3, 3);
 198     Sys->solve();
 199
 200     REQUIRE(double_equals(sys_var_1->get_value(), 3.333333, sg_maxmin_precision));
 201     REQUIRE(double_equals(sys_var_2->get_value(), 3.333333, sg_maxmin_precision));
 202     REQUIRE(double_equals(sys_var_3->get_value(), 3.333333, sg_maxmin_precision));
 203   }
 204
 205   SECTION("Consumption weight + variable weight")
 206   {
 207     /*
 208      * Strange system under consideration:
 209      * 56\times\rho_1^{74} + 21\times\rho_2^{6} + 2\times\rho_3^{2} \le 123
 210      * Expectation:
 211      *  - Variables are fixed using: \rho_j=\frac{\frac{123}{\frac{74}{56}}}{w_j}
 212      */
 213
 214     lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 123);
 215     sys_cnst->unshare();
 216     lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 56, 0.0, 1);
 217     lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 21, 0.0, 1);
 218     lmm::Variable* sys_var_3 = Sys->variable_new(nullptr, 3, 0.0, 1);
 219
 220     Sys->expand(sys_cnst, sys_var_1, 74);
 221     Sys->expand(sys_cnst, sys_var_2, 6);
 222     Sys->expand(sys_cnst, sys_var_3, 2);
 223     Sys->solve();
 224
 225     REQUIRE(double_equals(sys_var_1->get_value(), 1.662162, sg_maxmin_precision));
 226     REQUIRE(double_equals(sys_var_2->get_value(), 4.432432, sg_maxmin_precision));
 227     REQUIRE(double_equals(sys_var_3->get_value(), 31.02703, sg_maxmin_precision));
 228   }
 229
 230   Sys->variable_free_all();
 231   delete Sys;
 232 }
 233
 234 TEST_CASE("kernel::lmm Multiple constraint unshared systems", "[kernel-lmm-unshared-multiple-sys]")
 235 {
 236   lmm::System* Sys = lmm::make_new_maxmin_system(false);
 237
 238   SECTION("3 Constraints system")
 239   {
 240
 241     /*
 242      * System under consideration:
 243      * 4\times\rho_1^{5.1} + 2.6\times\rho_2^{7} + 1.2\times\rho_3^{8.5} \le 14.6 \\
 244      * 5\times\rho_4^{6.2} + 2\times\rho_2^{7}   + 4.1\times\rho_3^{8.5} \le 40.7 \\
 245      * 6\times\rho_5^1                                                   \le 7
 246      * Expectations:
 247      *  - Variable are fixed using: \rho_j=\frac{\frac{C_r}{max\left(\frac{a_{r},i}{w_i}\right)}}{w_j}
 248      *  - The order of inequation solving is expected to be: 3, 2 and 1
 249      */
 250
 251     lmm::Constraint* sys_cnst_1 = Sys->constraint_new(nullptr, 14.6);
 252     sys_cnst_1->unshare();
 253     lmm::Constraint* sys_cnst_2 = Sys->constraint_new(nullptr, 10.7);
 254     sys_cnst_2->unshare();
 255     lmm::Constraint* sys_cnst_3 = Sys->constraint_new(nullptr, 7);
 256     sys_cnst_3->unshare();
 257
 258     lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 5.1, 0.0, 1);
 259     lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 7, 0.0, 2);
 260     lmm::Variable* sys_var_3 = Sys->variable_new(nullptr, 8.5, 0.0, 2);
 261     lmm::Variable* sys_var_4 = Sys->variable_new(nullptr, 6.2, 0.0, 1);
 262     lmm::Variable* sys_var_5 = Sys->variable_new(nullptr, 1, 0.0, 1);
 263
 264     // Constraint 1
 265     Sys->expand(sys_cnst_1, sys_var_1, 4);
 266     Sys->expand(sys_cnst_1, sys_var_2, 2.6);
 267     Sys->expand(sys_cnst_1, sys_var_3, 1.2);
 268     // Constraint 2
 269     Sys->expand(sys_cnst_2, sys_var_4, 5);
 270     Sys->expand(sys_cnst_2, sys_var_2, 2);
 271     Sys->expand(sys_cnst_2, sys_var_3, 4.1);
 272     // Constraint 3
 273     Sys->expand(sys_cnst_3, sys_var_5, 6);
 274     Sys->solve();
 275
 276     REQUIRE(double_equals(sys_var_1->get_value(), 3.65, sg_maxmin_precision));
 277     REQUIRE(double_equals(sys_var_2->get_value(), 1.895429, sg_maxmin_precision));
 278     REQUIRE(double_equals(sys_var_3->get_value(), 1.560941, sg_maxmin_precision));
 279     REQUIRE(double_equals(sys_var_4->get_value(), 2.14, sg_maxmin_precision));
 280     REQUIRE(double_equals(sys_var_5->get_value(), 1.166667, sg_maxmin_precision));
 281   }
 282
 283   Sys->variable_free_all();
 284   delete Sys;
 285 }