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
  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_maxmin_precision));
  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_maxmin_precision));
  64     REQUIRE(double_equals(rho_2->get_value(), (3.0 / 2.0) / 10.0, sg_maxmin_precision));
  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_maxmin_precision));
  91     REQUIRE(double_equals(rho_2->get_value(), 1.0 / 3.0, sg_maxmin_precision));
  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_maxmin_precision));
 117     REQUIRE(double_equals(rho_2->get_value(), 0.0, sg_maxmin_precision));
 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_maxmin_precision));
 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_maxmin_precision));
 167     REQUIRE(double_equals(rho_2->get_value(), .8, sg_maxmin_precision));
 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_maxmin_precision));
 195     REQUIRE(double_equals(rho_2->get_value(), 3.0, sg_maxmin_precision));
 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_maxmin_precision));
 221     REQUIRE(double_equals(rho_2->get_value(), .5, sg_maxmin_precision));
 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_maxmin_precision));
 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_maxmin_precision));
 253     REQUIRE(double_equals(rho_2->get_value(), .25, sg_maxmin_precision));
 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_maxmin_precision));
 295     REQUIRE(double_equals(rho_2->get_value(), 1.0 / 11.0, sg_maxmin_precision));
 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_maxmin_precision));
 331     REQUIRE(double_equals(rho_2->get_value(), 4.0 / 9.0, sg_maxmin_precision));
 332     REQUIRE(double_equals(rho_3->get_value(), 4.0 / 9.0, sg_maxmin_precision));
 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_maxmin_precision));
 372     REQUIRE(double_equals(rho_2->get_value(), 1e6 / 2.0, sg_maxmin_precision));
 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_maxmin_precision));
 402     REQUIRE(double_equals(rho_2->get_value(), 1.0 / (2.0 + 2 * epsilon), sg_maxmin_precision));
 403     REQUIRE(double_equals(rho_3->get_value(), 1.0 / (1.0 + epsilon), sg_maxmin_precision));
 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_add(sys_cnst, rho_1, 5);
 438     Sys.expand_add(sys_cnst, rho_1, 7);
 439     Sys.expand_add(sys_cnst, rho_2, 7);
 440     Sys.expand_add(sys_cnst, rho_2, 5);
 441     Sys.solve();
 442
 443     REQUIRE(double_equals(rho_1->get_value(), 5.0 / 24.0, sg_maxmin_precision));
 444     REQUIRE(double_equals(rho_2->get_value(), 5.0 / 24.0, sg_maxmin_precision));
 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_add(sys_cnst, rho_1, 10);
 474     Sys.expand_add(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_maxmin_precision));
 479     REQUIRE(double_equals(rho_2->get_value(), (5.0 / 25.0), sg_maxmin_precision));
 480     REQUIRE(double_equals(15 * rho_1->get_value(), 10 * rho_2->get_value() * 3 / 2, sg_maxmin_precision));
 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_add(sys_cnst, rho_1, 1.0);
 509     Sys.expand_add(sys_cnst, rho_1, 1.0);
 510     Sys.expand(sys_cnst, rho_2, 1);
 511     Sys.expand_add(sys_cnst2, rho_1, 1.0 / 2.0);
 512     Sys.expand_add(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_maxmin_precision));
 517     REQUIRE(double_equals(rho_2->get_value(), (1.0 / 3.0), sg_maxmin_precision));
 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_add(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_maxmin_precision));
 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_add(sys_cnst, rho_1, 1.84467e+19);
 585     Sys.expand_add(sys_cnst2, rho_1, 1.84467e+19);
 586     Sys.expand_add(sys_cnst, rho_2, 1.84467e+19);
 587     Sys.expand_add(sys_cnst, rho_3, 1.91268e+11);
 588     Sys.solve();
 589   }
 590
 591   SECTION("is_bmf bug: all limited by bound")
 592   {
 593     /*
 594      * Particular case, 1 flow is saturated and the other increases
 595      * its speed until the contraint is reached
 596      */
 597
 598     lmm::Constraint* sys_cnst  = Sys.constraint_new(nullptr, 10);
 599     lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 8);
 600     lmm::Variable* rho_1       = Sys.variable_new(nullptr, 1, 1.5, 2);
 601     lmm::Variable* rho_2       = Sys.variable_new(nullptr, 1, 3, 2);
 602
 603     Sys.expand_add(sys_cnst, rho_1, 5.0);
 604     Sys.expand_add(sys_cnst2, rho_1, 1.0);
 605     Sys.expand_add(sys_cnst, rho_2, 1.0);
 606     Sys.expand_add(sys_cnst2, rho_2, 1.0);
 607     Sys.solve();
 608     REQUIRE(double_equals(rho_1->get_value(), 1.4, sg_maxmin_precision));
 609     REQUIRE(double_equals(rho_2->get_value(), 3, sg_maxmin_precision));
 610   }
 611
 612   SECTION("Variable penalty with bounds: thread bug")
 613   {
 614     /*
 615      * Detected by exec-thread.
 616      * Fair-sharing vector depends on the penalty too.
 617      */
 618
 619     /* don't change the order of creation, important to trigger the bug */
 620     lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 4e8);
 621     lmm::Variable* rho_2      = Sys.variable_new(nullptr, .25, 4e8, 1);
 622     lmm::Variable* rho_1      = Sys.variable_new(nullptr, 1, 1e8, 1);
 623     Sys.expand(sys_cnst, rho_2, 1);
 624     Sys.expand(sys_cnst, rho_1, 1);
 625     Sys.solve();
 626
 627     REQUIRE(double_equals(rho_1->get_value(), 8e7, sg_maxmin_precision));
 628     REQUIRE(double_equals(rho_2->get_value(), 3.2e8, sg_maxmin_precision));
 629   }
 630
 631   Sys.variable_free_all();
 632 }
 633
 634 TEST_CASE("kernel::bmf Stress-tests", "[.kernel-bmf-stress]")
 635 {
 636   lmm::BmfSystem Sys(false);
 637
 638   auto create_cnsts = [&Sys](int C, int capacity) -> auto
 639   {
 640     std::vector<lmm::Constraint*> sys_cnst;
 641     for (int i = 0; i < C; i++) {
 642       sys_cnst.push_back(Sys.constraint_new(nullptr, capacity));
 643     }
 644     return sys_cnst;
 645   };
 646
 647   auto test_shared = [&Sys, &create_cnsts](int C, int N, int capacity, const auto& data) {
 648     auto sys_cnst = create_cnsts(C, capacity);
 649     for (int j = 0; j < N; j++) {
 650       lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
 651       for (int i = 0; i < C; i++) {
 652         Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
 653       }
 654     }
 655     Sys.solve();
 656   };
 657
 658   SECTION("Random consumptions - independent flows")
 659   {
 660     int C         = 5;
 661     int N         = 2;
 662     auto data     = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
 663     auto sys_cnst = create_cnsts(C, 1);
 664     for (int j = 0; j < N; j++) {
 665       for (int i = 0; i < C; i++) {
 666         lmm::Variable* rho = Sys.variable_new(nullptr, 1);
 667         Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
 668       }
 669     }
 670     Sys.solve();
 671   }
 672
 673   SECTION("Random consumptions - flows sharing resources")
 674   {
 675     int C     = 5;
 676     int N     = 10;
 677     auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
 678     test_shared(C, N, 1, data);
 679   }
 680
 681   SECTION("Random integer consumptions - flows sharing resources")
 682   {
 683     int C     = 5;
 684     int N     = 10;
 685     auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10))));
 686     test_shared(C, N, 10, data);
 687   }
 688
 689   SECTION("Random consumptions - high number of constraints")
 690   {
 691     int C     = 500;
 692     int N     = 10;
 693     auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
 694     test_shared(C, N, 1, data);
 695   }
 696
 697   SECTION("Random integer consumptions - high number of constraints")
 698   {
 699     int C     = 500;
 700     int N     = 10;
 701     auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10))));
 702     test_shared(C, N, 10, data);
 703   }
 704
 705   Sys.variable_free_all();
 706 }
 707
 708 TEST_CASE("kernel::AllocationGenerator Basic tests", "[kernel-bmf-allocation-gen]")
 709 {
 710   SECTION("Full combinations")
 711   {
 712     Eigen::MatrixXd A(3, 3);
 713     A << 1, .5, 1, 1, 1, .5, 1, .75, .75;
 714     lmm::AllocationGenerator gen(std::move(A));
 715     int i = 0;
 716     std::vector<int> alloc;
 717     while (gen.next(alloc))
 718       i++;
 719     REQUIRE(i == 3 * 3 * 3);
 720   }
 721
 722   SECTION("Few options per player")
 723   {
 724     Eigen::MatrixXd A(3, 3);
 725     A << 1, 0, 0, 0, 1, 0, 0, 1, 1;
 726     lmm::AllocationGenerator gen(std::move(A));
 727     int i = 0;
 728     std::vector<int> alloc;
 729     while (gen.next(alloc))
 730       i++;
 731     REQUIRE(i == 1 * 2 * 1);
 732   }
 733 }