 Algorithmique Numérique Distribuée Public GIT Repository
3449a32667213e576f238e6dbc04e8f8b9850fcc
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 resolves inequations systems.
20  *
21  * Most SimGrid model rely on a "fluid/steady-state" modeling that
22  * samount to share 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  * Constraint:
53  *  - bound (set)
54  *  - shared (set)
55  *  - usage (computed)
56  * Variable:
57  *  - weight (set)
58  *  - bound (set)
59  *  - value (computed)
60  * Element:
61  *  - value (set)
62  *
63  * A possible system could be:
64  * - three variables: var1, var2, var3
65  * - two constraints: cons1, cons2
66  * - four elements linking:
67  *  - elem1 linking var1 and cons1
68  *  - elem2 linking var2 and cons1
69  *  - elem3 linking var2 and cons2
70  *  - elem4 linking var3 and cons2
71  *
72  * And the corresponding inequations will be:
73  *
74  *     var1.value <= var1.bound
75  *     var2.value <= var2.bound
76  *     var3.value <= var3.bound
77  *     var1.weight * var1.value * elem1.value + var2.weight * var2.value * elem2.value <= cons1.bound
78  *     var2.weight * var2.value * elem3.value + var3.weight * var3.value * elem4.value <= cons2.bound
79  *
80  * where var1.value, var2.value and var3.value are the unknown values
81  *
82  * if a constraint is not shared the sum is replace by a max
83  *
84  * Its usefull for the sharing of resources for various models.
85  * For instance for the network model the link are associated
86  * to consrtaint and the communications to variables.
87  */
89 XBT_PUBLIC_DATA(double) sg_maxmin_precision;
90 XBT_PUBLIC_DATA(double) sg_surf_precision;
92 static XBT_INLINE void double_update(double *variable, double value, double precision)
93 {
94   //printf("Updating %g -= %g +- %g\n",*variable,value,precision);
95   //xbt_assert(value==0  || value>precision);
96   //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...
98   *variable -= value;
99   if (*variable < precision)
100     *variable = 0.0;
101 }
103 static XBT_INLINE int double_positive(double value, double precision)
104 {
105   return (value > precision);
106 }
108 static XBT_INLINE int double_equals(double value1, double value2, double precision)
109 {
110   return (fabs(value1 - value2) < precision);
111 }
113 SG_BEGIN_DECL()
115 /** @{ @ingroup SURF_lmm */
116 /**
117  * @brief Create a new Linear MaxMim system
118  *
119  * @param selective_update [description]
120  */
121 XBT_PUBLIC(lmm_system_t) lmm_system_new(int selective_update);
123 /**
124  * @brief Free an existing Linear MaxMin system
125  *
126  * @param sys The lmm system to free
127  */
128 XBT_PUBLIC(void) lmm_system_free(lmm_system_t sys);
130 /**
131  * @brief Create a new Linear MaxMin constraint
132  *
133  * @param sys The system in which we add a constraint
134  * @param id Data associated to the constraint (e.g.: a network link)
135  * @param bound_value The bound value of the constraint
136  */
137 XBT_PUBLIC(lmm_constraint_t) lmm_constraint_new(lmm_system_t sys, void *id,
138                                                 double bound_value);
140 /**
141  * @brief Share a constraint
142  * @details [long description]
143  *
144  * @param cnst The constraint to share
145  */
146 XBT_PUBLIC(void) lmm_constraint_shared(lmm_constraint_t cnst);
148 /**
149  * @brief Check if a constraint is shared (shared by default)
150  *
151  * @param cnst The constraint to share
152  * @return 1 if shared, 0 otherwise
153  */
154 XBT_PUBLIC(int) lmm_constraint_is_shared(lmm_constraint_t cnst);
156 /**
157  * @brief Free a constraint
158  *
159  * @param sys The system associated to the constraint
160  * @param cnst The constraint to free
161  */
162 XBT_PUBLIC(void) lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst);
164 /**
165  * @brief Get the usage of the constraint after the last lmm solve
166  *
167  * @param cnst A constraint
168  * @return The usage of the constraint
169  */
170 XBT_PUBLIC(double) lmm_constraint_get_usage(lmm_constraint_t cnst);
172 /**
173  * @brief Create a new Linear MaxMin variable
174  *
175  * @param sys The system in which we add a constaint
176  * @param id Data associated to the variable (e.g.: a network communication)
177  * @param weight_value The weight of the variable (0.0 if not used)
178  * @param bound The maximum value of the variable (-1.0 if no maximum value)
179  * @param number_of_constraints The maximum number of constraint to associate to the variable
180  */
181 XBT_PUBLIC(lmm_variable_t) lmm_variable_new(lmm_system_t sys, void *id,
182                                             double weight_value,
183                                             double bound,
184                                             int number_of_constraints);
185 /**
186  * @brief Free a variable
187  *
188  * @param sys The system associated to the variable
189  * @param var The variable to free
190  */
191 XBT_PUBLIC(void) lmm_variable_free(lmm_system_t sys, lmm_variable_t var);
193 /**
194  * @brief Get the value of the variable after the last lmm solve
195  *
196  * @param var A variable
197  * @return The value of the variable
198  */
199 XBT_PUBLIC(double) lmm_variable_getvalue(lmm_variable_t var);
201 /**
202  * @brief Get the maximum value of the variable (-1.0 if no maximum value)
203  *
204  * @param var A variable
205  * @return The bound of the variable
206  */
207 XBT_PUBLIC(double) lmm_variable_getbound(lmm_variable_t var);
209 /**
210  * @brief Remove a variable from a constraint
211  *
212  * @param sys A system
213  * @param cnst A constraint
214  * @param var The variable to remove
215  */
216 XBT_PUBLIC(void) lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
217                             lmm_variable_t var);
219 /**
220  * @brief Associate a variable to a constraint with a coefficient
221  *
222  * @param sys A system
223  * @param cnst A constraint
224  * @param var A variable
225  * @param value The coefficient associated to the variable in the constraint
226  */
227 XBT_PUBLIC(void) lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
228                             lmm_variable_t var, double value);
230 /**
231  * @brief Add value to the coefficient between a constraint and a variable or
232  *        create one
233  *
234  * @param sys A system
235  * @param cnst A constraint
236  * @param var A variable
237  * @param value The value to add to the coefficient associated to the variable in the constraint
238  */
239 XBT_PUBLIC(void) lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
240                     lmm_variable_t var, double value);
242 /**
243  * @brief Get the numth constraint associated to the variable
244  *
245  * @param sys The system associated to the variable (not used)
246  * @param var A variable
247  * @param num The rank of constraint we want to get
248  * @return The numth constraint
249  */
250 XBT_PUBLIC(lmm_constraint_t) lmm_get_cnst_from_var(lmm_system_t sys,
251                                        lmm_variable_t var, int num);
253 /**
254  * @brief Get the weigth of the numth constraint associated to the variable
255  *
256  * @param sys The system associated to the variable (not used)
257  * @param var A variable
258  * @param num The rank of constraint we want to get
259  * @return The numth constraint
260  */
261 XBT_PUBLIC(double) lmm_get_cnst_weight_from_var(lmm_system_t sys, lmm_variable_t var,
262                                     int num);
264 /**
265  * @brief Get the number of constraint associated to a variable
266  *
267  * @param sys The system associated to the variable (not used)
268  * @param var A variable
269  * @return The number of constraint associated to the variable
270  */
271 XBT_PUBLIC(int) lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var);
273 /**
274  * @brief Get a var associated to a constraint
275  * @details Get the first variable of the next variable of elem if elem is not NULL
276  *
277  * @param sys The system associated to the variable (not used)
278  * @param cnst A constraint
279  * @param elem A element of constraint of the constraint or NULL
280  * @return A variable associated to a constraint
281  */
282 XBT_PUBLIC(lmm_variable_t) lmm_get_var_from_cnst(lmm_system_t sys,
283                                      lmm_constraint_t cnst,
284                                      lmm_element_t * elem);
286 /**
287  * @brief Get a var associated to a constraint
288  * @details Get the first variable of the next variable of elem if elem is not NULL
289  *
290  * @param cnst A constraint
291  * @param elem A element of constraint of the constraint or NULL
292  * @param nextelem A element of constraint of the constraint or NULL, the one after elem
293  * @param numelem parameter representing the number of elements to go
294  *
295  * @return A variable associated to a constraint
296  */
297 XBT_PUBLIC(lmm_variable_t) lmm_get_var_from_cnst_safe(lmm_system_t /*sys*/,
298                                      lmm_constraint_t cnst,
299                                      lmm_element_t * elem,
300                                      lmm_element_t * nextelem,
301                                      int * numelem);
303 /**
304  * @brief Get the first active constraint of a system
305  *
306  * @param sys A system
307  * @return The first active constraint
308  */
309 XBT_PUBLIC(lmm_constraint_t) lmm_get_first_active_constraint(lmm_system_t sys);
311 /**
312  * @brief Get the next active constraint of a constraint in a system
313  *
314  * @param sys A system
315  * @param cnst An active constraint of the system
316  *
317  * @return The next active constraint
318  */
319 XBT_PUBLIC(lmm_constraint_t) lmm_get_next_active_constraint(lmm_system_t sys,
320                                                 lmm_constraint_t cnst);
322 #ifdef HAVE_LATENCY_BOUND_TRACKING
323 XBT_PUBLIC(int) lmm_is_variable_limited_by_latency(lmm_variable_t var);
324 #endif
326 /**
327  * @brief Get the data associated to a constraint
328  *
329  * @param cnst A constraint
330  * @return The data associated to the constraint
331  */
332 XBT_PUBLIC(void *) lmm_constraint_id(lmm_constraint_t cnst);
334 /**
335  * @brief Get the data associated to a variable
336  *
337  * @param var A variable
338  * @return The data associated to the variable
339  */
340 XBT_PUBLIC(void *) lmm_variable_id(lmm_variable_t var);
342 /**
343  * @brief Update the value of element linking the constraint and the variable
344  *
345  * @param sys A system
346  * @param cnst A constraint
347  * @param var A variable
348  * @param value The new value
349  */
350 XBT_PUBLIC(void) lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
351                 lmm_variable_t var, double value);
353 /**
354  * @brief Update the bound of a variable
355  *
356  * @param sys A system
357  * @param var A constraint
358  * @param bound The new bound
359  */
360 XBT_PUBLIC(void) lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
361                                double bound);
363 /**
364  * @brief Update the weight of a variable
365  *
366  * @param sys A system
367  * @param var A variable
368  * @param weight The new weight of the variable
369  */
370 XBT_PUBLIC(void) lmm_update_variable_weight(lmm_system_t sys,
371                                             lmm_variable_t var,
372                                             double weight);
374 /**
375  * @brief Get the weight of a variable
376  *
377  * @param var A variable
378  * @return The weight of the variable
379  */
380 XBT_PUBLIC(double) lmm_get_variable_weight(lmm_variable_t var);
382 /**
383  * @brief Update a constraint bound
384  *
385  * @param sys A system
386  * @param cnst A constraint
387  * @param bound The new bound of the consrtaint
388  */
389 XBT_PUBLIC(void) lmm_update_constraint_bound(lmm_system_t sys,
390                                              lmm_constraint_t cnst,
391                                              double bound);
393 /**
394  * @brief [brief description]
395  *
396  * @param sys A system
397  * @param cnst A constraint
398  * @return [description]
399  */
400 XBT_PUBLIC(int) lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst);
402 /**
403  * @brief Solve the lmm system
404  *
405  * @param sys The lmm system to solve
406  */
407 XBT_PUBLIC(void) lmm_solve(lmm_system_t sys);
409 XBT_PUBLIC(void) lagrange_solve(lmm_system_t sys);
410 XBT_PUBLIC(void) bottleneck_solve(lmm_system_t sys);
412 /**
413  * Default functions associated to the chosen protocol. When
414  * using the lagrangian approach.
415  */
417 XBT_PUBLIC(void) lmm_set_default_protocol_function(double (*func_f)
418                                                     (lmm_variable_t var,
419                                                      double x),
420                                                    double (*func_fp)
421                                                     (lmm_variable_t var,
422                                                      double x),
423                                                    double (*func_fpi)
424                                                     (lmm_variable_t var,
425                                                      double x));
427 XBT_PUBLIC(double func_reno_f) (lmm_variable_t var, double x);
428 XBT_PUBLIC(double func_reno_fp) (lmm_variable_t var, double x);
429 XBT_PUBLIC(double func_reno_fpi) (lmm_variable_t var, double x);
431 XBT_PUBLIC(double func_reno2_f) (lmm_variable_t var, double x);
432 XBT_PUBLIC(double func_reno2_fp) (lmm_variable_t var, double x);
433 XBT_PUBLIC(double func_reno2_fpi) (lmm_variable_t var, double x);
435 XBT_PUBLIC(double func_vegas_f) (lmm_variable_t var, double x);
436 XBT_PUBLIC(double func_vegas_fp) (lmm_variable_t var, double x);
437 XBT_PUBLIC(double func_vegas_fpi) (lmm_variable_t var, double x);
439 /** @} */
440 SG_END_DECL()
442 #endif                          /* _SURF_MAXMIN_H */