src/kernel/lmm/bmf_test.cpp

   1 /* Copyright (c) 2019-2022. 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/bmf.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::bmf Basic tests", "[kernel-bmf-basic]")
  14 {
  15   lmm::BmfSystem Sys(false);
  16   xbt_log_control_set("ker_bmf.thres:debug");
  17
  18   SECTION("Single flow")
  19   {
  20     /*
  21      * A single variable using a single resource
  22      *
  23      * In details:
  24      *   o System:  a1 * p1 * \rho1 < C
  25      *   o consumption_weight: a1=1
  26      *   o sharing_penalty:    p1=1
  27      *
  28      * Expectations
  29      *   o rho1 = C
  30      */
  31
  32     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
  33     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
  34
  35     Sys.expand(sys_cnst, rho_1, 1);
  36     Sys.solve();
  37
  38     REQUIRE(double_equals(rho_1->get_value(), 3, sg_maxmin_precision));
  39   }
  40
  41   SECTION("Two flows")
  42   {
  43     /*
  44      * Two flows sharing a single resource
  45      *
  46      * In details:
  47      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
  48      *   o consumption_weight: a1=1 ; a2=10
  49      *   o sharing_penalty:    p1=1 ; p2=1
  50      *
  51      * Expectations
  52      *   o a1*rho1 = C/2
  53      *   o a2*rho2 = C/2
  54      */
  55
  56     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
  57     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
  58     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 1);
  59
  60     Sys.expand(sys_cnst, rho_1, 1);
  61     Sys.expand(sys_cnst, rho_2, 10);
  62     Sys.solve();
  63
  64     REQUIRE(double_equals(rho_1->get_value(), 3.0 / 2.0, sg_maxmin_precision));
  65     REQUIRE(double_equals(rho_2->get_value(), (3.0 / 2.0) / 10.0, sg_maxmin_precision));
  66   }
  67
  68   SECTION("Disable variable doesn't count")
  69   {
  70     /*
  71      * Two flows sharing a single resource, but only disabled
  72      *
  73      * In details:
  74      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
  75      *   o consumption_weight: a1=1 ; a2=10
  76      *   o sharing_penalty:    p1=1 ; p2=0
  77      *
  78      * Expectations
  79      *   o a1*rho1 = C
  80      */
  81
  82     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
  83     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
  84     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 0);
  85
  86     Sys.expand(sys_cnst, rho_1, 1);
  87     Sys.expand(sys_cnst, rho_2, 10);
  88     Sys.solve();
  89
  90     REQUIRE(double_equals(rho_1->get_value(), 3.0, sg_maxmin_precision));
  91     REQUIRE(double_equals(rho_2->get_value(), 0.0, sg_maxmin_precision));
  92   }
  93
  94   SECTION("No consumption variable")
  95   {
  96     /*
  97      * An empty variable, no consumption, just assure it receives something
  98      *
  99      *   o System:  a1 * p1 * \rho1 < C
 100      *   o consumption_weight: a1=0
 101      *   o sharing_penalty:    p1=1
 102      *
 103      * Expectations
 104      *   o rho1 > 0
 105      */
 106
 107     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
 108     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
 109     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 0);
 110
 111     Sys.expand(sys_cnst, rho_1, 1);
 112     Sys.expand(sys_cnst, rho_2, 10);
 113     Sys.solve();
 114
 115     REQUIRE(double_positive(rho_1->get_value(), sg_maxmin_precision));
 116   }
 117
 118   Sys.variable_free_all();
 119 }
 120
 121 TEST_CASE("kernel::bmf Advanced tests", "[kernel-bmf-advanced]")
 122 {
 123   lmm::BmfSystem Sys(false);
 124   xbt_log_control_set("ker_bmf.thres:debug");
 125
 126   SECTION("2 flows, 2 resources")
 127   {
 128     /*
 129      * Two flows sharing 2 resources with opposite requirements
 130      *
 131      * In details:
 132      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
 133      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C2
 134      *   o C1 == C2
 135      *   o consumption_weight: a11=1, a12=10, a21=10, a22=1
 136      *   o sharing_penalty:    p1=1, p2=1
 137      *
 138      * Expectations
 139      *   o rho1 = rho2 = C/11
 140
 141      * Matrices:
 142      * [1 10] * [rho1 rho2] = [1]
 143      * [10 1]                 [1]
 144      */
 145
 146     lmm::Constraint* sys_cnst  = Sys.constraint_new(nullptr, 1);
 147     lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
 148     lmm::Variable* rho_1       = Sys.variable_new(nullptr, 1, -1, 2);
 149     lmm::Variable* rho_2       = Sys.variable_new(nullptr, 1, -1, 2);
 150
 151     Sys.expand(sys_cnst, rho_1, 1);
 152     Sys.expand(sys_cnst2, rho_1, 10);
 153     Sys.expand(sys_cnst, rho_2, 10);
 154     Sys.expand(sys_cnst2, rho_2, 1);
 155     Sys.solve();
 156
 157     REQUIRE(double_equals(rho_1->get_value(), 1.0 / 11.0, sg_maxmin_precision));
 158     REQUIRE(double_equals(rho_2->get_value(), 1.0 / 11.0, sg_maxmin_precision));
 159   }
 160
 161   SECTION("BMF paper example")
 162   {
 163     /*
 164      * 3 flows sharing 3 resources
 165      *
 166      * In details:
 167      * [1  1  1/2] * [rho1 rho2 rho3] = [1]
 168      * [1 1/2  1 ]                      [1]
 169      * [1 3/4 3/4]                      [1]
 170      *
 171      * Expectations (several possible BMF allocations, our algorithm return this)
 172      *   o rho1 = rho2 = rho3 = 2/5
 173      */
 174
 175     lmm::Constraint* sys_cnst  = Sys.constraint_new(nullptr, 1);
 176     lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
 177     lmm::Constraint* sys_cnst3 = Sys.constraint_new(nullptr, 1);
 178     lmm::Variable* rho_1       = Sys.variable_new(nullptr, 1, -1, 3);
 179     lmm::Variable* rho_2       = Sys.variable_new(nullptr, 1, -1, 3);
 180     lmm::Variable* rho_3       = Sys.variable_new(nullptr, 1, -1, 3);
 181
 182     Sys.expand(sys_cnst3, rho_1, 1.0); // put this expand first to force a singular A' matrix
 183     Sys.expand(sys_cnst, rho_1, 1.0);
 184     Sys.expand(sys_cnst2, rho_1, 1.0);
 185     Sys.expand(sys_cnst, rho_2, 1.0);
 186     Sys.expand(sys_cnst2, rho_2, 1.0 / 2.0);
 187     Sys.expand(sys_cnst3, rho_2, 3.0 / 4.0);
 188     Sys.expand(sys_cnst, rho_3, 1.0 / 2.0);
 189     Sys.expand(sys_cnst2, rho_3, 1.0);
 190     Sys.expand(sys_cnst3, rho_3, 3.0 / 4.0);
 191     Sys.solve();
 192
 193     REQUIRE(double_equals(rho_1->get_value(), 1.0 / 3.0, sg_maxmin_precision));
 194     REQUIRE(double_equals(rho_2->get_value(), 4.0 / 9.0, sg_maxmin_precision));
 195     REQUIRE(double_equals(rho_3->get_value(), 4.0 / 9.0, sg_maxmin_precision));
 196   }
 197
 198   Sys.variable_free_all();
 199 }
 200
 201 TEST_CASE("kernel::bmf Subflows", "[kernel-bmf-subflow]")
 202 {
 203   lmm::BmfSystem Sys(false);
 204   xbt_log_control_set("ker_bmf.thres:debug");
 205
 206   SECTION("2 subflows and 1 resource")
 207   {
 208     /*
 209      * 2 identical flows composed of 2 subflows
 210      *
 211      * They must receive the same share and use same amount of resources
 212      *
 213      * In details:
 214      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
 215      *   o consumption_weight: a11=5, a12=7, a2=7, a2=5
 216      *   o sharing_penalty:    p1=1, p2=1
 217      *
 218      * Expectations
 219      *   o rho1 = rho2 = (C/2)/12
 220
 221      * Matrices:
 222      * [12 12] * [rho1 rho2] = [1]
 223      * [12 12]                 [0]
 224      */
 225
 226     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 5);
 227     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
 228     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 1);
 229
 230     Sys.expand_add(sys_cnst, rho_1, 5);
 231     Sys.expand_add(sys_cnst, rho_1, 7);
 232     Sys.expand_add(sys_cnst, rho_2, 7);
 233     Sys.expand_add(sys_cnst, rho_2, 5);
 234     Sys.solve();
 235
 236     REQUIRE(double_equals(rho_1->get_value(), 5.0 / 24.0, sg_maxmin_precision));
 237     REQUIRE(double_equals(rho_2->get_value(), 5.0 / 24.0, sg_maxmin_precision));
 238   }
 239
 240   SECTION("1 subflows, 1 flow and 1 resource")
 241   {
 242     /*
 243      * 2 flows, 1 resource
 244      * 1 flow composed of 2 subflows
 245      *
 246      * Same share/rho, but subflow uses 50% more resources since it has a second connection/subflow
 247      *
 248      * In details:
 249      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
 250      *   o consumption_weight: a11=10, a12=5 a2=10
 251      *   o sharing_penalty:    p1=1, p2=1
 252      *
 253      * Expectations
 254      *   o rho1 = (C/25)
 255      *   o rho2 = (C/25)
 256
 257      * Matrices:
 258      * [15 10] * [rho1 rho2] = [1]
 259      * [10 10]                 [0]
 260      */
 261
 262     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 5);
 263     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
 264     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 1);
 265
 266     Sys.expand_add(sys_cnst, rho_1, 10);
 267     Sys.expand_add(sys_cnst, rho_1, 5);
 268     Sys.expand(sys_cnst, rho_2, 10);
 269     Sys.solve();
 270
 271     REQUIRE(double_equals(rho_1->get_value(), (5.0 / 25.0), sg_maxmin_precision));
 272     REQUIRE(double_equals(rho_2->get_value(), (5.0 / 25.0), sg_maxmin_precision));
 273     REQUIRE(double_equals(15 * rho_1->get_value(), 10 * rho_2->get_value() * 3 / 2, sg_maxmin_precision));
 274   }
 275
 276   SECTION("1 subflows using 2 resources: different max for each resource")
 277   {
 278     /*
 279      * Test condition that we may have different max for different resources
 280      *
 281      * In details:
 282      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
 283      *   o consumption_weight: a11=1, a12=1, a2=1
 284      *   o consumption_weight: a21=1/2, a12=1/2 a2=3/2
 285      *   o sharing_penalty:    p1=1, p2=1
 286      *
 287      * Expectations
 288      *   o rho1 = (C1/3)
 289      *   o rho2 = (C1/3)
 290
 291      * Matrices:
 292      * [2 1 ] * [rho1 rho2] = [1]
 293      * [1 -1]                 [0]
 294      */
 295
 296     lmm::Constraint* sys_cnst  = Sys.constraint_new(nullptr, 1);
 297     lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
 298     lmm::Variable* rho_1       = Sys.variable_new(nullptr, 1, -1, 2);
 299     lmm::Variable* rho_2       = Sys.variable_new(nullptr, 1, -1, 2);
 300
 301     Sys.expand_add(sys_cnst, rho_1, 1.0);
 302     Sys.expand_add(sys_cnst, rho_1, 1.0);
 303     Sys.expand(sys_cnst, rho_2, 1);
 304     Sys.expand_add(sys_cnst2, rho_1, 1.0 / 2.0);
 305     Sys.expand_add(sys_cnst2, rho_1, 1.0 / 2.0);
 306     Sys.expand(sys_cnst2, rho_2, 3.0 / 2.0);
 307     Sys.solve();
 308
 309     REQUIRE(double_equals(rho_1->get_value(), (1.0 / 3.0), sg_maxmin_precision));
 310     REQUIRE(double_equals(rho_2->get_value(), (1.0 / 3.0), sg_maxmin_precision));
 311   }
 312
 313   Sys.variable_free_all();
 314 }