Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Merge branch 'master' of git+ssh://scm.gforge.inria.fr//gitroot/simgrid/simgrid
[simgrid.git] / src / include / surf / maxmin.h
1 /* Copyright (c) 2004-2014. The SimGrid Team.
2  * All rights reserved.                                                     */
3
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. */
6
7 #ifndef _SURF_MAXMIN_H
8 #define _SURF_MAXMIN_H
9
10 #include "portable.h"
11 #include "xbt/misc.h"
12 #include "surf/datatypes.h"
13 #include <math.h>
14
15
16 /** @addtogroup SURF_lmm 
17  * @details 
18  * A linear maxmin solver to resolves inequations systems.
19  * 
20  * A system is composed of variables, constraints and elements linking them.
21  * Constraint: 
22  *  - bound (set)
23  *  - shared (set)
24  *  - usage (computed)
25  * Variable:
26  *  - weight (set)
27  *  - bound (set)
28  *  - value (computed)
29  * Element:
30  *  - value (set)
31  * 
32  * A possible system could be:
33  * - three variables: `var1`, `var2`, `var3`
34  * - two constraints: `cons1`, `cons2`
35  * - four elements linking:
36  *  - `elem1` linking `var1` and `cons1`
37  *  - `elem2` linking `var2` and `cons1`
38  *  - `elem3` linking `var2` and `cons2`
39  *  - `elem4` linking `var3` and `cons2`
40  * 
41  * And the corresponding inequations will be:
42  * 
43  *     var1.value <= var1.bound
44  *     var2.value <= var2.bound
45  *     var3.value <= var3.bound
46  *     var1.weight * var1.value * elem1.value + var2.weight * var2.value * elem2.value <= cons1.bound
47  *     var2.weight * var2.value * elem3.value + var3.weight * var3.value * elem4.value <= cons2.bound
48  * 
49  * where `var1.value`, `var2.value` and `var3.value` are the unknown values
50  * 
51  * if a constraint is not shared the sum is replace by a max
52  * 
53  * Its usefull for the sharing of resources for various models.
54  * For instance for the network model the link are associated 
55  * to consrtaint and the communications to variables.
56  */
57
58 extern double sg_maxmin_precision;
59 #define MAXMIN_PRECISION sg_maxmin_precision
60 static XBT_INLINE void double_update(double *variable, double value)
61 {
62   *variable -= value;
63   if (*variable < MAXMIN_PRECISION)
64     *variable = 0.0;
65 }
66
67 static XBT_INLINE int double_positive(double value)
68 {
69   return (value > MAXMIN_PRECISION);
70 }
71
72 static XBT_INLINE int double_equals(double value1, double value2)
73 {
74   return (fabs(value1 - value2) < MAXMIN_PRECISION);
75 }
76
77 SG_BEGIN_DECL()
78
79 /** @{ @ingroup SURF_lmm */
80 /**
81  * @brief Create a new Linear MaxMim system
82  * 
83  * @param selective_update [description]
84  */
85 XBT_PUBLIC(lmm_system_t) lmm_system_new(int selective_update);
86
87 /**
88  * @brief Free an existing Linear MaxMin system
89  * 
90  * @param sys The lmm system to free
91  */
92 XBT_PUBLIC(void) lmm_system_free(lmm_system_t sys);
93
94 /**
95  * @brief Create a new Linear MaxMin constraint
96  * 
97  * @param sys The system in which we add a constraint
98  * @param id Data associated to the constraint (e.g.: a network link)
99  * @param bound_value The bound value of the constraint 
100  */
101 XBT_PUBLIC(lmm_constraint_t) lmm_constraint_new(lmm_system_t sys, void *id,
102                                                 double bound_value);
103
104 /**
105  * @brief Share a constraint
106  * @details [long description]
107  * 
108  * @param cnst The constraint to share
109  */
110 void lmm_constraint_shared(lmm_constraint_t cnst);
111
112 /**
113  * @brief Check if a constraint is shared (shared by default)
114  * 
115  * @param cnst The constraint to share
116  * @return 1 if shared, 0 otherwise
117  */
118 int lmm_constraint_is_shared(lmm_constraint_t cnst);
119
120 /**
121  * @brief Free a constraint
122  * 
123  * @param sys The system associated to the constraint
124  * @param cnst The constraint to free
125  */
126 void lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst);
127
128 /**
129  * @brief Get the usage of the constraint after the last lmm solve
130  * 
131  * @param cnst A constraint
132  * @return The usage of the constraint
133  */
134 double lmm_constraint_get_usage(lmm_constraint_t cnst);
135
136 /**
137  * @brief Create a new Linear MaxMin variable
138  * 
139  * @param sys The system in which we add a constaint
140  * @param id Data associated to the variable (e.g.: a network communication)
141  * @param weight_value The weight of the variable (0.0 if not used)
142  * @param bound The maximum value of the variable (-1.0 if no maximum value)
143  * @param number_of_constraints The maximum number of constraint to associate to the variable
144  */
145 XBT_PUBLIC(lmm_variable_t) lmm_variable_new(lmm_system_t sys, void *id,
146                                             double weight_value,
147                                             double bound,
148                                             int number_of_constraints);
149 /**
150  * @brief Free a variable
151  * 
152  * @param sys The system associated to the variable
153  * @param var The variable to free
154  */
155 XBT_PUBLIC(void) lmm_variable_free(lmm_system_t sys, lmm_variable_t var);
156
157 /**
158  * @brief Get the value of the variable after the last lmm solve
159  * 
160  * @param var A variable
161  * @return The value of the variable
162  */
163 XBT_PUBLIC(double) lmm_variable_getvalue(lmm_variable_t var);
164
165 /**
166  * @brief Get the maximum value of the variable (-1.0 if no maximum value)
167  * 
168  * @param var A variable
169  * @return The bound of the variable
170  */
171 XBT_PUBLIC(double) lmm_variable_getbound(lmm_variable_t var);
172
173 /**
174  * @brief Remove a variable from a constraint
175  * 
176  * @param sys A system
177  * @param cnst A constraint
178  * @param var The variable to remove
179  */
180 XBT_PUBLIC(void) lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
181                             lmm_variable_t var);
182
183 /**
184  * @brief Associate a variable to a constraint with a coefficient
185  * 
186  * @param sys A system
187  * @param cnst A constraint
188  * @param var A variable
189  * @param value The coefficient associated to the variable in the constraint
190  */
191 XBT_PUBLIC(void) lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
192                             lmm_variable_t var, double value);
193
194 /**
195  * @brief Add value to the coefficient between a constraint and a variable or 
196  *        create one
197  * 
198  * @param sys A system
199  * @param cnst A constraint
200  * @param var A variable
201  * @param value The value to add to the coefficient associated to the variable in the constraint
202  */
203 void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
204                     lmm_variable_t var, double value);
205
206 /**
207  * @brief Get the numth constraint associated to the variable
208  * 
209  * @param sys The system associated to the variable (not used)
210  * @param var A variable
211  * @param num The rank of constraint we want to get
212  * @return The numth constraint
213  */
214 lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys,
215                                        lmm_variable_t var, int num);
216
217 /**
218  * @brief Get the weigth of the numth constraint associated to the variable
219  * 
220  * @param sys The system associated to the variable (not used)
221  * @param var A variable
222  * @param num The rank of constraint we want to get
223  * @return The numth constraint
224  */
225 double lmm_get_cnst_weight_from_var(lmm_system_t sys, lmm_variable_t var,
226                                     int num);
227
228 /**
229  * @brief Get the number of constraint associated to a variable
230  * 
231  * @param sys The system associated to the variable (not used)
232  * @param var A variable
233  * @return The number of constraint associated to the variable
234  */
235 int lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var);
236
237 /**
238  * @brief Get a var associated to a constraint 
239  * @details Get the first variable of the next variable of elem if elem is not NULL
240  * 
241  * @param sys The system associated to the variable (not used)
242  * @param cnst A constraint
243  * @param elem A element of constraint of the constraint or NULL
244  * @return A variable associated to a constraint
245  */
246 lmm_variable_t lmm_get_var_from_cnst(lmm_system_t sys,
247                                      lmm_constraint_t cnst,
248                                      lmm_element_t * elem);
249
250 /**
251  * @brief Get the first active constraint of a system
252  * 
253  * @param sys A system
254  * @return The first active constraint
255  */
256 lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t sys);
257
258 /**
259  * @brief Get the next active constraint of a constraint in a system
260  * 
261  * @param sys A system
262  * @param cnst An active constraint of the system
263  * 
264  * @return The next active constraint
265  */
266 lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys,
267                                                 lmm_constraint_t cnst);
268
269 #ifdef HAVE_LATENCY_BOUND_TRACKING
270 XBT_PUBLIC(int) lmm_is_variable_limited_by_latency(lmm_variable_t var);
271 #endif
272
273 /**
274  * @brief Get the data associated to a constraint
275  * 
276  * @param cnst A constraint
277  * @return The data associated to the constraint
278  */
279 void *lmm_constraint_id(lmm_constraint_t cnst);
280
281 /**
282  * @brief Get the data associated to a variable
283  * 
284  * @param var A variable
285  * @return The data associated to the variable
286  */
287 void *lmm_variable_id(lmm_variable_t var);
288
289 /**
290  * @brief Update the value of element linking the constraint and the variable
291  * 
292  * @param sys A system
293  * @param cnst A constraint
294  * @param var A variable
295  * @param value The new value
296  */
297 void lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
298                 lmm_variable_t var, double value);
299
300 /**
301  * @brief Update the bound of a variable
302  * 
303  * @param sys A system
304  * @param var A constraint
305  * @param bound The new bound
306  */
307 void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
308                                double bound);
309
310 /**
311  * @brief Update the weight of a variable
312  * 
313  * @param sys A system
314  * @param var A┬ávariable
315  * @param weight The new weight of the variable
316  */
317 XBT_PUBLIC(void) lmm_update_variable_weight(lmm_system_t sys,
318                                             lmm_variable_t var,
319                                             double weight);
320
321 /**
322  * @brief Get the weight of a variable
323  * 
324  * @param var A variable
325  * @return The weight of the variable
326  */
327 double lmm_get_variable_weight(lmm_variable_t var);
328
329 /**
330  * @brief Update a constraint bound
331  * 
332  * @param sys A system
333  * @param cnst A constraint
334  * @param bound The new bound of the consrtaint
335  */
336 XBT_PUBLIC(void) lmm_update_constraint_bound(lmm_system_t sys,
337                                              lmm_constraint_t cnst,
338                                              double bound);
339
340 /**
341  * @brief [brief description]
342  * 
343  * @param sys A system
344  * @param cnst A constraint
345  * @return [description]
346  */
347 int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst);
348
349 /**
350  * @brief Solve the lmm system
351  * 
352  * @param sys The lmm system to solve
353  */
354 XBT_PUBLIC(void) lmm_solve(lmm_system_t sys);
355
356 XBT_PUBLIC(void) lagrange_solve(lmm_system_t sys);
357 XBT_PUBLIC(void) bottleneck_solve(lmm_system_t sys);
358
359 /**
360  * Default functions associated to the chosen protocol. When
361  * using the lagrangian approach.
362  */
363
364 XBT_PUBLIC(void) lmm_set_default_protocol_function(double (*func_f)
365                                                     (lmm_variable_t var,
366                                                      double x),
367                                                    double (*func_fp)
368                                                     (lmm_variable_t var,
369                                                      double x),
370                                                    double (*func_fpi)
371                                                     (lmm_variable_t var,
372                                                      double x));
373
374 XBT_PUBLIC(double func_reno_f) (lmm_variable_t var, double x);
375 XBT_PUBLIC(double func_reno_fp) (lmm_variable_t var, double x);
376 XBT_PUBLIC(double func_reno_fpi) (lmm_variable_t var, double x);
377
378 XBT_PUBLIC(double func_reno2_f) (lmm_variable_t var, double x);
379 XBT_PUBLIC(double func_reno2_fp) (lmm_variable_t var, double x);
380 XBT_PUBLIC(double func_reno2_fpi) (lmm_variable_t var, double x);
381
382 XBT_PUBLIC(double func_vegas_f) (lmm_variable_t var, double x);
383 XBT_PUBLIC(double func_vegas_fp) (lmm_variable_t var, double x);
384 XBT_PUBLIC(double func_vegas_fpi) (lmm_variable_t var, double x);
385
386 /** @} */
387 SG_END_DECL()
388
389 #endif                          /* _SURF_MAXMIN_H */