src/include/surf/maxmin.h

   1 /* Copyright (c) 2004-2013. 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 Change the value of the coefficient between a constraint and a variable
 208  *
 209  * @param sys A system
 210  * @param cnst A constraint
 211  * @param var A variable
 212  * @param value The new value of the coefficient between a constraint and a variable
 213  */
 214 void lmm_elem_set_value(lmm_system_t sys, lmm_constraint_t cnst,
 215                         lmm_variable_t var, double value);
 216
 217 /**
 218  * @brief Get 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 lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys,
 226                                        lmm_variable_t var, int num);
 227
 228 /**
 229  * @brief Get the weigth of the numth constraint associated to the variable
 230  *
 231  * @param sys The system associated to the variable (not used)
 232  * @param var A variable
 233  * @param num The rank of constraint we want to get
 234  * @return The numth constraint
 235  */
 236 double lmm_get_cnst_weight_from_var(lmm_system_t sys, lmm_variable_t var,
 237                                     int num);
 238
 239 /**
 240  * @brief Get the number of constraint associated to a variable
 241  *
 242  * @param sys The system associated to the variable (not used)
 243  * @param var A variable
 244  * @return The number of constraint associated to the variable
 245  */
 246 int lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var);
 247
 248 /**
 249  * @brief Get a var associated to a constraint
 250  * @details Get the first variable of the next variable of elem if elem is not NULL
 251  *
 252  * @param sys The system associated to the variable (not used)
 253  * @param cnst A constraint
 254  * @param elem A element of constraint of the constraint or NULL
 255  * @return A variable associated to a constraint
 256  */
 257 lmm_variable_t lmm_get_var_from_cnst(lmm_system_t sys,
 258                                      lmm_constraint_t cnst,
 259                                      lmm_element_t * elem);
 260
 261 /**
 262  * @brief Get the first active constraint of a system
 263  *
 264  * @param sys A system
 265  * @return The first active constraint
 266  */
 267 lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t sys);
 268
 269 /**
 270  * @brief Get the next active constraint of a constraint in a system
 271  *
 272  * @param sys A system
 273  * @param cnst An active constraint of the system
 274  *
 275  * @return The next active constraint
 276  */
 277 lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys,
 278                                                 lmm_constraint_t cnst);
 279
 280 #ifdef HAVE_LATENCY_BOUND_TRACKING
 281 XBT_PUBLIC(int) lmm_is_variable_limited_by_latency(lmm_variable_t var);
 282 #endif
 283
 284 /**
 285  * @brief Get the data associated to a constraint
 286  *
 287  * @param cnst A constraint
 288  * @return The data associated to the constraint
 289  */
 290 void *lmm_constraint_id(lmm_constraint_t cnst);
 291
 292 /**
 293  * @brief Get the data associated to a variable
 294  *
 295  * @param cnst A variable
 296  * @return The data associated to the variable
 297  */
 298 void *lmm_variable_id(lmm_variable_t var);
 299
 300 /**
 301  * @brief Update the value of element linking the constraint and the variable
 302  *
 303  * @param sys A system
 304  * @param cnst A constraint
 305  * @param var A variable
 306  * @param value The new value
 307  */
 308 void lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
 309                 lmm_variable_t var, double value);
 310
 311 /**
 312  * @brief Update the bound of a variable
 313  *
 314  * @param sys A system
 315  * @param var A constraint
 316  * @param bound The new bound
 317  */
 318 void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
 319                                double bound);
 320
 321 /**
 322  * @brief Update the weight of a variable
 323  *
 324  * @param sys A system
 325  * @param var A variable
 326  * @param weight The new weight of the variable
 327  */
 328 XBT_PUBLIC(void) lmm_update_variable_weight(lmm_system_t sys,
 329                                             lmm_variable_t var,
 330                                             double weight);
 331
 332 /**
 333  * @brief Get the weight of a variable
 334  *
 335  * @param var A variable
 336  * @return The weight of the variable
 337  */
 338 double lmm_get_variable_weight(lmm_variable_t var);
 339
 340 /**
 341  * @brief Update a constraint bound
 342  *
 343  * @param sys A system
 344  * @param cnst A constraint
 345  * @param bound The new bound of the consrtaint
 346  */
 347 XBT_PUBLIC(void) lmm_update_constraint_bound(lmm_system_t sys,
 348                                              lmm_constraint_t cnst,
 349                                              double bound);
 350
 351 /**
 352  * @brief [brief description]
 353  *
 354  * @param sys A system
 355  * @param cnst A constraint
 356  * @return [description]
 357  */
 358 int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst);
 359
 360 /**
 361  * @brief Solve the lmm system
 362  *
 363  * @param sys The lmm system to solve
 364  */
 365 XBT_PUBLIC(void) lmm_solve(lmm_system_t sys);
 366
 367 XBT_PUBLIC(void) lagrange_solve(lmm_system_t sys);
 368 XBT_PUBLIC(void) bottleneck_solve(lmm_system_t sys);
 369
 370 /**
 371  * Default functions associated to the chosen protocol. When
 372  * using the lagrangian approach.
 373  */
 374
 375 XBT_PUBLIC(void) lmm_set_default_protocol_function(double (*func_f)
 376                                                     (lmm_variable_t var,
 377                                                      double x),
 378                                                    double (*func_fp)
 379                                                     (lmm_variable_t var,
 380                                                      double x),
 381                                                    double (*func_fpi)
 382                                                     (lmm_variable_t var,
 383                                                      double x));
 384
 385 XBT_PUBLIC(double func_reno_f) (lmm_variable_t var, double x);
 386 XBT_PUBLIC(double func_reno_fp) (lmm_variable_t var, double x);
 387 XBT_PUBLIC(double func_reno_fpi) (lmm_variable_t var, double x);
 388
 389 XBT_PUBLIC(double func_reno2_f) (lmm_variable_t var, double x);
 390 XBT_PUBLIC(double func_reno2_fp) (lmm_variable_t var, double x);
 391 XBT_PUBLIC(double func_reno2_fpi) (lmm_variable_t var, double x);
 392
 393 XBT_PUBLIC(double func_vegas_f) (lmm_variable_t var, double x);
 394 XBT_PUBLIC(double func_vegas_fp) (lmm_variable_t var, double x);
 395 XBT_PUBLIC(double func_vegas_fpi) (lmm_variable_t var, double x);
 396
 397 /** @} */
 398 SG_END_DECL()
 399
 400 #endif                          /* _SURF_MAXMIN_H */