 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);
221 /**
222  * @brief Reset the concurrency maximum for a given variable (we will update the maximum to reflect constraint evolution).
223  *
224  * @param cnst A constraint
225  *
226 */
227 XBT_PUBLIC(void) lmm_constraint_concurrency_maximum_reset(lmm_constraint_t cnst);
230 /**
231  * @brief Get the concurrency maximum for a given variable (which reflects constraint evolution).
232  *
233  * @param cnst A constraint
234  * @return the maximum concurrency of the constraint
235  */
236 XBT_PUBLIC(int) lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst);
239 /**
240  * @brief Create a new Linear MaxMin variable
241  *
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
247  */
248 XBT_PUBLIC(lmm_variable_t) lmm_variable_new(lmm_system_t sys, void *id,
249                                             double weight_value,
250                                             double bound,
251                                             int number_of_constraints);
252 /**
253  * @brief Free a variable
254  *
255  * @param sys The system associated to the variable
256  * @param var The variable to free
257  */
258 XBT_PUBLIC(void) lmm_variable_free(lmm_system_t sys, lmm_variable_t var);
260 /**
261  * @brief Get the value of the variable after the last lmm solve
262  *
263  * @param var A variable
264  * @return The value of the variable
265  */
266 XBT_PUBLIC(double) lmm_variable_getvalue(lmm_variable_t var);
268 /**
269  * @brief Get the maximum value of the variable (-1.0 if no maximum value)
270  *
271  * @param var A variable
272  * @return The bound of the variable
273  */
274 XBT_PUBLIC(double) lmm_variable_getbound(lmm_variable_t var);
276 /**
277  * @brief Set the concurrent share of the variable
278  *
279  * @param var A variable
280  * @param concurrency_share The new concurrency share
281  */
282 XBT_PUBLIC(void) lmm_variable_concurrency_share_set(lmm_variable_t var, short int concurrency_share);
284 /**
285  * @brief Remove a variable from a constraint
286  *
287  * @param sys A system
288  * @param cnst A constraint
289  * @param var The variable to remove
290  */
291 XBT_PUBLIC(void) lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
292                             lmm_variable_t var);
294 /**
295  * @brief Associate a variable to a constraint with a coefficient
296  *
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
301  */
302 XBT_PUBLIC(void) lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
303                             lmm_variable_t var, double value);
305 /**
306  * @brief Add value to the coefficient between a constraint and a variable or
307  *        create one
308  *
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
313  */
314 XBT_PUBLIC(void) lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
315                     lmm_variable_t var, double value);
317 /**
318  * @brief Get the numth constraint associated to the variable
319  *
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
324  */
325 XBT_PUBLIC(lmm_constraint_t) lmm_get_cnst_from_var(lmm_system_t sys,
326                                        lmm_variable_t var, int num);
328 /**
329  * @brief Get the weigth of the numth constraint associated to the variable
330  *
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
335  */
336 XBT_PUBLIC(double) lmm_get_cnst_weight_from_var(lmm_system_t sys, lmm_variable_t var,
337                                     int num);
339 /**
340  * @brief Get the number of constraint associated to a variable
341  *
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
345  */
346 XBT_PUBLIC(int) lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var);
348 /**
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
351  *
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
356  */
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);
361 /**
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
364  *
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
369  *
370  * @return A variable associated to a constraint
371  */
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,
376                                      int * numelem);
378 /**
379  * @brief Get the first active constraint of a system
380  *
381  * @param sys A system
382  * @return The first active constraint
383  */
384 XBT_PUBLIC(lmm_constraint_t) lmm_get_first_active_constraint(lmm_system_t sys);
386 /**
387  * @brief Get the next active constraint of a constraint in a system
388  *
389  * @param sys A system
390  * @param cnst An active constraint of the system
391  *
392  * @return The next active constraint
393  */
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);
399 #endif
401 /**
402  * @brief Get the data associated to a constraint
403  *
404  * @param cnst A constraint
405  * @return The data associated to the constraint
406  */
407 XBT_PUBLIC(void *) lmm_constraint_id(lmm_constraint_t cnst);
409 /**
410  * @brief Get the data associated to a variable
411  *
412  * @param var A variable
413  * @return The data associated to the variable
414  */
415 XBT_PUBLIC(void *) lmm_variable_id(lmm_variable_t var);
417 /**
418  * @brief Update the value of element linking the constraint and the variable
419  *
420  * @param sys A system
421  * @param cnst A constraint
422  * @param var A variable
423  * @param value The new value
424  */
425 XBT_PUBLIC(void) lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
426                 lmm_variable_t var, double value);
428 /**
429  * @brief Update the bound of a variable
430  *
431  * @param sys A system
432  * @param var A constraint
433  * @param bound The new bound
434  */
435 XBT_PUBLIC(void) lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
436                                double bound);
438 /**
439  * @brief Update the weight of a variable
440  *
441  * @param sys A system
442  * @param var A variable
443  * @param weight The new weight of the variable
444  */
445 XBT_PUBLIC(void) lmm_update_variable_weight(lmm_system_t sys,
446                                             lmm_variable_t var,
447                                             double weight);
449 /**
450  * @brief Get the weight of a variable
451  *
452  * @param var A variable
453  * @return The weight of the variable
454  */
455 XBT_PUBLIC(double) lmm_get_variable_weight(lmm_variable_t var);
457 /**
458  * @brief Update a constraint bound
459  *
460  * @param sys A system
461  * @param cnst A constraint
462  * @param bound The new bound of the consrtaint
463  */
464 XBT_PUBLIC(void) lmm_update_constraint_bound(lmm_system_t sys,
465                                              lmm_constraint_t cnst,
466                                              double bound);
468 /**
469  * @brief [brief description]
470  *
471  * @param sys A system
472  * @param cnst A constraint
473  * @return [description]
474  */
475 XBT_PUBLIC(int) lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst);
477 /**
478  * @brief Solve the lmm system
479  *
480  * @param sys The lmm system to solve
481  */
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);
487 /**
488  * Default functions associated to the chosen protocol. When
489  * using the lagrangian approach.
490  */
492 XBT_PUBLIC(void) lmm_set_default_protocol_function(double (*func_f)
493                                                     (lmm_variable_t var,
494                                                      double x),
495                                                    double (*func_fp)
496                                                     (lmm_variable_t var,
497                                                      double x),
498                                                    double (*func_fpi)
499                                                     (lmm_variable_t var,
500                                                      double x));
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);
514 /** @} */
515 SG_END_DECL()
517 #endif                          /* _SURF_MAXMIN_H */