 Algorithmique Numérique Distribuée Public GIT Repository
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. */
7 #ifndef _SURF_MAXMIN_H
8 #define _SURF_MAXMIN_H
10 #include "src/portable.h"
11 #include "xbt/misc.h"
12 #include "xbt/asserts.h"
13 #include "surf/datatypes.h"
14 #include <math.h>
18  * @details
19  * A linear maxmin solver to resolve inequations systems.
20  *
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:
29  *
30  *   \f[ x_1 + x_2 \leq C_A \f]
31  *
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
35  * need to enforce:
36  *
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]
40  *
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
45  * large as possible".
46  *
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
50  * function.
51  *
52  *
53  * Constraint:
54  *  - bound (set)
55  *  - shared (set)
56  *  - usage (computed)
57  *
58  * Variable:
59  *  - weight (set)
60  *  - bound (set)
61  *  - value (computed)
62  *
63  * Element:
64  *  - value (set)
65  *
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
74  *
75  * And the corresponding inequations will be:
76  *
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
82  *
83  * where var1.value, var2.value and var3.value are the unknown values.
84  *
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:
87  *
88  *     max( var1.weight * var1.value * elem5.value  ,  var3.weight * var3.value * elem6.value ) <= cons3.bound
89  *
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.
93  *
94  *
95  * Implementation details
96  *
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.
103  *
104  *
105  * Concurrency limit and maximum
106  *
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.
110  *
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
115  *
116  * The concurrency limit can also be set to a negative value to disable concurrency limit. This can improve performance slightly.
117  *
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
122  *
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.
127  */
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)
133 {
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...
138   *variable -= value;
139   if (*variable < precision)
140     *variable = 0.0;
141 }
143 static XBT_INLINE int double_positive(double value, double precision)
144 {
145   return (value > precision);
146 }
148 static XBT_INLINE int double_equals(double value1, double value2, double precision)
149 {
150   return (fabs(value1 - value2) < precision);
151 }
153 SG_BEGIN_DECL()
155 /** @{ @ingroup SURF_lmm */
156 /**
157  * @brief Create a new Linear MaxMim system
158  *
159  * @param selective_update [description]
160  */
161 XBT_PUBLIC(lmm_system_t) lmm_system_new(int selective_update);
163 /**
164  * @brief Free an existing Linear MaxMin system
165  *
166  * @param sys The lmm system to free
167  */
168 XBT_PUBLIC(void) lmm_system_free(lmm_system_t sys);
170 /**
171  * @brief Create a new Linear MaxMin constraint
172  *
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
176  */
177 XBT_PUBLIC(lmm_constraint_t) lmm_constraint_new(lmm_system_t sys, void *id,
178                                                 double bound_value);
180 /**
181  * @brief Share a constraint
182  * @details [long description]
183  *
184  * @param cnst The constraint to share
185  */
186 XBT_PUBLIC(void) lmm_constraint_shared(lmm_constraint_t cnst);
188 /**
189  * @brief Check if a constraint is shared (shared by default)
190  *
191  * @param cnst The constraint to share
192  * @return 1 if shared, 0 otherwise
193  */
194 XBT_PUBLIC(int) lmm_constraint_sharing_policy(lmm_constraint_t cnst);
196 /**
197  * @brief Free a constraint
198  *
199  * @param sys The system associated to the constraint
200  * @param cnst The constraint to free
201  */
202 XBT_PUBLIC(void) lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst);
204 /**
205  * @brief Get the usage of the constraint after the last lmm solve
206  *
207  * @param cnst A constraint
208  * @return The usage of the constraint
209  */
210 XBT_PUBLIC(double) lmm_constraint_get_usage(lmm_constraint_t cnst);
212 /**
213  * @brief Sets the concurrency limit for this constraint
214  *
215  * @param cnst A constraint
216  * @param concurrency_limit The concurrency limit to use for this constraint
217  */
218 XBT_PUBLIC(void) lmm_constraint_concurrency_limit_set(lmm_constraint_t cnst, int concurrency_limit);
220 /**
221  * @brief Gets the concurrency limit for this constraint
222  *
223  * @param cnst A constraint
224  * @return The concurrency limit used by this constraint
225  */
226 XBT_PUBLIC(int) lmm_constraint_concurrency_limit_get(lmm_constraint_t cnst);
229 /**
230  * @brief Reset the concurrency maximum for a given variable (we will update the maximum to reflect constraint evolution).
231  *
232  * @param cnst A constraint
233  *
234 */
235 XBT_PUBLIC(void) lmm_constraint_concurrency_maximum_reset(lmm_constraint_t cnst);
238 /**
239  * @brief Get the concurrency maximum for a given variable (which reflects constraint evolution).
240  *
241  * @param cnst A constraint
242  * @return the maximum concurrency of the constraint
243  */
244 XBT_PUBLIC(int) lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst);
247 /**
248  * @brief Create a new Linear MaxMin variable
249  *
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
255  */
256 XBT_PUBLIC(lmm_variable_t) lmm_variable_new(lmm_system_t sys, void *id,
257                                             double weight_value,
258                                             double bound,
259                                             int number_of_constraints);
260 /**
261  * @brief Free a variable
262  *
263  * @param sys The system associated to the variable
264  * @param var The variable to free
265  */
266 XBT_PUBLIC(void) lmm_variable_free(lmm_system_t sys, lmm_variable_t var);
268 /**
269  * @brief Get the value of the variable after the last lmm solve
270  *
271  * @param var A variable
272  * @return The value of the variable
273  */
274 XBT_PUBLIC(double) lmm_variable_getvalue(lmm_variable_t var);
276 /**
277  * @brief Get the maximum value of the variable (-1.0 if no maximum value)
278  *
279  * @param var A variable
280  * @return The bound of the variable
281  */
282 XBT_PUBLIC(double) lmm_variable_getbound(lmm_variable_t var);
284 /**
285  * @brief Set the concurrent share of the variable
286  *
287  * @param var A variable
288  * @param concurrency_share The new concurrency share
289  */
290 XBT_PUBLIC(void) lmm_variable_concurrency_share_set(lmm_variable_t var, short int concurrency_share);
292 /**
293  * @brief Remove a variable from a constraint
294  *
295  * @param sys A system
296  * @param cnst A constraint
297  * @param var The variable to remove
298  */
299 XBT_PUBLIC(void) lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
300                             lmm_variable_t var);
302 /**
303  * @brief Associate a variable to a constraint with a coefficient
304  *
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
309  */
310 XBT_PUBLIC(void) lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
311                             lmm_variable_t var, double value);
313 /**
314  * @brief Add value to the coefficient between a constraint and a variable or
315  *        create one
316  *
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
321  */
322 XBT_PUBLIC(void) lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
323                     lmm_variable_t var, double value);
325 /**
326  * @brief Get the numth constraint associated to the variable
327  *
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
332  */
333 XBT_PUBLIC(lmm_constraint_t) lmm_get_cnst_from_var(lmm_system_t sys,
334                                        lmm_variable_t var, int num);
336 /**
337  * @brief Get the weigth of the numth constraint associated to the variable
338  *
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
343  */
344 XBT_PUBLIC(double) lmm_get_cnst_weight_from_var(lmm_system_t sys, lmm_variable_t var,
345                                     int num);
347 /**
348  * @brief Get the number of constraint associated to a variable
349  *
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
353  */
354 XBT_PUBLIC(int) lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var);
356 /**
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
359  *
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
364  */
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);
369 /**
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
372  *
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
377  *
378  * @return A variable associated to a constraint
379  */
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,
384                                      int * numelem);
386 /**
387  * @brief Get the first active constraint of a system
388  *
389  * @param sys A system
390  * @return The first active constraint
391  */
392 XBT_PUBLIC(lmm_constraint_t) lmm_get_first_active_constraint(lmm_system_t sys);
394 /**
395  * @brief Get the next active constraint of a constraint in a system
396  *
397  * @param sys A system
398  * @param cnst An active constraint of the system
399  *
400  * @return The next active constraint
401  */
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);
407 #endif
409 /**
410  * @brief Get the data associated to a constraint
411  *
412  * @param cnst A constraint
413  * @return The data associated to the constraint
414  */
415 XBT_PUBLIC(void *) lmm_constraint_id(lmm_constraint_t cnst);
417 /**
418  * @brief Get the data associated to a variable
419  *
420  * @param var A variable
421  * @return The data associated to the variable
422  */
423 XBT_PUBLIC(void *) lmm_variable_id(lmm_variable_t var);
425 /**
426  * @brief Update the value of element linking the constraint and the variable
427  *
428  * @param sys A system
429  * @param cnst A constraint
430  * @param var A variable
431  * @param value The new value
432  */
433 XBT_PUBLIC(void) lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
434                 lmm_variable_t var, double value);
436 /**
437  * @brief Update the bound of a variable
438  *
439  * @param sys A system
440  * @param var A constraint
441  * @param bound The new bound
442  */
443 XBT_PUBLIC(void) lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
444                                double bound);
446 /**
447  * @brief Update the weight of a variable
448  *
449  * @param sys A system
450  * @param var A variable
451  * @param weight The new weight of the variable
452  */
453 XBT_PUBLIC(void) lmm_update_variable_weight(lmm_system_t sys,
454                                             lmm_variable_t var,
455                                             double weight);
457 /**
458  * @brief Get the weight of a variable
459  *
460  * @param var A variable
461  * @return The weight of the variable
462  */
463 XBT_PUBLIC(double) lmm_get_variable_weight(lmm_variable_t var);
465 /**
466  * @brief Update a constraint bound
467  *
468  * @param sys A system
469  * @param cnst A constraint
470  * @param bound The new bound of the consrtaint
471  */
472 XBT_PUBLIC(void) lmm_update_constraint_bound(lmm_system_t sys,
473                                              lmm_constraint_t cnst,
474                                              double bound);
476 /**
477  * @brief [brief description]
478  *
479  * @param sys A system
480  * @param cnst A constraint
481  * @return [description]
482  */
483 XBT_PUBLIC(int) lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst);
485 /**
486  * @brief Print the lmm system
487  *
488  * @param sys The lmm system to print
489  */
490 XBT_PUBLIC(void) lmm_print(lmm_system_t sys);
492 /**
493  * @brief Solve the lmm system
494  *
495  * @param sys The lmm system to solve
496  */
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);
502 /**
503  * Default functions associated to the chosen protocol. When
504  * using the lagrangian approach.
505  */
507 XBT_PUBLIC(void) lmm_set_default_protocol_function(double (*func_f)
508                                                     (lmm_variable_t var,
509                                                      double x),
510                                                    double (*func_fp)
511                                                     (lmm_variable_t var,
512                                                      double x),
513                                                    double (*func_fpi)
514                                                     (lmm_variable_t var,
515                                                      double x));
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);
529 /** @} */
530 SG_END_DECL()
532 #endif                          /* _SURF_MAXMIN_H */