X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/29a3b2869c0075fc75e8ccc66fc1d9c4c8bf6a85..HEAD:/src/kernel/lmm/maxmin.hpp diff --git a/src/kernel/lmm/maxmin.hpp b/src/kernel/lmm/maxmin.hpp index 4dc68c10b9..5d0619ee79 100644 --- a/src/kernel/lmm/maxmin.hpp +++ b/src/kernel/lmm/maxmin.hpp @@ -1,655 +1,29 @@ -/* Copyright (c) 2004-2018. The SimGrid Team. All rights reserved. */ +/* Copyright (c) 2004-2023. The SimGrid Team. All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ -#ifndef SURF_MAXMIN_HPP -#define SURF_MAXMIN_HPP +#ifndef SIMGRID_KERNEL_LMM_MAXMIN_HPP +#define SIMGRID_KERNEL_LMM_MAXMIN_HPP -#include "simgrid/kernel/resource/Action.hpp" -#include "simgrid/s4u/Link.hpp" -#include "xbt/asserts.h" -#include "xbt/mallocator.h" +#include "src/kernel/lmm/System.hpp" -#include -#include -#include -#include - -namespace simgrid { -namespace kernel { -namespace lmm { - -/** @addtogroup SURF_lmm - * @details - * A linear maxmin solver to resolve inequations systems. - * - * Most SimGrid model rely on a "fluid/steady-state" modeling that simulate the sharing of resources between actions at - * relatively coarse-grain. Such sharing is generally done by solving a set of linear inequations. Let's take an - * example and assume we have the variables \f$x_1\f$, \f$x_2\f$, \f$x_3\f$, and \f$x_4\f$ . Let's say that \f$x_1\f$ - * and \f$x_2\f$ correspond to activities running and the same CPU \f$A\f$ whose capacity is \f$C_A\f$. In such a - * case, we need to enforce: - * - * \f[ x_1 + x_2 \leq C_A \f] - * - * Likewise, if \f$x_3\f$ (resp. \f$x_4\f$) corresponds to a network flow \f$F_3\f$ (resp. \f$F_4\f$) that goes through - * a set of links \f$L_1\f$ and \f$L_2\f$ (resp. \f$L_2\f$ and \f$L_3\f$), then we need to enforce: - * - * \f[ x_3 \leq C_{L_1} \f] - * \f[ x_3 + x_4 \leq C_{L_2} \f] - * \f[ x_4 \leq C_{L_3} \f] - * - * One could set every variable to 0 to make sure the constraints are satisfied but this would obviously not be very - * realistic. A possible objective is to try to maximize the minimum of the \f$x_i\f$ . This ensures that all the - * \f$x_i\f$ are positive and "as large as possible". - * - * This is called *max-min fairness* and is the most commonly used objective in SimGrid. Another possibility is to - * maximize \f$\sum_if(x_i)\f$, where \f$f\f$ is a strictly increasing concave function. - * - * Constraint: - * - bound (set) - * - shared (set) - * - usage (computed) - * - * Variable: - * - weight (set) - * - bound (set) - * - value (computed) - * - * Element: - * - value (set) - * - * A possible system could be: - * - three variables: `var1`, `var2`, `var3` - * - two constraints: `cons1`, `cons2` - * - four elements linking: - * - `elem1` linking `var1` and `cons1` - * - `elem2` linking `var2` and `cons1` - * - `elem3` linking `var2` and `cons2` - * - `elem4` linking `var3` and `cons2` - * - * And the corresponding inequations will be: - * - * var1.value <= var1.bound - * var2.value <= var2.bound - * var3.value <= var3.bound - * var1.weight * var1.value * elem1.value + var2.weight * var2.value * elem2.value <= cons1.bound - * var2.weight * var2.value * elem3.value + var3.weight * var3.value * elem4.value <= cons2.bound - * - * where `var1.value`, `var2.value` and `var3.value` are the unknown values. - * - * If a constraint is not shared, the sum is replaced by a max. - * For example, a third non-shared constraint `cons3` and the associated elements `elem5` and `elem6` could write as: - * - * max( var1.weight * var1.value * elem5.value , var3.weight * var3.value * elem6.value ) <= cons3.bound - * - * This is useful for the sharing of resources for various models. - * For instance, for the network model, each link is associated to a constraint and each communication to a variable. - * - * Implementation details - * - * 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. - * We call enabled variables, those which var.weight is strictly positive. Zero-weight variables are called disabled - * variables. - * Unfortunately this concept of enabled/disabled variables intersects with active/inactive variable. - * 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. - * A variable is active only if its var.value is non-zero (and, by construction, its var.weight is non-zero). - * 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. - * - * Concurrency limit and maximum - * - * We call concurrency, the number of variables that can be enabled at any time for each constraint. - * From a model perspective, this "concurrency" often represents the number of actions that actually compete for one - * constraint. - * The LMM solver is able to limit the concurrency for each constraint, and to monitor its maximum value. - * - * One may want to limit the concurrency of constraints for essentially three reasons: - * - Keep LMM system in a size that can be solved (it does not react very well with tens of thousands of variables per - * constraint) - * - Stay within parameters where the fluid model is accurate enough. - * - Model serialization effects - * - * The concurrency limit can also be set to a negative value to disable concurrency limit. This can improve performance - * slightly. - * - * Overall, each constraint contains three fields related to concurrency: - * - concurrency_limit which is the limit enforced by the solver - * - concurrency_current which is the current concurrency - * - concurrency_maximum which is the observed maximum concurrency - * - * Variables also have one field related to concurrency: concurrency_share. - * In effect, in some cases, one variable is involved multiple times (i.e. two elements) in a constraint. - * For example, cross-traffic is modeled using 2 elements per constraint. - * concurrency_share formally corresponds to the maximum number of elements that associate the variable and any given - * constraint. - */ - -/** @{ @ingroup SURF_lmm */ - -/** Default functions associated to the chosen protocol. When using the lagrangian approach. */ - -XBT_PUBLIC double func_reno_f(const Variable& var, double x); -XBT_PUBLIC double func_reno_fp(const Variable& var, double x); -XBT_PUBLIC double func_reno_fpi(const Variable& var, double x); - -XBT_PUBLIC double func_reno2_f(const Variable& var, double x); -XBT_PUBLIC double func_reno2_fp(const Variable& var, double x); -XBT_PUBLIC double func_reno2_fpi(const Variable& var, double x); - -XBT_PUBLIC double func_vegas_f(const Variable& var, double x); -XBT_PUBLIC double func_vegas_fp(const Variable& var, double x); -XBT_PUBLIC double func_vegas_fpi(const Variable& var, double x); - -/** - * @brief LMM element - * Elements can be seen as glue between constraint objects and variable objects. - * Basically, each variable will have a set of elements, one for each constraint where it is involved. - * 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. - */ -class XBT_PUBLIC Element { -public: - int get_concurrency() const; - void decrease_concurrency(); - void increase_concurrency(); - - void make_active(); - void make_inactive(); - - /* hookup to constraint */ - boost::intrusive::list_member_hook<> enabled_element_set_hook; - boost::intrusive::list_member_hook<> disabled_element_set_hook; - boost::intrusive::list_member_hook<> active_element_set_hook; - - Constraint* constraint; - Variable* variable; - - // consumption_weight: impact of 1 byte or flop of your application onto the resource (in byte or flop) - // - if CPU, then probably 1. - // - If network, then 1 in forward direction and 0.05 backward for the ACKs - double consumption_weight; -}; - -class ConstraintLight { -public: - double remaining_over_usage; - Constraint* cnst; -}; - -/** - * @brief LMM constraint - * Each constraint contains several partially overlapping logical sets of elements: - * \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). - * \li Enabled elements which variable's weight is non-zero. They are utilized in some LMM functions. - * \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. - */ -class XBT_PUBLIC Constraint { -public: - Constraint() = delete; - Constraint(void* id_value, double bound_value); - - /** @brief Unshare a constraint. */ - void unshare() { sharing_policy = s4u::Link::SharingPolicy::FATPIPE; } - - /** - * @brief Check if a constraint is shared (shared by default) - * @return 1 if shared, 0 otherwise - */ - s4u::Link::SharingPolicy get_sharing_policy() const { return sharing_policy; } - - /** - * @brief Get the usage of the constraint after the last lmm solve - * @return The usage of the constraint - */ - double get_usage() const; - int get_variable_amount() const; - - /** - * @brief Sets the concurrency limit for this constraint - * @param limit The concurrency limit to use for this constraint - */ - void set_concurrency_limit(int limit) - { - xbt_assert(limit < 0 || concurrency_maximum <= limit, - "New concurrency limit should be larger than observed concurrency maximum. Maybe you want to call" - " concurrency_maximum_reset() to reset the maximum?"); - concurrency_limit = limit; - } - - /** - * @brief Gets the concurrency limit for this constraint - * @return The concurrency limit used by this constraint - */ - int get_concurrency_limit() const { return concurrency_limit; } - - /** - * @brief Reset the concurrency maximum for a given variable (we will update the maximum to reflect constraint - * evolution). - */ - void reset_concurrency_maximum() { concurrency_maximum = 0; } - - /** - * @brief Get the concurrency maximum for a given variable (which reflects constraint evolution). - * @return the maximum concurrency of the constraint - */ - int get_concurrency_maximum() const - { - xbt_assert(concurrency_limit < 0 || concurrency_maximum <= concurrency_limit, - "Very bad: maximum observed concurrency is higher than limit. This is a bug of SURF, please report it."); - return concurrency_maximum; - } - - int get_concurrency_slack() const - { - return concurrency_limit < 0 ? std::numeric_limits::max() : concurrency_limit - concurrency_current; - } - - /** - * @brief Get a var associated to a constraint - * @details Get the first variable of the next variable of elem if elem is not NULL - * @param elem A element of constraint of the constraint or NULL - * @return A variable associated to a constraint - */ - Variable* get_variable(const Element** elem) const; - - /** - * @brief Get a var associated to a constraint - * @details Get the first variable of the next variable of elem if elem is not NULL - * @param elem A element of constraint of the constraint or NULL - * @param nextelem A element of constraint of the constraint or NULL, the one after elem - * @param numelem parameter representing the number of elements to go - * @return A variable associated to a constraint - */ - Variable* get_variable_safe(const Element** elem, const Element** nextelem, int* numelem) const; - - /** - * @brief Get the data associated to a constraint - * @return The data associated to the constraint - */ - void* get_id() const { return id; } - - /* hookup to system */ - boost::intrusive::list_member_hook<> constraint_set_hook; - boost::intrusive::list_member_hook<> active_constraint_set_hook; - boost::intrusive::list_member_hook<> modified_constraint_set_hook; - boost::intrusive::list_member_hook<> saturated_constraint_set_hook; - boost::intrusive::list, - &Element::enabled_element_set_hook>> - enabled_element_set; - boost::intrusive::list, - &Element::disabled_element_set_hook>> - disabled_element_set; - boost::intrusive::list, - &Element::active_element_set_hook>> - active_element_set; - double remaining; - double usage; - double bound; - // TODO MARTIN Check maximum value across resources at the end of simulation and give a warning is more than e.g. 500 - int concurrency_current; /* The current concurrency */ - int concurrency_maximum; /* The maximum number of (enabled and disabled) variables associated to the constraint at any - * given time (essentially for tracing)*/ - - s4u::Link::SharingPolicy sharing_policy; - int id_int; - double lambda; - double new_lambda; - ConstraintLight* cnst_light; - -private: - static int Global_debug_id; - int concurrency_limit; /* The maximum number of variables that may be enabled at any time (stage variables if - * necessary) */ - void* id; -}; - -/** - * @brief LMM variable - * - * 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 - */ -class XBT_PUBLIC Variable { -public: - void initialize(resource::Action* id_value, double sharing_weight_value, double bound_value, - int number_of_constraints, unsigned visited_value); - - /** - * @brief Get the value of the variable after the last lmm solve - * @return The value of the variable - */ - double get_value() const { return value; } - - /** - * @brief Get the maximum value of the variable (-1.0 if no maximum value) - * @return The bound of the variable - */ - double get_bound() const { return bound; } - - /** - * @brief Set the concurrent share of the variable - * @param value The new concurrency share - */ - void set_concurrency_share(short int value) { concurrency_share = value; } - - /** - * @brief Get the numth constraint associated to the variable - * @param num The rank of constraint we want to get - * @return The numth constraint - */ - Constraint* get_constraint(unsigned num) const { return num < cnsts.size() ? cnsts[num].constraint : nullptr; } - - /** - * @brief Get the weigth of the numth constraint associated to the variable - * @param num The rank of constraint we want to get - * @return The numth constraint - */ - double get_constraint_weight(unsigned num) const { return num < cnsts.size() ? cnsts[num].consumption_weight : 0.0; } - - /** - * @brief Get the number of constraint associated to a variable - * @return The number of constraint associated to the variable - */ - int get_number_of_constraint() const { return cnsts.size(); } - - /** - * @brief Get the data associated to a variable - * @return The data associated to the variable - */ - resource::Action* get_id() const { return id; } - - /** - * @brief Get the weight of a variable - * @return The weight of the variable - */ - double get_weight() const { return sharing_weight; } - - /** @brief Measure the minimum concurrency slack across all constraints where the given var is involved */ - int get_min_concurrency_slack() const; - - /** @brief Check if a variable can be enabled - * Make sure to set staged_weight before, if your intent is only to check concurrency - */ - int can_enable() const { return staged_weight > 0 && get_min_concurrency_slack() >= concurrency_share; } - - /* hookup to system */ - boost::intrusive::list_member_hook<> variable_set_hook; - boost::intrusive::list_member_hook<> saturated_variable_set_hook; - - std::vector cnsts; - - // sharing_weight: variable's impact on the resource during the sharing - // if == 0, the variable is not considered by LMM - // on CPU, actions with N threads have a sharing of N - // on network, the actions with higher latency have a lesser sharing_weight - double sharing_weight; - - double staged_weight; /* If non-zero, variable is staged for addition as soon as maxconcurrency constraints will be - * met */ - double bound; - double value; - short int concurrency_share; /* The maximum number of elements that variable will add to a constraint */ - resource::Action* id; - int id_int; - unsigned visited; /* used by System::update_modified_set() */ - /* \begin{For Lagrange only} */ - double mu; - double new_mu; - /* \end{For Lagrange only} */ - -private: - static int Global_debug_id; -}; - -inline void Element::make_active() -{ - constraint->active_element_set.push_front(*this); -} -inline void Element::make_inactive() -{ - if (active_element_set_hook.is_linked()) - simgrid::xbt::intrusive_erase(constraint->active_element_set, *this); -} - -/** - * @brief LMM system - */ -class XBT_PUBLIC System { -public: - /** - * @brief Create a new Linear MaxMim system - * @param selective_update whether we should do lazy updates - */ - explicit System(bool selective_update); - /** @brief Free an existing Linear MaxMin system */ - virtual ~System(); - - /** - * @brief Create a new Linear MaxMin constraint - * @param id Data associated to the constraint (e.g.: a network link) - * @param bound_value The bound value of the constraint - */ - Constraint* constraint_new(void* id, double bound_value); - - /** - * @brief Create a new Linear MaxMin variable - * @param id Data associated to the variable (e.g.: a network communication) - * @param weight_value The weight of the variable (0.0 if not used) - * @param bound The maximum value of the variable (-1.0 if no maximum value) - * @param number_of_constraints The maximum number of constraint to associate to the variable - */ - Variable* variable_new(resource::Action* id, double weight_value, double bound, int number_of_constraints); - - /** - * @brief Free a variable - * @param var The variable to free - */ - void variable_free(Variable * var); - - /** - * @brief Associate a variable to a constraint with a coefficient - * @param cnst A constraint - * @param var A variable - * @param value The coefficient associated to the variable in the constraint - */ - void expand(Constraint * cnst, Variable * var, double value); - - /** - * @brief Add value to the coefficient between a constraint and a variable or create one - * @param cnst A constraint - * @param var A variable - * @param value The value to add to the coefficient associated to the variable in the constraint - */ - void expand_add(Constraint * cnst, Variable * var, double value); - - /** - * @brief Update the bound of a variable - * @param var A constraint - * @param bound The new bound - */ - void update_variable_bound(Variable * var, double bound); - - /** - * @brief Update the weight of a variable - * @param var A variable - * @param weight The new weight of the variable - */ - void update_variable_weight(Variable * var, double weight); - - /** - * @brief Update a constraint bound - * @param cnst A constraint - * @param bound The new bound of the consrtaint - */ - void update_constraint_bound(Constraint * cnst, double bound); - - /** - * @brief [brief description] - * @param cnst A constraint - * @return [description] - */ - int constraint_used(Constraint * cnst) { return cnst->active_constraint_set_hook.is_linked(); } - - /** @brief Print the lmm system */ - void print() const; - - /** @brief Solve the lmm system */ - void lmm_solve(); - - /** @brief Solve the lmm system. May be specialized in subclasses. */ - virtual void solve() { lmm_solve(); } - -private: - static void* variable_mallocator_new_f(); - static void variable_mallocator_free_f(void* var); - - void var_free(Variable * var); - void cnst_free(Constraint * cnst); - Variable* extract_variable() - { - if (variable_set.empty()) - return nullptr; - Variable* res = &variable_set.front(); - variable_set.pop_front(); - return res; - } - Constraint* extract_constraint() - { - if (constraint_set.empty()) - return nullptr; - Constraint* res = &constraint_set.front(); - constraint_set.pop_front(); - return res; - } - void insert_constraint(Constraint * cnst) { constraint_set.push_back(*cnst); } - void remove_variable(Variable * var) - { - if (var->variable_set_hook.is_linked()) - simgrid::xbt::intrusive_erase(variable_set, *var); - if (var->saturated_variable_set_hook.is_linked()) - simgrid::xbt::intrusive_erase(saturated_variable_set, *var); - } - void make_constraint_active(Constraint * cnst) - { - if (not cnst->active_constraint_set_hook.is_linked()) - active_constraint_set.push_back(*cnst); - } - void make_constraint_inactive(Constraint * cnst) - { - if (cnst->active_constraint_set_hook.is_linked()) - simgrid::xbt::intrusive_erase(active_constraint_set, *cnst); - if (cnst->modified_constraint_set_hook.is_linked()) - simgrid::xbt::intrusive_erase(modified_constraint_set, *cnst); - } - - void enable_var(Variable * var); - void disable_var(Variable * var); - void on_disabled_var(Constraint * cnstr); - - /** - * @brief Update the value of element linking the constraint and the variable - * @param cnst A constraint - * @param var A variable - * @param value The new value - */ - void update(Constraint * cnst, Variable * var, double value); - - void update_modified_set(Constraint * cnst); - void update_modified_set_rec(Constraint * cnst); - - /** @brief Remove all constraints of the modified_constraint_set. */ - void remove_all_modified_set(); - void check_concurrency() const; - - template void lmm_solve(CnstList& cnst_list); +namespace simgrid::kernel::lmm { +class XBT_PUBLIC MaxMin : public System { public: - bool modified_ = false; - boost::intrusive::list, - &Variable::variable_set_hook>> - variable_set; - boost::intrusive::list, - &Constraint::active_constraint_set_hook>> - active_constraint_set; - boost::intrusive::list, - &Variable::saturated_variable_set_hook>> - saturated_variable_set; - boost::intrusive::list, - &Constraint::saturated_constraint_set_hook>> - saturated_constraint_set; - - resource::Action::ModifiedSet* modified_set_ = nullptr; + using System::System; private: - bool selective_update_active; /* flag to update partially the system only selecting changed portions */ - unsigned visited_counter_ = 1; /* used by System::update_modified_set() and System::remove_all_modified_set() to - * cleverly (un-)flag the constraints (more details in these functions) */ - boost::intrusive::list, - &Constraint::constraint_set_hook>> - constraint_set; - boost::intrusive::list, - &Constraint::modified_constraint_set_hook>> - modified_constraint_set; - xbt_mallocator_t variable_mallocator_ = - xbt_mallocator_new(65536, System::variable_mallocator_new_f, System::variable_mallocator_free_f, nullptr); - ; -}; + void do_solve() final; + template void maxmin_solve(CnstList& cnst_list); -class XBT_PUBLIC FairBottleneck : public System { -public: - explicit FairBottleneck(bool selective_update) : System(selective_update) {} - void solve() final { bottleneck_solve(); } + using dyn_light_t = std::vector; -private: - void bottleneck_solve(); + std::vector cnst_light_vec; + dyn_light_t saturated_constraints; }; -class XBT_PUBLIC Lagrange : public System { -public: - explicit Lagrange(bool selective_update) : System(selective_update) {} - void solve() final { lagrange_solve(); } - - static void set_default_protocol_function(double (*func_f)(const Variable& var, double x), - double (*func_fp)(const Variable& var, double x), - double (*func_fpi)(const Variable& var, double x)); - -private: - void lagrange_solve(); - - bool check_feasible(bool warn); - double dual_objective(); - - static double (*func_f)(const Variable& var, double x); /* (f) */ - static double (*func_fp)(const Variable& var, double x); /* (f') */ - static double (*func_fpi)(const Variable& var, double x); /* (f')^{-1} */ - - /* - * Local prototypes to implement the Lagrangian optimization with optimal step, also called dichotomy. - */ - // computes the value of the dichotomy using a initial values, init, with a specific variable or constraint - static double dichotomy(double init, double diff(double, const Constraint&), const Constraint& cnst, - double min_error); - // computes the value of the differential of constraint cnst applied to lambda - static double partial_diff_lambda(double lambda, const Constraint& cnst); - - static double new_value(const Variable& var); - static double new_mu(const Variable& var); -}; - -XBT_PUBLIC System* make_new_maxmin_system(bool selective_update); -XBT_PUBLIC System* make_new_fair_bottleneck_system(bool selective_update); -XBT_PUBLIC System* make_new_lagrange_system(bool selective_update); - -/** @} */ -} -} -} +} // namespace simgrid::kernel::lmm #endif