1 /* Copyright (c) 2019-2022. The SimGrid Team. All rights reserved. */
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. */
6 #include "src/include/catch.hpp"
7 #include "src/kernel/lmm/bmf.hpp"
8 #include "src/surf/surf_interface.hpp"
11 namespace lmm = simgrid::kernel::lmm;
13 TEST_CASE("kernel::bmf Basic tests", "[kernel-bmf-basic]")
15 lmm::BmfSystem Sys(false);
17 SECTION("Single flow")
20 * A single variable using a single resource
23 * o System: a1 * p1 * \rho1 < C
24 * o consumption_weight: a1=1
25 * o sharing_penalty: p1=1
31 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
32 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
34 Sys.expand(sys_cnst, rho_1, 1);
37 REQUIRE(double_equals(rho_1->get_value(), 3, sg_maxmin_precision));
43 * Two flows sharing a single resource
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
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);
59 Sys.expand(sys_cnst, rho_1, 1);
60 Sys.expand(sys_cnst, rho_2, 10);
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));
67 SECTION("Variable penalty/priority")
70 * A variable with twice the penalty gets half of the share
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
78 * o rho1 = 2* rho2 (because rho2 has twice the penalty)
79 * o rho1 + rho2 = C (because all weights are 1)
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);
86 Sys.expand(sys_cnst, rho_1, 1);
87 Sys.expand(sys_cnst, rho_2, 1);
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));
94 SECTION("Disable variable doesn't count")
97 * Two flows sharing a single resource, but one is disabled
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
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);
112 Sys.expand(sys_cnst, rho_1, 1);
113 Sys.expand(sys_cnst, rho_2, 10);
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));
120 SECTION("No consumption variable")
123 * An empty variable, no consumption, just assure it receives something
125 * o System: a1 * p1 * \rho1 < C
126 * o consumption_weight: a1=0
127 * o sharing_penalty: p1=1
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);
137 Sys.expand(sys_cnst, rho_1, 1);
138 Sys.expand(sys_cnst, rho_2, 10);
141 REQUIRE(double_positive(rho_1->get_value(), sg_maxmin_precision));
144 SECTION("Bounded variable")
147 * Assures a player receives the min(bound, share) if it's bounded
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
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);
163 Sys.expand(sys_cnst, rho_1, 2);
164 Sys.expand(sys_cnst, rho_2, 1);
166 REQUIRE(double_equals(rho_1->get_value(), .1, sg_maxmin_precision));
167 REQUIRE(double_equals(rho_2->get_value(), .8, sg_maxmin_precision));
173 * Two flows using a fatpipe resource
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
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);
190 Sys.expand(sys_cnst, rho_1, 1);
191 Sys.expand(sys_cnst, rho_2, 1);
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));
198 SECTION("(un)Bounded variable")
201 * Assures a player receives the share if bound is greater than share
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
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);
217 Sys.expand(sys_cnst, rho_1, 1);
218 Sys.expand(sys_cnst, rho_2, 1);
220 REQUIRE(double_equals(rho_1->get_value(), .5, sg_maxmin_precision));
221 REQUIRE(double_equals(rho_2->get_value(), .5, sg_maxmin_precision));
224 SECTION("Dynamic bounds")
227 * Resource bound is modified by user callback and shares are adapted accordingly
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
234 * o rho1 = .5 and .25
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);
245 REQUIRE(double_equals(rho_1->get_value(), 1, sg_maxmin_precision));
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);
252 REQUIRE(double_equals(rho_1->get_value(), .25, sg_maxmin_precision));
253 REQUIRE(double_equals(rho_2->get_value(), .25, sg_maxmin_precision));
256 Sys.variable_free_all();
259 TEST_CASE("kernel::bmf Advanced tests", "[kernel-bmf-advanced]")
261 lmm::BmfSystem Sys(false);
263 SECTION("2 flows, 2 resources")
266 * Two flows sharing 2 resources with opposite requirements
269 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
270 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C2
272 * o consumption_weight: a11=1, a12=10, a21=10, a22=1
273 * o sharing_penalty: p1=1, p2=1
276 * o rho1 = rho2 = C/11
279 * [1 10] * [rho1 rho2] = [1]
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);
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);
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));
298 SECTION("BMF paper example")
301 * 3 flows sharing 3 resources
304 * [1 1 1/2] * [rho1 rho2 rho3] = [1]
308 * Expectations (several possible BMF allocations, our algorithm return this)
309 * o rho1 = rho2 = rho3 = 2/5
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);
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);
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));
335 SECTION("IO - example")
338 * Two flows sharing 1 disk
339 * read, write and readwrite constraint
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
346 * o consumption_weight: a1=1, a2=1
347 * o sharing_penalty: p1=1, p2=1
350 * o rho1 = rho2 = C/2
353 * [1 10] * [rho1 rho2] = [1]
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);
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);
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));
375 SECTION("Proportional fairness")
378 * 3 flows sharing 2 resources with crosstraffic
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
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);
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);
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));
406 Sys.variable_free_all();
409 TEST_CASE("kernel::bmf Subflows", "[kernel-bmf-subflow]")
411 lmm::BmfSystem Sys(false);
413 SECTION("2 subflows and 1 resource")
416 * 2 identical flows composed of 2 subflows
418 * They must receive the same share and use same amount of resources
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
426 * o rho1 = rho2 = (C/2)/12
429 * [12 12] * [rho1 rho2] = [1]
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);
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);
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));
447 SECTION("1 subflows, 1 flow and 1 resource")
450 * 2 flows, 1 resource
451 * 1 flow composed of 2 subflows
453 * Same share/rho, but subflow uses 50% more resources since it has a second connection/subflow
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
465 * [15 10] * [rho1 rho2] = [1]
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);
473 Sys.expand(sys_cnst, rho_1, 10);
474 Sys.expand(sys_cnst, rho_1, 5);
475 Sys.expand(sys_cnst, rho_2, 10);
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));
483 SECTION("1 subflows using 2 resources: different max for each resource")
486 * Test condition that we may have different max for different resources
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
499 * [2 1 ] * [rho1 rho2] = [1]
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);
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);
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));
520 Sys.variable_free_all();
523 TEST_CASE("kernel::bmf Loop", "[kernel-bmf-loop]")
525 lmm::BmfSystem Sys(false);
527 SECTION("Initial allocation loops")
530 * Complex matrix whose initial allocation loops and is unable
531 * to stabilize after 10 iterations.
533 * The algorithm needs to restart from another point
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}};
544 std::vector<lmm::Constraint*> sys_cnst;
546 sys_cnst.push_back(Sys.constraint_new(nullptr, c));
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]);
558 for (const auto* rho : vars) {
559 REQUIRE(double_positive(rho->get_value(), sg_maxmin_precision));
563 Sys.variable_free_all();
566 TEST_CASE("kernel::bmf Bugs", "[kernel-bmf-bug]")
568 lmm::BmfSystem Sys(false);
570 SECTION("DadOu's bug: sum of bounds/phi greater than C")
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'
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);
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);
591 SECTION("DadOu's bug: complete matrix")
593 constexpr int cnsts = 71;
594 constexpr int flows = 3;
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;
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;
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;
632 Eigen::VectorXd phi(flows);
633 phi << 1.35273, 2.27328e-10, 2.27328e-10;
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());
641 SECTION("is_bmf bug: all limited by bound")
644 * Particular case, 1 flow is saturated and the other increases
645 * its speed until the contraint is reached
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);
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);
658 REQUIRE(double_equals(rho_1->get_value(), 1.4, sg_maxmin_precision));
659 REQUIRE(double_equals(rho_2->get_value(), 3, sg_maxmin_precision));
662 SECTION("s4u-cloud-capping bug: all limited by bound extra case")
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.
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);
675 Sys.expand(sys_cnst, rho_1, 1);
676 Sys.expand(sys_cnst, rho_2, 1);
678 REQUIRE(double_equals(rho_1->get_value(), 7.6296e+06, sg_maxmin_precision));
679 REQUIRE(double_equals(rho_2->get_value(), 3.8148e+07, sg_maxmin_precision));
682 SECTION("Variable penalty with bounds: thread bug")
685 * Detected by exec-thread.
686 * Fair-sharing vector depends on the penalty too.
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);
697 REQUIRE(double_equals(rho_1->get_value(), 8e7, sg_maxmin_precision));
698 REQUIRE(double_equals(rho_2->get_value(), 3.2e8, sg_maxmin_precision));
701 SECTION("Variable penalty with bounds greater than C")
704 * Detected by exec-thread. 6 thread running in a 4 core CPU.
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);
712 REQUIRE(double_equals(rho_1->get_value(), 4e8, sg_maxmin_precision));
715 Sys.variable_free_all();
718 TEST_CASE("kernel::bmf Stress-tests", "[.kernel-bmf-stress]")
720 lmm::BmfSystem Sys(false);
722 auto create_cnsts = [&Sys](int C, int capacity) -> auto
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));
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]);
742 SECTION("Random consumptions - independent flows")
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]);
757 SECTION("Random consumptions - flows sharing resources")
761 auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
762 test_shared(C, N, 1, data);
765 SECTION("Random integer consumptions - flows sharing resources")
769 auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10))));
770 test_shared(C, N, 10, data);
773 SECTION("Random consumptions - high number of constraints")
777 auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
778 test_shared(C, N, 1, data);
781 SECTION("Random integer consumptions - high number of constraints")
785 auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10))));
786 test_shared(C, N, 10, data);
789 Sys.variable_free_all();
792 TEST_CASE("kernel::AllocationGenerator Basic tests", "[kernel-bmf-allocation-gen]")
794 SECTION("Full combinations")
796 Eigen::MatrixXd A(3, 3);
797 A << 1, .5, 1, 1, 1, .5, 1, .75, .75;
798 lmm::AllocationGenerator gen(std::move(A));
800 std::vector<int> alloc;
801 while (gen.next(alloc))
803 REQUIRE(i == 3 * 3 * 3);
806 SECTION("Few options per player")
808 Eigen::MatrixXd A(3, 3);
809 A << 1, 0, 0, 0, 1, 0, 0, 1, 1;
810 lmm::AllocationGenerator gen(std::move(A));
812 std::vector<int> alloc;
813 while (gen.next(alloc))
815 REQUIRE(i == 1 * 2 * 1);