1 /* Copyright (c) 2004-2015. The SimGrid Team.
2 * All rights reserved. */
4 /* This program is free software; you can redistribute it and/or modify it
5 * under the terms of the license (GNU LGPL) which comes with this package. */
10 #include "src/portable.h"
12 #include "xbt/asserts.h"
13 #include "surf/datatypes.h"
17 /** @addtogroup SURF_lmm
19 * A linear maxmin solver to resolve inequations systems.
21 * Most SimGrid model rely on a "fluid/steady-state" modeling that
22 * simulate the sharing of resources between actions at relatively
23 * coarse-grain. Such sharing is generally done by solving a set of
24 * linear inequations. Let's take an example and assume we have the
25 * variables \f$x_1\f$, \f$x_2\f$, \f$x_3\f$, and \f$x_4\f$ . Let's
26 * say that \f$x_1\f$ and \f$x_2\f$ correspond to activities running
27 * and the same CPU \f$A\f$ whose capacity is \f$C_A\f$. In such a
28 * case, we need to enforce:
30 * \f[ x_1 + x_2 \leq C_A \f]
32 * Likewise, if \f$x_3\f$ (resp. \f$x_4\f$) corresponds to a network
33 * flow \f$F_3\f$ (resp. \f$F_4\f$) that goes through a set of links
34 * \f$L_1\f$ and \f$L_2\f$ (resp. \f$L_2\f$ and \f$L_3\f$), then we
37 * \f[ x_3 \leq C_{L_1} \f]
38 * \f[ x_3 + x_4 \leq C_{L_2} \f]
39 * \f[ x_4 \leq C_{L_3} \f]
41 * One could set every variable to 0 to make sure the constraints are
42 * satisfied but this would obviously not be very realistic. A
43 * possible objective is to try to maximize the minimum of the
44 * \f$x_i\f$ . This ensures that all the \f$x_i\f$ are positive and "as
47 * This is called *max-min fairness* and is the most commonly used
48 * objective in SimGrid. Another possibility is to maximize
49 * \f$\sum_if(x_i)\f$, where \f$f\f$ is a strictly increasing concave
66 * A possible system could be:
67 * - three variables: `var1`, `var2`, `var3`
68 * - two constraints: `cons1`, `cons2`
69 * - four elements linking:
70 * - `elem1` linking `var1` and `cons1`
71 * - `elem2` linking `var2` and `cons1`
72 * - `elem3` linking `var2` and `cons2`
73 * - `elem4` linking `var3` and `cons2`
75 * And the corresponding inequations will be:
77 * var1.value <= var1.bound
78 * var2.value <= var2.bound
79 * var3.value <= var3.bound
80 * var1.weight * var1.value * elem1.value + var2.weight * var2.value * elem2.value <= cons1.bound
81 * var2.weight * var2.value * elem3.value + var3.weight * var3.value * elem4.value <= cons2.bound
83 * where `var1.value`, `var2.value` and `var3.value` are the unknown values.
85 * If a constraint is not shared, the sum is replaced by a max.
86 * For example, a third non-shared constraint `cons3` and the associated elements `elem5` and `elem6` could write as:
88 * max( var1.weight * var1.value * elem5.value , var3.weight * var3.value * elem6.value ) <= cons3.bound
90 * This is usefull for the sharing of resources for various models.
91 * For instance, for the network model, each link is associated
92 * to a constraint and each communication to a variable.
95 * Implementation details
97 * For implementation reasons, we are interested in distinguishing variables that actually participate to the computation of constraints, and those who are part of the equations but are stuck to zero.
98 * We call enabled variables, those which var.weight is strictly positive. Zero-weight variables are called disabled variables.
99 * Unfortunately this concept of enabled/disabled variables intersects with active/inactive variable.
100 * Semantically, the intent is similar, but the conditions under which a variable is active is slightly more strict than the conditions for it to be enabled.
101 * A variable is active only if its var.value is non-zero (and, by construction, its var.weight is non-zero).
102 * In general, variables remain disabled after their creation, which often models an initialization phase (e.g. first packet propagating in the network). Then, it is enabled by the corresponding model. Afterwards, the max-min solver (lmm_solve()) activates it when appropriate. It is possible that the variable is again disabled, e.g. to model the pausing of an action.
105 * Concurrency limit and maximum
107 * We call concurrency, the number of variables that can be enabled at any time for each constraint.
108 * From a model perspective, this "concurrency" often represents the number of actions that actually compete for one constraint.
109 * The LMM solver is able to limit the concurrency for each constraint, and to monitor its maximum value.
111 * One may want to limit the concurrency of constraints for essentially three reasons:
112 * - Keep LMM system in a size that can be solved (it does not react very well with tens of thousands of variables per constraint)
113 * - Stay within parameters where the fluid model is accurate enough.
114 * - Model serialization effects
116 * The concurrency limit can also be set to a negative value to disable concurrency limit. This can improve performance slightly.
118 * Overall, each constraint contains three fields related to concurrency:
119 * - concurrency_limit which is the limit enforced by the solver
120 * - concurrency_current which is the current concurrency
121 * - concurrency_maximum which is the observed maximum concurrency
123 * Variables also have one field related to concurrency: concurrency_share.
124 * In effect, in some cases, one variable is involved multiple times (i.e. two elements) in a constraint.
125 * For example, cross-traffic is modeled using 2 elements per constraint.
126 * concurrency_share formally corresponds to the maximum number of elements that associate the variable and any given constraint.
129 XBT_PUBLIC_DATA(double) sg_maxmin_precision;
130 XBT_PUBLIC_DATA(double) sg_surf_precision;
132 static XBT_INLINE void double_update(double *variable, double value, double precision)
134 //printf("Updating %g -= %g +- %g\n",*variable,value,precision);
135 //xbt_assert(value==0 || value>precision);
136 //Check that precision is higher than the machine-dependent size of the mantissa. If not, brutal rounding may happen, and the precision mechanism is not active...
137 //xbt_assert(*variable< (2<<DBL_MANT_DIG)*precision && FLT_RADIX==2);
139 if (*variable < precision)
143 static XBT_INLINE int double_positive(double value, double precision)
145 return (value > precision);
148 static XBT_INLINE int double_equals(double value1, double value2, double precision)
150 return (fabs(value1 - value2) < precision);
155 /** @{ @ingroup SURF_lmm */
157 * @brief Create a new Linear MaxMim system
159 * @param selective_update [description]
161 XBT_PUBLIC(lmm_system_t) lmm_system_new(int selective_update);
164 * @brief Free an existing Linear MaxMin system
166 * @param sys The lmm system to free
168 XBT_PUBLIC(void) lmm_system_free(lmm_system_t sys);
171 * @brief Create a new Linear MaxMin constraint
173 * @param sys The system in which we add a constraint
174 * @param id Data associated to the constraint (e.g.: a network link)
175 * @param bound_value The bound value of the constraint
177 XBT_PUBLIC(lmm_constraint_t) lmm_constraint_new(lmm_system_t sys, void *id,
181 * @brief Share a constraint
182 * @details [long description]
184 * @param cnst The constraint to share
186 XBT_PUBLIC(void) lmm_constraint_shared(lmm_constraint_t cnst);
189 * @brief Check if a constraint is shared (shared by default)
191 * @param cnst The constraint to share
192 * @return 1 if shared, 0 otherwise
194 XBT_PUBLIC(int) lmm_constraint_sharing_policy(lmm_constraint_t cnst);
197 * @brief Free a constraint
199 * @param sys The system associated to the constraint
200 * @param cnst The constraint to free
202 XBT_PUBLIC(void) lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst);
205 * @brief Get the usage of the constraint after the last lmm solve
207 * @param cnst A constraint
208 * @return The usage of the constraint
210 XBT_PUBLIC(double) lmm_constraint_get_usage(lmm_constraint_t cnst);
213 * @brief Sets the concurrency limit for this constraint
215 * @param cnst A constraint
216 * @param concurrency_limit The concurrency limit to use for this constraint
218 XBT_PUBLIC(void) lmm_constraint_concurrency_limit_set(lmm_constraint_t cnst, int concurrency_limit);
222 * @brief Reset the concurrency maximum for a given variable (we will update the maximum to reflect constraint evolution).
224 * @param cnst A constraint
227 XBT_PUBLIC(void) lmm_constraint_concurrency_maximum_reset(lmm_constraint_t cnst);
231 * @brief Get the concurrency maximum for a given variable (which reflects constraint evolution).
233 * @param cnst A constraint
234 * @return the maximum concurrency of the constraint
236 XBT_PUBLIC(int) lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst);
240 * @brief Create a new Linear MaxMin variable
242 * @param sys The system in which we add a constaint
243 * @param id Data associated to the variable (e.g.: a network communication)
244 * @param weight_value The weight of the variable (0.0 if not used)
245 * @param bound The maximum value of the variable (-1.0 if no maximum value)
246 * @param number_of_constraints The maximum number of constraint to associate to the variable
248 XBT_PUBLIC(lmm_variable_t) lmm_variable_new(lmm_system_t sys, void *id,
251 int number_of_constraints);
253 * @brief Free a variable
255 * @param sys The system associated to the variable
256 * @param var The variable to free
258 XBT_PUBLIC(void) lmm_variable_free(lmm_system_t sys, lmm_variable_t var);
261 * @brief Get the value of the variable after the last lmm solve
263 * @param var A variable
264 * @return The value of the variable
266 XBT_PUBLIC(double) lmm_variable_getvalue(lmm_variable_t var);
269 * @brief Get the maximum value of the variable (-1.0 if no maximum value)
271 * @param var A variable
272 * @return The bound of the variable
274 XBT_PUBLIC(double) lmm_variable_getbound(lmm_variable_t var);
277 * @brief Set the concurrent share of the variable
279 * @param var A variable
280 * @param concurrency_share The new concurrency share
282 XBT_PUBLIC(void) lmm_variable_concurrency_share_set(lmm_variable_t var, short int concurrency_share);
285 * @brief Remove a variable from a constraint
287 * @param sys A system
288 * @param cnst A constraint
289 * @param var The variable to remove
291 XBT_PUBLIC(void) lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
295 * @brief Associate a variable to a constraint with a coefficient
297 * @param sys A system
298 * @param cnst A constraint
299 * @param var A variable
300 * @param value The coefficient associated to the variable in the constraint
302 XBT_PUBLIC(void) lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
303 lmm_variable_t var, double value);
306 * @brief Add value to the coefficient between a constraint and a variable or
309 * @param sys A system
310 * @param cnst A constraint
311 * @param var A variable
312 * @param value The value to add to the coefficient associated to the variable in the constraint
314 XBT_PUBLIC(void) lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
315 lmm_variable_t var, double value);
318 * @brief Get the numth constraint associated to the variable
320 * @param sys The system associated to the variable (not used)
321 * @param var A variable
322 * @param num The rank of constraint we want to get
323 * @return The numth constraint
325 XBT_PUBLIC(lmm_constraint_t) lmm_get_cnst_from_var(lmm_system_t sys,
326 lmm_variable_t var, int num);
329 * @brief Get the weigth of the numth constraint associated to the variable
331 * @param sys The system associated to the variable (not used)
332 * @param var A variable
333 * @param num The rank of constraint we want to get
334 * @return The numth constraint
336 XBT_PUBLIC(double) lmm_get_cnst_weight_from_var(lmm_system_t sys, lmm_variable_t var,
340 * @brief Get the number of constraint associated to a variable
342 * @param sys The system associated to the variable (not used)
343 * @param var A variable
344 * @return The number of constraint associated to the variable
346 XBT_PUBLIC(int) lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var);
349 * @brief Get a var associated to a constraint
350 * @details Get the first variable of the next variable of elem if elem is not NULL
352 * @param sys The system associated to the variable (not used)
353 * @param cnst A constraint
354 * @param elem A element of constraint of the constraint or NULL
355 * @return A variable associated to a constraint
357 XBT_PUBLIC(lmm_variable_t) lmm_get_var_from_cnst(lmm_system_t sys,
358 lmm_constraint_t cnst,
359 lmm_element_t * elem);
362 * @brief Get a var associated to a constraint
363 * @details Get the first variable of the next variable of elem if elem is not NULL
365 * @param cnst A constraint
366 * @param elem A element of constraint of the constraint or NULL
367 * @param nextelem A element of constraint of the constraint or NULL, the one after elem
368 * @param numelem parameter representing the number of elements to go
370 * @return A variable associated to a constraint
372 XBT_PUBLIC(lmm_variable_t) lmm_get_var_from_cnst_safe(lmm_system_t /*sys*/,
373 lmm_constraint_t cnst,
374 lmm_element_t * elem,
375 lmm_element_t * nextelem,
379 * @brief Get the first active constraint of a system
381 * @param sys A system
382 * @return The first active constraint
384 XBT_PUBLIC(lmm_constraint_t) lmm_get_first_active_constraint(lmm_system_t sys);
387 * @brief Get the next active constraint of a constraint in a system
389 * @param sys A system
390 * @param cnst An active constraint of the system
392 * @return The next active constraint
394 XBT_PUBLIC(lmm_constraint_t) lmm_get_next_active_constraint(lmm_system_t sys,
395 lmm_constraint_t cnst);
397 #ifdef HAVE_LATENCY_BOUND_TRACKING
398 XBT_PUBLIC(int) lmm_is_variable_limited_by_latency(lmm_variable_t var);
402 * @brief Get the data associated to a constraint
404 * @param cnst A constraint
405 * @return The data associated to the constraint
407 XBT_PUBLIC(void *) lmm_constraint_id(lmm_constraint_t cnst);
410 * @brief Get the data associated to a variable
412 * @param var A variable
413 * @return The data associated to the variable
415 XBT_PUBLIC(void *) lmm_variable_id(lmm_variable_t var);
418 * @brief Update the value of element linking the constraint and the variable
420 * @param sys A system
421 * @param cnst A constraint
422 * @param var A variable
423 * @param value The new value
425 XBT_PUBLIC(void) lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
426 lmm_variable_t var, double value);
429 * @brief Update the bound of a variable
431 * @param sys A system
432 * @param var A constraint
433 * @param bound The new bound
435 XBT_PUBLIC(void) lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
439 * @brief Update the weight of a variable
441 * @param sys A system
442 * @param var A variable
443 * @param weight The new weight of the variable
445 XBT_PUBLIC(void) lmm_update_variable_weight(lmm_system_t sys,
450 * @brief Get the weight of a variable
452 * @param var A variable
453 * @return The weight of the variable
455 XBT_PUBLIC(double) lmm_get_variable_weight(lmm_variable_t var);
458 * @brief Update a constraint bound
460 * @param sys A system
461 * @param cnst A constraint
462 * @param bound The new bound of the consrtaint
464 XBT_PUBLIC(void) lmm_update_constraint_bound(lmm_system_t sys,
465 lmm_constraint_t cnst,
469 * @brief [brief description]
471 * @param sys A system
472 * @param cnst A constraint
473 * @return [description]
475 XBT_PUBLIC(int) lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst);
478 * @brief Solve the lmm system
480 * @param sys The lmm system to solve
482 XBT_PUBLIC(void) lmm_solve(lmm_system_t sys);
484 XBT_PUBLIC(void) lagrange_solve(lmm_system_t sys);
485 XBT_PUBLIC(void) bottleneck_solve(lmm_system_t sys);
488 * Default functions associated to the chosen protocol. When
489 * using the lagrangian approach.
492 XBT_PUBLIC(void) lmm_set_default_protocol_function(double (*func_f)
502 XBT_PUBLIC(double func_reno_f) (lmm_variable_t var, double x);
503 XBT_PUBLIC(double func_reno_fp) (lmm_variable_t var, double x);
504 XBT_PUBLIC(double func_reno_fpi) (lmm_variable_t var, double x);
506 XBT_PUBLIC(double func_reno2_f) (lmm_variable_t var, double x);
507 XBT_PUBLIC(double func_reno2_fp) (lmm_variable_t var, double x);
508 XBT_PUBLIC(double func_reno2_fpi) (lmm_variable_t var, double x);
510 XBT_PUBLIC(double func_vegas_f) (lmm_variable_t var, double x);
511 XBT_PUBLIC(double func_vegas_fp) (lmm_variable_t var, double x);
512 XBT_PUBLIC(double func_vegas_fpi) (lmm_variable_t var, double x);
517 #endif /* _SURF_MAXMIN_H */