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