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);
221 * @brief Gets the concurrency limit for this constraint
223 * @param cnst A constraint
224 * @return The concurrency limit used by this constraint
226 XBT_PUBLIC(int) lmm_constraint_concurrency_limit_get(lmm_constraint_t cnst);
230 * @brief Reset the concurrency maximum for a given variable (we will update the maximum to reflect constraint evolution).
232 * @param cnst A constraint
235 XBT_PUBLIC(void) lmm_constraint_concurrency_maximum_reset(lmm_constraint_t cnst);
239 * @brief Get the concurrency maximum for a given variable (which reflects constraint evolution).
241 * @param cnst A constraint
242 * @return the maximum concurrency of the constraint
244 XBT_PUBLIC(int) lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst);
248 * @brief Create a new Linear MaxMin variable
250 * @param sys The system in which we add a constaint
251 * @param id Data associated to the variable (e.g.: a network communication)
252 * @param weight_value The weight of the variable (0.0 if not used)
253 * @param bound The maximum value of the variable (-1.0 if no maximum value)
254 * @param number_of_constraints The maximum number of constraint to associate to the variable
256 XBT_PUBLIC(lmm_variable_t) lmm_variable_new(lmm_system_t sys, void *id,
259 int number_of_constraints);
261 * @brief Free a variable
263 * @param sys The system associated to the variable
264 * @param var The variable to free
266 XBT_PUBLIC(void) lmm_variable_free(lmm_system_t sys, lmm_variable_t var);
269 * @brief Get the value of the variable after the last lmm solve
271 * @param var A variable
272 * @return The value of the variable
274 XBT_PUBLIC(double) lmm_variable_getvalue(lmm_variable_t var);
277 * @brief Get the maximum value of the variable (-1.0 if no maximum value)
279 * @param var A variable
280 * @return The bound of the variable
282 XBT_PUBLIC(double) lmm_variable_getbound(lmm_variable_t var);
285 * @brief Set the concurrent share of the variable
287 * @param var A variable
288 * @param concurrency_share The new concurrency share
290 XBT_PUBLIC(void) lmm_variable_concurrency_share_set(lmm_variable_t var, short int concurrency_share);
293 * @brief Remove a variable from a constraint
295 * @param sys A system
296 * @param cnst A constraint
297 * @param var The variable to remove
299 XBT_PUBLIC(void) lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
303 * @brief Associate a variable to a constraint with a coefficient
305 * @param sys A system
306 * @param cnst A constraint
307 * @param var A variable
308 * @param value The coefficient associated to the variable in the constraint
310 XBT_PUBLIC(void) lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
311 lmm_variable_t var, double value);
314 * @brief Add value to the coefficient between a constraint and a variable or
317 * @param sys A system
318 * @param cnst A constraint
319 * @param var A variable
320 * @param value The value to add to the coefficient associated to the variable in the constraint
322 XBT_PUBLIC(void) lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
323 lmm_variable_t var, double value);
326 * @brief Get the numth constraint associated to the variable
328 * @param sys The system associated to the variable (not used)
329 * @param var A variable
330 * @param num The rank of constraint we want to get
331 * @return The numth constraint
333 XBT_PUBLIC(lmm_constraint_t) lmm_get_cnst_from_var(lmm_system_t sys,
334 lmm_variable_t var, int num);
337 * @brief Get the weigth of the numth constraint associated to the variable
339 * @param sys The system associated to the variable (not used)
340 * @param var A variable
341 * @param num The rank of constraint we want to get
342 * @return The numth constraint
344 XBT_PUBLIC(double) lmm_get_cnst_weight_from_var(lmm_system_t sys, lmm_variable_t var,
348 * @brief Get the number of constraint associated to a variable
350 * @param sys The system associated to the variable (not used)
351 * @param var A variable
352 * @return The number of constraint associated to the variable
354 XBT_PUBLIC(int) lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var);
357 * @brief Get a var associated to a constraint
358 * @details Get the first variable of the next variable of elem if elem is not NULL
360 * @param sys The system associated to the variable (not used)
361 * @param cnst A constraint
362 * @param elem A element of constraint of the constraint or NULL
363 * @return A variable associated to a constraint
365 XBT_PUBLIC(lmm_variable_t) lmm_get_var_from_cnst(lmm_system_t sys,
366 lmm_constraint_t cnst,
367 lmm_element_t * elem);
370 * @brief Get a var associated to a constraint
371 * @details Get the first variable of the next variable of elem if elem is not NULL
373 * @param cnst A constraint
374 * @param elem A element of constraint of the constraint or NULL
375 * @param nextelem A element of constraint of the constraint or NULL, the one after elem
376 * @param numelem parameter representing the number of elements to go
378 * @return A variable associated to a constraint
380 XBT_PUBLIC(lmm_variable_t) lmm_get_var_from_cnst_safe(lmm_system_t /*sys*/,
381 lmm_constraint_t cnst,
382 lmm_element_t * elem,
383 lmm_element_t * nextelem,
387 * @brief Get the first active constraint of a system
389 * @param sys A system
390 * @return The first active constraint
392 XBT_PUBLIC(lmm_constraint_t) lmm_get_first_active_constraint(lmm_system_t sys);
395 * @brief Get the next active constraint of a constraint in a system
397 * @param sys A system
398 * @param cnst An active constraint of the system
400 * @return The next active constraint
402 XBT_PUBLIC(lmm_constraint_t) lmm_get_next_active_constraint(lmm_system_t sys,
403 lmm_constraint_t cnst);
405 #ifdef HAVE_LATENCY_BOUND_TRACKING
406 XBT_PUBLIC(int) lmm_is_variable_limited_by_latency(lmm_variable_t var);
410 * @brief Get the data associated to a constraint
412 * @param cnst A constraint
413 * @return The data associated to the constraint
415 XBT_PUBLIC(void *) lmm_constraint_id(lmm_constraint_t cnst);
418 * @brief Get the data associated to a variable
420 * @param var A variable
421 * @return The data associated to the variable
423 XBT_PUBLIC(void *) lmm_variable_id(lmm_variable_t var);
426 * @brief Update the value of element linking the constraint and the variable
428 * @param sys A system
429 * @param cnst A constraint
430 * @param var A variable
431 * @param value The new value
433 XBT_PUBLIC(void) lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
434 lmm_variable_t var, double value);
437 * @brief Update the bound of a variable
439 * @param sys A system
440 * @param var A constraint
441 * @param bound The new bound
443 XBT_PUBLIC(void) lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
447 * @brief Update the weight of a variable
449 * @param sys A system
450 * @param var A variable
451 * @param weight The new weight of the variable
453 XBT_PUBLIC(void) lmm_update_variable_weight(lmm_system_t sys,
458 * @brief Get the weight of a variable
460 * @param var A variable
461 * @return The weight of the variable
463 XBT_PUBLIC(double) lmm_get_variable_weight(lmm_variable_t var);
466 * @brief Update a constraint bound
468 * @param sys A system
469 * @param cnst A constraint
470 * @param bound The new bound of the consrtaint
472 XBT_PUBLIC(void) lmm_update_constraint_bound(lmm_system_t sys,
473 lmm_constraint_t cnst,
477 * @brief [brief description]
479 * @param sys A system
480 * @param cnst A constraint
481 * @return [description]
483 XBT_PUBLIC(int) lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst);
486 * @brief Print the lmm system
488 * @param sys The lmm system to print
490 XBT_PUBLIC(void) lmm_print(lmm_system_t sys);
493 * @brief Solve the lmm system
495 * @param sys The lmm system to solve
497 XBT_PUBLIC(void) lmm_solve(lmm_system_t sys);
499 XBT_PUBLIC(void) lagrange_solve(lmm_system_t sys);
500 XBT_PUBLIC(void) bottleneck_solve(lmm_system_t sys);
503 * Default functions associated to the chosen protocol. When
504 * using the lagrangian approach.
507 XBT_PUBLIC(void) lmm_set_default_protocol_function(double (*func_f)
517 XBT_PUBLIC(double func_reno_f) (lmm_variable_t var, double x);
518 XBT_PUBLIC(double func_reno_fp) (lmm_variable_t var, double x);
519 XBT_PUBLIC(double func_reno_fpi) (lmm_variable_t var, double x);
521 XBT_PUBLIC(double func_reno2_f) (lmm_variable_t var, double x);
522 XBT_PUBLIC(double func_reno2_fp) (lmm_variable_t var, double x);
523 XBT_PUBLIC(double func_reno2_fpi) (lmm_variable_t var, double x);
525 XBT_PUBLIC(double func_vegas_f) (lmm_variable_t var, double x);
526 XBT_PUBLIC(double func_vegas_fp) (lmm_variable_t var, double x);
527 XBT_PUBLIC(double func_vegas_fpi) (lmm_variable_t var, double x);
532 #endif /* _SURF_MAXMIN_H */