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 */