src/surf/maxmin_private.hpp

   1 /* Copyright (c) 2004-2017. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #ifndef SURF_MAXMIN_PRIVATE_H
   7 #define SURF_MAXMIN_PRIVATE_H
   8
   9 #include "surf/maxmin.hpp"
  10 #include "surf_interface.hpp"
  11 #include "xbt/mallocator.h"
  12 #include "xbt/swag.h"
  13
  14 #include <vector>
  15
  16 /** @ingroup SURF_lmm
  17  * @brief LMM element
  18  * Elements can be seen as glue between constraint objects and variable objects.
  19  * Basically, each variable will have a set of elements, one for each constraint where it is involved.
  20  * Then, it is used to list all variables involved in constraint through constraint's xxx_element_set lists, or
  21  * vice-versa list all constraints for a given variable.
  22  */
  23 class s_lmm_element_t {
  24 public:
  25   int get_concurrency() const;
  26   void decrease_concurrency();
  27   void increase_concurrency();
  28
  29   void make_active();
  30   void make_inactive();
  31
  32   /* hookup to constraint */
  33   s_xbt_swag_hookup_t enabled_element_set_hookup;
  34   s_xbt_swag_hookup_t disabled_element_set_hookup;
  35   s_xbt_swag_hookup_t active_element_set_hookup;
  36
  37   lmm_constraint_t constraint;
  38   lmm_variable_t variable;
  39
  40   // consumption_weight: impact of 1 byte or flop of your application onto the resource (in byte or flop)
  41   //   - if CPU, then probably 1.
  42   //   - If network, then 1 in forward direction and 0.05 backward for the ACKs
  43   double consumption_weight;
  44 };
  45
  46 struct s_lmm_constraint_light_t {
  47   double remaining_over_usage;
  48   lmm_constraint_t cnst;
  49 };
  50
  51 /** @ingroup SURF_lmm
  52  * @brief LMM constraint
  53  * Each constraint contains several partially overlapping logical sets of elements:
  54  * \li Disabled elements which variable's weight is zero. This variables are not at all processed by LMM, but eventually the corresponding action will enable it (at least this is the idea).
  55  * \li Enabled elements which variable's weight is non-zero. They are utilized in some LMM functions.
  56  * \li Active elements which variable's weight is non-zero (i.e. it is enabled) AND its element value is non-zero. LMM_solve iterates over active elements during resolution, dynamically making them active or unactive.
  57  *
  58  */
  59 class s_lmm_constraint_t {
  60 public:
  61   s_lmm_constraint_t() = default;
  62   s_lmm_constraint_t(void* id_value, double bound_value);
  63
  64   /** @brief Share a constraint. FIXME: name is misleading */
  65   void shared() { sharing_policy = 0; }
  66
  67   /**
  68    * @brief Check if a constraint is shared (shared by default)
  69    * @return 1 if shared, 0 otherwise
  70    */
  71   int get_sharing_policy() const { return sharing_policy; }
  72
  73   /**
  74    * @brief Get the usage of the constraint after the last lmm solve
  75    * @return The usage of the constraint
  76    */
  77   double get_usage() const;
  78   int get_variable_amount() const;
  79
  80   /**
  81    * @brief Sets the concurrency limit for this constraint
  82    * @param concurrency_limit The concurrency limit to use for this constraint
  83    */
  84   void set_concurrency_limit(int limit)
  85   {
  86     xbt_assert(limit < 0 || concurrency_maximum <= limit,
  87                "New concurrency limit should be larger than observed concurrency maximum. Maybe you want to call"
  88                " concurrency_maximum_reset() to reset the maximum?");
  89     concurrency_limit = limit;
  90   }
  91
  92   /**
  93    * @brief Gets the concurrency limit for this constraint
  94    * @return The concurrency limit used by this constraint
  95    */
  96   int get_concurrency_limit() const { return concurrency_limit; }
  97
  98   /**
  99    * @brief Reset the concurrency maximum for a given variable (we will update the maximum to reflect constraint
 100    * evolution).
 101    */
 102   void reset_concurrency_maximum() { concurrency_maximum = 0; }
 103
 104   /**
 105    * @brief Get the concurrency maximum for a given variable (which reflects constraint evolution).
 106    * @return the maximum concurrency of the constraint
 107    */
 108   int get_concurrency_maximum() const
 109   {
 110     xbt_assert(concurrency_limit < 0 || concurrency_maximum <= concurrency_limit,
 111                "Very bad: maximum observed concurrency is higher than limit. This is a bug of SURF, please report it.");
 112     return concurrency_maximum;
 113   }
 114
 115   int get_concurrency_slack() const
 116   {
 117     return concurrency_limit < 0 ? std::numeric_limits<int>::max() : concurrency_limit - concurrency_current;
 118   }
 119
 120   /**
 121    * @brief Get a var associated to a constraint
 122    * @details Get the first variable of the next variable of elem if elem is not NULL
 123    * @param elem A element of constraint of the constraint or NULL
 124    * @return A variable associated to a constraint
 125    */
 126   lmm_variable_t get_variable(lmm_element_t* elem) const;
 127
 128   /**
 129    * @brief Get a var associated to a constraint
 130    * @details Get the first variable of the next variable of elem if elem is not NULL
 131    * @param elem A element of constraint of the constraint or NULL
 132    * @param nextelem A element of constraint of the constraint or NULL, the one after elem
 133    * @param numelem parameter representing the number of elements to go
 134    * @return A variable associated to a constraint
 135    */
 136   lmm_variable_t get_variable_safe(lmm_element_t* elem, lmm_element_t* nextelem, int* numelem) const;
 137
 138   /**
 139    * @brief Get the data associated to a constraint
 140    * @return The data associated to the constraint
 141    */
 142   void* get_id() const { return id; }
 143
 144   /* hookup to system */
 145   s_xbt_swag_hookup_t constraint_set_hookup           = {nullptr, nullptr};
 146   s_xbt_swag_hookup_t active_constraint_set_hookup    = {nullptr, nullptr};
 147   s_xbt_swag_hookup_t modified_constraint_set_hookup  = {nullptr, nullptr};
 148   s_xbt_swag_hookup_t saturated_constraint_set_hookup = {nullptr, nullptr};
 149   s_xbt_swag_t enabled_element_set;     /* a list of lmm_element_t */
 150   s_xbt_swag_t disabled_element_set;     /* a list of lmm_element_t */
 151   s_xbt_swag_t active_element_set;      /* a list of lmm_element_t */
 152   double remaining;
 153   double usage;
 154   double bound;
 155   //TODO MARTIN Check maximum value across resources at the end of simulation and give a warning is more than e.g. 500
 156   int concurrency_current; /* The current concurrency */
 157   int concurrency_maximum; /* The maximum number of (enabled and disabled) variables associated to the constraint at any given time (essentially for tracing)*/
 158
 159   int sharing_policy; /* see @e_surf_link_sharing_policy_t (0: FATPIPE, 1: SHARED, 2: FULLDUPLEX) */
 160   int id_int;
 161   double lambda;
 162   double new_lambda;
 163   lmm_constraint_light_t cnst_light;
 164
 165 private:
 166   static int Global_debug_id;
 167   int concurrency_limit; /* The maximum number of variables that may be enabled at any time (stage variables if
 168                           * necessary) */
 169   void* id;
 170 };
 171
 172 /** @ingroup SURF_lmm
 173  * @brief LMM variable
 174  *
 175  * When something prevents us from enabling a variable, we "stage" the weight that we would have like to set, so that as soon as possible we enable the variable with desired weight
 176  */
 177 class s_lmm_variable_t {
 178 public:
 179   void initialize(simgrid::surf::Action* id_value, double sharing_weight_value, double bound_value,
 180                   int number_of_constraints, unsigned visited_value);
 181
 182   /**
 183    * @brief Get the value of the variable after the last lmm solve
 184    * @return The value of the variable
 185    */
 186   double get_value() const { return value; }
 187
 188   /**
 189    * @brief Get the maximum value of the variable (-1.0 if no maximum value)
 190    * @return The bound of the variable
 191    */
 192   double get_bound() const { return bound; }
 193
 194   /**
 195    * @brief Set the concurrent share of the variable
 196    * @param concurrency_share The new concurrency share
 197    */
 198   void set_concurrency_share(short int value) { concurrency_share = value; }
 199
 200   /**
 201    * @brief Get the numth constraint associated to the variable
 202    * @param num The rank of constraint we want to get
 203    * @return The numth constraint
 204    */
 205   lmm_constraint_t get_constraint(unsigned num) const { return num < cnsts.size() ? cnsts[num].constraint : nullptr; }
 206
 207   /**
 208    * @brief Get the weigth of the numth constraint associated to the variable
 209    * @param num The rank of constraint we want to get
 210    * @return The numth constraint
 211    */
 212   double get_constraint_weight(unsigned num) const { return num < cnsts.size() ? cnsts[num].consumption_weight : 0.0; }
 213
 214   /**
 215    * @brief Get the number of constraint associated to a variable
 216    * @return The number of constraint associated to the variable
 217    */
 218   int get_number_of_constraint() const { return cnsts.size(); }
 219
 220   /**
 221    * @brief Get the data associated to a variable
 222    * @return The data associated to the variable
 223    */
 224   simgrid::surf::Action* get_id() const { return id; }
 225
 226   /**
 227    * @brief Get the weight of a variable
 228    * @return The weight of the variable
 229    */
 230   double get_weight() const { return sharing_weight; }
 231
 232   /** @brief Measure the minimum concurrency slack across all constraints where the given var is involved */
 233   int get_min_concurrency_slack() const;
 234
 235   /** @brief Check if a variable can be enabled
 236    * Make sure to set staged_weight before, if your intent is only to check concurrency
 237    */
 238   int can_enable() const { return staged_weight > 0 && get_min_concurrency_slack() >= concurrency_share; }
 239
 240   /* hookup to system */
 241   s_xbt_swag_hookup_t variable_set_hookup;
 242   s_xbt_swag_hookup_t saturated_variable_set_hookup;
 243
 244   std::vector<s_lmm_element_t> cnsts;
 245
 246   // sharing_weight: variable's impact on the resource during the sharing
 247   //   if == 0, the variable is not considered by LMM
 248   //   on CPU, actions with N threads have a sharing of N
 249   //   on network, the actions with higher latency have a lesser sharing_weight
 250   double sharing_weight;
 251
 252   double staged_weight; /* If non-zero, variable is staged for addition as soon as maxconcurrency constraints will be met */
 253   double bound;
 254   double value;
 255   short int concurrency_share; /* The maximum number of elements that variable will add to a constraint */
 256   simgrid::surf::Action* id;
 257   int id_int;
 258   unsigned visited;             /* used by lmm_update_modified_set */
 259   /* \begin{For Lagrange only} */
 260   double mu;
 261   double new_mu;
 262   double (*func_f)(s_lmm_variable_t* var, double x);   /* (f)    */
 263   double (*func_fp)(s_lmm_variable_t* var, double x);  /* (f')    */
 264   double (*func_fpi)(s_lmm_variable_t* var, double x); /* (f')^{-1}    */
 265   /* \end{For Lagrange only} */
 266
 267 private:
 268   static int Global_debug_id;
 269 };
 270
 271 inline void s_lmm_element_t::make_active()
 272 {
 273   xbt_swag_insert_at_head(this, &constraint->active_element_set);
 274 }
 275 inline void s_lmm_element_t::make_inactive()
 276 {
 277   xbt_swag_remove(this, &constraint->active_element_set);
 278 }
 279
 280 /** @ingroup SURF_lmm
 281  * @brief LMM system
 282  */
 283 class s_lmm_system_t {
 284 public:
 285   /**
 286    * @brief Create a new Linear MaxMim system
 287    * @param selective_update whether we should do lazy updates
 288    */
 289   s_lmm_system_t(bool selective_update);
 290   /** @brief Free an existing Linear MaxMin system */
 291   ~s_lmm_system_t();
 292
 293   /**
 294    * @brief Create a new Linear MaxMin constraint
 295    * @param id Data associated to the constraint (e.g.: a network link)
 296    * @param bound_value The bound value of the constraint
 297    */
 298   lmm_constraint_t constraint_new(void* id, double bound_value);
 299
 300   /**
 301    * @brief Create a new Linear MaxMin variable
 302    * @param id Data associated to the variable (e.g.: a network communication)
 303    * @param weight_value The weight of the variable (0.0 if not used)
 304    * @param bound The maximum value of the variable (-1.0 if no maximum value)
 305    * @param number_of_constraints The maximum number of constraint to associate to the variable
 306    */
 307   lmm_variable_t variable_new(simgrid::surf::Action* id, double weight_value, double bound, int number_of_constraints);
 308
 309   /**
 310    * @brief Free a variable
 311    * @param var The variable to free
 312    */
 313   void variable_free(lmm_variable_t var);
 314
 315   /**
 316    * @brief Associate a variable to a constraint with a coefficient
 317    * @param cnst A constraint
 318    * @param var A variable
 319    * @param value The coefficient associated to the variable in the constraint
 320    */
 321   void expand(lmm_constraint_t cnst, lmm_variable_t var, double value);
 322
 323   /**
 324    * @brief Add value to the coefficient between a constraint and a variable or create one
 325    * @param cnst A constraint
 326    * @param var A variable
 327    * @param value The value to add to the coefficient associated to the variable in the constraint
 328    */
 329   void expand_add(lmm_constraint_t cnst, lmm_variable_t var, double value);
 330
 331   /**
 332    * @brief Update the bound of a variable
 333    * @param var A constraint
 334    * @param bound The new bound
 335    */
 336   void update_variable_bound(lmm_variable_t var, double bound);
 337
 338   /**
 339    * @brief Update the weight of a variable
 340    * @param var A variable
 341    * @param weight The new weight of the variable
 342    */
 343   void update_variable_weight(lmm_variable_t var, double weight);
 344
 345   /**
 346    * @brief Update a constraint bound
 347    * @param cnst A constraint
 348    * @param bound The new bound of the consrtaint
 349    */
 350   void update_constraint_bound(lmm_constraint_t cnst, double bound);
 351
 352   /**
 353    * @brief [brief description]
 354    * @param cnst A constraint
 355    * @return [description]
 356    */
 357   int constraint_used(lmm_constraint_t cnst) { return xbt_swag_belongs(cnst, &active_constraint_set); }
 358
 359   /** @brief Print the lmm system */
 360   void print();
 361
 362   /** @brief Solve the lmm system */
 363   void solve();
 364
 365 private:
 366   static void* variable_mallocator_new_f();
 367   static void variable_mallocator_free_f(void* var);
 368
 369   void var_free(lmm_variable_t var);
 370   void cnst_free(lmm_constraint_t cnst);
 371   lmm_variable_t extract_variable() { return static_cast<lmm_variable_t>(xbt_swag_extract(&variable_set)); }
 372   lmm_constraint_t extract_constraint() { return static_cast<lmm_constraint_t>(xbt_swag_extract(&constraint_set)); }
 373   void insert_constraint(lmm_constraint_t cnst) { xbt_swag_insert(cnst, &constraint_set); }
 374   void remove_variable(lmm_variable_t var)
 375   {
 376     xbt_swag_remove(var, &variable_set);
 377     xbt_swag_remove(var, &saturated_variable_set);
 378   }
 379   void remove_constraint(lmm_constraint_t cnst) // FIXME: unused
 380   {
 381     xbt_swag_remove(cnst, &constraint_set);
 382     xbt_swag_remove(cnst, &saturated_constraint_set);
 383   }
 384   void make_constraint_active(lmm_constraint_t cnst) { xbt_swag_insert(cnst, &active_constraint_set); }
 385   void make_constraint_inactive(lmm_constraint_t cnst)
 386   {
 387     xbt_swag_remove(cnst, &active_constraint_set);
 388     xbt_swag_remove(cnst, &modified_constraint_set);
 389   }
 390
 391   void enable_var(lmm_variable_t var);
 392   void disable_var(lmm_variable_t var);
 393   void on_disabled_var(lmm_constraint_t cnstr);
 394
 395   /**
 396    * @brief Update the value of element linking the constraint and the variable
 397    * @param cnst A constraint
 398    * @param var A variable
 399    * @param value The new value
 400    */
 401   void update(lmm_constraint_t cnst, lmm_variable_t var, double value);
 402
 403   void update_modified_set(lmm_constraint_t cnst);
 404   void update_modified_set_rec(lmm_constraint_t cnst);
 405
 406   /** @brief Remove all constraints of the modified_constraint_set. */
 407   void remove_all_modified_set();
 408   void check_concurrency();
 409
 410 public:
 411   int modified;
 412   s_xbt_swag_t variable_set;    /* a list of lmm_variable_t */
 413   s_xbt_swag_t active_constraint_set;   /* a list of lmm_constraint_t */
 414   s_xbt_swag_t saturated_variable_set;  /* a list of lmm_variable_t */
 415   s_xbt_swag_t saturated_constraint_set;        /* a list of lmm_constraint_t_t */
 416
 417   simgrid::surf::ActionLmmListPtr keep_track;
 418
 419   void (*solve_fun)(lmm_system_t self);
 420
 421 private:
 422   bool selective_update_active; /* flag to update partially the system only selecting changed portions */
 423   unsigned visited_counter;     /* used by lmm_update_modified_set and lmm_remove_modified_set to cleverly (un-)flag the
 424                                  * constraints (more details in these functions) */
 425   s_xbt_swag_t constraint_set;  /* a list of lmm_constraint_t */
 426   s_xbt_swag_t modified_constraint_set; /* a list of modified lmm_constraint_t */
 427   xbt_mallocator_t variable_mallocator;
 428 };
 429
 430 extern XBT_PRIVATE double (*func_f_def) (lmm_variable_t, double);
 431 extern XBT_PRIVATE double (*func_fp_def) (lmm_variable_t, double);
 432 extern XBT_PRIVATE double (*func_fpi_def) (lmm_variable_t, double);
 433
 434 #endif /* SURF_MAXMIN_PRIVATE_H */