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  * @brief Gets the concurrency limit for this constraint
 222  *
 223  * @param cnst A constraint
 224  * @return The concurrency limit used by this constraint
 225  */
 226 XBT_PUBLIC(int) lmm_constraint_concurrency_limit_get(lmm_constraint_t cnst);
 227
 228
 229 /**
 230  * @brief Reset the concurrency maximum for a given variable (we will update the maximum to reflect constraint evolution).
 231  *
 232  * @param cnst A constraint
 233  *
 234 */
 235 XBT_PUBLIC(void) lmm_constraint_concurrency_maximum_reset(lmm_constraint_t cnst);
 236
 237
 238 /**
 239  * @brief Get the concurrency maximum for a given variable (which reflects constraint evolution).
 240  *
 241  * @param cnst A constraint
 242  * @return the maximum concurrency of the constraint
 243  */
 244 XBT_PUBLIC(int) lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst);
 245
 246
 247 /**
 248  * @brief Create a new Linear MaxMin variable
 249  *
 250  * @param sys The system in which we add a constaint
 251  * @param id Data associated to the variable (e.g.: a network communication)
 252  * @param weight_value The weight of the variable (0.0 if not used)
 253  * @param bound The maximum value of the variable (-1.0 if no maximum value)
 254  * @param number_of_constraints The maximum number of constraint to associate to the variable
 255  */
 256 XBT_PUBLIC(lmm_variable_t) lmm_variable_new(lmm_system_t sys, void *id,
 257                                             double weight_value,
 258                                             double bound,
 259                                             int number_of_constraints);
 260 /**
 261  * @brief Free a variable
 262  *
 263  * @param sys The system associated to the variable
 264  * @param var The variable to free
 265  */
 266 XBT_PUBLIC(void) lmm_variable_free(lmm_system_t sys, lmm_variable_t var);
 267
 268 /**
 269  * @brief Get the value of the variable after the last lmm solve
 270  *
 271  * @param var A variable
 272  * @return The value of the variable
 273  */
 274 XBT_PUBLIC(double) lmm_variable_getvalue(lmm_variable_t var);
 275
 276 /**
 277  * @brief Get the maximum value of the variable (-1.0 if no maximum value)
 278  *
 279  * @param var A variable
 280  * @return The bound of the variable
 281  */
 282 XBT_PUBLIC(double) lmm_variable_getbound(lmm_variable_t var);
 283
 284 /**
 285  * @brief Set the concurrent share of the variable
 286  *
 287  * @param var A variable
 288  * @param concurrency_share The new concurrency share
 289  */
 290 XBT_PUBLIC(void) lmm_variable_concurrency_share_set(lmm_variable_t var, short int concurrency_share);
 291
 292 /**
 293  * @brief Remove a variable from a constraint
 294  *
 295  * @param sys A system
 296  * @param cnst A constraint
 297  * @param var The variable to remove
 298  */
 299 XBT_PUBLIC(void) lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
 300                             lmm_variable_t var);
 301
 302 /**
 303  * @brief Associate a variable to a constraint with a coefficient
 304  *
 305  * @param sys A system
 306  * @param cnst A constraint
 307  * @param var A variable
 308  * @param value The coefficient associated to the variable in the constraint
 309  */
 310 XBT_PUBLIC(void) lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
 311                             lmm_variable_t var, double value);
 312
 313 /**
 314  * @brief Add value to the coefficient between a constraint and a variable or
 315  *        create one
 316  *
 317  * @param sys A system
 318  * @param cnst A constraint
 319  * @param var A variable
 320  * @param value The value to add to the coefficient associated to the variable in the constraint
 321  */
 322 XBT_PUBLIC(void) lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
 323                     lmm_variable_t var, double value);
 324
 325 /**
 326  * @brief Get the numth constraint associated to the variable
 327  *
 328  * @param sys The system associated to the variable (not used)
 329  * @param var A variable
 330  * @param num The rank of constraint we want to get
 331  * @return The numth constraint
 332  */
 333 XBT_PUBLIC(lmm_constraint_t) lmm_get_cnst_from_var(lmm_system_t sys,
 334                                        lmm_variable_t var, int num);
 335
 336 /**
 337  * @brief Get the weigth of the numth constraint associated to the variable
 338  *
 339  * @param sys The system associated to the variable (not used)
 340  * @param var A variable
 341  * @param num The rank of constraint we want to get
 342  * @return The numth constraint
 343  */
 344 XBT_PUBLIC(double) lmm_get_cnst_weight_from_var(lmm_system_t sys, lmm_variable_t var,
 345                                     int num);
 346
 347 /**
 348  * @brief Get the number of constraint associated to a variable
 349  *
 350  * @param sys The system associated to the variable (not used)
 351  * @param var A variable
 352  * @return The number of constraint associated to the variable
 353  */
 354 XBT_PUBLIC(int) lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var);
 355
 356 /**
 357  * @brief Get a var associated to a constraint
 358  * @details Get the first variable of the next variable of elem if elem is not NULL
 359  *
 360  * @param sys The system associated to the variable (not used)
 361  * @param cnst A constraint
 362  * @param elem A element of constraint of the constraint or NULL
 363  * @return A variable associated to a constraint
 364  */
 365 XBT_PUBLIC(lmm_variable_t) lmm_get_var_from_cnst(lmm_system_t sys,
 366                                      lmm_constraint_t cnst,
 367                                      lmm_element_t * elem);
 368
 369 /**
 370  * @brief Get a var associated to a constraint
 371  * @details Get the first variable of the next variable of elem if elem is not NULL
 372  *
 373  * @param cnst A constraint
 374  * @param elem A element of constraint of the constraint or NULL
 375  * @param nextelem A element of constraint of the constraint or NULL, the one after elem
 376  * @param numelem parameter representing the number of elements to go
 377  *
 378  * @return A variable associated to a constraint
 379  */
 380 XBT_PUBLIC(lmm_variable_t) lmm_get_var_from_cnst_safe(lmm_system_t /*sys*/,
 381                                      lmm_constraint_t cnst,
 382                                      lmm_element_t * elem,
 383                                      lmm_element_t * nextelem,
 384                                      int * numelem);
 385
 386 /**
 387  * @brief Get the first active constraint of a system
 388  *
 389  * @param sys A system
 390  * @return The first active constraint
 391  */
 392 XBT_PUBLIC(lmm_constraint_t) lmm_get_first_active_constraint(lmm_system_t sys);
 393
 394 /**
 395  * @brief Get the next active constraint of a constraint in a system
 396  *
 397  * @param sys A system
 398  * @param cnst An active constraint of the system
 399  *
 400  * @return The next active constraint
 401  */
 402 XBT_PUBLIC(lmm_constraint_t) lmm_get_next_active_constraint(lmm_system_t sys,
 403                                                 lmm_constraint_t cnst);
 404
 405 #ifdef HAVE_LATENCY_BOUND_TRACKING
 406 XBT_PUBLIC(int) lmm_is_variable_limited_by_latency(lmm_variable_t var);
 407 #endif
 408
 409 /**
 410  * @brief Get the data associated to a constraint
 411  *
 412  * @param cnst A constraint
 413  * @return The data associated to the constraint
 414  */
 415 XBT_PUBLIC(void *) lmm_constraint_id(lmm_constraint_t cnst);
 416
 417 /**
 418  * @brief Get the data associated to a variable
 419  *
 420  * @param var A variable
 421  * @return The data associated to the variable
 422  */
 423 XBT_PUBLIC(void *) lmm_variable_id(lmm_variable_t var);
 424
 425 /**
 426  * @brief Update the value of element linking the constraint and the variable
 427  *
 428  * @param sys A system
 429  * @param cnst A constraint
 430  * @param var A variable
 431  * @param value The new value
 432  */
 433 XBT_PUBLIC(void) lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
 434                 lmm_variable_t var, double value);
 435
 436 /**
 437  * @brief Update the bound of a variable
 438  *
 439  * @param sys A system
 440  * @param var A constraint
 441  * @param bound The new bound
 442  */
 443 XBT_PUBLIC(void) lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
 444                                double bound);
 445
 446 /**
 447  * @brief Update the weight of a variable
 448  *
 449  * @param sys A system
 450  * @param var A variable
 451  * @param weight The new weight of the variable
 452  */
 453 XBT_PUBLIC(void) lmm_update_variable_weight(lmm_system_t sys,
 454                                             lmm_variable_t var,
 455                                             double weight);
 456
 457 /**
 458  * @brief Get the weight of a variable
 459  *
 460  * @param var A variable
 461  * @return The weight of the variable
 462  */
 463 XBT_PUBLIC(double) lmm_get_variable_weight(lmm_variable_t var);
 464
 465 /**
 466  * @brief Update a constraint bound
 467  *
 468  * @param sys A system
 469  * @param cnst A constraint
 470  * @param bound The new bound of the consrtaint
 471  */
 472 XBT_PUBLIC(void) lmm_update_constraint_bound(lmm_system_t sys,
 473                                              lmm_constraint_t cnst,
 474                                              double bound);
 475
 476 /**
 477  * @brief [brief description]
 478  *
 479  * @param sys A system
 480  * @param cnst A constraint
 481  * @return [description]
 482  */
 483 XBT_PUBLIC(int) lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst);
 484
 485 /**
 486  * @brief Print the lmm system
 487  *
 488  * @param sys The lmm system to print
 489  */
 490 XBT_PUBLIC(void) lmm_print(lmm_system_t sys);
 491
 492 /**
 493  * @brief Solve the lmm system
 494  *
 495  * @param sys The lmm system to solve
 496  */
 497 XBT_PUBLIC(void) lmm_solve(lmm_system_t sys);
 498
 499 XBT_PUBLIC(void) lagrange_solve(lmm_system_t sys);
 500 XBT_PUBLIC(void) bottleneck_solve(lmm_system_t sys);
 501
 502 /**
 503  * Default functions associated to the chosen protocol. When
 504  * using the lagrangian approach.
 505  */
 506
 507 XBT_PUBLIC(void) lmm_set_default_protocol_function(double (*func_f)
 508                                                     (lmm_variable_t var,
 509                                                      double x),
 510                                                    double (*func_fp)
 511                                                     (lmm_variable_t var,
 512                                                      double x),
 513                                                    double (*func_fpi)
 514                                                     (lmm_variable_t var,
 515                                                      double x));
 516
 517 XBT_PUBLIC(double func_reno_f) (lmm_variable_t var, double x);
 518 XBT_PUBLIC(double func_reno_fp) (lmm_variable_t var, double x);
 519 XBT_PUBLIC(double func_reno_fpi) (lmm_variable_t var, double x);
 520
 521 XBT_PUBLIC(double func_reno2_f) (lmm_variable_t var, double x);
 522 XBT_PUBLIC(double func_reno2_fp) (lmm_variable_t var, double x);
 523 XBT_PUBLIC(double func_reno2_fpi) (lmm_variable_t var, double x);
 524
 525 XBT_PUBLIC(double func_vegas_f) (lmm_variable_t var, double x);
 526 XBT_PUBLIC(double func_vegas_fp) (lmm_variable_t var, double x);
 527 XBT_PUBLIC(double func_vegas_fpi) (lmm_variable_t var, double x);
 528
 529 /** @} */
 530 SG_END_DECL()
 531
 532 #endif                          /* _SURF_MAXMIN_H */