1 /* Copyright (c) 2019-2023. 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 "simgrid/math_utils.h"
7 #include "src/include/catch.hpp"
8 #include "src/kernel/lmm/maxmin.hpp"
11 namespace lmm = simgrid::kernel::lmm;
13 TEST_CASE("kernel::lmm Single constraint shared systems", "[kernel-lmm-shared-single-sys]")
15 lmm::MaxMin Sys(false);
17 SECTION("Variable penalty")
20 * A variable with twice the penalty gets half of the share
23 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
24 * o consumption_weight: a1=1 ; a2=1
25 * o sharing_penalty: p1=1 ; p2=2
28 * o rho1 = 2* rho2 (because rho2 has twice the penalty)
29 * o rho1 + rho2 = C (because all weights are 1)
32 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
33 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
34 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2);
36 Sys.expand(sys_cnst, rho_1, 1);
37 Sys.expand(sys_cnst, rho_2, 1);
40 REQUIRE(double_equals(rho_1->get_value(), 2, sg_precision_workamount));
41 REQUIRE(double_equals(rho_2->get_value(), 1, sg_precision_workamount));
44 SECTION("Consumption weight")
47 * Variables of higher consumption weight consume more resource but get the same share
50 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
51 * o consumption_weight: a1=1 ; a2=2
52 * o sharing_penalty: p1=1 ; p2=1
55 * o rho1 = rho2 (because all penalties are 1)
56 * o rho1 + 2* rho2 = C (because weight_2 is 2)
57 * o so, rho1 = rho2 = 1 (because C is 3)
60 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
61 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
62 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
64 Sys.expand(sys_cnst, rho_1, 1);
65 Sys.expand(sys_cnst, rho_2, 2);
68 REQUIRE(double_equals(rho_1->get_value(), 1, sg_precision_workamount));
69 REQUIRE(double_equals(rho_2->get_value(), 1, sg_precision_workamount));
72 SECTION("Consumption weight + variable penalty")
75 * Resource proportionality between variable is kept while
76 * varying consumption weight
79 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
80 * o consumption_weight: a1=1 ; a2=2
81 * o sharing_penalty: p1=1 ; p2=2
84 * o rho1 = 2* rho2 (because rho2 has twice the penalty)
85 * o rho1 + 2*rho2 = C (because consumption weight of rho2 is 2)
88 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 20);
89 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
90 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2);
92 Sys.expand(sys_cnst, rho_1, 1);
93 Sys.expand(sys_cnst, rho_2, 2);
96 double rho_1_share = 10;
97 REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_precision_workamount));
98 REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_precision_workamount));
101 SECTION("Multiple constraints systems")
104 * Multiple constraint systems can be solved with shared variables
107 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
108 * a3 * p1 * \rho1 + a4 * p3 * \rho3 < C2
109 * o consumption_weight: a1=1 ; a2=2 ; a3=2 ; a4=1
110 * o sharing_penalty: p1=1 ; p2=2 ; p3=1
111 * o load: load_1=C1/(p1/a1 + p2/a2)=20 ; load_2=C2/(a2/p1 + a3/p3)=30
114 * o First constraint will be solve first (because load_1 < load_2)
115 * o rho1 = 2* rho2 (because rho2 has twice the penalty)
116 * o rho1 + 2*rho2 = C1 (because consumption weight of rho2 is 2)
117 * o 2*rho1 + rho3 = C2 (because consumption weight of rho1 is 2)
120 lmm::Constraint* sys_cnst_1 = Sys.constraint_new(nullptr, 20);
121 lmm::Constraint* sys_cnst_2 = Sys.constraint_new(nullptr, 60);
123 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
124 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2, -1, 1);
125 lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 1);
128 Sys.expand(sys_cnst_1, rho_1, 1);
129 Sys.expand(sys_cnst_1, rho_2, 2);
132 Sys.expand(sys_cnst_2, rho_1, 2);
133 Sys.expand(sys_cnst_2, rho_3, 1);
136 double rho_1_share = 10; // Start by solving the first constraint (results is the same as previous tests)
137 REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_precision_workamount));
138 REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_precision_workamount));
139 REQUIRE(double_equals(rho_3->get_value(), 60 - 2 * rho_1_share, sg_precision_workamount));
142 Sys.variable_free_all();
145 TEST_CASE("kernel::lmm Single constraint unshared systems", "[kernel-lmm-unshared-single-sys]")
147 lmm::MaxMin Sys(false);
149 SECTION("Variable penalty")
152 * A variable with a penalty of two get half of the max_share
155 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
156 * o consumption_weight: a1=1 ; a2=1
157 * o sharing_penalty: p1=1 ; p2=2
158 * o max_share: max(C1/(a1/p1),C1/(a2/p2))
162 * o rho2 = max_share/2 (because penalty of rho2 is 2)
165 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10);
166 sys_cnst->unshare(); // FATPIPE
167 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
168 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2);
170 Sys.expand(sys_cnst, rho_1, 1);
171 Sys.expand(sys_cnst, rho_2, 1);
174 REQUIRE(double_equals(rho_1->get_value(), 10, sg_precision_workamount));
175 REQUIRE(double_equals(rho_2->get_value(), 10 / 2, sg_precision_workamount));
178 SECTION("Consumption weight")
181 * In a given constraint with all variable penalty to 1,
182 * the max_share is affected only by the maximum consumption weight
185 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
186 * o consumption_weight: a1=1 ; a2=1
187 * o sharing_penalty: p1=1 ; p2=2
188 * o max_share: max(C1/(a1/p1),C1/(a2/p2))
191 * o rho1 = max_share/2 (because penalty of rho1 is 1)
192 * o rho2 = max_share/2 (because penalty of rho2 is 1)
195 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10);
196 sys_cnst->unshare(); // FATPIPE
197 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
198 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
200 Sys.expand(sys_cnst, rho_1, 1);
201 Sys.expand(sys_cnst, rho_2, 2);
204 REQUIRE(double_equals(rho_1->get_value(), 5, sg_precision_workamount));
205 REQUIRE(double_equals(rho_2->get_value(), 5, sg_precision_workamount));
208 SECTION("Consumption weight + variable penalty")
211 * Resource proportionality between variable is kept but
212 * constraint bound can be violated
215 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
216 * o consumption_weight: a1=1 ; a2=2
217 * o sharing_penalty: p1=1 ; p2=2
220 * o rho1 = 2 * rho2 (because rho2 has twice the penalty)
221 * o rho1 + 2*rho2 can be greater than C
222 * o rho1 <= C and 2*rho2 <= C
225 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10);
227 lmm::Variable* sys_var_1 = Sys.variable_new(nullptr, 1);
228 lmm::Variable* sys_var_2 = Sys.variable_new(nullptr, 2);
230 Sys.expand(sys_cnst, sys_var_1, 1);
231 Sys.expand(sys_cnst, sys_var_2, 2);
234 REQUIRE(double_equals(sys_var_1->get_value(), 10, sg_precision_workamount));
235 REQUIRE(double_equals(sys_var_2->get_value(), 5, sg_precision_workamount));
238 SECTION("Multiple constraints systems")
241 * Multiple constraint systems can be solved with shared variables
242 * on unshared constraints.
245 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
246 * a3 * p1 * \rho1 + a4 * p3 * \rho3 < C2
247 * o consumption_weight: a1=1 ; a2=2 ; a3=2 ; a4=1
248 * o sharing_penalty: p1=1 ; p2=2 ; p3=1
249 * o load: load_1=C1/max(p1/a1,p2/a2)=20 ; load_2=C2/max(a3/p1,a4/p3)=30
252 * o First constraint will be solve first (because load_1 < load_2)
253 * o Second constraint load will not be updated !
254 * o Each constraint should satisfy max(a_i * rho_i) <= C_r
257 lmm::Constraint* sys_cnst_1 = Sys.constraint_new(nullptr, 10);
258 lmm::Constraint* sys_cnst_2 = Sys.constraint_new(nullptr, 60);
259 sys_cnst_1->unshare(); // FATPIPE
260 sys_cnst_2->unshare();
262 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
263 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2, -1, 1);
264 lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 1);
267 Sys.expand(sys_cnst_1, rho_1, 1);
268 Sys.expand(sys_cnst_1, rho_2, 2);
271 Sys.expand(sys_cnst_2, rho_1, 2);
272 Sys.expand(sys_cnst_2, rho_3, 1);
275 double rho_1_share = 10; // Start by solving the first constraint (results is the same as previous tests)
276 REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_precision_workamount));
277 REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_precision_workamount));
278 REQUIRE(double_equals(rho_3->get_value(), 60, sg_precision_workamount));
281 Sys.variable_free_all();
284 TEST_CASE("kernel::lmm dynamic constraint shared systems", "[kernel-lmm-shared-single-sys]")
286 auto cb = [](double bound, int flows) -> double {
287 // decrease 10 % for each extra flow sharing this resource
288 return bound - (flows - 1) * .10 * bound;
290 lmm::MaxMin Sys(false);
291 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10);
292 sys_cnst->set_sharing_policy(lmm::Constraint::SharingPolicy::NONLINEAR, cb);
294 SECTION("1 activity, 100% C")
297 * A single variable gets all the share
300 * o System: a1 * p1 * \rho1 < C
301 * o consumption_weight: a1=1
302 * o sharing_penalty: p1=1
305 * o rho1 = C (because all weights are 1)
308 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
310 Sys.expand(sys_cnst, rho_1, 1);
313 REQUIRE(double_equals(rho_1->get_value(), 10, sg_precision_workamount));
316 SECTION("2 activities, but ignore crosstraffic 100% C")
319 * Ignore small activities (e.g. crosstraffic)
322 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
323 * o consumption_weight: a1=1 ; a2=0.05
324 * o sharing_penalty: p1=1 ; p2=1
329 * o rho1 = rho2 (because rho1 and rho2 has the same penalty)
332 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
333 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
335 Sys.expand(sys_cnst, rho_1, 1);
336 Sys.expand(sys_cnst, rho_2, 0.05);
339 REQUIRE(double_equals(rho_1->get_value(), 10 / 1.05, sg_precision_workamount));
340 REQUIRE(double_equals(rho_1->get_value(), rho_2->get_value(), sg_precision_workamount));
343 SECTION("2 activities, 1 inactive 100% C")
346 * 2 activities but 1 is inactive (sharing_penalty = 0)
349 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
350 * o consumption_weight: a1=1 ; a2=1
351 * o sharing_penalty: p1=1 ; p2=0
358 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
359 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 0);
361 Sys.expand(sys_cnst, rho_1, 1);
362 Sys.expand(sys_cnst, rho_2, 1);
365 REQUIRE(double_equals(rho_1->get_value(), 10, sg_precision_workamount));
366 REQUIRE(double_equals(rho_2->get_value(), 0, sg_precision_workamount));
369 SECTION("2 activity, 90% C")
372 * 2 similar variables degrades performance, but get same share
375 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < .9C
376 * o consumption_weight: a1=1 ; a2=1
377 * o sharing_penalty: p1=1 ; p2=1
381 * o rho1 + rho2 = C (because all weights are 1)
384 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
385 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
387 Sys.expand(sys_cnst, rho_1, 1);
388 Sys.expand(sys_cnst, rho_2, 1);
391 REQUIRE(double_equals(rho_1->get_value(), 4.5, sg_precision_workamount));
392 REQUIRE(double_equals(rho_1->get_value(), 4.5, sg_precision_workamount));
395 SECTION("3 activity, 80% C")
398 * 3 similar variables degrades performance, sharing proportional to penalty
401 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 + a3 * p3 * \rho3 < .8C
402 * o consumption_weight: a1=1 ; a2=1 ; a3=1
403 * o sharing_penalty: p1=1 ; p2=3 ; p3=4
406 * o rho1 = 2*rho2 = 2*rho3
407 * 0 rho1 = 4, rho2 = 2, rho3 = 2
408 * o rho1 + rho2 + rho3 = .8C (because all weights are 1)
411 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
412 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2);
413 lmm::Variable* rho_3 = Sys.variable_new(nullptr, 2);
415 Sys.expand(sys_cnst, rho_1, 1);
416 Sys.expand(sys_cnst, rho_2, 1);
417 Sys.expand(sys_cnst, rho_3, 1);
420 REQUIRE(double_equals(rho_1->get_value(), 4, sg_precision_workamount));
421 REQUIRE(double_equals(rho_2->get_value(), 2, sg_precision_workamount));
422 REQUIRE(double_equals(rho_3->get_value(), 2, sg_precision_workamount));
425 Sys.variable_free_all();
428 TEST_CASE("kernel::lmm shared systems with crosstraffic", "[kernel-lmm-shared-crosstraffic]")
430 lmm::MaxMin Sys(false);
432 SECTION("3 flows, 3 resource: crosstraffic")
435 * 3 flows sharing 2 constraints, single
438 * o System: a1 * \rho1 + a2 * \rho2 + epsilon * \rho3 < C1
439 * epsilon * \rho1 + epsilon * \rho2 + a3 * \rho3 < C2
440 * o consumption_weight: a1=1, a2=1, a3=1, epsilon=0.05
444 * o rho1 = rho2 = rho3 = 1/2
446 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
447 lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
448 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
449 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 2);
450 lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 2);
452 double epsilon = 0.05;
453 Sys.expand(sys_cnst, rho_1, 1.0);
454 Sys.expand(sys_cnst2, rho_1, epsilon);
455 Sys.expand(sys_cnst, rho_2, 1.0);
456 Sys.expand(sys_cnst2, rho_2, epsilon);
457 Sys.expand(sys_cnst2, rho_3, 1.0);
458 Sys.expand(sys_cnst, rho_3, epsilon);
461 REQUIRE(double_equals(rho_1->get_value(), 1.0 / (2.0 + epsilon), sg_precision_workamount));
462 REQUIRE(double_equals(rho_2->get_value(), 1.0 / (2.0 + epsilon), sg_precision_workamount));
463 REQUIRE(double_equals(rho_3->get_value(), 1.0 / (2.0 + epsilon), sg_precision_workamount));
466 Sys.variable_free_all();