src/kernel/lmm/bmf_test.cpp

   1 /* Copyright (c) 2019-2023. 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 "simgrid/math_utils.h"
   7 #include "src/include/catch.hpp"
   8 #include "src/kernel/lmm/bmf.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
  17   SECTION("Single flow")
  18   {
  19     /*
  20      * A single variable using a single resource
  21      *
  22      * In details:
  23      *   o System:  a1 * p1 * \rho1 < C
  24      *   o consumption_weight: a1=1
  25      *   o sharing_penalty:    p1=1
  26      *
  27      * Expectations
  28      *   o rho1 = C
  29      */
  30
  31     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
  32     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
  33
  34     Sys.expand(sys_cnst, rho_1, 1);
  35     Sys.solve();
  36
  37     REQUIRE(double_equals(rho_1->get_value(), 3, sg_precision_workamount));
  38   }
  39
  40   SECTION("Two flows")
  41   {
  42     /*
  43      * Two flows sharing a single resource
  44      *
  45      * In details:
  46      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
  47      *   o consumption_weight: a1=1 ; a2=10
  48      *   o sharing_penalty:    p1=1 ; p2=1
  49      *
  50      * Expectations
  51      *   o a1*rho1 = C/2
  52      *   o a2*rho2 = C/2
  53      */
  54
  55     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
  56     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
  57     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 1);
  58
  59     Sys.expand(sys_cnst, rho_1, 1);
  60     Sys.expand(sys_cnst, rho_2, 10);
  61     Sys.solve();
  62
  63     REQUIRE(double_equals(rho_1->get_value(), 3.0 / 2.0, sg_precision_workamount));
  64     REQUIRE(double_equals(rho_2->get_value(), (3.0 / 2.0) / 10.0, sg_precision_workamount));
  65   }
  66
  67   SECTION("Variable penalty/priority")
  68   {
  69     /*
  70      * A variable with twice the penalty gets half of the share
  71      *
  72      * In details:
  73      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
  74      *   o consumption_weight: a1=1 ; a2=1
  75      *   o sharing_penalty:    p1=1 ; p2=2
  76      *
  77      * Expectations
  78      *   o rho1 = 2* rho2 (because rho2 has twice the penalty)
  79      *   o rho1 + rho2 = C (because all weights are 1)
  80      */
  81
  82     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
  83     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
  84     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 2);
  85
  86     Sys.expand(sys_cnst, rho_1, 1);
  87     Sys.expand(sys_cnst, rho_2, 1);
  88     Sys.solve();
  89
  90     REQUIRE(double_equals(rho_1->get_value(), 2.0 / 3.0, sg_precision_workamount));
  91     REQUIRE(double_equals(rho_2->get_value(), 1.0 / 3.0, sg_precision_workamount));
  92   }
  93
  94   SECTION("Disable variable doesn't count")
  95   {
  96     /*
  97      * Two flows sharing a single resource, but one is disabled
  98      *
  99      * In details:
 100      *   o System:  a1 * p1 * \rho1  +  a2 * p2 * \rho2 < C
 101      *   o consumption_weight: a1=1 ; a2=10
 102      *   o sharing_penalty:    p1=1 ; p2=0
 103      *
 104      * Expectations
 105      *   o a1*rho1 = C
 106      */
 107
 108     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
 109     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
 110     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 0);
 111
 112     Sys.expand(sys_cnst, rho_1, 1);
 113     Sys.expand(sys_cnst, rho_2, 10);
 114     Sys.solve();
 115
 116     REQUIRE(double_equals(rho_1->get_value(), 1.0, sg_precision_workamount));
 117     REQUIRE(double_equals(rho_2->get_value(), 0.0, sg_precision_workamount));
 118   }
 119
 120   SECTION("No consumption variable")
 121   {
 122     /*
 123      * An empty variable, no consumption, just assure it receives something
 124      *
 125      *   o System:  a1 * p1 * \rho1 < C
 126      *   o consumption_weight: a1=0
 127      *   o sharing_penalty:    p1=1
 128      *
 129      * Expectations
 130      *   o rho1 > 0
 131      */
 132
 133     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
 134     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
 135     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 0);
 136
 137     Sys.expand(sys_cnst, rho_1, 1);
 138     Sys.expand(sys_cnst, rho_2, 10);
 139     Sys.solve();
 140
 141     REQUIRE(double_positive(rho_1->get_value(), sg_precision_workamount));
 142   }
 143
 144   SECTION("Bounded variable")
 145   {
 146     /*
 147      * Assures a player receives the min(bound, share) if it's bounded
 148      *
 149      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
 150      *   o bounds: b1=0.1, b2=-1
 151      *   o consumption_weight: a1=1, a2=1
 152      *   o sharing_penalty:    p1=1, p2=1
 153      *
 154      * Expectations
 155      *   o rho1 = .1
 156      *   o rho2 = .8
 157      */
 158
 159     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
 160     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1, .1);
 161     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 1);
 162
 163     Sys.expand(sys_cnst, rho_1, 2);
 164     Sys.expand(sys_cnst, rho_2, 1);
 165     Sys.solve();
 166     REQUIRE(double_equals(rho_1->get_value(), .1, sg_precision_workamount));
 167     REQUIRE(double_equals(rho_2->get_value(), .8, sg_precision_workamount));
 168   }
 169
 170   SECTION("Fatpipe")
 171   {
 172     /*
 173      * Two flows using a fatpipe resource
 174      *
 175      * In details:
 176      *   o System:  a1 * p1 * \rho1 < C and  a2 * p2 * \rho2 < C
 177      *   o consumption_weight: a1=1 ; a2=1
 178      *   o sharing_penalty:    p1=1 ; p2=1
 179      *
 180      * Expectations
 181      *   o a1*rho1 = C
 182      *   o a2*rho2 = C
 183      */
 184
 185     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
 186     sys_cnst->set_sharing_policy(lmm::Constraint::SharingPolicy::FATPIPE, {});
 187     lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
 188     lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
 189
 190     Sys.expand(sys_cnst, rho_1, 1);
 191     Sys.expand(sys_cnst, rho_2, 1);
 192     Sys.solve();
 193
 194     REQUIRE(double_equals(rho_1->get_value(), 3.0, sg_precision_workamount));
 195     REQUIRE(double_equals(rho_2->get_value(), 3.0, sg_precision_workamount));
 196   }
 197
 198   SECTION("(un)Bounded variable")
 199   {
 200     /*
 201      * Assures a player receives the share if bound is greater than share
 202      *
 203      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
 204      *   o bounds: b1=1, b2=-1
 205      *   o consumption_weight: a1=1, a2=1
 206      *   o sharing_penalty:    p1=1, p2=1
 207      *
 208      * Expectations
 209      *   o rho1 = .5
 210      *   o rho2 = .5
 211      */
 212
 213     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
 214     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1, 1);
 215     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 1);
 216
 217     Sys.expand(sys_cnst, rho_1, 1);
 218     Sys.expand(sys_cnst, rho_2, 1);
 219     Sys.solve();
 220     REQUIRE(double_equals(rho_1->get_value(), .5, sg_precision_workamount));
 221     REQUIRE(double_equals(rho_2->get_value(), .5, sg_precision_workamount));
 222   }
 223
 224   SECTION("Dynamic bounds")
 225   {
 226     /*
 227      * Resource bound is modified by user callback and shares are adapted accordingly
 228      *
 229      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
 230      *   o consumption_weight: a1=1, a2=1
 231      *   o sharing_penalty:    p1=1, p2=1
 232      *
 233      * Expectations
 234      *   o rho1 = .5 and .25
 235      *   o rho2 =  - and .25
 236      */
 237
 238     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
 239     sys_cnst->set_sharing_policy(lmm::Constraint::SharingPolicy::NONLINEAR,
 240                                  [](double bound, int n) { return bound / n; });
 241     // alone, full capacity
 242     lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
 243     Sys.expand(sys_cnst, rho_1, 1);
 244     Sys.solve();
 245     REQUIRE(double_equals(rho_1->get_value(), 1, sg_precision_workamount));
 246
 247     // add another variable, half initial capacity
 248     lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
 249     Sys.expand(sys_cnst, rho_2, 1);
 250     Sys.solve();
 251
 252     REQUIRE(double_equals(rho_1->get_value(), .25, sg_precision_workamount));
 253     REQUIRE(double_equals(rho_2->get_value(), .25, sg_precision_workamount));
 254   }
 255
 256   Sys.variable_free_all();
 257 }
 258
 259 TEST_CASE("kernel::bmf Advanced tests", "[kernel-bmf-advanced]")
 260 {
 261   lmm::BmfSystem Sys(false);
 262
 263   SECTION("2 flows, 2 resources")
 264   {
 265     /*
 266      * Two flows sharing 2 resources with opposite requirements
 267      *
 268      * In details:
 269      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
 270      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C2
 271      *   o C1 == C2
 272      *   o consumption_weight: a11=1, a12=10, a21=10, a22=1
 273      *   o sharing_penalty:    p1=1, p2=1
 274      *
 275      * Expectations
 276      *   o rho1 = rho2 = C/11
 277
 278      * Matrices:
 279      * [1 10] * [rho1 rho2] = [1]
 280      * [10 1]                 [1]
 281      */
 282
 283     lmm::Constraint* sys_cnst  = Sys.constraint_new(nullptr, 1);
 284     lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
 285     lmm::Variable* rho_1       = Sys.variable_new(nullptr, 1, -1, 2);
 286     lmm::Variable* rho_2       = Sys.variable_new(nullptr, 1, -1, 2);
 287
 288     Sys.expand(sys_cnst, rho_1, 1);
 289     Sys.expand(sys_cnst2, rho_1, 10);
 290     Sys.expand(sys_cnst, rho_2, 10);
 291     Sys.expand(sys_cnst2, rho_2, 1);
 292     Sys.solve();
 293
 294     REQUIRE(double_equals(rho_1->get_value(), 1.0 / 11.0, sg_precision_workamount));
 295     REQUIRE(double_equals(rho_2->get_value(), 1.0 / 11.0, sg_precision_workamount));
 296   }
 297
 298   SECTION("BMF paper example")
 299   {
 300     /*
 301      * 3 flows sharing 3 resources
 302      *
 303      * In details:
 304      * [1  1  1/2] * [rho1 rho2 rho3] = [1]
 305      * [1 1/2  1 ]                      [1]
 306      * [1 3/4 3/4]                      [1]
 307      *
 308      * Expectations (several possible BMF allocations, our algorithm return this)
 309      *   o rho1 = rho2 = rho3 = 2/5
 310      */
 311
 312     lmm::Constraint* sys_cnst  = Sys.constraint_new(nullptr, 1);
 313     lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
 314     lmm::Constraint* sys_cnst3 = Sys.constraint_new(nullptr, 1);
 315     lmm::Variable* rho_1       = Sys.variable_new(nullptr, 1, -1, 3);
 316     lmm::Variable* rho_2       = Sys.variable_new(nullptr, 1, -1, 3);
 317     lmm::Variable* rho_3       = Sys.variable_new(nullptr, 1, -1, 3);
 318
 319     Sys.expand(sys_cnst3, rho_1, 1.0); // put this expand first to force a singular A' matrix
 320     Sys.expand(sys_cnst, rho_1, 1.0);
 321     Sys.expand(sys_cnst2, rho_1, 1.0);
 322     Sys.expand(sys_cnst, rho_2, 1.0);
 323     Sys.expand(sys_cnst2, rho_2, 1.0 / 2.0);
 324     Sys.expand(sys_cnst3, rho_2, 3.0 / 4.0);
 325     Sys.expand(sys_cnst, rho_3, 1.0 / 2.0);
 326     Sys.expand(sys_cnst2, rho_3, 1.0);
 327     Sys.expand(sys_cnst3, rho_3, 3.0 / 4.0);
 328     Sys.solve();
 329
 330     REQUIRE(double_equals(rho_1->get_value(), 1.0 / 3.0, sg_precision_workamount));
 331     REQUIRE(double_equals(rho_2->get_value(), 4.0 / 9.0, sg_precision_workamount));
 332     REQUIRE(double_equals(rho_3->get_value(), 4.0 / 9.0, sg_precision_workamount));
 333   }
 334
 335   SECTION("IO - example")
 336   {
 337     /*
 338      * Two flows sharing 1 disk
 339      * read, write and readwrite constraint
 340      *
 341      * In details:
 342      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
 343      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C2
 344      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C3
 345      *   o C1 == C2 == C3
 346      *   o consumption_weight: a1=1, a2=1
 347      *   o sharing_penalty:    p1=1, p2=1
 348      *
 349      * Expectations
 350      *   o rho1 = rho2 = C/2
 351
 352      * Matrices:
 353      * [1 10] * [rho1 rho2] = [1]
 354      * [10 1]                 [1]
 355      */
 356
 357     lmm::Constraint* sys_cnst  = Sys.constraint_new(nullptr, 1e6);
 358     lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1e6);
 359     lmm::Constraint* sys_cnst3 = Sys.constraint_new(nullptr, 1e6);
 360     lmm::Variable* rho_1       = Sys.variable_new(nullptr, 1, -1, 3);
 361     lmm::Variable* rho_2       = Sys.variable_new(nullptr, 1, -1, 3);
 362
 363     /* A' and C' matrices are dependent on the order of initialization
 364      * this order is needed to identify a bug in the solver */
 365     Sys.expand(sys_cnst2, rho_2, 1);
 366     Sys.expand(sys_cnst, rho_1, 1);
 367     Sys.expand(sys_cnst3, rho_1, 1);
 368     Sys.expand(sys_cnst3, rho_2, 1);
 369     Sys.solve();
 370
 371     REQUIRE(double_equals(rho_1->get_value(), 1e6 / 2.0, sg_precision_workamount));
 372     REQUIRE(double_equals(rho_2->get_value(), 1e6 / 2.0, sg_precision_workamount));
 373   }
 374
 375   SECTION("Proportional fairness")
 376   {
 377     /*
 378      * 3 flows sharing 2 resources with crosstraffic
 379      *
 380      * Regular max-min would give B/2 for every flow.
 381      * BMF is equivalent to proportional fairness in this case, and give a quite
 382      * different sharing.
 383      *
 384      */
 385
 386     lmm::Constraint* sys_cnst  = Sys.constraint_new(nullptr, 1);
 387     lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
 388     lmm::Variable* rho_1       = Sys.variable_new(nullptr, 1, -1, 2);
 389     lmm::Variable* rho_2       = Sys.variable_new(nullptr, 1, -1, 2);
 390     lmm::Variable* rho_3       = Sys.variable_new(nullptr, 1, -1, 2);
 391
 392     double epsilon = 0.05;
 393     Sys.expand(sys_cnst, rho_1, 1.0);
 394     Sys.expand(sys_cnst2, rho_1, epsilon);
 395     Sys.expand(sys_cnst, rho_2, 1.0);
 396     Sys.expand(sys_cnst2, rho_2, epsilon);
 397     Sys.expand(sys_cnst2, rho_3, 1.0);
 398     Sys.expand(sys_cnst, rho_3, epsilon);
 399     Sys.solve();
 400
 401     REQUIRE(double_equals(rho_1->get_value(), 1.0 / (2.0 + 2 * epsilon), sg_precision_workamount));
 402     REQUIRE(double_equals(rho_2->get_value(), 1.0 / (2.0 + 2 * epsilon), sg_precision_workamount));
 403     REQUIRE(double_equals(rho_3->get_value(), 1.0 / (1.0 + epsilon), sg_precision_workamount));
 404   }
 405
 406   Sys.variable_free_all();
 407 }
 408
 409 TEST_CASE("kernel::bmf Subflows", "[kernel-bmf-subflow]")
 410 {
 411   lmm::BmfSystem Sys(false);
 412
 413   SECTION("2 subflows and 1 resource")
 414   {
 415     /*
 416      * 2 identical flows composed of 2 subflows
 417      *
 418      * They must receive the same share and use same amount of resources
 419      *
 420      * In details:
 421      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
 422      *   o consumption_weight: a11=5, a12=7, a2=7, a2=5
 423      *   o sharing_penalty:    p1=1, p2=1
 424      *
 425      * Expectations
 426      *   o rho1 = rho2 = (C/2)/12
 427
 428      * Matrices:
 429      * [12 12] * [rho1 rho2] = [1]
 430      * [12 12]                 [0]
 431      */
 432
 433     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 5);
 434     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
 435     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 1);
 436
 437     Sys.expand(sys_cnst, rho_1, 5);
 438     Sys.expand(sys_cnst, rho_1, 7);
 439     Sys.expand(sys_cnst, rho_2, 7);
 440     Sys.expand(sys_cnst, rho_2, 5);
 441     Sys.solve();
 442
 443     REQUIRE(double_equals(rho_1->get_value(), 5.0 / 24.0, sg_precision_workamount));
 444     REQUIRE(double_equals(rho_2->get_value(), 5.0 / 24.0, sg_precision_workamount));
 445   }
 446
 447   SECTION("1 subflows, 1 flow and 1 resource")
 448   {
 449     /*
 450      * 2 flows, 1 resource
 451      * 1 flow composed of 2 subflows
 452      *
 453      * Same share/rho, but subflow uses 50% more resources since it has a second connection/subflow
 454      *
 455      * In details:
 456      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
 457      *   o consumption_weight: a11=10, a12=5 a2=10
 458      *   o sharing_penalty:    p1=1, p2=1
 459      *
 460      * Expectations
 461      *   o rho1 = (C/25)
 462      *   o rho2 = (C/25)
 463
 464      * Matrices:
 465      * [15 10] * [rho1 rho2] = [1]
 466      * [10 10]                 [0]
 467      */
 468
 469     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 5);
 470     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1);
 471     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 1);
 472
 473     Sys.expand(sys_cnst, rho_1, 10);
 474     Sys.expand(sys_cnst, rho_1, 5);
 475     Sys.expand(sys_cnst, rho_2, 10);
 476     Sys.solve();
 477
 478     REQUIRE(double_equals(rho_1->get_value(), (5.0 / 25.0), sg_precision_workamount));
 479     REQUIRE(double_equals(rho_2->get_value(), (5.0 / 25.0), sg_precision_workamount));
 480     REQUIRE(double_equals(15 * rho_1->get_value(), 10 * rho_2->get_value() * 3 / 2, sg_precision_workamount));
 481   }
 482
 483   SECTION("1 subflows using 2 resources: different max for each resource")
 484   {
 485     /*
 486      * Test condition that we may have different max for different resources
 487      *
 488      * In details:
 489      *   o System:  a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
 490      *   o consumption_weight: a11=1, a12=1, a2=1
 491      *   o consumption_weight: a21=1/2, a12=1/2 a2=3/2
 492      *   o sharing_penalty:    p1=1, p2=1
 493      *
 494      * Expectations
 495      *   o rho1 = (C1/3)
 496      *   o rho2 = (C1/3)
 497
 498      * Matrices:
 499      * [2 1 ] * [rho1 rho2] = [1]
 500      * [1 -1]                 [0]
 501      */
 502
 503     lmm::Constraint* sys_cnst  = Sys.constraint_new(nullptr, 1);
 504     lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
 505     lmm::Variable* rho_1       = Sys.variable_new(nullptr, 1, -1, 2);
 506     lmm::Variable* rho_2       = Sys.variable_new(nullptr, 1, -1, 2);
 507
 508     Sys.expand(sys_cnst, rho_1, 1.0);
 509     Sys.expand(sys_cnst, rho_1, 1.0);
 510     Sys.expand(sys_cnst, rho_2, 1);
 511     Sys.expand(sys_cnst2, rho_1, 1.0 / 2.0);
 512     Sys.expand(sys_cnst2, rho_1, 1.0 / 2.0);
 513     Sys.expand(sys_cnst2, rho_2, 3.0 / 2.0);
 514     Sys.solve();
 515
 516     REQUIRE(double_equals(rho_1->get_value(), (1.0 / 3.0), sg_precision_workamount));
 517     REQUIRE(double_equals(rho_2->get_value(), (1.0 / 3.0), sg_precision_workamount));
 518   }
 519
 520   Sys.variable_free_all();
 521 }
 522
 523 TEST_CASE("kernel::bmf Loop", "[kernel-bmf-loop]")
 524 {
 525   lmm::BmfSystem Sys(false);
 526
 527   SECTION("Initial allocation loops")
 528   {
 529     /*
 530      * Complex matrix whose initial allocation loops and is unable
 531      * to stabilize after 10 iterations.
 532      *
 533      * The algorithm needs to restart from another point
 534      */
 535
 536     std::vector<double> C              = {1.0, 1.0, 1.0, 1.0, 1.0};
 537     std::vector<std::vector<double>> A = {
 538         {0.0918589, 0.980201, 0.553352, 0.0471331, 0.397493, 0.0494386, 0.158874, 0.737557, 0.822504, 0.364411},
 539         {0.852866, 0.383171, 0.924183, 0.318345, 0.937625, 0.980201, 0.0471331, 0.0494386, 0.737557, 0.364411},
 540         {0.12043, 0.985661, 0.153195, 0.852866, 0.247113, 0.318345, 0.0918589, 0.0471331, 0.158874, 0.364411},
 541         {0.387291, 0.159939, 0.641492, 0.985661, 0.0540999, 0.383171, 0.318345, 0.980201, 0.0494386, 0.364411},
 542         {0.722983, 0.924512, 0.474874, 0.819576, 0.572598, 0.0540999, 0.247113, 0.937625, 0.397493, 0.364411}};
 543
 544     std::vector<lmm::Constraint*> sys_cnst;
 545     for (auto c : C) {
 546       sys_cnst.push_back(Sys.constraint_new(nullptr, c));
 547     }
 548     std::vector<lmm::Variable*> vars;
 549     std::for_each(A[0].begin(), A[0].end(),
 550                   [&vars, &Sys, &A](const auto&) { vars.push_back(Sys.variable_new(nullptr, 1, -1, A.size())); });
 551     for (size_t j = 0; j < A.size(); j++) {
 552       for (size_t i = 0; i < A[j].size(); i++) {
 553         Sys.expand(sys_cnst[j], vars[i], A[j][i]);
 554       }
 555     }
 556     Sys.solve();
 557
 558     for (const auto* rho : vars) {
 559       REQUIRE(double_positive(rho->get_value(), sg_precision_workamount));
 560     }
 561   }
 562
 563   Sys.variable_free_all();
 564 }
 565
 566 TEST_CASE("kernel::bmf Bugs", "[kernel-bmf-bug]")
 567 {
 568   lmm::BmfSystem Sys(false);
 569
 570   SECTION("DadOu's bug: sum of bounds/phi greater than C")
 571   {
 572     /*
 573      * Ptasks in a g5k platform.
 574      * Extracted from original test.
 575      * The sum of bounds for 1 resource exceed its capacity, giving a negative value in C'
 576      */
 577
 578     lmm::Constraint* sys_cnst  = Sys.constraint_new(nullptr, 2.5e9);
 579     lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 2.5e9);
 580     lmm::Variable* rho_1       = Sys.variable_new(nullptr, 1, 2.27328e-10, 2);
 581     lmm::Variable* rho_2       = Sys.variable_new(nullptr, 1, 2.27328e-10, 2);
 582     lmm::Variable* rho_3       = Sys.variable_new(nullptr, 1);
 583
 584     Sys.expand(sys_cnst, rho_1, 1.84467e+19);
 585     Sys.expand(sys_cnst2, rho_1, 1.84467e+19);
 586     Sys.expand(sys_cnst, rho_2, 1.84467e+19);
 587     Sys.expand(sys_cnst, rho_3, 1.91268e+11);
 588     Sys.solve();
 589   }
 590
 591   SECTION("DadOu's bug: complete matrix")
 592   {
 593     constexpr int cnsts = 71;
 594     constexpr int flows = 3;
 595
 596     Eigen::MatrixXd A(cnsts, flows);
 597     A << 0, 0, 0, 0, 0, 0, 0, 0, 1.84467e+19, 1.91268e+11, 1.84467e+19, 1.84467e+19, 0, 0, 1.84467e+19, 0, 1.84467e+19,
 598         0, 0, 1.84467e+19, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0,
 599         4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11,
 600         0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 1.256e+09, 0, 0, 2.2372e+10, 0, 0,
 601         2.2684e+10, 0, 0, 2.2588e+10, 0, 0, 2.3188e+10, 0, 0, 2.228e+10, 0, 0, 2.058e+10, 0, 0, 2.2684e+10, 0, 0,
 602         2.2824e+10, 0, 0, 2.2976e+10, 0, 0, 2.2632e+10, 0, 0, 2.2584e+10, 0, 0, 2.2736e+10, 0, 0, 2.2616e+10, 0, 0,
 603         2.0828e+10, 0, 0, 2.3184e+10, 0, 0, 2.2524e+10, 0, 0, 2.278e+10, 0, 0, 2.2164e+10, 0, 0, 1.26e+09, 0, 0,
 604         2.1872e+10, 0, 0, 1.4e+09, 0, 0, 2.3184e+10, 0, 0, 8.52e+08, 0, 0, 2.2268e+10, 0, 0, 1.756e+09, 0, 0,
 605         2.0636e+10, 0, 0, 3.4e+09, 0, 0, 2.2576e+10, 0, 0, 1.352e+09, 0, 0, 2.2832e+10, 0, 0, 1.2e+09, 0, 0, 2.3092e+10,
 606         0, 0, 9.48e+08, 0, 0, 2.2436e+10, 0, 0, 1.4e+09, 0, 0, 2.2572e+10, 0, 0, 1.452e+09, 0, 0, 2.2692e+10, 0, 0,
 607         1.3e+09, 0, 0, 2.2832e+10, 0, 0, 1.2e+09, 0, 0, 2.1232e+10, 0, 0, 2.804e+09, 0, 0, 2.3184e+10, 0, 0,
 608         8.56001e+08, 0, 0, 2.2512e+10, 0, 0, 1.5e+09, 0, 0;
 609
 610     Eigen::MatrixXd maxA(cnsts, flows);
 611     maxA << 0, 0, 0, 0, 0, 0, 0, 0, 1.84467e+19, 3.1e+09, 1.84467e+19, 1.84467e+19, 0, 0, 1.84467e+19, 0, 1.84467e+19,
 612         0, 0, 1.84467e+19, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 1, 4.975e+11, 0, 0,
 613         4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11,
 614         0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 4.975e+11, 0, 0, 1.256e+09, 0, 0, 3.504e+09, 0, 0,
 615         3.056e+09, 0, 0, 3.1e+09, 0, 0, 2.952e+09, 0, 0, 2.404e+09, 0, 0, 2.304e+09, 0, 0, 2.556e+09, 0, 0, 2.4e+09, 0,
 616         0, 2.804e+09, 0, 0, 2.552e+09, 0, 0, 2.408e+09, 0, 0, 2.9e+09, 0, 0, 2.4e+09, 0, 0, 2.256e+09, 0, 0, 3.504e+09,
 617         0, 0, 3.244e+09, 0, 0, 2.556e+09, 0, 0, 2.952e+09, 0, 0, 1.26e+09, 0, 0, 2.552e+09, 0, 0, 1.4e+09, 0, 0,
 618         3.244e+09, 0, 0, 8.52e+08, 0, 0, 2.556e+09, 0, 0, 1.756e+09, 0, 0, 2.256e+09, 0, 0, 3.4e+09, 0, 0, 2.6e+09, 0,
 619         0, 1.352e+09, 0, 0, 2.952e+09, 0, 0, 1.2e+09, 0, 0, 2.452e+09, 0, 0, 9.48e+08, 0, 0, 2.804e+09, 0, 0, 1.4e+09,
 620         0, 0, 3.1e+09, 0, 0, 1.452e+09, 0, 0, 2.404e+09, 0, 0, 1.3e+09, 0, 0, 2.952e+09, 0, 0, 1.2e+09, 0, 0, 3.056e+09,
 621         0, 0, 2.804e+09, 0, 0, 2.4e+09, 0, 0, 8.56001e+08, 0, 0, 2.9e+09, 0, 0, 1.5e+09, 0, 0;
 622
 623     Eigen::VectorXd C(cnsts);
 624     C << 3.2e+20, 3.2e+20, 2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 3.2e+20, 3.2e+20, 3.2e+20, 3.2e+20, 3.2e+20,
 625         3.2e+20, 3.2e+20, 3.2e+20, 3.2e+20, 3.2e+20, 3.2e+20, 3.2e+20, 3.2e+20, 3.2e+20, 3.2e+20, 3.2e+20, 1.83484e+10,
 626         2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09,
 627         2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 2.5e+09, 1.83484e+10, 2.5e+09, 1.83484e+10, 2.5e+09, 1.83484e+10,
 628         2.5e+09, 1.83484e+10, 2.5e+09, 1.83484e+10, 2.5e+09, 1.83484e+10, 2.5e+09, 1.83484e+10, 2.5e+09, 1.83484e+10,
 629         2.5e+09, 1.83484e+10, 2.5e+09, 1.83484e+10, 2.5e+09, 1.83484e+10, 2.5e+09, 1.83484e+10, 2.5e+09, 1.83484e+10,
 630         2.5e+09, 1.83484e+10, 2.5e+09, 1.83484e+10;
 631
 632     Eigen::VectorXd phi(flows);
 633     phi << 1.35273, 2.27328e-10, 2.27328e-10;
 634
 635     std::vector<bool> shared(cnsts, true);
 636     lmm::BmfSolver solver(A, maxA, C, shared, phi);
 637     auto rho = solver.solve();
 638     REQUIRE((rho.array() > 0).all());
 639   }
 640
 641   SECTION("is_bmf bug: all limited by bound")
 642   {
 643     /*
 644      * Particular case, 1 flow is saturated and the other increases
 645      * its speed until the contraint is reached
 646      */
 647
 648     lmm::Constraint* sys_cnst  = Sys.constraint_new(nullptr, 10);
 649     lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 8);
 650     lmm::Variable* rho_1       = Sys.variable_new(nullptr, 1, 1.5, 2);
 651     lmm::Variable* rho_2       = Sys.variable_new(nullptr, 1, 3, 2);
 652
 653     Sys.expand(sys_cnst, rho_1, 5.0);
 654     Sys.expand(sys_cnst2, rho_1, 1.0);
 655     Sys.expand(sys_cnst, rho_2, 1.0);
 656     Sys.expand(sys_cnst2, rho_2, 1.0);
 657     Sys.solve();
 658     REQUIRE(double_equals(rho_1->get_value(), 1.4, sg_precision_workamount));
 659     REQUIRE(double_equals(rho_2->get_value(), 3, sg_precision_workamount));
 660   }
 661
 662   SECTION("s4u-cloud-capping bug: all limited by bound extra case")
 663   {
 664     /*
 665      * Inspired by s4u-cloud-capping test.
 666      * Step 9: "Put an activity on a PM and an activity on the VM capped by 10%."
 667      * Extracted from original test.
 668      * The sum of bounds for 1 resource is smaller than C.
 669      */
 670
 671     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 7.6296e+07);
 672     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1, 7.6296e+06, 1);
 673     lmm::Variable* rho_2      = Sys.variable_new(nullptr, 1, 3.8148e+07, 1);
 674
 675     Sys.expand(sys_cnst, rho_1, 1);
 676     Sys.expand(sys_cnst, rho_2, 1);
 677     Sys.solve();
 678     REQUIRE(double_equals(rho_1->get_value(), 7.6296e+06, sg_precision_workamount));
 679     REQUIRE(double_equals(rho_2->get_value(), 3.8148e+07, sg_precision_workamount));
 680   }
 681
 682   SECTION("Variable penalty with bounds: thread bug")
 683   {
 684     /*
 685      * Detected by exec-thread.
 686      * Fair-sharing vector depends on the penalty too.
 687      */
 688
 689     /* don't change the order of creation, important to trigger the bug */
 690     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 4e8);
 691     lmm::Variable* rho_2      = Sys.variable_new(nullptr, .25, 4e8, 1);
 692     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1, 1e8, 1);
 693     Sys.expand(sys_cnst, rho_2, 1);
 694     Sys.expand(sys_cnst, rho_1, 1);
 695     Sys.solve();
 696
 697     REQUIRE(double_equals(rho_1->get_value(), 8e7, sg_precision_workamount));
 698     REQUIRE(double_equals(rho_2->get_value(), 3.2e8, sg_precision_workamount));
 699   }
 700
 701   SECTION("Variable penalty with bounds greater than C")
 702   {
 703     /*
 704      * Detected by exec-thread. 6 thread running in a 4 core CPU.
 705      */
 706
 707     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 4e8);
 708     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1.0 / 6.0, 6e8, 1);
 709     Sys.expand(sys_cnst, rho_1, 1);
 710     Sys.solve();
 711
 712     REQUIRE(double_equals(rho_1->get_value(), 4e8, sg_precision_workamount));
 713   }
 714
 715   Sys.variable_free_all();
 716 }
 717
 718 TEST_CASE("kernel::bmf Stress-tests", "[.kernel-bmf-stress]")
 719 {
 720   lmm::BmfSystem Sys(false);
 721
 722   auto create_cnsts = [&Sys](int C, int capacity) -> auto
 723   {
 724     std::vector<lmm::Constraint*> sys_cnst;
 725     for (int i = 0; i < C; i++) {
 726       sys_cnst.push_back(Sys.constraint_new(nullptr, capacity));
 727     }
 728     return sys_cnst;
 729   };
 730
 731   auto test_shared = [&Sys, &create_cnsts](int C, int N, int capacity, const auto& data) {
 732     auto sys_cnst = create_cnsts(C, capacity);
 733     for (int j = 0; j < N; j++) {
 734       lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
 735       for (int i = 0; i < C; i++) {
 736         Sys.expand(sys_cnst[i], rho, data[i * j + j]);
 737       }
 738     }
 739     Sys.solve();
 740   };
 741
 742   SECTION("Random consumptions - independent flows")
 743   {
 744     int C         = 5;
 745     int N         = 2;
 746     auto data     = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
 747     auto sys_cnst = create_cnsts(C, 1);
 748     for (int j = 0; j < N; j++) {
 749       for (int i = 0; i < C; i++) {
 750         lmm::Variable* rho = Sys.variable_new(nullptr, 1);
 751         Sys.expand(sys_cnst[i], rho, data[i * j + j]);
 752       }
 753     }
 754     Sys.solve();
 755   }
 756
 757   SECTION("Random consumptions - flows sharing resources")
 758   {
 759     int C     = 5;
 760     int N     = 10;
 761     auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
 762     test_shared(C, N, 1, data);
 763   }
 764
 765   SECTION("Random integer consumptions - flows sharing resources")
 766   {
 767     int C     = 5;
 768     int N     = 10;
 769     auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10))));
 770     test_shared(C, N, 10, data);
 771   }
 772
 773   SECTION("Random consumptions - high number of constraints")
 774   {
 775     int C     = 500;
 776     int N     = 10;
 777     auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
 778     test_shared(C, N, 1, data);
 779   }
 780
 781   SECTION("Random integer consumptions - high number of constraints")
 782   {
 783     int C     = 500;
 784     int N     = 10;
 785     auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10))));
 786     test_shared(C, N, 10, data);
 787   }
 788
 789   Sys.variable_free_all();
 790 }
 791
 792 TEST_CASE("kernel::AllocationGenerator Basic tests", "[kernel-bmf-allocation-gen]")
 793 {
 794   SECTION("Full combinations")
 795   {
 796     Eigen::MatrixXd A(3, 3);
 797     A << 1, .5, 1, 1, 1, .5, 1, .75, .75;
 798     lmm::AllocationGenerator gen(std::move(A));
 799     int i = 0;
 800     std::vector<int> alloc;
 801     while (gen.next(alloc))
 802       i++;
 803     REQUIRE(i == 3 * 3 * 3);
 804   }
 805
 806   SECTION("Few options per player")
 807   {
 808     Eigen::MatrixXd A(3, 3);
 809     A << 1, 0, 0, 0, 1, 0, 0, 1, 1;
 810     lmm::AllocationGenerator gen(std::move(A));
 811     int i = 0;
 812     std::vector<int> alloc;
 813     while (gen.next(alloc))
 814       i++;
 815     REQUIRE(i == 1 * 2 * 1);
 816   }
 817 }