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 "src/include/catch.hpp"
7 #include "src/kernel/lmm/maxmin.hpp"
10 namespace lmm = simgrid::kernel::lmm;
12 TEST_CASE("kernel::lmm Single constraint shared systems", "[kernel-lmm-shared-single-sys]")
14 lmm::MaxMin Sys(false);
16 SECTION("Variable penalty")
19 * A variable with twice the penalty gets half of the share
22 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
23 * o consumption_weight: a1=1 ; a2=1
24 * o sharing_penalty: p1=1 ; p2=2
27 * o rho1 = 2* rho2 (because rho2 has twice the penalty)
28 * o rho1 + rho2 = C (because all weights are 1)
31 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
32 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
33 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2);
35 Sys.expand(sys_cnst, rho_1, 1);
36 Sys.expand(sys_cnst, rho_2, 1);
39 REQUIRE(double_equals(rho_1->get_value(), 2, sg_precision_workamount));
40 REQUIRE(double_equals(rho_2->get_value(), 1, sg_precision_workamount));
43 SECTION("Consumption weight")
46 * Variables of higher consumption weight consume more resource but get the same share
49 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
50 * o consumption_weight: a1=1 ; a2=2
51 * o sharing_penalty: p1=1 ; p2=1
54 * o rho1 = rho2 (because all penalties are 1)
55 * o rho1 + 2* rho2 = C (because weight_2 is 2)
56 * o so, rho1 = rho2 = 1 (because C is 3)
59 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
60 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
61 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
63 Sys.expand(sys_cnst, rho_1, 1);
64 Sys.expand(sys_cnst, rho_2, 2);
67 REQUIRE(double_equals(rho_1->get_value(), 1, sg_precision_workamount));
68 REQUIRE(double_equals(rho_2->get_value(), 1, sg_precision_workamount));
71 SECTION("Consumption weight + variable penalty")
74 * Resource proportionality between variable is kept while
75 * varying consumption weight
78 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
79 * o consumption_weight: a1=1 ; a2=2
80 * o sharing_penalty: p1=1 ; p2=2
83 * o rho1 = 2* rho2 (because rho2 has twice the penalty)
84 * o rho1 + 2*rho2 = C (because consumption weight of rho2 is 2)
87 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 20);
88 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
89 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2);
91 Sys.expand(sys_cnst, rho_1, 1);
92 Sys.expand(sys_cnst, rho_2, 2);
95 double rho_1_share = 10;
96 REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_precision_workamount));
97 REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_precision_workamount));
100 SECTION("Multiple constraints systems")
103 * Multiple constraint systems can be solved with shared variables
106 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
107 * a3 * p1 * \rho1 + a4 * p3 * \rho3 < C2
108 * o consumption_weight: a1=1 ; a2=2 ; a3=2 ; a4=1
109 * o sharing_penalty: p1=1 ; p2=2 ; p3=1
110 * o load: load_1=C1/(p1/a1 + p2/a2)=20 ; load_2=C2/(a2/p1 + a3/p3)=30
113 * o First constraint will be solve first (because load_1 < load_2)
114 * o rho1 = 2* rho2 (because rho2 has twice the penalty)
115 * o rho1 + 2*rho2 = C1 (because consumption weight of rho2 is 2)
116 * o 2*rho1 + rho3 = C2 (because consumption weight of rho1 is 2)
119 lmm::Constraint* sys_cnst_1 = Sys.constraint_new(nullptr, 20);
120 lmm::Constraint* sys_cnst_2 = Sys.constraint_new(nullptr, 60);
122 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
123 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2, -1, 1);
124 lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 1);
127 Sys.expand(sys_cnst_1, rho_1, 1);
128 Sys.expand(sys_cnst_1, rho_2, 2);
131 Sys.expand(sys_cnst_2, rho_1, 2);
132 Sys.expand(sys_cnst_2, rho_3, 1);
135 double rho_1_share = 10; // Start by solving the first constraint (results is the same as previous tests)
136 REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_precision_workamount));
137 REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_precision_workamount));
138 REQUIRE(double_equals(rho_3->get_value(), 60 - 2 * rho_1_share, sg_precision_workamount));
141 Sys.variable_free_all();
144 TEST_CASE("kernel::lmm Single constraint unshared systems", "[kernel-lmm-unshared-single-sys]")
146 lmm::MaxMin Sys(false);
148 SECTION("Variable penalty")
151 * A variable with a penalty of two get half of the max_share
154 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
155 * o consumption_weight: a1=1 ; a2=1
156 * o sharing_penalty: p1=1 ; p2=2
157 * o max_share: max(C1/(a1/p1),C1/(a2/p2))
161 * o rho2 = max_share/2 (because penalty of rho2 is 2)
164 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10);
165 sys_cnst->unshare(); // FATPIPE
166 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
167 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2);
169 Sys.expand(sys_cnst, rho_1, 1);
170 Sys.expand(sys_cnst, rho_2, 1);
173 REQUIRE(double_equals(rho_1->get_value(), 10, sg_precision_workamount));
174 REQUIRE(double_equals(rho_2->get_value(), 10 / 2, sg_precision_workamount));
177 SECTION("Consumption weight")
180 * In a given constraint with all variable penalty to 1,
181 * the max_share is affected only by the maximum consumption weight
184 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
185 * o consumption_weight: a1=1 ; a2=1
186 * o sharing_penalty: p1=1 ; p2=2
187 * o max_share: max(C1/(a1/p1),C1/(a2/p2))
190 * o rho1 = max_share/2 (because penalty of rho1 is 1)
191 * o rho2 = max_share/2 (because penalty of rho2 is 1)
194 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10);
195 sys_cnst->unshare(); // FATPIPE
196 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
197 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
199 Sys.expand(sys_cnst, rho_1, 1);
200 Sys.expand(sys_cnst, rho_2, 2);
203 REQUIRE(double_equals(rho_1->get_value(), 5, sg_precision_workamount));
204 REQUIRE(double_equals(rho_2->get_value(), 5, sg_precision_workamount));
207 SECTION("Consumption weight + variable penalty")
210 * Resource proportionality between variable is kept but
211 * constraint bound can be violated
214 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
215 * o consumption_weight: a1=1 ; a2=2
216 * o sharing_penalty: p1=1 ; p2=2
219 * o rho1 = 2 * rho2 (because rho2 has twice the penalty)
220 * o rho1 + 2*rho2 can be greater than C
221 * o rho1 <= C and 2*rho2 <= C
224 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10);
226 lmm::Variable* sys_var_1 = Sys.variable_new(nullptr, 1);
227 lmm::Variable* sys_var_2 = Sys.variable_new(nullptr, 2);
229 Sys.expand(sys_cnst, sys_var_1, 1);
230 Sys.expand(sys_cnst, sys_var_2, 2);
233 REQUIRE(double_equals(sys_var_1->get_value(), 10, sg_precision_workamount));
234 REQUIRE(double_equals(sys_var_2->get_value(), 5, sg_precision_workamount));
237 SECTION("Multiple constraints systems")
240 * Multiple constraint systems can be solved with shared variables
241 * on unshared constraints.
244 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
245 * a3 * p1 * \rho1 + a4 * p3 * \rho3 < C2
246 * o consumption_weight: a1=1 ; a2=2 ; a3=2 ; a4=1
247 * o sharing_penalty: p1=1 ; p2=2 ; p3=1
248 * o load: load_1=C1/max(p1/a1,p2/a2)=20 ; load_2=C2/max(a3/p1,a4/p3)=30
251 * o First constraint will be solve first (because load_1 < load_2)
252 * o Second constraint load will not be updated !
253 * o Each constraint should satisfy max(a_i * rho_i) <= C_r
256 lmm::Constraint* sys_cnst_1 = Sys.constraint_new(nullptr, 10);
257 lmm::Constraint* sys_cnst_2 = Sys.constraint_new(nullptr, 60);
258 sys_cnst_1->unshare(); // FATPIPE
259 sys_cnst_2->unshare();
261 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
262 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2, -1, 1);
263 lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 1);
266 Sys.expand(sys_cnst_1, rho_1, 1);
267 Sys.expand(sys_cnst_1, rho_2, 2);
270 Sys.expand(sys_cnst_2, rho_1, 2);
271 Sys.expand(sys_cnst_2, rho_3, 1);
274 double rho_1_share = 10; // Start by solving the first constraint (results is the same as previous tests)
275 REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_precision_workamount));
276 REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_precision_workamount));
277 REQUIRE(double_equals(rho_3->get_value(), 60, sg_precision_workamount));
280 Sys.variable_free_all();
283 TEST_CASE("kernel::lmm dynamic constraint shared systems", "[kernel-lmm-shared-single-sys]")
285 auto cb = [](double bound, int flows) -> double {
286 // decrease 10 % for each extra flow sharing this resource
287 return bound - (flows - 1) * .10 * bound;
289 lmm::MaxMin Sys(false);
290 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10);
291 sys_cnst->set_sharing_policy(lmm::Constraint::SharingPolicy::NONLINEAR, cb);
293 SECTION("1 activity, 100% C")
296 * A single variable gets all the share
299 * o System: a1 * p1 * \rho1 < C
300 * o consumption_weight: a1=1
301 * o sharing_penalty: p1=1
304 * o rho1 = C (because all weights are 1)
307 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
309 Sys.expand(sys_cnst, rho_1, 1);
312 REQUIRE(double_equals(rho_1->get_value(), 10, sg_precision_workamount));
315 SECTION("2 activities, but ignore crosstraffic 100% C")
318 * Ignore small activities (e.g. crosstraffic)
321 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
322 * o consumption_weight: a1=1 ; a2=0.05
323 * o sharing_penalty: p1=1 ; p2=1
328 * o rho1 = rho2 (because rho1 and rho2 has the same penalty)
331 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
332 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
334 Sys.expand(sys_cnst, rho_1, 1);
335 Sys.expand(sys_cnst, rho_2, 0.05);
338 REQUIRE(double_equals(rho_1->get_value(), 10 / 1.05, sg_precision_workamount));
339 REQUIRE(double_equals(rho_1->get_value(), rho_2->get_value(), sg_precision_workamount));
342 SECTION("2 activities, 1 inactive 100% C")
345 * 2 activities but 1 is inactive (sharing_penalty = 0)
348 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
349 * o consumption_weight: a1=1 ; a2=1
350 * o sharing_penalty: p1=1 ; p2=0
357 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
358 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 0);
360 Sys.expand(sys_cnst, rho_1, 1);
361 Sys.expand(sys_cnst, rho_2, 1);
364 REQUIRE(double_equals(rho_1->get_value(), 10, sg_precision_workamount));
365 REQUIRE(double_equals(rho_2->get_value(), 0, sg_precision_workamount));
368 SECTION("2 activity, 90% C")
371 * 2 similar variables degrades performance, but get same share
374 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < .9C
375 * o consumption_weight: a1=1 ; a2=1
376 * o sharing_penalty: p1=1 ; p2=1
380 * o rho1 + rho2 = C (because all weights are 1)
383 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
384 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
386 Sys.expand(sys_cnst, rho_1, 1);
387 Sys.expand(sys_cnst, rho_2, 1);
390 REQUIRE(double_equals(rho_1->get_value(), 4.5, sg_precision_workamount));
391 REQUIRE(double_equals(rho_1->get_value(), 4.5, sg_precision_workamount));
394 SECTION("3 activity, 80% C")
397 * 3 similar variables degrades performance, sharing proportional to penalty
400 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 + a3 * p3 * \rho3 < .8C
401 * o consumption_weight: a1=1 ; a2=1 ; a3=1
402 * o sharing_penalty: p1=1 ; p2=3 ; p3=4
405 * o rho1 = 2*rho2 = 2*rho3
406 * 0 rho1 = 4, rho2 = 2, rho3 = 2
407 * o rho1 + rho2 + rho3 = .8C (because all weights are 1)
410 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
411 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2);
412 lmm::Variable* rho_3 = Sys.variable_new(nullptr, 2);
414 Sys.expand(sys_cnst, rho_1, 1);
415 Sys.expand(sys_cnst, rho_2, 1);
416 Sys.expand(sys_cnst, rho_3, 1);
419 REQUIRE(double_equals(rho_1->get_value(), 4, sg_precision_workamount));
420 REQUIRE(double_equals(rho_2->get_value(), 2, sg_precision_workamount));
421 REQUIRE(double_equals(rho_3->get_value(), 2, sg_precision_workamount));
424 Sys.variable_free_all();
427 TEST_CASE("kernel::lmm shared systems with crosstraffic", "[kernel-lmm-shared-crosstraffic]")
429 lmm::MaxMin Sys(false);
431 SECTION("3 flows, 3 resource: crosstraffic")
434 * 3 flows sharing 2 constraints, single
437 * o System: a1 * \rho1 + a2 * \rho2 + epsilon * \rho3 < C1
438 * epsilon * \rho1 + epsilon * \rho2 + a3 * \rho3 < C2
439 * o consumption_weight: a1=1, a2=1, a3=1, epsilon=0.05
443 * o rho1 = rho2 = rho3 = 1/2
445 lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
446 lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
447 lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
448 lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 2);
449 lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 2);
451 double epsilon = 0.05;
452 Sys.expand(sys_cnst, rho_1, 1.0);
453 Sys.expand(sys_cnst2, rho_1, epsilon);
454 Sys.expand(sys_cnst, rho_2, 1.0);
455 Sys.expand(sys_cnst2, rho_2, epsilon);
456 Sys.expand(sys_cnst2, rho_3, 1.0);
457 Sys.expand(sys_cnst, rho_3, epsilon);
460 REQUIRE(double_equals(rho_1->get_value(), 1.0 / (2.0 + epsilon), sg_precision_workamount));
461 REQUIRE(double_equals(rho_2->get_value(), 1.0 / (2.0 + epsilon), sg_precision_workamount));
462 REQUIRE(double_equals(rho_3->get_value(), 1.0 / (2.0 + epsilon), sg_precision_workamount));
465 Sys.variable_free_all();