src/include/surf/maxmin.h

   1 /* Copyright (c) 2004-2015. 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 "src/portable.h"
  11 #include "xbt/misc.h"
  12 #include "xbt/asserts.h"
  13 #include "surf/datatypes.h"
  14 #include <math.h>
  15
  16
  17 /** @addtogroup SURF_lmm
  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  */
 128
 129 XBT_PUBLIC_DATA(double) sg_maxmin_precision;
 130 XBT_PUBLIC_DATA(double) sg_surf_precision;
 131
 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...
 137   //xbt_assert(*variable< (2<<DBL_MANT_DIG)*precision && FLT_RADIX==2);
 138   *variable -= value;
 139   if (*variable < precision)
 140     *variable = 0.0;
 141 }
 142
 143 static XBT_INLINE int double_positive(double value, double precision)
 144 {
 145   return (value > precision);
 146 }
 147
 148 static XBT_INLINE int double_equals(double value1, double value2, double precision)
 149 {
 150   return (fabs(value1 - value2) < precision);
 151 }
 152
 153 SG_BEGIN_DECL()
 154
 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);
 162
 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);
 169
 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);
 179
 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);
 187
 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);
 195
 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);
 203
 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);
 211
 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);
 219
 220
 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);
 228
 229
 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);
 237
 238
 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);
 259
 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);
 267
 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);
 275
 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);
 283
 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);
 293
 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);
 304
 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);
 316
 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);
 327
 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);
 338
 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);
 347
 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);
 360
 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);
 377
 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);
 385
 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);
 396
 397 #ifdef HAVE_LATENCY_BOUND_TRACKING
 398 XBT_PUBLIC(int) lmm_is_variable_limited_by_latency(lmm_variable_t var);
 399 #endif
 400
 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);
 408
 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);
 416
 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);
 427
 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);
 437
 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);
 448
 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);
 456
 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);
 467
 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);
 476
 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);
 483
 484 XBT_PUBLIC(void) lagrange_solve(lmm_system_t sys);
 485 XBT_PUBLIC(void) bottleneck_solve(lmm_system_t sys);
 486
 487 /**
 488  * Default functions associated to the chosen protocol. When
 489  * using the lagrangian approach.
 490  */
 491
 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));
 501
 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);
 505
 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);
 509
 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);
 513
 514 /** @} */
 515 SG_END_DECL()
 516
 517 #endif                          /* _SURF_MAXMIN_H */