1 /* Copyright (c) 2019-2020. 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"
8 #include "src/surf/surf_interface.hpp"
11 namespace lmm = simgrid::kernel::lmm;
13 TEST_CASE("kernel::lmm Single constraint shared systems", "[kernel-lmm-shared-single-sys]")
15 lmm::System* Sys = lmm::make_new_maxmin_system(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_maxmin_precision));
41 REQUIRE(double_equals(rho_2->get_value(), 1, sg_maxmin_precision));
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_maxmin_precision));
69 REQUIRE(double_equals(rho_2->get_value(), 1, sg_maxmin_precision));
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_maxmin_precision));
98 REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_maxmin_precision));
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_maxmin_precision));
138 REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_maxmin_precision));
139 REQUIRE(double_equals(rho_3->get_value(), 60 - 2 * rho_1_share, sg_maxmin_precision));
142 Sys->variable_free_all();
146 TEST_CASE("kernel::lmm Single constraint unshared systems", "[kernel-lmm-unshared-single-sys]")
148 lmm::System* Sys = lmm::make_new_maxmin_system(false);
150 SECTION("Variable penalty")
153 * A variable with a penalty of two get half of the max_share
156 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
157 * o consumption_weight: a1=1 ; a2=1
158 * o sharing_penalty: p1=1 ; p2=2
159 * o max_share: max(C1/(a1/p1),C1/(a2/p2))
163 * o rho2 = max_share/2 (because penalty of rho2 is 2)
166 lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
167 sys_cnst->unshare(); // FATPIPE
168 lmm::Variable* rho_1 = Sys->variable_new(nullptr, 1);
169 lmm::Variable* rho_2 = Sys->variable_new(nullptr, 2);
171 Sys->expand(sys_cnst, rho_1, 1);
172 Sys->expand(sys_cnst, rho_2, 1);
175 REQUIRE(double_equals(rho_1->get_value(), 10, sg_maxmin_precision));
176 REQUIRE(double_equals(rho_2->get_value(), 10 / 2, sg_maxmin_precision));
179 SECTION("Consumption weight")
182 * In a given constraint with all variable penalty to 1,
183 * the max_share is affected only by the maximum consumption weight
186 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
187 * o consumption_weight: a1=1 ; a2=1
188 * o sharing_penalty: p1=1 ; p2=2
189 * o max_share: max(C1/(a1/p1),C1/(a2/p2))
192 * o rho1 = max_share/2 (because penalty of rho1 is 1)
193 * o rho2 = max_share/2 (because penalty of rho2 is 1)
196 lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
197 sys_cnst->unshare(); // FATPIPE
198 lmm::Variable* rho_1 = Sys->variable_new(nullptr, 1);
199 lmm::Variable* rho_2 = Sys->variable_new(nullptr, 1);
201 Sys->expand(sys_cnst, rho_1, 1);
202 Sys->expand(sys_cnst, rho_2, 2);
205 REQUIRE(double_equals(rho_1->get_value(), 5, sg_maxmin_precision));
206 REQUIRE(double_equals(rho_2->get_value(), 5, sg_maxmin_precision));
209 SECTION("Consumption weight + variable penalty")
212 * Resource proportionality between variable is kept but
213 * constraint bound can be violated
216 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
217 * o consumption_weight: a1=1 ; a2=2
218 * o sharing_penalty: p1=1 ; p2=2
221 * o rho1 = 2 * rho2 (because rho2 has twice the penalty)
222 * o rho1 + 2*rho2 can be greater than C
223 * o rho1 <= C and 2*rho2 <= C
226 lmm::Constraint* sys_cnst = Sys->constraint_new(nullptr, 10);
228 lmm::Variable* sys_var_1 = Sys->variable_new(nullptr, 1);
229 lmm::Variable* sys_var_2 = Sys->variable_new(nullptr, 2);
231 Sys->expand(sys_cnst, sys_var_1, 1);
232 Sys->expand(sys_cnst, sys_var_2, 2);
235 REQUIRE(double_equals(sys_var_1->get_value(), 10, sg_maxmin_precision));
236 REQUIRE(double_equals(sys_var_2->get_value(), 5, sg_maxmin_precision));
239 SECTION("Multiple constraints systems")
242 * Multiple constraint systems can be solved with shared variables
243 * on unshared constraints.
246 * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
247 * a3 * p1 * \rho1 + a4 * p3 * \rho3 < C2
248 * o consumption_weight: a1=1 ; a2=2 ; a3=2 ; a4=1
249 * o sharing_penalty: p1=1 ; p2=2 ; p3=1
250 * o load: load_1=C1/max(p1/a1,p2/a2)=20 ; load_2=C2/max(a3/p1,a4/p3)=30
253 * o First constraint will be solve first (because load_1 < load_2)
254 * o Second constraint load will not be updated !
255 * o Each constraint should satisfy max(a_i * rho_i) <= C_r
258 lmm::Constraint* sys_cnst_1 = Sys->constraint_new(nullptr, 10);
259 lmm::Constraint* sys_cnst_2 = Sys->constraint_new(nullptr, 60);
260 sys_cnst_1->unshare(); // FATPIPE
261 sys_cnst_2->unshare();
263 lmm::Variable* rho_1 = Sys->variable_new(nullptr, 1, -1, 2);
264 lmm::Variable* rho_2 = Sys->variable_new(nullptr, 2, -1, 1);
265 lmm::Variable* rho_3 = Sys->variable_new(nullptr, 1, -1, 1);
268 Sys->expand(sys_cnst_1, rho_1, 1);
269 Sys->expand(sys_cnst_1, rho_2, 2);
272 Sys->expand(sys_cnst_2, rho_1, 2);
273 Sys->expand(sys_cnst_2, rho_3, 1);
276 double rho_1_share = 10; // Start by solving the first constraint (results is the same as previous tests)
277 REQUIRE(double_equals(rho_1->get_value(), rho_1_share, sg_maxmin_precision));
278 REQUIRE(double_equals(rho_2->get_value(), rho_1_share / 2, sg_maxmin_precision));
279 REQUIRE(double_equals(rho_3->get_value(), 60, sg_maxmin_precision));
282 Sys->variable_free_all();