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