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 vice-versa list all constraints for a given variable.
  21  */
  22 struct s_lmm_element_t {
  23   /* hookup to constraint */
  24   s_xbt_swag_hookup_t enabled_element_set_hookup;
  25   s_xbt_swag_hookup_t disabled_element_set_hookup;
  26   s_xbt_swag_hookup_t active_element_set_hookup;
  27
  28   lmm_constraint_t constraint;
  29   lmm_variable_t variable;
  30
  31   // consumption_weight: impact of 1 byte or flop of your application onto the resource (in byte or flop)
  32   //   - if CPU, then probably 1.
  33   //   - If network, then 1 in forward direction and 0.05 backward for the ACKs
  34   double consumption_weight;
  35 };
  36 #define make_elem_active(elem) xbt_swag_insert_at_head((elem), &((elem)->constraint->active_element_set))
  37 #define make_elem_inactive(elem) xbt_swag_remove((elem), &((elem)->constraint->active_element_set))
  38
  39 struct s_lmm_constraint_light_t {
  40   double remaining_over_usage;
  41   lmm_constraint_t cnst;
  42 };
  43
  44 /** @ingroup SURF_lmm
  45  * @brief LMM constraint
  46  * Each constraint contains several partially overlapping logical sets of elements:
  47  * \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).
  48  * \li Enabled elements which variable's weight is non-zero. They are utilized in some LMM functions.
  49  * \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.
  50  *
  51  */
  52 class s_lmm_constraint_t {
  53 public:
  54   s_lmm_constraint_t() = default;
  55   s_lmm_constraint_t(void* id_value, double bound_value);
  56
  57   /** @brief Share a constraint. FIXME: name is misleading */
  58   void shared() { sharing_policy = 0; }
  59
  60   /**
  61    * @brief Check if a constraint is shared (shared by default)
  62    * @return 1 if shared, 0 otherwise
  63    */
  64   int get_sharing_policy() const { return sharing_policy; }
  65
  66   /**
  67    * @brief Get the usage of the constraint after the last lmm solve
  68    * @return The usage of the constraint
  69    */
  70   double get_usage() const;
  71   int get_variable_amount() const;
  72
  73   /**
  74    * @brief Sets the concurrency limit for this constraint
  75    * @param concurrency_limit The concurrency limit to use for this constraint
  76    */
  77   void set_concurrency_limit(int limit)
  78   {
  79     xbt_assert(limit < 0 || concurrency_maximum <= limit,
  80                "New concurrency limit should be larger than observed concurrency maximum. Maybe you want to call"
  81                " concurrency_maximum_reset() to reset the maximum?");
  82     concurrency_limit = limit;
  83   }
  84
  85   /**
  86    * @brief Gets the concurrency limit for this constraint
  87    * @return The concurrency limit used by this constraint
  88    */
  89   int get_concurrency_limit() const { return concurrency_limit; }
  90
  91   /**
  92    * @brief Reset the concurrency maximum for a given variable (we will update the maximum to reflect constraint
  93    * evolution).
  94    */
  95   void reset_concurrency_maximum() { concurrency_maximum = 0; }
  96
  97   /**
  98    * @brief Get the concurrency maximum for a given variable (which reflects constraint evolution).
  99    * @return the maximum concurrency of the constraint
 100    */
 101   int get_concurrency_maximum() const
 102   {
 103     xbt_assert(concurrency_limit < 0 || concurrency_maximum <= concurrency_limit,
 104                "Very bad: maximum observed concurrency is higher than limit. This is a bug of SURF, please report it.");
 105     return concurrency_maximum;
 106   }
 107
 108   int get_concurrency_slack() const
 109   {
 110     return concurrency_limit < 0 ? std::numeric_limits<int>::max() : concurrency_limit - concurrency_current;
 111   }
 112
 113   /**
 114    * @brief Get a var associated to a constraint
 115    * @details Get the first variable of the next variable of elem if elem is not NULL
 116    * @param elem A element of constraint of the constraint or NULL
 117    * @return A variable associated to a constraint
 118    */
 119   lmm_variable_t get_variable(lmm_element_t* elem) const;
 120
 121   /**
 122    * @brief Get a var associated to a constraint
 123    * @details Get the first variable of the next variable of elem if elem is not NULL
 124    * @param elem A element of constraint of the constraint or NULL
 125    * @param nextelem A element of constraint of the constraint or NULL, the one after elem
 126    * @param numelem parameter representing the number of elements to go
 127    * @return A variable associated to a constraint
 128    */
 129   lmm_variable_t get_variable_safe(lmm_element_t* elem, lmm_element_t* nextelem, int* numelem) const;
 130
 131   /**
 132    * @brief Get the data associated to a constraint
 133    * @return The data associated to the constraint
 134    */
 135   void* get_id() const { return id; }
 136
 137   /* hookup to system */
 138   s_xbt_swag_hookup_t constraint_set_hookup           = {nullptr, nullptr};
 139   s_xbt_swag_hookup_t active_constraint_set_hookup    = {nullptr, nullptr};
 140   s_xbt_swag_hookup_t modified_constraint_set_hookup  = {nullptr, nullptr};
 141   s_xbt_swag_hookup_t saturated_constraint_set_hookup = {nullptr, nullptr};
 142   s_xbt_swag_t enabled_element_set;     /* a list of lmm_element_t */
 143   s_xbt_swag_t disabled_element_set;     /* a list of lmm_element_t */
 144   s_xbt_swag_t active_element_set;      /* a list of lmm_element_t */
 145   double remaining;
 146   double usage;
 147   double bound;
 148   //TODO MARTIN Check maximum value across resources at the end of simulation and give a warning is more than e.g. 500
 149   int concurrency_current; /* The current concurrency */
 150   int concurrency_maximum; /* The maximum number of (enabled and disabled) variables associated to the constraint at any given time (essentially for tracing)*/
 151
 152   int sharing_policy; /* see @e_surf_link_sharing_policy_t (0: FATPIPE, 1: SHARED, 2: FULLDUPLEX) */
 153   int id_int;
 154   double lambda;
 155   double new_lambda;
 156   lmm_constraint_light_t cnst_light;
 157
 158 private:
 159   static int Global_debug_id;
 160   int concurrency_limit; /* The maximum number of variables that may be enabled at any time (stage variables if
 161                           * necessary) */
 162   void* id;
 163 };
 164
 165 /** @ingroup SURF_lmm
 166  * @brief LMM variable
 167  *
 168  * 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
 169  */
 170 struct s_lmm_variable_t {
 171   /* hookup to system */
 172   s_xbt_swag_hookup_t variable_set_hookup;
 173   s_xbt_swag_hookup_t saturated_variable_set_hookup;
 174
 175   std::vector<s_lmm_element_t> cnsts;
 176
 177   // sharing_weight: variable's impact on the resource during the sharing
 178   //   if == 0, the variable is not considered by LMM
 179   //   on CPU, actions with N threads have a sharing of N
 180   //   on network, the actions with higher latency have a lesser sharing_weight
 181   double sharing_weight;
 182
 183   double staged_weight; /* If non-zero, variable is staged for addition as soon as maxconcurrency constraints will be met */
 184   double bound;
 185   double value;
 186   short int concurrency_share; /* The maximum number of elements that variable will add to a constraint */
 187   simgrid::surf::Action* id;
 188   int id_int;
 189   unsigned visited;             /* used by lmm_update_modified_set */
 190   /* \begin{For Lagrange only} */
 191   double mu;
 192   double new_mu;
 193   double (*func_f)(s_lmm_variable_t* var, double x);   /* (f)    */
 194   double (*func_fp)(s_lmm_variable_t* var, double x);  /* (f')    */
 195   double (*func_fpi)(s_lmm_variable_t* var, double x); /* (f')^{-1}    */
 196   /* \end{For Lagrange only} */
 197 };
 198
 199 /** @ingroup SURF_lmm
 200  * @brief LMM system
 201  */
 202 class s_lmm_system_t {
 203 public:
 204   /**
 205    * @brief Create a new Linear MaxMim system
 206    * @param selective_update whether we should do lazy updates
 207    */
 208   s_lmm_system_t(bool selective_update);
 209   /** @brief Free an existing Linear MaxMin system */
 210   ~s_lmm_system_t();
 211
 212   /**
 213    * @brief Create a new Linear MaxMin constraint
 214    * @param id Data associated to the constraint (e.g.: a network link)
 215    * @param bound_value The bound value of the constraint
 216    */
 217   lmm_constraint_t constraint_new(void* id, double bound_value);
 218
 219   /**
 220    * @brief Create a new Linear MaxMin variable
 221    * @param id Data associated to the variable (e.g.: a network communication)
 222    * @param weight_value The weight of the variable (0.0 if not used)
 223    * @param bound The maximum value of the variable (-1.0 if no maximum value)
 224    * @param number_of_constraints The maximum number of constraint to associate to the variable
 225    */
 226   lmm_variable_t variable_new(simgrid::surf::Action* id, double weight_value, double bound, int number_of_constraints);
 227
 228   /**
 229    * @brief Free a variable
 230    * @param var The variable to free
 231    */
 232   void variable_free(lmm_variable_t var);
 233
 234   /**
 235    * @brief Associate a variable to a constraint with a coefficient
 236    * @param cnst A constraint
 237    * @param var A variable
 238    * @param value The coefficient associated to the variable in the constraint
 239    */
 240   void expand(lmm_constraint_t cnst, lmm_variable_t var, double value);
 241
 242   /**
 243    * @brief Add value to the coefficient between a constraint and a variable or create one
 244    * @param cnst A constraint
 245    * @param var A variable
 246    * @param value The value to add to the coefficient associated to the variable in the constraint
 247    */
 248   void expand_add(lmm_constraint_t cnst, lmm_variable_t var, double value);
 249
 250   /**
 251    * @brief Update the bound of a variable
 252    * @param var A constraint
 253    * @param bound The new bound
 254    */
 255   void update_variable_bound(lmm_variable_t var, double bound);
 256
 257   /**
 258    * @brief Update the weight of a variable
 259    * @param var A variable
 260    * @param weight The new weight of the variable
 261    */
 262   void update_variable_weight(lmm_variable_t var, double weight);
 263
 264   /**
 265    * @brief Update a constraint bound
 266    * @param cnst A constraint
 267    * @param bound The new bound of the consrtaint
 268    */
 269   void update_constraint_bound(lmm_constraint_t cnst, double bound);
 270
 271   /**
 272    * @brief [brief description]
 273    * @param cnst A constraint
 274    * @return [description]
 275    */
 276   int constraint_used(lmm_constraint_t cnst) { return xbt_swag_belongs(cnst, &active_constraint_set); }
 277
 278   /** @brief Print the lmm system */
 279   void print();
 280
 281   /** @brief Solve the lmm system */
 282   void solve();
 283
 284 private:
 285   static void* variable_mallocator_new_f();
 286   static void variable_mallocator_free_f(void* var);
 287
 288   void var_free(lmm_variable_t var);
 289   void cnst_free(lmm_constraint_t cnst);
 290   lmm_variable_t extract_variable() { return static_cast<lmm_variable_t>(xbt_swag_extract(&variable_set)); }
 291   lmm_constraint_t extract_constraint() { return static_cast<lmm_constraint_t>(xbt_swag_extract(&constraint_set)); }
 292   void insert_constraint(lmm_constraint_t cnst) { xbt_swag_insert(cnst, &constraint_set); }
 293   void remove_variable(lmm_variable_t var)
 294   {
 295     xbt_swag_remove(var, &variable_set);
 296     xbt_swag_remove(var, &saturated_variable_set);
 297   }
 298   void remove_constraint(lmm_constraint_t cnst) // FIXME: unused
 299   {
 300     xbt_swag_remove(cnst, &constraint_set);
 301     xbt_swag_remove(cnst, &saturated_constraint_set);
 302   }
 303   void make_constraint_active(lmm_constraint_t cnst) { xbt_swag_insert(cnst, &active_constraint_set); }
 304   void make_constraint_inactive(lmm_constraint_t cnst)
 305   {
 306     xbt_swag_remove(cnst, &active_constraint_set);
 307     xbt_swag_remove(cnst, &modified_constraint_set);
 308   }
 309
 310   void enable_var(lmm_variable_t var);
 311   void disable_var(lmm_variable_t var);
 312   void on_disabled_var(lmm_constraint_t cnstr);
 313
 314   /**
 315    * @brief Update the value of element linking the constraint and the variable
 316    * @param cnst A constraint
 317    * @param var A variable
 318    * @param value The new value
 319    */
 320   void update(lmm_constraint_t cnst, lmm_variable_t var, double value);
 321
 322   void update_modified_set(lmm_constraint_t cnst);
 323   void update_modified_set_rec(lmm_constraint_t cnst);
 324
 325   /** @brief Remove all constraints of the modified_constraint_set. */
 326   void remove_all_modified_set();
 327   void check_concurrency();
 328
 329 public:
 330   int modified;
 331   s_xbt_swag_t variable_set;    /* a list of lmm_variable_t */
 332   s_xbt_swag_t active_constraint_set;   /* a list of lmm_constraint_t */
 333   s_xbt_swag_t saturated_variable_set;  /* a list of lmm_variable_t */
 334   s_xbt_swag_t saturated_constraint_set;        /* a list of lmm_constraint_t_t */
 335
 336   simgrid::surf::ActionLmmListPtr keep_track;
 337
 338   void (*solve_fun)(lmm_system_t self);
 339
 340 private:
 341   bool selective_update_active; /* flag to update partially the system only selecting changed portions */
 342   unsigned visited_counter;     /* used by lmm_update_modified_set and lmm_remove_modified_set to cleverly (un-)flag the
 343                                  * constraints (more details in these functions) */
 344   s_xbt_swag_t constraint_set;  /* a list of lmm_constraint_t */
 345   s_xbt_swag_t modified_constraint_set; /* a list of modified lmm_constraint_t */
 346   xbt_mallocator_t variable_mallocator;
 347 };
 348
 349 extern XBT_PRIVATE double (*func_f_def) (lmm_variable_t, double);
 350 extern XBT_PRIVATE double (*func_fp_def) (lmm_variable_t, double);
 351 extern XBT_PRIVATE double (*func_fpi_def) (lmm_variable_t, double);
 352
 353 #endif /* SURF_MAXMIN_PRIVATE_H */